Preconditioner
From Wikipedia, the free encyclopedia
In linear algebra and numerical analysis, a preconditioner P of a matrix A is a matrix such that P−1A has a smaller condition number than A. A preconditioner as defined here is also known as a left preconditioner; there are also right preconditioners, but they are not discussed in this article.
Preconditioners are useful when using an iterative method to solve a large, sparse linear system
for x. Solving the preconditioned system
is equivalent to solving the original system. However, the preconditioned system has a smaller condition number; it is better conditioned. The number of iterations used to solve the system increases with the condition number so by reducing the number of needed iterations (if the cost — computing time — of applying P-1 is small), a gain in efficiency is achieved.
The matrix P−1A is almost never explicitly formed. In using an iterative method, only the action of applying P−1 to a given vector need be computed.
The desired effect in a applying a preconditioner is to make the quadratic form of P − 1A be nearly spherical[1]
Contents |
[edit] Examples
[edit] Jacobi preconditioner
The Jacobi preconditioner is the diagonal of the matrix. That is,
and so
[edit] SSOR
The SSOR (Symmetric Successive Over Relaxation) preconditioner factors A as follows:
- A = L + D + LT
where L is the lower part of A and D the diagonal part of A. SSOR then takes P to be
where ω is a "relaxation parameter" between 0 and 2, exclusive.
[edit] See also
[edit] External links
- Preconditioned Conjugate Gradient – math-linux.com
- An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.
