20100907, 15:52  #1 
Oct 2007
152_{8} 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? 
20100910, 12:53  #2 
Tribal Bullet
Oct 2004
2×5^{2}×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) 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 
20100910, 14:26  #3 
Oct 2007
2·53 Posts 
Interesting. Thanks.

20100910, 15:01  #4 
Aug 2006
5,987 Posts 

20100911, 01:34  #5 
Tribal Bullet
Oct 2004
2·5^{2}·71 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Promising initial letters of mathematicians.  davieddy  Lounge  17  20110106 22:16 
Messed up initial setup  relay_man  Information & Answers  3  20090415 00:45 
Intel Advanced Vector Extensions (256bit SSE)  nuutti  Programming  3  20080408 18:01 
Initial Pattern  davar55  Puzzles  6  20070612 00:00 
Rotating the Initial Start Value Of a LL Test  dave_0273  Math  9  20040825 18:24 