a Krylov subspace
/ KREE-loff /
Imagine you are only allowed to do one thing with the matrix A: multiply it by a vector. You cannot factor it, cannot peek inside it, cannot even store it — you can only hand it a vector and get back A times that vector. What solutions to A x = b can you build out of nothing but this? Start with the right-hand side b. Apply A to get A b. Apply A again to get A^2 b. Keep going. The space spanned by b, A b, A^2 b, A^3 b, ..., up to A^{k-1} b is the Krylov subspace of dimension k. It is the entire universe of vectors reachable from b using only matrix-vector products.
Why is this the right place to look? Because of a deep algebraic fact: by the Cayley-Hamilton theorem, A^{-1} b — the exact solution — is itself a polynomial in A applied to b, so the true answer LIVES inside a Krylov subspace (of dimension at most n). A Krylov method therefore searches the growing subspace span{b, A b, ..., A^{k-1} b} for the best approximate solution it can find there, and as the subspace grows it must eventually contain the exact answer. Different methods define 'best' differently — conjugate gradient minimizes energy, GMRES minimizes the residual norm, MINRES minimizes residual for symmetric problems — but all of them are Krylov methods, distinguished only by which optimal vector they extract from the same Krylov subspace.
This idea is the great leap beyond stationary iterations. A stationary method like Jacobi mechanically repeats one fixed step; a Krylov method instead remembers all the directions it has explored and picks the optimal combination, which is why it can converge in far fewer steps. The whole machinery rests on one cheap operation — the matrix-vector product — which is exactly what sparse and matrix-free settings provide. The only practical headache is that the raw Krylov vectors A^k b quickly become nearly parallel (they all tilt toward the dominant eigenvector), so in practice one builds an orthonormal basis for the subspace via the Arnoldi or Lanczos process before doing the optimization.
After 3 steps the Krylov subspace is span{b, A b, A^2 b}. A Krylov method seeks x_3 in this 3-dimensional space minimizing some measure of error. If A has only 3 distinct eigenvalues, the exact solution already lies in this subspace and the method finishes in 3 steps, regardless of how large n is.
Build the solution from b, A b, A^2 b, ... — using only matrix-vector products.
The raw power vectors b, A b, A^2 b, ... become numerically nearly linearly dependent fast (they align with the dominant eigenvector), so you never use them directly; the Arnoldi/Lanczos process orthogonalizes them. Krylov convergence depends strongly on the spectrum, which is why preconditioning matters so much.