Iterative Algorithms
Iterative algorithms solve the eigenvalue problem by producing sequences that converge to the eigenvalues. Some algorithms also produce sequences of vectors that converge to the eigenvectors. Most commonly, the eigenvalue sequences are expressed as sequences of similar matrices which converge to a triangular or diagonal form, allowing the eigenvalues to be read easily. The eigenvector sequences are expressed as the corresponding similarity matrices.
| Method | Applies to | Produces | Cost per step | Convergence | Description |
|---|---|---|---|---|---|
| Power iteration | General | eigenpair with largest value | Linear | Repeatedly applies the matrix to an arbitrary starting vector and renormalizes. | |
| Inverse iteration | General | eigenpair with value closest to μ | Linear | Power iteration for (A - μI )-1 | |
| Rayleigh quotient iteration | Hermitian | eigenpair with value closest to μ | Cubic | Power iteration for (A - μiI )-1, where μi for each iteration is the Raleigh quotient of the previous iteration. | |
| Preconditioned Inverse iteration or LOBPCG algorithm | Positive Definite Real Symmetric | eigenpair with value closest to μ | Inverse iteration using a preconditioner (an approximate inverse to A). | ||
| Bisection method | Real Symmetric Tridiagonal | any eigenvalue | linear | Uses the bisection method to find roots of the characteristic polynomial, supported by the Sturm sequence. | |
| Laguerre iteration | Real Symmetric Tridiagonal | any eigenvalue | cubic | Uses Laguerre's method to find roots of the characteristic polynomial, supported by the Sturm sequence. | |
| QR algorithm | Hessenberg | all eigenvalues | O(n2) | cubic | Factors A = QR, where Q is orthogonal and R is triangular, then applies the next iteration to RQ. |
| all eigenpairs | 6n3 + O(n2) | ||||
| Jacobi eigenvalue algorithm | Real Symmetric | all eigenvalues | O(n3) | quadratic | Uses Givens rotations to attempt clearing all off-diagonal entries. This fails, but strengthens the diagonal. |
| Divide-and-conquer | Hermitian Tridiagonal | all eigenvalues | O(n2) | Divides the matrix into submatrices that are diagonalized then recombined. | |
| all eigenpairs | (4⁄3)n3 + O(n2) | ||||
| Homotopy method | Real Symmetric Tridiagonal | all eigenpairs | O(n2) | Constructs a computable homotopy path from a diagonal eigenvalue problem. | |
| Folded spectrum method | Real Symmetric | eigenpair with value closest to μ | Preconditioned inverse iteration applied to (A - μI )2 | ||
| MRRR algorithm | Real Symmetric Tridiagonal | some or all eigenpairs | O(n2) | "Multiple Relatively Robust Representations" - Performs inverse iteration on a LDLT decomposition of the shifted matrix. |
Read more about this topic: Eigenvalue Algorithm