Previous: Special cases: central differences
Up: Point incomplete factorizations
Next: Parallelism aspects
Previous Page: Special cases: central differences
Next Page: Parallelism aspects
One modification to the basic idea of incomplete factorizations is as
follows:
If the product
is nonzero, and fill is not allowed in position
,
instead of simply discarding this fill quantity subtract it from
diagonal element
.
Mathematically this corresponds to forcing the preconditioner to have the same rowsums as the original matrix; in applications of computational fluid mechanics this idea is justified with the argument that the preconditioner does not introduce any artificial diffusion into the system; see Appleyard and Cheshire [4] and Dupont, Kendall and Rachford [78] for early applications of this idea.
Such a factorization scheme is usually called a ``modified incomplete factorization''. In this case there is a danger of breakdown, especially when the variables are numbered other than in the natural row-by-row ordering. This was noted by Chan and Kuo [49], and a full analysis was given by Eijkhout [83] and Notay [157].
One reason for considering modified incomplete factorizations is the
behavior of the spectral condition number of the preconditioned
system. It was mentioned above that the condition number of the
coefficient matrix is as a function of the discretization
mesh width. This order of magnitude is preserved by simple incomplete
factorizations, although usually a reduction by a large constant
factor is obtained.
Modified factorizations are of interest because, in
combination with small perturbations, the spectral condition number of
the preconditioned system can be of a lower order.
It was first proved by Dupont, Kendall and
Rachford [78] that
a modified incomplete factorization of gives
for the central difference case. More
general proofs are given by Gustafsson [111],
Axelsson and Barker ([14], and
Beauwens [31][30],7.2).
A slight variant of modified incomplete factorizations consists of the
class of ``relaxed incomplete factorizations''. Here the fill is
multiplied by a parameter before it is subtracted from
the diagonal; see
Ashcraft and Grimes [11],
Axelsson and Lindskog [19][18],
Chan [43],
Eijkhout [83],
Notay [158],
Stone [190], and
Van der Vorst [199].
For the dangers of MILU in the presence of rounding error, see
Van der Vorst [201].