1 Implicit Jacobi algorithms for the symmetric eigenproblem

By Froilan M. Dopico.

The Jacobi algorithm for computing the eigenvalues and eigenvectors of a symmetric matrix is one of the earliest methods in numerical analysis, dating to 1846. It was the standard procedure for solving dense symmetric eigenvalue problems before the QR algorithm was developed. The Jacobi method is much slower than QR or than any other algorithm based on previous reduction to tridiagonal form, and, as a consequence, it is not used in practice. However, in the last twenty years the Jacobi algorithm has received considerable attention because it can compute the eigenvalues and eigenvectors of many types of structured matrices with much more accuracy than other algorithms. The essential idea is to compute first an accurate factorization of the matrix A, and then to apply the Jacobi algorithm implicitly on the factors. The theoretical property that supports this approach is that a factorization A = XDX^{T}, where X is well conditioned and D is diagonal and nonsingular, determines very accurately the eigenvalues and eigenvectors of A, i.e., small componentwise perturbations of D and small normwise perturbations of X produce small relative variations in the eigenvalues of A, and small variations in the eigenvectors with respect the eigenvalue relative gap. The purpose of this talk is to present a unified overview on implicit Jacobi algorithms, on classes of symmetric matrices for which they work, on the perturbation results that are needed to prove the accuracy of the computed eigenvalues and eigenvectors, and, finally, to present very recent developments in this area that include a new, simple, and satisfactory algorithm for symmetric indefinite matrices.