Preconditioning

Preconditioning transforms a linear system into an equivalent one with a more favorable spectrum, so that an iterative solver converges in far fewer steps; it is often the single most important factor in the performance of large sparse solvers.

Definition

A preconditioner is a matrix, applied implicitly or explicitly to a linear system, that approximates the coefficient matrix or its inverse so that the preconditioned system has spectral properties leading to much faster convergence of an iterative method.

Scope

This topic covers the idea of an approximate inverse that clusters eigenvalues or lowers the condition number, the main families of preconditioners — diagonal and block diagonal, incomplete LU and Cholesky factorizations, sparse approximate inverses, and domain-decomposition and multigrid preconditioners — and the trade-off between a preconditioner's effectiveness and its cost to build and apply.

Core questions

• How does a preconditioner change the spectrum of a system to accelerate iterative convergence?
• What makes a good preconditioner, balancing approximation quality against construction and application cost?
• How are incomplete factorizations and sparse approximate inverses constructed?
• When are multigrid or domain-decomposition methods used as preconditioners rather than standalone solvers?

Key theories

Spectral transformation

Applying a preconditioner that approximates the inverse of the matrix yields a preconditioned operator whose eigenvalues are clustered or whose condition number is reduced; since Krylov convergence depends on the spectrum, this can shrink the iteration count by orders of magnitude.

Incomplete factorization preconditioners

Incomplete LU and incomplete Cholesky factorizations compute approximate triangular factors while discarding fill-in beyond a chosen sparsity pattern or threshold, producing an inexpensive preconditioner that captures much of the matrix's action.

Mechanisms

A preconditioner M is chosen so that solving systems with M is cheap and the preconditioned operator is close to the identity, clustering its eigenvalues. Diagonal (Jacobi) preconditioning simply rescales; incomplete LU or Cholesky factorizations build approximate sparse triangular factors by dropping small or out-of-pattern entries during elimination; sparse approximate inverses directly construct a sparse M approximating the inverse so that only matrix-vector products are needed. More powerful preconditioners apply one multigrid cycle or a domain-decomposition solve per iteration. In every case the preconditioner is applied within each step of a Krylov method, and its design balances how well it approximates the inverse against how much it costs to form and apply.

Clinical relevance

Preconditioning is decisive for solving the enormous ill-conditioned systems from PDE discretizations and large-scale optimization; the right preconditioner can turn an iteration that stagnates into one that converges in a handful of steps, and choosing and tuning preconditioners is a central practical concern in computational science and engineering software.

History

Preconditioning grew alongside Krylov methods from the 1970s onward, with incomplete factorizations introduced by Meijerink and van der Vorst in 1977 and a broad array of algebraic and multilevel preconditioners developed since; it is now recognized as often more important to solver performance than the choice of Krylov method itself.

Key figures

• Yousef Saad
• Michele Benzi
• Henk van der Vorst
• Olof Widlund

Seminal works

• saad2003
• benzi2002

Frequently asked questions

What makes a preconditioner good?

A good preconditioner closely approximates the inverse of the matrix so the preconditioned system is easy for the iterative method, yet is cheap to construct and apply. The art is balancing these competing goals: a more accurate preconditioner costs more per step but needs fewer steps.

Can a solver be used as a preconditioner?

Yes. A single cycle of multigrid or one domain-decomposition solve is frequently used as a preconditioner inside a Krylov method, combining the robustness of the Krylov iteration with the rapid error reduction of the inner solver.