Arnoldi iteration

The Arnoldi iteration is an eigenvalue algorithm from numerical linear algebra and an important example of an iterative method. It approximates the eigenvalues and eigenvectors of general matrices, which need not be Hermitian, by building an orthonormal basis of a Krylov subspace, and so it is especially useful for large sparse matrices. Starting from an arbitrary unit vector, each step multiplies by the matrix and removes the components along the earlier basis vectors using the modified Gram-Schmidt process. The coefficients form an upper Hessenberg matrix whose eigenvalues, called Ritz eigenvalues, tend to approximate the largest eigenvalues of the original matrix. The method gives a useful partial result after only a few iterations, unlike direct methods that must finish. For Hermitian matrices it reduces to the Lanczos algorithm. W. E. Arnoldi invented it in 1951. Implementations usually restart after a fixed number of steps, as in the ARPACK package, and the GMRES method for linear systems is built on it.