Lanczos Algorithm

The Lanczos algorithm compresses a Hermitian Hamiltonian into a small tridiagonal matrix whose extremal eigenpairs often converge rapidly. It uses Hamiltonian–vector products rather than all matrix entries. Its elegant three-term recurrence is exact-arithmetic structure; reliable floating-point implementations must also manage the orthogonality that roundoff erodes.

Helpful background. Sparse eigensolvers explains target selection and original-problem residuals.

The Hermitian Krylov recurrence

For a starting vector $q_1$, Lanczos constructs an orthonormal basis of

$$\mathcal K_m(H,q_1) =\operatorname{span}\{q_1,Hq_1,\ldots,H^{m-1}q_1\}.$$

Every vector in this space is $p(H)q_1$ for a polynomial of degree below $m$. If $q_1=\sum_k a_k u_k$ in energy eigenvectors, then $p(H)q_1=\sum_k a_k p(E_k)u_k$: the polynomial changes the weights of existing spectral components but cannot create one with $a_k=0$. The projected eigenproblem is a Rayleigh–Ritz calculation; its variational interpretation depends on the target and trial space.

Start with a normalized vector $q_1$, set $q_0=0$ and $\beta_0=0$, and form

$$\begin{aligned} w_j&=Hq_j-\beta_{j-1}q_{j-1},\\ \alpha_j&=q_j^\dagger w_j,\\ w_j&\leftarrow w_j-\alpha_jq_j,\\ \beta_j&=\|w_j\|,\qquad q_{j+1}=w_j/\beta_j. \end{aligned}$$

Hermiticity makes $\alpha_j$ real. In exact arithmetic, $Hq_j$ is orthogonal to every $q_k$ with $k<j-1$: move $H$ to the other side of the inner product and use the preceding recurrence. This proves the three-term form by induction. For $Q_m=(q_1,\ldots,q_m)$,

$$HQ_m=Q_mT_m+\beta_mq_{m+1}e_m^T,$$

where $T_m$ has diagonal $\alpha_j$ and adjacent diagonals $\beta_j$. Its eigenpair $T_my=\theta y$ gives the Ritz vector $x=Q_my$ and, for orthonormal $Q_m$,

$$\|Hx-\theta x\|=\beta_m|e_m^Ty|.$$

This inexpensive estimate permits frequent convergence checks. Before accepting a result, explicitly evaluate $Hx-\theta x$ to detect accumulated recurrence or orthogonality error.

Breakdown, ghosts, and restarts

If $\beta_j=0$ in exact arithmetic, the current Krylov space is invariant: the iteration has exhausted the spectral components present in the start vector. This is a successful termination, not a reason to divide by an arbitrary small number. Near-breakdown needs a numerical tolerance based on the operator scale.

Once a Ritz vector converges, floating-point noise can reintroduce its direction into later vectors. The tridiagonal matrix may then contain repeated copies of one eigenvalue, often called ghosts. Check $Q_m^\dagger Q_m$ and use full, selective, or partial reorthogonalization appropriate to the implementation. Reorthogonalizing twice can be necessary when a newly generated direction is almost dependent.

Full reorthogonalization costs roughly $O(nm^2)$ over $m$ steps and stores the basis. Restarted Lanczos retains wanted Ritz information while limiting $m$; retaining too few vectors near a cluster can stall convergence. One starting vector cannot recover multiple independent vectors in an exactly degenerate eigenspace: polynomial actions only scale its one component there. Block Lanczos or independent starts are needed to resolve multiplicity.

A three-level calculation

Take $H=\operatorname{diag}(0,1,2)$ and $q_1=(1,1,1)^T/\sqrt3$. Then

$$\alpha_1=1,\qquad \beta_1=\sqrt{2/3},\qquad q_2=(-1,0,1)^T/\sqrt2.$$

At two steps,

$$T_2=\begin{pmatrix}1&\sqrt{2/3}\\\sqrt{2/3}&1\end{pmatrix},$$

with Ritz values $1\pm\sqrt{2/3}$. They approach the spectral edges but are not eigenvalues of $H$. The next coefficient is $\beta_2=1/\sqrt3$. Since each normalized eigenvector of $T_2$ has last-component magnitude $1/\sqrt2$, both residual norms are $1/\sqrt6$. Three independent steps recover the full spectrum and terminate.

The same projection also approximates $q_1^\dagger f(H)q_1$ by $e_1^Tf(T_m)e_1$, connecting Lanczos to quadrature and spectral measures. Accuracy for an eigenvalue does not automatically certify a sharply resolved spectral function; its frequency resolution and broadening need their own convergence study.

The many-body Lanczos application uses this projection for symmetry-resolved states and continued-fraction response. Krylov time evolution applies the same subspace idea to $e^{-iHt/\hbar}q_1$ with propagation-specific error checks.

Exercises

What happens in the example if the starting vector is $q_1=(0,1,0)^T$?

Solution

$Hq_1=q_1$, so $\alpha_1=1$ and $\beta_1=0$. The one-dimensional invariant subspace contains only the middle eigenstate. Exact termination says nothing about the absent energies $0$ and $2$.

Why does Hermiticity reduce Arnoldi’s upper-Hessenberg projection to a tridiagonal matrix in exact arithmetic? Does that remove the need to monitor orthogonality numerically?

Solution

Arnoldi’s projection has zero entries below its first subdiagonal. For Hermitian $H$ and orthonormal $Q_m$, the projection $Q_m^\dagger HQ_m$ is also Hermitian. The conjugate entries above the first superdiagonal therefore vanish as well, leaving a tridiagonal matrix. Roundoff can destroy the basis orthogonality used in that argument, so practical Lanczos still needs Gram-matrix checks and an appropriate reorthogonalization or restart strategy.

References

• Bai, Z., J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, 2000, online text — reorthogonalization and restarted algorithms.
• Cullum, J. K., and R. A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue Computations, SIAM, 2002 — finite-precision Lanczos, spectral validation, and spurious repeated eigenvalues.
• Lanczos, C., “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” Journal of Research of the National Bureau of Standards 45, 255–282 (1950), NIST historical source guide — original projection method.