GMRES
/ JEE-em-rez /
GMRES is the go-to Krylov method when A is a general matrix — nonsymmetric, possibly with complex eigenvalues, the kind that comes from convection-dominated flows and many real engineering systems. Conjugate gradient needs the cozy structure of symmetric positive-definiteness to work its energy-minimizing trick; GMRES throws that requirement away and instead does the most natural thing imaginable: among all candidate solutions in the current Krylov subspace, pick the one whose residual r = b - A x has the smallest possible length. GMRES stands for Generalized Minimal RESidual, and minimizing the residual norm is literally its definition.
Mechanically, GMRES uses the Arnoldi process to build an orthonormal basis of the Krylov subspace span{b, A b, A^2 b, ...} one vector at a time, and at each step it solves a small least-squares problem to find the residual-minimizing combination. Because the residual norm can only go down (you are optimizing over a growing space), GMRES never breaks down and its residual decreases monotonically — a very reassuring property. In exact arithmetic it would reach the exact answer within n steps. The cost is the catch: to keep all the directions orthogonal, GMRES must store every basis vector it has built and orthogonalize against all of them, so its memory and work per step GROW as the iteration proceeds — after k steps you are holding k full vectors and doing O(k) work per new step.
That growing cost is why nobody runs full GMRES for long. The standard fix is restarting, written GMRES(m): run m steps, take the current approximation as a new starting guess, throw away the accumulated basis, and begin again. This caps memory at m vectors, but it also discards hard-won information, so restarted GMRES can stagnate where full GMRES would have converged — choosing m is a real engineering trade-off between memory and robustness. As always with Krylov methods, the decisive factor is preconditioning: a good preconditioner clusters the spectrum so that GMRES (or its restarted version) converges in a handful of steps instead of hundreds.
GMRES(30) runs 30 Arnoldi steps, minimizes the residual over that 30-dimensional Krylov subspace, then restarts from the best vector found — holding at most 30 basis vectors. Full GMRES on the same problem might converge in 80 steps but would need to store all 80 vectors.
GMRES minimizes the residual norm over a growing Krylov subspace; restarting caps its growing memory.
Full GMRES never stagnates and its residual decreases monotonically, but its cost per step grows without bound — restarted GMRES(m) bounds the cost yet can stall, sometimes never converging on hard problems. There is no free lunch: GMRES's robustness for nonsymmetric A is paid for in memory or in the risk of restart stagnation, and preconditioning is what makes it practical.