The Conjugate Gradient Method
The conjugate gradient method solves symmetric positive-definite systems efficiently using short recurrences and conjugate search directions.
Minimizing along conjugate directions
The conjugate gradient (CG) method solves A*x = b when A is symmetric positive-definite by reformulating it as the minimization of a quadratic energy. Rather than descending along the steepest gradient, which zigzags inefficiently, CG chooses search directions that are conjugate (A-orthogonal) to all previous ones. This guarantees that progress made in earlier directions is never undone, and in exact arithmetic the method reaches the exact solution in at most n steps for an n-dimensional system.
In practice, CG is used as an iterative method that reaches an accurate solution in far fewer than n steps, its convergence governed by the matrix's condition number.
The short recurrence advantage
CG's defining efficiency is that it maintains conjugacy using only a three-term recurrence: each step needs only the current residual, the previous search direction, and one matrix-vector product. Unlike GMRES it does not store the whole subspace, so its memory and per-iteration cost are fixed and small. This economy is possible precisely because the matrix is symmetric.
Convergence and preconditioning
The number of iterations scales roughly with the square root of the condition number, so ill-conditioned systems converge slowly. Preconditioned conjugate gradient (PCG) applies a symmetric positive-definite preconditioner (Jacobi, incomplete Cholesky, multigrid) to reduce the effective condition number, often turning an intractable problem into a rapidly converging one. PCG with a multigrid preconditioner is a common near-optimal solver for elliptic problems.
- Requires a symmetric positive-definite matrix
- Conjugate search directions avoid redundant progress
- Short three-term recurrence: low fixed memory
- Convergence scales with sqrt of the condition number
CG and PCG are standard for the symmetric positive-definite systems that arise from elliptic operators, such as potential and pressure solves, in fusion field and fluid codes.