**Previous:** Creating an incomplete factorization

**Up:** Incomplete Factorization Preconditioners

**Next:** Block factorization methods

**Previous Page:** Creating an incomplete factorization

**Next Page:** Special cases: central differences

The most common type of incomplete factorization is based on taking a set of matrix positions, and keeping all positions outside this set equal to zero during the factorization. The resulting factorization is incomplete in the sense that fill is supressed.

The set is usually chosen to encompass all positions for
which . A position that is zero in but not so in an
exact factorization is called a * fill* position, and if it is
outside , the fill there is said to be ``discarded''.
Often, is chosen to coincide with the set of nonzero positions
in , discarding all fill. This factorization type is called
the factorization: the Incomplete factorization of
degree zero.

We can describe an incomplete factorization formally as

Meijerink and Van der Vorst [149] proved that, if is an -matrix, such a factorization exists for any choice of , and gives a symmetric positive definite matrix if is symmetric positive definite. Guidelines for allowing levels of fill were given by Meijerink and Van der Vorst in [150].

For the method, the incomplete factorization never alters the nonzero elements of the original matrix, so that we have the following situation. If the coefficient matrix is split into its diagonal, lower triangular, and upper triangular parts as , the preconditioner can be written as where is the diagonal matrix containing the pivots generated.

Remark: the resulting and factors of the preconditioner have only nonzero elements in the set , but this fact is in general not true for the preconditioner itself.

The fact that the preconditioner contains the off-diagonal parts of the original matrix was used by Eisenstat [87] to derive at a more efficient implementation of preconditioned CG. This new implementation merges the application of the tridiagonal factors of the matrix and the preconditioner, thereby saving a substantial number of operations per iteration.