[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.
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
[3][4] In 1988, Ojalvo produced a more detailed history of this algorithm and an efficient eigenvalue error test.
Schemes for improving numerical stability are typically judged against this high performance.
Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition.
The power method for finding the eigenvalue of largest magnitude and a corresponding eigenvector of a matrix
is roughly A critique that can be raised against this method is that it is wasteful: it spends a lot of work (the matrix–vector products in step 2.1) extracting information from the matrix
, but pays attention only to the very last result; implementations typically use the same variable for all the vectors
One way of stating that without introducing sets into the algorithm is to claim that it computes this is trivially satisfied by
To avoid that, one can combine the power iteration with a Gram–Schmidt process, to instead produce an orthonormal basis of these Krylov subspaces.
(Indeed, it turns out that the data collected here give significantly better approximations of the largest eigenvalue than one gets from an equal number of iterations in the power method, although that is not necessarily obvious at this point.)
The Lanczos algorithm then arises as the simplification one gets from eliminating calculation steps that turn out to be trivial when
(This is essentially also the reason why sequences of orthogonal polynomials can always be given a three-term recurrence relation.)
In general so the directions of interest are easy enough to compute in matrix arithmetic, but if one wishes to improve on both
cannot converge slower than that of the power method, and will achieve more by approximating both eigenvalue extremes.
has enough nonzero elements, the algorithm will output a general tridiagonal symmetric matrix as
, so Furthermore the quantity (i.e., the ratio of the first eigengap to the diameter of the rest of the spectrum) is thus of key importance for the convergence rate here.
, but since the power method primarily is sensitive to the quotient between absolute values of the eigenvalues, we need
by The estimate of the largest eigenvalue is then so the above bound for the Lanczos algorithm convergence rate should be compared to which shrinks by a factor of
region is where the Lanczos algorithm convergence-wise makes the smallest improvement on the power method.
Stability means how much the algorithm will be affected (i.e. will it produce the approximate result close to the original one) if there are small numerical errors introduced and accumulated.
Numerical stability is the central criterion for judging the usefulness of implementing an algorithm on a computer with roundoff.
However, in practice (as the calculations are performed in floating point arithmetic where inaccuracy is inevitable), the orthogonality is quickly lost and in some cases the new vector could even be linearly dependent on the set that is already constructed.
Practical implementations of the Lanczos algorithm go in three directions to fight this stability issue:[6][7] Variations on the Lanczos algorithm exist where the vectors involved are tall, narrow matrices instead of vectors and the normalizing constants are small square matrices.
These are called "block" Lanczos algorithms and can be much faster on computers with large numbers of registers and long memory-fetch times.
[12] Another successful restarted variation is the Thick-Restart Lanczos method,[13] which has been implemented in a software package called TRLan.
[14] In 1995, Peter Montgomery published an algorithm, based on the Lanczos algorithm, for finding elements of the nullspace of a large sparse matrix over GF(2); since the set of people interested in large sparse matrices over finite fields and the set of people interested in large eigenvalue problems scarcely overlap, this is often also called the block Lanczos algorithm without causing unreasonable confusion.
[16] The NAG Library contains several routines[17] for the solution of large scale linear systems and eigenproblems which use the Lanczos algorithm.
The GraphLab[18] collaborative filtering library incorporates a large scale parallel implementation of the Lanczos algorithm (in C++) for multicore.