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