Previous: Special cases: central differences
Up: Point incomplete factorizations
Next: Parallelism aspects
Previous Page: Special cases: central differences
Next Page: Parallelism aspects

Modified incomplete factorizations

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].