Lanczos algorithm - Wikipedia
numerical-linear-algebraeigenvaluessparse-matrixiterative-methodskrylov
Abstraction: Iterative Krylov method finding extreme eigenvalues of large sparse Hermitian matrices
Key points:
- Reduces eigendecomposition of a large Hermitian matrix to a small tridiagonal matrix via Krylov subspace projection; only requires matrix-vector products
- Devised by Cornelius Lanczos (1950); made numerically stable by Ojalvo and Newman (1970) via full reorthogonalization of Lanczos vectors
- Raw algorithm is numerically unstable in floating-point: orthogonality is lost, producing spurious eigenvalues; stability requires reorthogonalization or post-processing
- Convergence rate governed by Chebyshev polynomial bounds; depends on the eigengap ratio—significantly faster than power iteration when eigengap is small
- Complexity O(n·k) for k iterations on a matrix with average n nonzeros per row; highly parallelisable
- Used in latent semantic indexing, PageRank, HITS algorithm; implemented in ARPACK (also exposed via SciPy, Julia)
Connections: Arpack · Eigenvalue Algorithms · Numerical Linear Algebra · Krylov Methods · Sparse Matrix Computation