Talk:Lanczos algorithm: Difference between revisions

Content deleted Content added
Cewbot (talk | contribs)
m Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "C" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Maths rating}}. Remove 1 deprecated parameter: field.
 
(37 intermediate revisions by 12 users not shown)
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|priority=Low }}
}}
== Old comments that did not have a section of their own ==
[[http://en.wikipedia.org/wiki/Lanczos_algorithm]] - an unfocused variety of Lanczos algorithm
<span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:134.219.166.104|134.219.166.104]] ([[User talk:134.219.166.104|talk]] • [[Special:Contributions/134.219.166.104|contribs]]) 21:23, 1 September 2005</span><!-- Template:Unsigned -->
 
This doesn't have much but it does have a reference to a book [http://mathworld.wolfram.com/LanczosAlgorithm.html mathworld on Lanczos Algorithm]]<span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:RJFJR|RJFJR]] ([[User talk:RJFJR|talk]] • [[Special:Contributions/RJFJR|contribs]]) 23:36, 25 September 2005</span><!-- Template:Unsigned -->
 
I don't believe this is the Lanczos algorithm at all.
It is the power method.
<span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:130.126.55.123|130.126.55.123]] ([[User talk:130.126.55.123|talk]] • [[Special:Contributions/130.126.55.123|contribs]]) 01:04, 5 August 2006</span><!-- Template:Unsigned -->
 
I don't know if the algorithm is correct, but it's certainly different than the power method, and presented pretty clearly. I think it's gotten me on the right track at least... Thanks. --[[User:Jjdonald|Jjdonald]] ([[User talk:Jjdonald|talk]]) 22:22, 17 December 2007 (UTC)
 
:It is not easy to say it's wrong or correct, since quite some information is missing<s> in order to apply it: (a) how to choose v[1], (b) how to choose ''m'', (c) how to recognize the eigenvalues of A among those of T_mm</s>. Unfortunately, this vagueness is by no means eliminated by the ''Numerical stability'' section. &mdash; [[User:MFH|MFH]]:[[User talk:MFH|Talk]] 21:57, 12 September 2008 (UTC)
 
::It is certainly not completely correct: there's at least something faulty with the indices. &mdash; [[User:MFH|MFH]]:[[User talk:MFH|Talk]] 19:59, 8 December 2011 (UTC)
 
It should state that "it applies to Hermitian matrices" at the start of the article and not somewhere in the middle. [[User:limweizhong|limweizhong]] ([[User talk:limweizhong|talk]]) 09:54, 11 November 2008 (UTC)
 
:There is a paper about Non-Symmetric Lanczos' algorithm (compared to Arnoldi) by Jane Cullum. &mdash; [[User:MFH|MFH]]:[[User talk:MFH|Talk]] 20:07, 8 December 2011 (UTC)
 
== In Latent Semantic Indexing, for... ==
 
I really think that this sentense has nothing to do in the first paragraph! Please someone who understand anything about it should create a separate section and explain what this is about!
[[User:Alain Michaud|Alain Michaud]] ([[User talk:Alain Michaud|talk]]) 16:52, 19 February 2010 (UTC)
 
== Block Lanczos algorithm ==
 
