The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an Hermitian matrix, where is often but not necessarily much smaller than . Although computationally efficient in principle, the method as initially formulated was not useful, due to its numerical instability.
In 1970, Ojalvo and Newman showed how to make the method numerically stable and applied it to the solution of very large engineering structures subjected to dynamic loading. This was achieved using a method for purifying the Lanczos vectors (i.e. by repeatedly reorthogonalizing each newly generated vector with all previously generated ones) to any degree of accuracy, which when not performed, produced a series of vectors that were highly contaminated by those associated with the lowest natural frequencies.
In their original work, these authors also suggested how to select a starting vector (i.e. use a random-number generator to select each element of the starting vector) and suggested an empirically determined method for determining , the reduced number of vectors (i.e. it should be selected to be approximately 1.5 times the number of accurate eigenvalues desired). Soon thereafter their work was followed by Paige, who also provided an error analysis. In 1988, Ojalvo produced a more detailed history of this algorithm and an efficient eigenvalue error test.
The algorithm
Input a Hermitian matrix of size , and optionally a number of iterations (as default, let ). Strictly speaking, the algorithm does not need access to the explicit matrix, but only a function that computes the product of the matrix by an arbitrary vector. This function is called at most times. Output an matrix with orthonormal columns and a tridiagonal real symmetric matrix of size . If , then is unitary, and . Warning The Lanczos iteration is prone to numerical instability. When executed in non-exact arithmetic, additional measures (as outlined in later sections) should be taken to ensure validity of the results. Let be an arbitrary vector with Euclidean norm . Abbreviated initial iteration step: Let . Let . Let . For do: Let (also Euclidean norm). If , then let , else pick as an arbitrary vector with Euclidean norm that is orthogonal to all of . Let . Let . Let . Let be the matrix with columns . Let . Note for .
There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable. In practice the initial vector may be taken as another argument of the procedure, with and indicators of numerical imprecision being included as additional loop termination conditions.
Not counting the matrix–vector multiplication, each iteration does arithmetical operations. The matrix–vector multiplication can be done in arithmetical operations where is the average number of nonzero elements in a row. The total complexity is thus , or if ; the Lanczos algorithm can be very fast for sparse matrices. Schemes for improving numerical stability are typically judged against this high performance.
The vectors are called Lanczos vectors. The vector is not used after is computed, and the vector is not used after is computed. Hence one may use the same storage for all three. Likewise, if only the tridiagonal matrix is sought, then the raw iteration does not need after having computed , although some schemes for improving the numerical stability would need it later on. Sometimes the subsequent Lanczos vectors are recomputed from when needed.