Lanczos algorithm

The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the ${\displaystyle m}$ "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an ${\displaystyle n\times n}$ Hermitian matrix, where ${\displaystyle m}$ is often but not necessarily much smaller than ${\displaystyle n}$.^[1] 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.^[2] 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)^[2] 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 ${\displaystyle m}$, 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.^[3][4] In 1988, Ojalvo produced a more detailed history of this algorithm and an efficient eigenvalue error test.^[5]