mersenneforum.org Initial vector in Lanczos
 Register FAQ Search Today's Posts Mark Forums Read

 2010-09-07, 15:52 #1 Robert Holmes     Oct 2007 1528 Posts Initial vector in Lanczos Silly question: What if, instead of choosing a random initial vector for the Lanczos iteration, one could "guess" some vector x such that M.x = v, where v is not the null vector but has very low Hamming weight. Would this affect the number of iterations required to achieve a solution?
 2010-09-10, 12:53 #2 jasonp Tribal Bullet     Oct 2004 2×52×71 Posts Interesting question; I did some experiments with 2^128+1. Ordinarily one would get Code: matrix is 453 x 517 (0.0 MB) with weight 8236 (15.93/col) sparse part has weight 8236 (15.93/col) commencing Lanczos iteration memory use: 0.1 MB lanczos halted after 9 iterations (dim = 449) so for this size problem it takes 9 iterations to find a vector in the nullspace of the symmetrized version of the input matrix. If I take the output of the iteration, perturb a few entries and rerun the iteration (disabling the check that every column has to participate in two successive iterations) I then get Code: commencing Lanczos iteration memory use: 0.1 MB lanczos halted after 9 iterations (dim = 449) linear algebra failed; retrying... commencing Lanczos iteration memory use: 0.1 MB lanczos halted after 52 iterations (dim = 450) recovered 60 nontrivial dependencies prp17 factor: 59649589127497217 prp22 factor: 5704689200685129054721 As the input gets closer and closer to the real nullspace vector the number of iterations shoots up. So the randomness of the input does affect the number of iterations, but not in the direction we want :)
 2010-09-10, 14:26 #3 Robert Holmes     Oct 2007 2·53 Posts Interesting. Thanks.
2010-09-10, 15:01   #4
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by jasonp As the input gets closer and closer to the real nullspace vector the number of iterations shoots up. So the randomness of the input does affect the number of iterations, but not in the direction we want :)
Do you expect that to happen consistently?

2010-09-11, 01:34   #5
jasonp
Tribal Bullet

Oct 2004

2·52·71 Posts

Quote:
 Originally Posted by CRGreathouse Do you expect that to happen consistently?
I don't know what to expect; the inner workings of Krylov subspace methods are still a mystery to me, even if you don't count the strange block version that's involved here.

My guess is that if you violate the assumptions that the Lanczos recurrence is based on, i.e. that all columns of the current solution are used in the current or the previous iteration, then it shouldn't be surprising that the recurrence stops working in a subtle way.

 Similar Threads Thread Thread Starter Forum Replies Last Post davieddy Lounge 17 2011-01-06 22:16 relay_man Information & Answers 3 2009-04-15 00:45 nuutti Programming 3 2008-04-08 18:01 davar55 Puzzles 6 2007-06-12 00:00 dave_0273 Math 9 2004-08-25 18:24

All times are UTC. The time now is 23:38.

Tue Nov 29 23:38:17 UTC 2022 up 103 days, 21:06, 0 users, load averages: 1.08, 0.95, 0.97