Use of the conjugate gradient method

The system of linear equations produced by the FE method can be solved either by direct or iterative methods. The aim in both cases is to avoid explicitly constructing the full Galerkin matrix. For machines with vector and/or low level parallel architectures, direct methods can be useful. The most popular are frontal or multi-frontal methods (Duff et al., 1986). These direct methods do not map well onto a massively parallel architecture. In contrast, iterative methods can be implemented efficiently on a massively parallel architecture. The most popular iterative method is the conjugate gradient (CG) algorithm. The Galerkin matrix is a real, symmetric, positive definite operator. For this type of operator the CG method has guaranteed convergence. The CG algorithm does not require construction of the global matrix. The main operations in the CG algorithm are calculation of the result of applying the operator to a vector and calculation of the dot product of two vectors.

The standard CG method to calculate a sequence of iterates ${x^0,x^1,\cdots}$ with $Ax^i \rightarrow b$ as $i \rightarrow \infty$ is given by setting $p^0 = b-Ax^0 \equiv r^0$, and then for $i=0,1,2,\cdots$

$$\begin{eqnarray} \alpha_k & = & ( r^k,r^k) / (p^k,Ap^k) \nonumber \\ x^{k+1} &... ...k,r^k) \nonumber \\ p^{k+1} & = & r^{k+1} + \beta_k p^k \nonumber \end{eqnarray}$$ (1)

(.,.) is the L² inner product.

This method is clearly suitable for solution of the unassembled Galerkin system. The calculation of Ap_k, which is performed once per iteration, can be done using the method outlined in the previous section. The only global operations in the algorithm are the calculation of the two inner products,(p^k,Ap^k) and (r^k+1,r^k+1).