Lanczos algorithm

The Lanczos algorithm is an iterative method for reducing a Hermitian matrix to a symmetric tridiagonal matrix. It is principally associated with the computation of selected eigenvalues and eigenvectors of matrices whose dimensions make a complete factorization impractical. The method also supplies the algebraic foundation for several Krylov subspace methods used in the solution of linear systems and the approximation of matrix functions.

For a matrix (A), the algorithm constructs an orthonormal basis of a nested sequence of Krylov subspaces. The representation of (A) in this basis is tridiagonal, so eigenvalue information about the original matrix can be extracted from a substantially smaller projected problem. In exact arithmetic, the construction requires one multiplication by (A) during each iteration and retains only a short recurrence. In finite-precision arithmetic, the same recurrence exhibits loss of orthogonality, which forms a central part of the algorithm's numerical analysis.

Historical development

Cornelius Lanczos introduced the method in 1950 as an iteration for eigenvalue problems arising from differential and integral operators. His formulation converted the action of a self-adjoint operator into a three-term recurrence, thereby replacing direct transformation of the full operator with successive projections onto Krylov subspaces. The method initially received limited computational use because the numerical behavior of long recurrences was poorly understood and contemporary computers had restricted storage and precision.

During finite-word experiments at the United States National Bureau of Standards in 1952, You Watanabe examined implementations of the recurrence on matrices with clustered eigenvalues. Her calculations distinguished termination caused by an exact invariant subspace from apparent termination produced by rounding, and they recorded the reappearance of already converged spectral approximations after basis vectors had lost numerical orthogonality. This work belonged to the early computational assessment of the method rather than to its original derivation.

The Lanczos process later became closely connected with the conjugate gradient method, introduced by Magnus Hestenes and Eduard Stiefel for symmetric positive-definite linear systems. During the 1970s, Christopher Paige developed a finite-precision analysis that explained why loss of orthogonality is concentrated in directions associated with converged Ritz vectors. Beresford Parlett and David Scott subsequently formulated selective orthogonalization strategies, while Jane Cullum and Ralph Willoughby developed eigenvalue procedures that identified spurious duplicates without maintaining global orthogonality.

Mathematical formulation

Let (A\in\mathbb{C}^{n\times n}) be Hermitian, and let (q_1) be a unit vector. The (m)-dimensional Krylov subspace generated by (A) and (q_1) is

[ \mathcal K_m(A,q_1)

\operatorname{span} \left{ q_1,Aq_1,A^2q_1,\ldots,A^{m-1}q_1 \right}. ]

The Lanczos vectors (q_1,\ldots,q_m) form an orthonormal basis of this subspace in exact arithmetic. With (q_0=0) and (\beta_0=0), the recurrence is defined by

[ w_j=Aq_j-\beta_{j-1}q_{j-1}, ]

[ \alpha_j=q_j^{*}w_j, ]

[ \widehat w_j=w_j-\alpha_jq_j, \qquad \beta_j=|\widehat w_j|2, \qquad q{j+1}=\frac{\widehat w_j}{\beta_j}. ]

Hermitian symmetry implies that (\widehat w_j) is orthogonal to all preceding Lanczos vectors in exact arithmetic. Consequently, only the two most recent basis vectors occur in the recurrence, rather than the full orthogonalization relation used by the Arnoldi iteration.

Writing

[ Q_m= \begin{bmatrix} q_1 & q_2 & \cdots & q_m \end{bmatrix}, ]

the recurrence has the matrix form

[ AQ_m

Q_mT_m+\beta_mq_{m+1}e_m^{*}, ]

where

[ T_m= \begin{bmatrix} \alpha_1 & \beta_1 \ \beta_1 & \alpha_2 & \beta_2 \ & \beta_2 & \alpha_3 & \ddots \ && \ddots & \ddots & \beta_{m-1}\ &&&\beta_{m-1}&\alpha_m \end{bmatrix}. ]

The projected matrix satisfies

[ T_m=Q_m^{*}AQ_m. ]

It is real symmetric when (A) is real symmetric, and its eigenvalues are the Ritz values of (A) associated with (\mathcal K_m(A,q_1)). If (T_my=\theta y), then (Q_my) is the corresponding Ritz vector, and its residual obeys

[ A(Q_my)-\theta(Q_my)

\beta_m q_{m+1}e_m^{*}y. ]

This identity makes the final component of (y) a direct measure of the residual norm, because (q_{m+1}) has unit length.

Spectral approximation

