How to Learn the Lanczos Algorithm: Krylov Subspaces, Three-Term Recurrence, Ritz Values, Reorthogonalization and Sparse Eigenproblems

Wait, What?

To estimate a few eigenvalues of a matrix with millions of rows, you may never need to factorize the matrix—or even store it explicitly.

The Lanczos algorithm is a Krylov-subspace method for extracting a small number of eigenvalues and eigenvectors from a large real symmetric or complex Hermitian matrix. Instead of solving the full eigenproblem, it repeatedly multiplies the matrix by a vector and builds a much smaller tridiagonal matrix whose eigenvalues—Ritz values—approximate those of the original operator.

Quick Answer

Learn Lanczos through symmetric eigenproblems → power iteration → Krylov subspaces → orthogonal bases → three-term recurrence → tridiagonal projection → Ritz values/vectors → residuals → loss of orthogonality → reorthogonalization → restart/shift-invert → sparse production solvers. Do not start from an ARPACK function call. Start by seeing why symmetry collapses a general orthogonalization process into a short recurrence.

1. Begin With the Partial Eigenvalue Job

A dense eigendecomposition computes all eigenvalues and often all eigenvectors. That is unnecessary when a large sparse problem needs only the largest few, smallest few, or values near a target. Lanczos is built for this partial-spectrum setting.

Applications include vibration modes, structural mechanics, quantum systems, graph spectra, covariance operators and dimensionality-reduction pipelines.

2. Rebuild Power Iteration First

Power iteration repeatedly applies A to a vector:

q_(k+1) = A q_k / ||A q_k||

Under favorable conditions it converges toward a dominant eigenvector. But it extracts limited spectral information and may converge slowly when dominant eigenvalues are close. Lanczos keeps a whole sequence of directions generated by repeated applications of A, preserving much more information.

3. The Krylov Subspace

Starting from a nonzero vector q₁, the order-m Krylov subspace is:

K_m(A,q1) = span{q1, A q1, A² q1, ..., A^(m-1) q1}

Rather than manipulating the enormous ambient space directly, Lanczos builds an orthonormal basis for this subspace. The quality of the approximation improves as useful spectral information accumulates in that basis.

4. Symmetry Creates the Three-Term Recurrence

For a symmetric matrix A, the Arnoldi orthogonalization structure simplifies dramatically. In exact arithmetic, each new Lanczos vector only needs the two previous Lanczos vectors:

beta_0 = 0
q_0 = 0
choose unit q_1

for j = 1,2,...:
    w = A q_j - beta_(j-1) q_(j-1)
    alpha_j = q_j^T w
    w = w - alpha_j q_j
    beta_j = ||w||
    q_(j+1) = w / beta_j

The scalars α and β form a symmetric tridiagonal matrix Tₘ. This short recurrence is what makes Lanczos memory-efficient and practical for large sparse operators.

5. Projection Turns a Huge Matrix Into a Small One

Let Qₘ contain the Lanczos basis vectors. The projected matrix is:

T_m = Q_m^T A Q_m

For Lanczos, Tₘ is tridiagonal. Solve the small eigenproblem:

T_m y = theta y

The scalar θ is a Ritz value approximating an eigenvalue of A, and Qₘy is the corresponding Ritz vector approximation.

6. Work a Small Symmetric Matrix by Hand

Choose a 4×4 symmetric tridiagonal matrix and a normalized starting vector. Compute q₁, then one α, one β and q₂. Continue for two or three iterations. Construct T₂ or T₃ and compare its eigenvalues with the eigenvalues of A.

The purpose of the exercise is to watch spectral information move from a large matrix-vector operation into a tiny projected eigenproblem.

7. Residuals Tell You Whether a Ritz Pair Is Ready

For an approximate eigenpair (θ,v), the residual is:

r = A v - theta v

A small residual means the pair nearly satisfies the original eigenvalue equation. Production solvers use residual-based convergence tests rather than judging convergence from changes in θ alone.

8. Exact Arithmetic and Floating Point Are Different Algorithms in Practice

In exact arithmetic, Lanczos vectors remain orthogonal through the three-term recurrence. In floating-point arithmetic, roundoff causes loss of orthogonality. Once a Ritz vector converges, numerical contamination can reintroduce that direction and create duplicate or “ghost” eigenvalues.

This is one of the most important professional lessons in numerical algorithms: a mathematically valid invariant can decay in floating point even when every line of code matches the textbook.

