Jacobi eigenvalue algorithm: Difference between revisions

Revision as of 19:36, 9 February 2016

Revision as of 19:38, 9 February 2016

Line 81:

Each Jacobi rotation can be done in ''n'' steps when the pivot element ''p'' is known. However the search for ''p'' requires inspection of all ''N''&nbsp;≈&nbsp;½&nbsp;''n''² off-diag elements. We can reduce this to ''n'' steps too if we introduce an additional index array <math> m_1, \, \dots \, , \, m_{n - 1} </math> with the property that <math> m_i </math> is the index of the largest element in row ''i'', (''i'' = 1, …, ''n''&nbsp;&minus;&nbsp;1) of the current ''S''. Then (''k'', ''l'') must be one of the pairs <math> (i, m_i) </math> . Since only columns ''k'' and ''l'' change, only <math> m_k \mbox{ and } m_l </math> must be updated, which again can be done in ''n'' steps. Thus each rotation has O(''n'') cost and one sweep has O(''n''³) cost which is equivalent to one matrix multiplication. Additionally the <math> m_i </math> must be initialized before the process starts, this can be done in ''n''² steps.

**(Problem: Jacobi rotations affect both columns k and l, and rows k and l. So the O("n") scheme described above doesn't in fact find the pivot element corresponding to the largest off-diagonal element after a Jacobi rotation. You also have to check that the updates to rows k and l (for all other columns on the upper or lower triangular part of the matrix) don't also change the corresponding <math>m_i</math>, for i not equal to k or l, which will in general be altered by the rotation. In worst case this is O("n²). **)

Typically the Jacobi method converges within numerical precision after a small number of sweeps. Note that multiple eigenvalues reduce the number of iterations since <math>N_S < N</math>.

(Note: Sweeps refer to cyclic Jacobi, where the pivot cyles over all upper (or lower) off-diagonal elements, not classic Jacobi which searches for the maximum (magnitude) off-diagonal element.)

== Algorithm ==