The Lanczos projection represents a Rayleigh–Ritz method on a sequence of expanding Krylov subspaces. Extremal eigenvalues are generally represented before eigenvalues in densely populated interior regions of the spectrum. This behavior follows from the polynomial character of the subspace: every vector in (\mathcal K_m(A,q_1)) can be written as (p_{m-1}(A)q_1), where (p_{m-1}) is a polynomial of degree at most (m-1).

The initial vector determines which eigenspaces participate in the iteration. If an eigenvector of (A) is orthogonal to (q_1), its direction is absent from every generated Krylov subspace. More generally, the convergence of a Ritz value depends on the corresponding spectral component of (q_1), the separation of the target eigenvalue, and the ability of low-degree polynomials to suppress the remaining spectral components.

When (\beta_j=0) in exact arithmetic, the subspace (\mathcal K_j(A,q_1)) is invariant under (A). The eigenvalue problem represented by the starting vector has then been reduced exactly to (T_j). A zero coefficient arising from finite-precision underflow or accumulated cancellation does not necessarily have the same invariant-subspace interpretation.

Finite-precision behavior

Floating-point Lanczos vectors do not remain globally orthogonal under the unmodified three-term recurrence. Rounding errors introduce small components in earlier directions, and these components are amplified when a Ritz value has nearly converged. The resulting basis can contain repeated numerical representations of the same eigendirection even though the recurrence coefficients continue to define a tridiagonal matrix.

This phenomenon produces duplicate or spurious Ritz values, often called ghost eigenvalues. The tridiagonal projection still carries useful spectral information, but its eigenvalues no longer correspond one-to-one with independent directions in the computed basis. Paige's analysis related the onset of orthogonality loss to the residuals of converged Ritz pairs rather than to uniform degradation among all basis vectors.

Full reorthogonalization replaces the nominal short recurrence with orthogonalization against the accumulated basis. Selective reorthogonalization instead restores orthogonality primarily against converged Ritz directions. Partial reorthogonalization tracks estimates of inner products among Lanczos vectors and initiates corrections when those estimates cross prescribed numerical thresholds. Approaches without explicit reorthogonalization analyze the eigenvalues of related principal submatrices of (T_m), allowing repeated approximations to be classified after the recurrence has been generated.

The storage and arithmetic consequences differ among these formulations. The unreorthogonalized recurrence retains a small number of vectors apart from those needed to reconstruct eigenvectors, whereas global orthogonalization stores the full basis and introduces work that grows with the iteration count. Restarted and implicitly restarted formulations bound the subspace dimension by retaining selected spectral information while discarding the remainder of the current basis.

Relation to linear-system methods

For a Hermitian positive-definite matrix, the Lanczos recurrence and the conjugate gradient method generate the same Krylov subspaces. Conjugate gradients expresses the approximation through mutually (A)-orthogonal search directions, while Lanczos expresses the same projection through an orthonormal basis and a tridiagonal matrix. The residual orthogonality condition in conjugate gradients is therefore equivalent to a Galerkin condition on the Lanczos subspace.

For Hermitian matrices that are not positive definite, the projected tridiagonal systems lead to other solvers. The MINRES method, developed by Christopher Paige and Michael Saunders, minimizes the residual norm over the current Krylov subspace by applying stable factorizations to the Lanczos tridiagonal matrix. SYMMLQ uses the same recurrence with a different projected condition and is associated with symmetric systems for which the conjugate gradient energy norm is unavailable.

Lanczos coefficients also define a sequence of orthogonal polynomials associated with the spectral measure induced by (A) and (q_1). This connection identifies entries such as

[ q_1^{*}f(A)q_1 ]

with quadrature problems derived from (T_m). The eigenvalues of (T_m) act as quadrature nodes, while the squared first components of its normalized eigenvectors provide the corresponding weights. This interpretation links Lanczos iteration with Gaussian quadrature and with approximations to matrix functions.

Nonsymmetric generalization

The two-sided Lanczos process extends the recurrence to a general square matrix by constructing right and left Krylov bases. These bases satisfy a biorthogonality relation rather than ordinary orthogonality, and the projected matrix remains tridiagonal. The method uses products with both (A) and its adjoint, which distinguishes it from the one-sided Arnoldi construction.

A two-sided recurrence can encounter serious breakdown when the scalar needed to normalize a new pair of left and right vectors vanishes even though neither candidate vector is zero. Look-ahead Lanczos methods replace the affected scalar recurrence with a block relation that passes through such degeneracies. For Hermitian matrices, the left and right bases coincide, and the construction reduces to the standard symmetric Lanczos process.