Preconditioning

Preconditioning is a technique used in numerical linear algebra to improve the efficiency of iterative methods for solving linear systems and eigenvalue problems. It transforms the original system A x = b into a system that has more favorable properties for convergence by introducing a preconditioner matrix M, designed so that M is easier to invert and M approximates A in a useful way. The common forms are left preconditioning, right preconditioning, and split preconditioning, resulting in systems M^{-1} A x = M^{-1} b or A M^{-1} y = b with x = M^{-1} y.

By applying M, the spectrum of the system is altered to cluster eigenvalues and reduce the condition number kappa(A). This typically reduces the number of iterations required by Krylov subspace methods such as Conjugate Gradient, GMRES, or BiCGSTAB, often with a modest increase in per-iteration cost.

Common preconditioners include Jacobi (diagonal) M = diag(A), Gauss-Seidel and SOR, incomplete factorizations such as ILU and ICC, incomplete Cholesky for symmetric positive definite A, and multigrid or block preconditioners for certain structures. Polynomial preconditioners and domain decomposition are also used.

For symmetric positive definite A, symmetric preconditioning using M^{-1/2} A M^{-1/2} preserves SPD structure and allows the use of CG with improved efficiency.

Choice depends on problem characteristics; the preconditioner should be cheap to apply relative to the work saved in solving the transformed system. In optimization, preconditioning improves conditioning of the objective or Hessian to stabilize and accelerate gradient-based methods. Preconditioning is a broad tool with applications in scientific computing, engineering, and data analysis.