12.4. The Solution to the Eigenvalue Problem

The eig function in MATLAB is quite complex. It looks at the data and performs pre-conditioning transformations to make the computation faster. It uses different algorithms to compute the eigenvalues depending on the size and relationships of the values in the matrix. Obviously, it does not find the eigenvalues by finding the roots of the characteristic polynomial, i.e., find the \lambdas that satisfy the equation det(\mathbf{A} - \lambda\,\mathbf{I}) = \bm{0}. We will offer only minor comments about the exact algorithms used by MATLAB’s eig function. Our focus is on the algorithmic foundations of modern numerical analysis software.

Although several algorithms exist for finding eigenvalues, we will focus on two orthogonal iterative algorithms that are fairly simple yet well-known for quickly finding accurate eigenvalues. These algorithms were developed by John Francis, whom we introduced in Introduction. The second algorithm, which we call the Francis algorithm establishes the foundation for eigensystem solutions in modern software such as MATLAB. The eig function in MATLAB uses the QZ algorithm for dense matrices. QZ finds the generalized eigendecomposition that finds the factorization \mathbf{A\,X} = \mathbf{B\,X\,\Lambda}. If matrix \bf{B} is an identity matrix, then we have the more common eigenvalue problem we discussed. Indeed, the QZ is an extension of the Francis algorithm. Although not as closely related, the Krylov algorithm used with sparse matrices, [1] is also derivative of the Francis algorithm [WATKINS11].

We will first review the power method that finds only the largest eigenvalue of a matrix. Then, we will focus on the orthogonal solutions that find all the eigenvalues. There are two reasons to mention the power method here. First, some problems only need the largest eigenvalue [2]. Secondly, the power method has theoretical relevance to why the QR and Francis algorithms converge (Convergence by Similarity Transforms).

[1]Problems related to artificial intelligence and machine learning make use of sparse matrices, which are huge matrices dominated by zeros.
[2]Google’s page rank algorithm only uses the largest eigenvalue and its corresponding eigenvector.