Preconditioner: Information from Answers.com

"Preconditioning" redirects here. For other uses, see Preconditioning (disambiguation).

In linear algebra and numerical analysis, a preconditioner P of a matrix A is a matrix such that P⁻¹A has a smaller condition number than A. Preconditioners are useful when using an iterative method to solve a large, sparse linear system

$Ax = b\,$

for x since the rate of convergence for most iterative linear solvers degrades as the condition number of a matrix increases. Instead of solving the original linear system above, one may solve either the left preconditioned system

$P^{-1}Ax = P^{-1}b,\,$

via the two solves

$c=P^{-1}b, \qquad (P^{-1}A)x=c,\,$

or the right preconditioned system

$AP^{-1}Px = b,\,$

via the two solves

$(AP^{-1})y=b, \qquad x=P^{-1}y,\,$

which are both equivalent to solving the original system so long as the preconditioner matrix P is nonsingular.

The goal of this preconditioned system is to reduce the condition number of the left or right preconditioned system matrix

$P^{-1}A,\,$

$AP^{-1},\,$

respectively.

Typically there is a trade-off in the choice of P. Since the operator P^-1 must be applied at each step of the iterative linear solver, it should be very efficient in order to reduce the cost (computing time) of applying the P^-1 operation. The most efficient preconditioner would therefore be

$P=I, \quad\text{since then}\quad P^{-1}=I;\,$

unfortunately this results in the original linear system and the preconditioner does nothing. At the other limit, if one could choose

$P=A, \quad\text{since then}\quad P^{-1}A = AP^{-1} = I,\,$

which has optimal condition number of 1, requiring a single iteration for convergence; however in this case

$P^{-1}=A^{-1},\,$

and the preconditioner solve is as difficult as solving the original system. One therefore chooses the matrix P as somewhere between these two extremes, in an attempt to achieve a minimal number of linear iterations while keeping the operator P^-1 as simple as possible. Some examples of typical preconditioning approaches are detailed below.

We note that in the above discussion, the preconditioned matrix

$P^{-1}A,\quad\text{resp.}\quad AP^{-1}\,$

is almost never explicitly formed. In using an iterative method, only the action of applying the preconditioner solve operation P^-1 to a given vector need be computed.

It may also be noted that for symmetric matrices A, the desired effect in applying a preconditioner is to make the quadratic form of the preconditioned operator $P - 1 A$ to be nearly spherical[1]

1 Examples
- 1.1 Jacobi preconditioner
- 1.2 SOR
2 See also
3 External links

Examples

Two popular preconditioning strategies are based on splitting A into the three components

$A = L + D + U\,$

where L is the lower triangular part of A, D is the diagonal part of A, and U is the upper triangular part of A.

Jacobi preconditioner

The Jacobi preconditioner is one of the simplest forms of preconditioning, in which the preconditioner is chosen to be the diagonal of the matrix only,

$P = D.\,$