2.4.4 Preconditioning

next up previous
Next: 2.4.5 Nonlinear Conjugate Gradient Up: 2.4 Gradient Methods Previous: 2.4.3 Conjugate Gradient

2.4.4 Preconditioning


Performance of the CG method is generally very sensitive to roundoff in the computations that may destroy the mutual conjugacy property. The method was actually neglected for many years until it was realized that a preconditioning technique can be used to accelerate convergence significantly [32][21][10].

Preconditioning involves modification of the target linear system through application of a positive-definite preconditioner that is closely related to . The modified system can be written as


Essentially, the new coefficient matrix is . Preconditioning aims to produce a more clustered eigenvalue structure for and/or lower condition number than for to improve the relevant convergence ratio. However, preconditioning also adds to the computational effort by requiring that a linear system involving (namely ) be solved at every step. Thus, it is essential for efficiency of the method that be factored very rapidly in relation to the original . This can be achieved, for example, if is a sparse component of the dense . Whereas the solution of an dense linear system requires order of operations, the work for sparse systems can be as low as order [32][11].

The recurrence relations for the PCG method can be derived for Algorithm 2.2 after substituting and . New search vectors can be used to derive the iteration process, and then the tilde modifiers dropped. The PCG method becomes the following iterative process.


Note above that the system must be solved repeatedly for and that the matrix/vector products are required as before.