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

Point incomplete factorizations

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.



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