next up previous

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 [10,21,32].

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 n [11,32].