the Lanczos algorithm
/ LAN-tsosh /
Imagine a symmetric matrix so large — millions of rows — that you cannot even store it as a full array, only multiply by it. You do not want all its eigenvalues; you want a handful at the extremes (the largest few, or the smallest few), which is exactly what arises in vibration analysis, quantum chemistry, and spectral graph methods. The QR algorithm is hopeless here: it needs the full matrix and finds everything. The Lanczos algorithm is the tool built for precisely this job — a few extreme eigenvalues of a huge sparse symmetric matrix, using only matrix-vector products.
It is the power method's clever cousin. The power method throws away every intermediate vector A v, A^2 v, A^3 v except the last; Lanczos keeps them and remembers that together they span a Krylov subspace, which contains far more spectral information than any single vector. Starting from a vector q_1, it builds an orthonormal basis of the Krylov space one vector at a time, and the magic of symmetry makes this a SHORT three-term recurrence: each new basis vector needs only the previous two (q_{j+1} comes from A q_j minus its projections onto q_j and q_{j-1}). In that basis the giant matrix A is represented by a tiny tridiagonal matrix T_k of size k. You compute the eigenvalues of T_k (cheap, since k is small) — these are the Ritz values, and the extreme ones converge to the extreme eigenvalues of A remarkably fast.
Two honest caveats. First, in exact arithmetic the basis vectors are orthogonal, but in floating point they LOSE orthogonality once a Ritz value converges — ghost copies of already-found eigenvalues appear. Practical Lanczos must reorthogonalize (full, selective, or partial) to stay reliable, or detect and discard the spurious copies. Second, Lanczos shines for the EXTREME eigenvalues; interior eigenvalues converge slowly, so to target an interior region you combine it with a shift-and-invert step (turning interior into extreme, at the cost of solving linear systems). Used well, Lanczos finds the ten largest eigenvalues of a billion-by-billion sparse matrix that no dense method could touch.
To find the two largest eigenvalues of a 10-million-by-10-million graph Laplacian (which you only have as a function that multiplies a vector), run Lanczos for, say, 50 steps. You build a 50x50 tridiagonal T, compute its eigenvalues, and the top two Ritz values already match A's top two eigenvalues to many digits — at a cost of 50 matrix-vector products, not 10-million-cubed flops.
Lanczos projects a huge sparse symmetric matrix onto a small Krylov subspace via a three-term recurrence, then reads extreme eigenvalues off a small tridiagonal matrix.
Loss of orthogonality in floating point is the central practical pitfall: it produces spurious duplicate (ghost) eigenvalues, so any production Lanczos uses some reorthogonalization scheme. Naive textbook Lanczos without it will silently report the same eigenvalue several times.