Previous: Preconditioning by the symmetric part
Up: Preconditioners from properties of the
differential equation
Next: Alternating Direction Implicit methods
Previous Page: Preconditioning by the symmetric part
Next Page: Alternating Direction Implicit methods
In many applications, the coefficient matrix is symmetric and positive
definite. The reason for this is usually that the partial differential
operator from which it is derived is self-adjoint, coercive, and bounded
(see Axelsson and Barker [14], 3.2).
It follows that for the coefficient
matrix the following relation holds for any matrix
from a
similar differential equation:
where ,
do not depend on the matrix size. The importance of
this is that the use of
as a preconditioner gives an iterative
method with a number of iterations that does not depend on the matrix size.
Thus we can precondition our original matrix by one derived from a different PDE, if one can be found that has attractive properties as preconditioner. One choice would be to take a matrix from a separable PDE. A system involving such a matrix can be solved with various so-called ``fast solvers'', such as FFT methods, cyclic reduction, or the generalized marching algorithm (see Dorr [72], Swarztrauber [191], Bank [24] and Bank and Rose [27]). For instance, if the original matrix arises from
then the preconditioner can be formed from
An extension to the non-self adjoint case is considered by Elman and Schultz [90].
Fast solvers are attractive in that the number of operations they
require is (slightly higher than) of the order of the number of
variables. Coupled with the fact that the number of iterations in the
resulting preconditioned iterative methods is independent of the
matrix size, such methods are close to optimal. However, fast solvers
are usually only applicable if the physical domain is a rectangle or
other Cartesian product structure. (For a domain consisting of a
number of such pieces, domain decomposition methods can be used;
see §).