The Conjugate Gradient Method - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 186

Chapter IV
The Conjugate Gradient Method
The discretization of boundary-value problems leads to very large systems of equa-
tions which often involve several thousand unknowns. The systems are particularly
large for three-dimensional problems and for problems of higher order. Often the
bandwidth of the matrices is so large that the classical Gauss elimination algorithm
and its modern variants are not efficient methods. This suggests that even for linear
problems, we should use iterative methods.
Iterative methods first became popular at the end of the fifties, primarily as
a means for solving large problems using computers with a small memory. The
methods developed then are no longer competitive, but they still provide useful
ingredients for modern iterative methods, and so we review them in §1. The bulk
of this chapter is devoted to the conjugate gradient method which is particularly
useful for the solution of variational problems and saddle point problems. Since
the CG methods discussed here can be applied to a broad spectrum of problems,
they are competitive with the still faster multigrid methods to be discussed later
(whose implementation is generally more complicated and requires more individ-
ual programming).
We begin by classifying problems according to the number n of unknowns:
1. Small problems : For linear problems we can use a direct method. For nonlinear
problems (e.g., using the Newton method), all elements of the Jacobi matrices
should be computed (at least approximately).
2. Midsized problems : If the matrices are sparse, we should make use of this
fact. For nonlinear problems (e.g., for quasi-Newton methods), the Jacobi
matrices should be approximated. Iterative methods can still be used even
when the number of steps in the iteration exceeds n .
3. Very large problems : Here the only choice is to use iterative methods which
require fewer than n steps to compute a solution.
For very large problems, we have to deal with completely different aspects
of the method of conjugate gradients as compared with midsized problems. For
example, the fact that in exact arithmetic CG methods produce a solution in n
steps plays no role for very large problems. In this case it is more important that
the accuracy of the approximate solution depends on the condition number of the
matrix.