9. Reorthogonalization Is a Controlled Cost

Full reorthogonalization compares each new vector against all previous Lanczos vectors, improving robustness but increasing time and memory. Selective or partial reorthogonalization restores orthogonality only when needed. Parlett and Scott’s classic work showed how selective orthogonalization can suppress duplicate converged eigenvectors without paying the full cost every step.

The right strategy depends on requested accuracy, number of eigenpairs, spectral clustering and available memory.

10. Breakdown Can Be Good or Bad

If βⱼ becomes zero in exact arithmetic, the Krylov subspace has become invariant: no new direction exists, and the current projection may already contain exact spectral information for the reachable subspace. In finite precision, an extremely small β may also signal numerical trouble. Always distinguish mathematical termination from numerical near-breakdown.

11. Restarting Keeps Memory Bounded

A long Lanczos run stores many basis vectors if Ritz vectors are required or if reorthogonalization is used. Practical eigensolvers therefore restart while retaining useful spectral information. ARPACK popularized implicitly restarted Lanczos for symmetric problems and implicitly restarted Arnoldi for general nonsymmetric problems.

Current SciPy eigsh wraps ARPACK for symmetric/Hermitian partial eigenproblems and exposes controls such as the number of desired eigenpairs, Krylov-subspace size, initial vector, tolerance and shift-invert mode.

12. Shift-Invert Changes Which Eigenvalues Are Easy

Lanczos naturally favors extreme eigenvalues. To target eigenvalues near a shift σ, solve transformed systems involving:

(A - sigma I)^(-1)

Eigenvalues near σ become dominant in the transformed problem. This can dramatically accelerate interior-eigenvalue searches, but each iteration now requires solving a linear system. The true cost may therefore move from sparse matrix-vector products to factorization or iterative linear solves.

13. Matrix-Free Is a Major Professional Advantage

Lanczos only needs the operation v ↦ Av. If A is too large to store but its action on a vector can be computed, use a linear operator. This is common in PDE discretizations, graph Laplacians and scientific simulations.

A matrix-free implementation should benchmark the operator cost, communication cost on distributed hardware, orthogonalization cost and memory traffic separately.

14. How to Learn Lanczos Efficiently

Use Predict–Run–Investigate–Modify–Make. Predict the result of one matrix-vector multiplication and Gram–Schmidt step. Run power iteration. Investigate the Krylov basis. Modify the code into the Lanczos three-term recurrence. Then make a residual-controlled sparse eigensolver. Worked examples and partially completed recurrences are useful scaffolds because the indexing is easy to get wrong before the underlying geometry is understood.

Common Failure States

• Applying symmetric Lanczos to a nonsymmetric matrix without justification.
• Confusing Ritz values with exact eigenvalues before residuals are small.
• Ignoring loss of orthogonality and accepting ghost eigenpairs.
• Normalizing after β has underflowed or become numerically meaningless.
• Requesting many eigenpairs with too-small a Krylov subspace.
• Using shift-invert without accounting for the cost and stability of linear solves.
• Benchmarking only iteration count while ignoring matrix-vector and reorthogonalization cost.

Practice Ladder

• Beginner: run power iteration on a 3×3 symmetric matrix.
• Foundation: compute three Lanczos steps and build T₃ by hand.
• Intermediate: form Ritz vectors and monitor residual norms.
• Advanced: deliberately create clustered eigenvalues and observe loss of orthogonality.
• Professional: compare a custom Lanczos implementation with SciPy eigsh, varying subspace dimension, restart, shift-invert, sparse storage and matrix-free operators.

Learning Hall Boundary

This article owns Lanczos as a symmetric/Hermitian Krylov projection method for partial eigenproblems. It does not replace the existing Krylov article’s CG/GMRES linear-system job, general numerical linear algebra, power iteration foundations or Arnoldi methods for nonsymmetric operators.

Evidence Boundary

Cornelius Lanczos introduced the method in 1950 as an iteration process for eigenvalue problems. The practical numerical story includes later work on loss of orthogonality and selective reorthogonalization, notably Parlett and Scott. Current SciPy documentation states that eigsh uses the Implicitly Restarted Lanczos Method through ARPACK for real symmetric and complex Hermitian partial eigenproblems.

Professional rule: you understand Lanczos when you can derive the three-term recurrence from symmetry, interpret Ritz residuals, recognize loss of orthogonality, and explain when restart or shift-invert changes the real computational bottleneck.