Eigenvalue Algorithm - Iterative Algorithms

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.
QR algorithm	Hessenberg	all eigenpairs	6n3 + O(n2)	cubic
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.
Divide-and-conquer	Hermitian Tridiagonal	all eigenpairs	(4⁄₃)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.