GMRES
GMRES — the Generalized Minimal RESidual method — is the workhorse Krylov solver for general, nonsymmetric Ax = b, where the elegant tricks of conjugate gradient no longer apply. Its defining principle is exactly what its name says: at step k it picks the vector x_k in the Krylov subspace that minimizes the Euclidean norm of the residual ||b - A x_k||. Among all candidates the subspace offers, GMRES always returns the one with the smallest leftover.
Mechanically, it runs the Arnoldi process to build an orthonormal basis of the Krylov subspace and to reduce A to a small upper-Hessenberg matrix. Minimizing the residual then collapses to a tiny least-squares problem on that Hessenberg matrix, solved cheaply each step. Because the residual norm is monotonically non-increasing, GMRES never gets worse — a comforting guarantee that CG-for-nonsymmetric variants do not all share.
The catch is memory and cost. Unlike CG's short recurrence, full GMRES must store every Arnoldi basis vector and re-orthogonalize against all of them, so step k costs and stores O(k) — growing without bound. The standard remedy is restarting, GMRES(m): run m steps, take the current answer as a new starting guess, and begin afresh. This caps the memory but can stall, because restarting throws away the global subspace.
Convergence for nonsymmetric matrices is genuinely harder to predict than for CG; eigenvalues alone do not determine it when A is far from normal. In practice GMRES is rarely competitive without a good preconditioner, but with one it is the reliable default for the asymmetric, nonsymmetric systems that pervade fluid dynamics, electromagnetics, and circuit simulation.
GMRES is defined by a minimization: at each step it returns the Krylov-subspace vector with the smallest residual in the 2-norm.
Full GMRES is mathematically the cleanest but practically expensive; almost everyone runs the restarted GMRES(m). Choosing m is an art: larger m converges in fewer outer cycles but costs more memory and work per cycle.