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

1. Subdivide the domain. The solution of the much smaller systems corre-
sponding to the partial domains serves as a preconditioning; cf. Widlund [1988].
2. Alter the boundary conditions to give a simpler problem. (For example, a
modification of the boundary conditions for the biharmonic equation leads to two
decoupled Laplace equations, see Braess and Peisker [1986].) The approximate
solution so obtained is then used for the preconditioning.
3. Use so-called hierarchical bases , i.e., choose basis functions consisting of
low and high frequency functions, respectively; see Yserentant [1986], Xu [1992],
or Bramble, Pasciak, and Xu [1990]. The condition number can be significantly
reduced by a suitable scaling of the different parts.

Preconditioning by SSOR

A simple but effective preconditioning can be obtained from the Gauss-Seidel
method, despite its slow convergence when it is used as stand-alone iteration. We
decompose the given symmetric matrix A as

A = D − L − L t ,

where L is a lower triangular matrix and D is a diagonal matrix. Then for 1 <
ω< 2,

x → (D − ωL) − 1 (ωb + ωL t x − (ω − 1 )Dx)

defines an iteration step in the forward direction; cf. (1.19). Similarly, the relaxation
in the backwards direction is defined by

x → (D − ωL t ) − 1 (ωb + ωLx − (ω − 1 )Dx).

Then the first half step gives

x 1 / 2 = ω(D − ωL) − 1 g k ,

where x = 0 and b = g k , and the second half step gives

− ω)(D − ωL t ) − 1 D(D − ωL) − 1 g k , h k = ω( 2

ωLx 1 / 2 Dx 1 / 2 C − 1 g k with C : since ωg k + −

ω) ] − 1 (D − ωL)D − 1 (D − ωL t ) . Clearly, the matrix C is symmetric and positive
definite.
We point out that multiplying the preconditioning matrix C by a positive
factor has no influence on the iteration. Thus, the factor ω( 2

− = 0. In particular, h k = = [ ω( 2

− ω) can be ignored

in the calculation.