Is there estimate for convergence of the Jacobi eigenvalue algorithm for Hermitian matrices for "parallel ordring" (Brent-Luk ordering (see comment below)) ?
For example for 4 4 matrices parallel ordering is the following
1a) 12
1b) 34
2a) 23
2b) 14
3a) 13
3b) 24
[EDIT] Moreover convergence itself is not known for such ordering even in 4×4 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.
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.
The detail is the following consider 2×2 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.
I spent about 2 weeks trying to prove this just in the 4×4 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…
[END of EDIT on 21 Jan. 2012]
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).
Actually even the convergence for arbirary ordering is not clear for me.
Paper by Walter Mascarenhas:
SIAM. J. Matrix Anal. & 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)
Best Answer
Here is a link to the paper that you are referring to
http://epubs.siam.org/sima/resource/1/sjmael/v16/i4/p1197_s1
Of course, you should have access to SIAM or buy the article.
Best,