Lanczos Method

The Lanczos algorithm is closely related to the iterative algorithms discussed in the previous section in that it needs to access the matrix only in the form of matrix-vector operations. It is different in that it makes much better use of the information obtained by remembering all the directions computed and always lets the matrix operate on a vector orthogonal to all those previously tried.

In this section we describe the Hermitian Lanczos algorithm
applicable to the eigenvalue
problem,

The algorithm starts with a properly chosen starting vector
and builds up an
orthogonal basis of the Krylov subspace,

is needed. In the new orthogonal basis the operator is represented by a real symmetric tridiagonal matrix,

which is also built up one row and column at a time, using the basic recursion,

At any step , we may compute an eigensolution of ,

where the superscript is used to indicate that these quantities change for each iteration . The Ritz value and its Ritz vector,

will be a good approximation to an eigenpair of if the residual has small norm; see §4.8.

Let us compute the residual for this Ritz pair,

We see that its norm satisfies

so we need to monitor only the subdiagonal elements of and the last elements of its eigenvectors to get an estimate of the norm of the residual. As soon as this estimate is small, we may flag the Ritz value as converged to the eigenvalue . Note that the computation of the Ritz values does not need the matrix-vector multiplication (4.12). We can save this time-consuming operation until the step , when the estimate () indicates convergence.

- Algorithm
- Convergence Properties
- Spectral Transformation
- Reorthogonalization
- Software Availability
- Numerical Examples