mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-09-07, 15:52   #1
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

6A16 Posts
Default 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?
Robert Holmes is offline   Reply With Quote
Old 2010-09-10, 12:53   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5×709 Posts
Default

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 :)
jasonp is offline   Reply With Quote
Old 2010-09-10, 14:26   #3
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

2×53 Posts
Default

Interesting. Thanks.
Robert Holmes is offline   Reply With Quote
Old 2010-09-10, 15:01   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2010-09-11, 01:34   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354510 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Promising initial letters of mathematicians. davieddy Lounge 17 2011-01-06 22:16
Messed up initial setup relay_man Information & Answers 3 2009-04-15 00:45
Intel Advanced Vector Extensions (256-bit SSE) nuutti Programming 3 2008-04-08 18:01
Initial Pattern davar55 Puzzles 6 2007-06-12 00:00
Rotating the Initial Start Value Of a LL Test dave_0273 Math 9 2004-08-25 18:24

All times are UTC. The time now is 08:28.


Fri Aug 12 08:28:23 UTC 2022 up 36 days, 3:15, 2 users, load averages: 1.29, 1.16, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