Symmetric EVD

Real number λ and vector z are called an eigen pair of matrix A, if Az = λz. For a real matrix A there could be both the problem of finding the eigenvalues and the problem of finding the eigenvalues and eigenvectors.

If matrix A of size NxN is symmetric, it has N eigenvalues (not necessarily distinctive) and N corresponding eigenvectors which form an orthonormal basis (generally, eigenvectors are not orthogonal, and their number could be lower than N).

Overview of the existing algorithms solving the eigenvalue problem.

The first algorithm solving the eigenvalue problem for a symmetric NxN matrix was the Jacobi algorithm which had reduced matrix to diagonal form by using an orthogonal transformation. During the transformations, the diagonal elements were increased, and the off-diagonal elements were decreased. The result of this process is a matrix whose off-diagonal elements were equal to 0, and whose diagonal elements were equal to the eigenvalues.

The Jacobi algorithm is simple but ineffective: it performs operations upon a full matrix A even when most of the elements have already been converged to 0. Almost all later algorithms for solving the symmetric eigenvalue problem preliminary reduce the matrix to tridiagonal form (this operation is performed by non-iterative algorithm in a finite number of steps) and then work with a tridiagonal matrix.

The most widespread algorithms family is a algorithms based on QL/QR iteration applied to a tridiagonal matrix. We can mention the algorithm from the LINPACK library which implements the simplest QL algorithm (the subroutines which are related to this algorithm could be found in many sources) and a more up-to-date variant from the LAPACK library (the xSTEQR subroutine) which uses implicit shifts and can switch between QL and QR iterations depending on their performance for the given matrix. The algorithm from the LAPACK library is bigger but more reliable and accurate, so it is this algorithm that is used as the basis of a source code available on this page.

There are some other algorithms for finding the eigen pairs in the LAPACK library. We can point to a divide-and-conquer algorithm and an RRR algorithm. They can significantly speed up the finding of eigen pairs for the big symmetric tridiagonal matrix. Speeding-up can reach several dozen times for a tridiagonal matrix, for a symmetric matrix (taking into account the time required to reduce the matrix to tridiagonal form) it can reach 2-4 times. These algorithms are rather complex, therefore they haven't been included in the ALGLIB library yet. If the time required to find the eigen pairs of big symmetric matrices is critical, it is recommended to use the LAPACK library.

Note #1
If we have to find the eigenvalues and eigenvectors from a given interval (or having given numbers), it is reasonable to use algorithm on the basis of bisection and inverse iteration. If we only have to find a small part of the spectrum, we can increase the performance considerably in comparison to the algorithms which find all the eigenvalues and eigenvectors.

Subroutine description

This algorithm finds all the eigenvalues (and, if needed, the eigenvectors) of a symmetric matrix. The symmetric matrix is reduced to tridiagonal form by using orthogonal transformation. After that, the algorithm for solving this problem for a tridiagonal matrix is called. The algorithm is iterative, so, theoretically, it may not converge. In this case, it returns False.

This algorithm uses the subroutines from the LAPACK 3.0 library.

This article is licensed for personal use only.