most recent 30 from http://mathoverflow.net 2013-05-22T11:27:36Z http://mathoverflow.net/feeds/question/77434 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77434/convergence-speed-of-jacobi-eigenvalue-algorithm-for-parallel-orderingbrent-luk Alexander Chervov 2011-10-07T08:05:27Z 2013-05-03T13:22:00Z

<p>Is there estimate for convergence of the Jacobi eigenvalue algorithm for Hermitian matrices for "parallel ordring" (Brent-Luk ordering (see comment below)) ?</p> <hr> <p>For example for 4 4 matrices parallel ordering is the following 1a) 12 1b) 34 2a) 23 2b) 14 3a) 13 3b) 24</p> <hr> <p>[EDIT] Moreover convergence itself is not known for such ordering even in 4x4 case. I have consulted with many experts in the field - it is not proved. Numerical simulations (checked more than 10^10 matrices of different form) shows that the convergence exists.</p> <p>There is certain subtlety in the definition of method. Which lead some authors to claim that there is NO convergence. But actually counter-example is not for "reasonable" implementation of details.</p> <p>The detail is the following consider 2x2 matrix such that diagonal elements are equal. Then the rotation can be either +45 either -45 - no unique choice. What the authors claim that if we have a freedom to choose +45 or -45 by our own wish, in each step where ambiguity occurs - then there will be counterexample ! However this counter-example does NOT work if we fix +45 (or -45) once and forever ! I.e. in the case of ambiguity we ALWAYS choose angle to be the same. Simulations shows - that than there is no problem.</p> <p>I spent about 2 weeks trying to prove this just in the 4x4 example - but I was unable to prove it. The difficulty is that we need to analyse about 3-4 sweeps. It can be shown that there always exists a matrix that can be arbitrary "BAD" after 1-2 sweeps...</p> <p>[END of EDIT on 21 Jan. 2012]</p> <hr> <p>As far as I can expect that there should be ultimate quadratic convergence [EDIT] actually as works of Walter F. Mascarenhas suggests their will be cubic ultimate convergence[EDIT] but I am interested at the first iteration - they should be at most linear convergence, but it is not clear for is there uniform convergence speed or there can be some matrices where convergence can be arbitrary bad ? (From simulation we see that probably there is NO bad examples - convergence seems rather fast, but there are certain difficulties in proving this theoretically).</p> <p>Actually even the convergence for arbirary ordering is not clear for me.</p> <p>Paper by Walter Mascarenhas:</p> <p>SIAM. J. Matrix Anal. &amp; Appl. 16, pp. 1197-1209 (13 pages) On the Convergence of the Jacobi Method for Arbitrary Orderings Walter F. Mascarenhas States only convergence of the diagonal elements. Non-diagonal elements may not converge, for some sophisticated orderings. He constructed examples in his PhD at MIT unpublished (private communication from him)</p>

http://mathoverflow.net/questions/77434/convergence-speed-of-jacobi-eigenvalue-algorithm-for-parallel-orderingbrent-luk/79391#79391 zouzias 2011-10-28T14:42:47Z 2011-10-28T14:42:47Z

<p>Here is a link to the paper that you are referring to</p> <p><a href="http://epubs.siam.org/sima/resource/1/sjmael/v16/i4/p1197_s1" rel="nofollow">http://epubs.siam.org/sima/resource/1/sjmael/v16/i4/p1197_s1</a></p> <p>Of course, you should have access to SIAM or buy the article.</p> <p>Best,</p>