Verify
For the moment, assume we have a positive definite left preconditioner matrix
has a Cholesky decomposition
T
We will use this decomposition to obtain an equivalent system
where
is positive definite so the
method applies.
System 21.15 is equivalent to the original system
The fact that
is symmetric is left to the exercises. Note that
−1
only if
Thus,
is positive definite because
Use the
method to solve
After obtaining
find
by solving
The incomplete Cholesky decomposition is frequently used for preconditioning the
method. As stated in the introduction, iterative methods are applied primarily to large, sparse systems. However, the Cholesky factor
used in system
is usually less sparse than
shows the distribution of nonzero entries in a
positive definite sparse matrix, POWERMAT.mat, used in a power network problem, and
shows the distribution in its Cholesky factor. Note the significant loss of zeros in the Cholesky factor.
The incomplete Cholesky decomposition is a modification of the original Cholesky algorithm. If an element
ij
off the diagonal of
is zero, the corresponding element
ij
is set to zero. The factor returned,
has the same distribution of nonzeros as
above the diagonal. Form
T
from a modified Cholesky factor of
with the hope that the condition number of
−1
is considerably smaller than that of
The function icholesky in the software distribution implements it with the calling sequence R = icholesky(A). Implementation involves replacing the body of the inner for loop with
We can directly apply
to system
by implementing the following statements.
Initialize
Upon completion, solve the upper triangular system
However, this is not an efficient implementation. Improvement can be made by determining relationships between the transformed variables and the original ones.
We can express the residual,
i
in terms of the original residual,
i
by
Make a change of variable by letting
i
i
This leads to
By applying Equations 21.16 and 21.17, it follows that (Problem 21.11):
Applying the identities to the
algorithm for the computation of
gives the preconditioned
algorithm 21.3. Note that the algorithm requires the computation of the incomplete Cholesky factor
and then the solution of systems
i
which can be done using the incomplete Cholesky factor (Section 13.3.3). It is never necessary to compute
or
−1