Lanczos Algorithm

Purpose: Find extreme eigenvalues and eigenvectors of a large sparse symmetric matrix, or solve sparse symmetric linear systems, using only matrix-vector products — $O(k\cdot \mathrm{nnz})$ for $k$ iterations.

The Idea: Krylov subspaces

Given $A$ and a start vector $v_1$, the Krylov subspace is

${\mathcal{K}}_k=\mathrm{span}\{v_1,A{v}_1,A^2{v}_1,\dots ,A^{k-1}{v}_1\}.$

These vectors quickly become numerically parallel, so Lanczos orthogonalises as it goes. For a symmetric $A$, the miracle is that each new vector only needs to be orthogonalised against the previous two — a three-term recurrence:

${\beta }_{j+1}{v}_{j+1}=A{v}_j-{\alpha }_j{v}_j-{\beta }_j{v}_{j-1},$
${\alpha }_j=v_j^{T}A{v}_j,{\beta }_{j+1}=\Vert A{v}_j-{\alpha }_j{v}_j-{\beta }_j{v}_{j-1}\Vert .$

In the resulting orthonormal basis, $A$ becomes a small tridiagonal matrix $T_k$, whose eigenvalues (computable in $O(k^2)$) approximate the extreme eigenvalues of $A$ extremely well — long before $k$ reaches $n$.

Complexity

• Per iteration: one matrix-vector product, $O(\mathrm{nnz})$, plus $O(n)$ vector arithmetic
• $k$ iterations: $O(k\cdot \mathrm{nnz}+k^2)$
• Space: $O(n)$ if only eigenvalues are needed (keep three vectors); $O(kn)$ to reconstruct eigenvectors

Extreme eigenvalues typically converge in $k\ll n$ iterations — often a few dozen for matrices with millions of rows.

Loss of orthogonality

In floating point, the computed $v_j$ lose mutual orthogonality once an eigenvalue converges, producing spurious duplicate (“ghost”) eigenvalues. Real implementations use selective or partial reorthogonalisation to control this. Over a finite field the problem disappears entirely — which is why the block Lanczos used in factorisation is numerically trivial.

Lanczos vs Wiedemann over finite fields

Both solve sparse systems using only matrix-vector products; they are the two standard choices for the linear algebra stage of the number field sieve.

	Lanczos	Wiedemann
Needs symmetry	yes ($A^{T}A$ if not)	no
Iterations	$\approx n$	$\approx 2n$
Failure mode	self-orthogonal vectors over ${\mathbb{F}}_2$ (handled by blocking)	unlucky random vectors (retry)
Parallelism	good (block Lanczos)	excellent (block Wiedemann)
Memory	$O(n)$ vectors	$O(n)$ scalars

Block Lanczos (Montgomery) is generally faster on a single machine; block Wiedemann distributes better across many.

Related Krylov methods

Method	For
Lanczos	symmetric eigenproblems
Conjugate gradient	symmetric positive definite systems — is Lanczos, rearranged
Arnoldi	non-symmetric eigenproblems; full orthogonalisation, $O(k^{2}n)$
GMRES	non-symmetric systems, built on Arnoldi
Power iteration	the single dominant eigenvalue; Lanczos is strictly better

Variants / Use Cases

• PageRank and spectral graph theory — the second eigenvalue of a graph Laplacian, spectral clustering, expansion
• Integer factorisation / discrete logs — block Lanczos over ${\mathbb{F}}_2$
• Physics and quantum chemistry — ground-state energies of enormous sparse Hamiltonians; the original motivation
• Wiedemann — the finite-field alternative
• Rank and Linear Systems — the topic page