Krylov Subspace Methods
A family of iterative solvers that build solutions from powers of a matrix applied to a vector, using only matrix-vector products.
The Krylov subspace
Given a matrix A and a vector b, the m-dimensional Krylov subspace is the span of b, Ab, A^2 b, up to A^(m-1) b. Krylov methods approximate the solution of Ax = b (or eigenvalues of A) by searching within this growing subspace. The key feature is that they never require A explicitly; they need only the ability to compute the product of A with a vector.
This makes them ideal for large sparse systems, where A may have millions of rows but only a handful of nonzeros per row. In fusion plasma codes, discretized transport, MHD equilibrium, and field solves all produce such systems, and Krylov solvers are the standard workhorse for them.
Why the subspace grows well
The residual polynomial view explains convergence: after m steps the error is p(A) applied to the initial error, where p is a degree-m polynomial with p(0) = 1. Convergence is fast when a low-degree polynomial can be made small over the spectrum of A. Well-clustered eigenvalues converge quickly; a spectrum spread over many orders of magnitude converges slowly, which is why preconditioning is almost always paired with Krylov methods.
The method families
- For symmetric positive-definite A: the conjugate gradient method
- For symmetric indefinite A: MINRES and SYMMLQ
- For general nonsymmetric A: GMRES, BiCGStab, and their variants
- For eigenvalue problems: Lanczos (symmetric) and Arnoldi (nonsymmetric)
Each is built on an orthogonalization process that produces an orthonormal or biorthogonal basis for the Krylov subspace, reducing A to a small structured matrix whose problem is cheap to solve.
Short vs long recurrences
For symmetric A the basis obeys a three-term recurrence, so memory and work per step stay constant. For nonsymmetric A no short recurrence with full optimality exists (a theorem of Faber and Manteuffel), forcing a choice between growing memory (GMRES) or losing optimality (BiCGStab). This trade-off shapes the entire nonsymmetric solver landscape.