Preconditioning changes the geometry of a linear system so that an iterative method sees a better conditioned problem.
Preconditioned system
Definition. A preconditioner \(M\) approximates \(A\) but is easier to invert. One may solve \(M^{-1}Ax=M^{-1}b\), \(AM^{-1}y=b\), or a symmetrically preconditioned equivalent system.
Spectral clustering
Proposition. For Krylov methods, a good preconditioner clusters eigenvalues or reduces the effective condition number of the preconditioned operator. The preconditioner should also be cheap enough that each iteration remains affordable.
Incomplete factorization
Definition. Incomplete LU or Cholesky factorization drops selected fill-in entries while approximating a direct factorization. The dropping rule balances memory, stability, and quality of approximation.
Multigrid principle
Theorem. For many elliptic discretizations, smoothers reduce high-frequency error while coarse-grid correction reduces low-frequency error. Combining these effects can yield convergence rates essentially independent of mesh size.
Problem dependence
Remark. There is no universal preconditioner. Effective preconditioning uses structure: ellipticity, graph geometry, block variables, low-rank components, or statistical covariance models.
Equivalent systems and transformed geometry
Left, right, and split preconditioning solve \[ M^{-1}Ax=M^{-1}b,\qquad AM^{-1}y=b,\ x=M^{-1}y, \] or \[ M_L^{-1}AM_R^{-1}y=M_L^{-1}b. \] The goal is not to approximate \(A^{-1}\) entrywise, but to make the transformed operator easy for the chosen iteration while keeping applications of \(M^{-1}\) cheap.
Spectral equivalence for conjugate gradients
Theorem. Let \(A,M\) be symmetric positive definite and suppose \[ c\,x^\top Mx \le x^\top Ax \le C\,x^\top Mx \quad\text{for all }x. \] Then eigenvalues of \(M^{-1}A\) lie in \([c,C]\), so preconditioned CG obeys \[ \frac{\|e_k\|_A}{\|e_0\|_A} \le2\left( \frac{\sqrt{C/c}-1}{\sqrt{C/c}+1} \right)^k. \]
Proof. Generalized eigenvalues satisfy \[ \lambda=\frac{x^\top Ax}{x^\top Mx}, \] so the Rayleigh quotient lies in \([c,C]\). Apply the CG bound to the symmetric matrix \(M^{-1/2}AM^{-1/2}\).
Classical preconditioners
- Jacobi scaling uses \(M=\operatorname{diag}(A)\) and corrects units.
- Incomplete LU or Cholesky drops fill during factorization; drop tolerance balances cost and quality.
- Multigrid smooths high-frequency error and corrects low-frequency error on coarse grids, ideally yielding mesh-independent iteration counts.
- Domain decomposition solves local subproblems and coordinates them through overlap or a coarse space.
- Deflation and low-rank corrections remove isolated troublesome spectral directions.
Preconditioning normal and saddle-point systems
For least squares, preconditioning \(A\) before forming normal equations is preferable to preconditioning \(A^\top A\) blindly. Saddle-point matrices \[ \begin{pmatrix}A&B^\top\\B&0\end{pmatrix} \] need block preconditioners approximating \(A\) and the Schur complement \(BA^{-1}B^\top\). Preserving symmetry and definiteness determines whether CG, MINRES, or GMRES is applicable.
Cost model
A stronger preconditioner is not automatically faster. Total work is \[ \text{setup cost} +(\text{iterations})\times (\text{matrix, preconditioner, and communication cost}). \] In parallel computation, synchronization and data movement can dominate floating-point operations. Reuse across related systems often justifies expensive setup.