# Convergence speed of Jacobi eigenvalue algorithm for parallel ordering(Brent-Luk) ?

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 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.

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 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.

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...

[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)

-
Related question by Dennis Serre: mathoverflow.net/questions/39063/… But as far as I understand he is interested in ultimate convergence, but I am in the first steps. Actually in simulation for small size matrices 3-4 "sweeps" are enough to get averagely 1e-6 1e-14 off diagonal norm for 4*4 matrices. –  Alexander Chervov Oct 7 '11 at 8:39
Are you saying you can't find the paper of Mascarenhas? I have it; send me mail at bdm(at)cs.anu.edu.au and I'll give you copy. –  Brendan McKay Oct 9 '11 at 3:26
@Brendan Thank you very much ! Finally I have got a paper for 25\$ :) Also I had an email exchange with Walter Mascarenhas. It seems his work does not answer my question he claims that the diagonal elements converge, while non-diagonal may not converge (in his PhD (which I cannot get) he said he constructed example but for some sophisticated orderings, it seems BrentLuk ordering is not his family, but it is not clear). –  Alexander Chervov Oct 9 '11 at 9:33
I don't know about the convergence for every ordering. However, I have proved that for every Hermitian matrix, the method converges for almost every ordering. See the second edition of my book on matrices, Springer-Verlag GTM 216. –  Denis Serre Oct 12 '11 at 6:52
By the way, my first name is French, so Denis has only one N. –  Denis Serre Oct 12 '11 at 6:53