Jacobi eigenvalue algorithm

In numerical linear algebra, the Jacobi eigenvalue algorithm is an iterative method for the calculation of the eigenvalues and eigenvectors of a real symmetric matrix (a process known as diagonalization). It is named after Carl Gustav Jacob Jacobi, who first proposed the method in 1846, but only became widely used in the 1950s with the advent of computers.

Each Jacobi rotation can be done in O(n) steps when the pivot element p is known. However the search for p requires inspection of all N ≈  n2 off diagonal elements. We can reduce this to O(n) complexity too if we introduce an additional index array with the property that is the index of the largest element in row i, (i = 1, , n − 1) of the current S. Then the indices of the pivot (k, l) must be one of the pairs Also the updating of the index array can be done in O(n) average case complexity: First, the maximum entry in the updated rows k and l can be found in O(n) steps. In the other rows i, only the entries in columns k and l change. Looping over these rows, if is neither k nor l, it suffices to compare the old maximum at to the new entries and update if necessary. If should be equal to k or l and the corresponding entry decreased during the update, the maximum over row i has to be found from scratch in O(n) complexity. However, this will happen on average only once per rotation. Thus, each rotation has O(n) and one sweep O(n3) average case complexity, which is equivalent to one matrix multiplication. Additionally the must be initialized before the process starts, which can be done in n2 steps. Typically the Jacobi method converges within numerical precision after a small number of sweeps. Note that multiple eigenvalues reduce the number of iterations since .