To use CG to solve Ax=b, A must be symmetric and positive definite. In other short recurrence methods, other properties of A may be required or desirable, but we will not exploit these properties explicitly here.
Most often, CG is used
in combination with some kind of preconditioning
[79,4,97].
This means that the matrix
A is implicitly multiplied by an approximation
of 
. Usually, K is constructed to be an approximation of
A,
and so that Ky=z is easier to solve than Ax=b. Unfortunately, a
popular class of preconditioners, those based on incomplete factorizations of
A,
are hard to parallelize. We have
discussed some efforts to obtain more parallelism in the preconditioner
in Section 9.1.
Here we will assume the preconditioner is chosen
such that the time to solve Ky=z in parallel is comparable with the time
to compute Ap.
For CG we also require that the preconditioner K be symmetric positive
definite. We exploit this to implement the preconditioner more
efficiently.
The preconditioned CG algorithm is as follows.
If A or K is not very sparse, most work is done in multiplying
or solving 
, and this is where
parallelism is most beneficial. It is also completely dependent on
the structures of A and K.