I suppose that Peter Montgomery`s 1995 paper was very good, but I do not see the need to inform everyone about its existence. This topic is much too advanced to be discussed at the top of the page. Please move this (second paragraph) towards the end of the page.
 
[[User:Alain Michaud|Alain Michaud]] ([[User talk:Alain Michaud|talk]]) 16:50, 19 February 2010 (UTC)
== Extracting information from tridiagonal matrix ==
 
So Lanczos gives you a tridiagonal matrix. I think a link would be helpful which explains how to extract low eigenvalues/eigenvectors from this matrix. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/209.6.144.249|209.6.144.249]] ([[User talk:209.6.144.249|talk]]) 06:30, 2 March 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
 
:Agree - or largest eigenvalues: anyway, the article starts by saying that it's for calculating eigenvalues, but then stops with the tridiag. matrix.
:B.t.w., the algorithm calculates up to v[m+1], I think this could be avoided. (also, "unrolling" the 1st part of the m=1 case as initialization should allow to avoid using v[0].) &mdash; [[User:MFH|MFH]]:[[User talk:MFH|Talk]] 03:09, 11 September 2008 (UTC)
:PS: also, it should be said what is 'm'...
 
*'''Seconded''' — the article spends a lot of ink on the Lanczos iteration (but could do a better job at explaining it) for producing a tridiagonal matrix, says various other algorithms can be used for calculating eigenvalues and eigenvectors of that tridiagonal matrix, but is almost silent on how the two are related. As far as I can tell, early steps of the iteration tends to put most of the weight on the extreme eigenvalues (largest and smallest both, ''regardless of their absolute values''), meaning those are fairly accurately reproduced in the tridiagonal matrix, and the algorithm proceeds towards less extreme eigenvalues the longer it is run; it's 'tends' because the initial weight distribution depends on the initial vector, which is chosen at random. What is not clear from mere thought experiments is how concentrated the distribution is … [[Special:Contributions/130.243.68.202|130.243.68.202]] ([[User talk:130.243.68.202|talk]]) 14:22, 2 May 2017 (UTC)
 
:Thinking some more about this, I find it desirable to modify the way the algorithm is stated — partly to address the case <math>\beta_{j+1}=0</math>, and partly to do something about the "changes to" remark at the end, which is confusing in that no variable assigned in the algorithm is ever changed. It turns out the remark is boilerplate text in the {{tl|algorithm-end}} template, and there is no option to omit it. Since [[Wikipedia:WikiProject_Computer_science/Manual_of_style#Algorithms_and_data_structures]] does not recommend using that template, and instead recommends using (numbered) lists with explicit '''input''' and '''output''' headings, a rewrite from scratch seems in order.
:Said rewrite is now live in the article. It also addresses the gap of where to go when you've got the tridiagonal matrix. A remaining gap is the result that eigenvalues of <math>T</math> approximates eigenvalues of <math>A</math>. [[Special:Contributions/130.243.68.122|130.243.68.122]] ([[User talk:130.243.68.122|talk]]) 15:48, 26 May 2017 (UTC)
 
Following up on the previous comment, the section "Application to eigenproblem" misleadingly implies that the eigenvalues of the mxm matrix T are exactly the eigenvalues of A, which is obviously false. (Indeed the equation in parentheses at the end of the first paragraph is only valid if m =n). The point is that these eigenvalues approximate the eigenvalues of A; more work needs to be done to understand why and how good the approximation is.
 
== Define variables ==
 
It would be nice if variables are defined before (or just after) being used. For example, at the begining, <math>U</math> and <math>\sigma_i</math> are not defined and its confusing for non-expert public.
 
[[User:Felipebm|Felipebm]] ([[User talk:Felipebm|talk]]) 13:34, 17 May 2011 (UTC)
 
== problematic matrix decomposition ==
 
In the section "Power method for finding eigenvalues", the matrix A is represented as <math>A=U\text{diag}(\sigma_i)U'</math>, which is true only for [[normal matrices]]. For the general case, SVD decomposition should be used, i.e. <math>A=U\text{diag}(\sigma_i)V'</math> where U and V are some orthogonal matrices. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/89.139.52.157|89.139.52.157]] ([[User talk:89.139.52.157|talk]]) 12:14, 24 April 2016 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
 
: It's not stated explicitly at that point, but presumably <math>A</math> is already taken to be Hermitian (as it needs to be for the Lanczos algorithm to work), which means it ''has'' an eigendecomposition of the form stated. Instead using the SVD decomposition in this argument won't work, because the entire point is that <math>U' U = I</math> so that the product telescopes! Possibly it would be clearer to just use <math>A = U \operatorname{diag}(\sigma_i) U^{-1}</math>, i.e., hold off on requiring orthogonality — the reason being that the paragraph in question is about the plain power method, which applies in a greater generality. [[Special:Contributions/130.243.68.202|130.243.68.202]] ([[User talk:130.243.68.202|talk]]) 13:01, 2 May 2017 (UTC)
 
== External links modified ==
 
Hello fellow Wikipedians,
 
I have just modified one external link on [[Lanczos algorithm]]. Please take a moment to review [[special:diff/815699167|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:
*Added archive https://web.archive.org/web/20110314171151/http://www.graphlab.ml.cmu.edu/pmf.html to http://www.graphlab.ml.cmu.edu/pmf.html
 
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
 
{{sourcecheck|checked=false|needhelp=}}
 
Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 14:26, 16 December 2017 (UTC)