Previous: Incomplete Factorization Preconditioners
Up: Incomplete Factorization Preconditioners
Next: Point incomplete factorizations
Previous Page: Incomplete Factorization Preconditioners
Next Page: Point incomplete factorizations

Creating an incomplete factorization

Incomplete factorizations are the first preconditioners we have encountered so far for which there is a non-trivial creation stage. Incomplete factorizations may break down (attempted division by zero pivot) or result in indefinite matrices (negative pivots) even if the full factorization of the same matrix is guaranteed to exist and yield a positive definite matrix.

An incomplete factorization is guaranteed to exist for many factorization strategies if the original matrix is an -matrix. This was originally proved by Meijerink and Van der Vorst [149]; see further Beauwens and Quenon [32], Manteuffel [144], and Van der Vorst [195].

In cases where pivots are zero or negative, strategies have been proposed such as substituting an arbitrary positive number (see Kershaw [132]), or restarting the factorization on for some positive value of (see Manteuffel [144]).

An important consideration for incomplete factorization preconditioners is the cost of the factorization process. Even if the incomplete factorization exists, the number of operations involved in creating it is at least as much as for solving a system with such a coefficient matrix, so the cost may equal that of one or more iterations of the iterative method. On parallel computers this problem is aggravated by the generally poor parallel efficiency of the factorization.

Such factorization costs can be amortized if the iterative method takes many iterations, or if the same preconditioner will be used for several linear systems, for instance in successive time steps or Newton iterations.