In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method.
Preconditioning for linear systems
In linear algebra and numerical analysis, a preconditioner of a matrix is a matrix such that has a smaller condition number than . It is also common to call the preconditioner, rather than , since itself is rarely explicitly available. In modern preconditioning, the application of , i.e., multiplication of a column vector, or a block of column vectors, by , is commonly performed in a matrix-free fashion, i.e., where neither , nor (and often not even ) are explicitly available in a matrix form.
Preconditioners are useful in iterative methods to solve a linear system for since the rate of convergence for most iterative linear solvers increases because the condition number of a matrix decreases as a result of preconditioning. Preconditioned iterative solvers typically outperform direct solvers, e.g., Gaussian elimination, for large, especially for sparse, matrices. Iterative solvers can be used as matrix-free methods, i.e. become the only choice if the coefficient matrix is not stored explicitly, but is accessed by evaluating matrix-vector products.
Description
Instead of solving the original linear system for , one may consider the right preconditioned system
and solve
for and
for .
Alternatively, one may solve the left preconditioned system
Both systems give the same solution as the original system as long as the preconditioner matrix is nonsingular. The left preconditioning is more traditional.
The two-sided preconditioned system
may be beneficial, e.g., to preserve the matrix symmetry: if the original matrix is real symmetric and real preconditioners and satisfy then the preconditioned matrix is also symmetric. The two-sided preconditioning is common for diagonal scaling where the preconditioners and are diagonal and scaling is applied both to columns and rows of the original matrix , e.g., in order to decrease the dynamic range of entries of the matrix.
The goal of preconditioning is reducing the condition number, e.g., of the left or right preconditioned system matrix or . Small condition numbers benefit fast convergence of iterative solvers and improve stability of the solution with respect to perturbations in the system matrix and the right-hand side, e.g., allowing for more aggressive quantization of the matrix entries using lower computer precision.
The preconditioned matrix or is rarely explicitly formed. Only the action of applying the preconditioner solve operation to a given vector may need to be computed.
Typically there is a trade-off in the choice of . Since the operator must be applied at each step of the iterative linear solver, it should have a small cost (computing time) of applying the operation. The cheapest preconditioner would therefore be since then Clearly, this results in the original linear system and the preconditioner does nothing. At the other extreme, the choice gives which has optimal condition number of 1, requiring a single iteration for convergence; however in this case and applying the preconditioner is as difficult as solving the original system. One therefore chooses as somewhere between these two extremes, in an attempt to achieve a minimal number of linear iterations while keeping the operator as simple as possible. Some examples of typical preconditioning approaches are detailed below.
Preconditioned iterative methods
Preconditioned iterative methods for are, in most cases, mathematically equivalent to standard iterative methods applied to the preconditioned system For example, the standard Richardson iteration for solving is
Applied to the preconditioned system it turns into a preconditioned method
Examples of popular preconditioned iterative methods for linear systems include the preconditioned conjugate gradient method, the biconjugate gradient method, and generalized minimal residual method. Iterative methods, which use scalar products to compute the iterative parameters, require corresponding changes in the scalar product together with substituting for