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

Experience shows that the quality of the preconditioning is not very sensitive
to the choice of the parameter ω . Calculation with the fixed value ω = 1 . 3 is only
slightly worse than using the corresponding optimal values, which in practice lie
between 1.2 and 1.6 [Axelsson and Barker 1984].
On the other hand, the numbering of the variables has a major influence on
the performance of the method. The differences are very evident for the equations
arising from five-point stencils on a rectangular mesh. We recommend that the
lexicographical ordering x 11 ,x 12 ,...,x 1 n ,x 21 ,x 22 ,...,x nn be used. The checker-
board ordering , where all variables x ij with i

j even appear first, followed by all
those with i + j odd (or conversely), reduces the efficiency of the SSOR precon-
ditioner dramatically. Thus it cannot be recommended. The disadvantages of this
numbering are so great that they cannot even be compensated by vectorization or
parallelization.

+

Preconditioning by ILU

Another preconditioning method can be developed from a variant of the Cholesky
decomposition. For symmetric matrices of the type which appear in the finite el-
ement method, the Cholesky decomposition A = LDL t or A = LL t leads to a
triangular matrix L which is significantly less sparse than A . Using an approximate
inverse leads to the so-called incomplete Cholesky decomposition (ICC) or incom-
plete LU decomposition (ILU) ; see Varga [1960]. In the simplest case, we simply
avoid calculation with all matrix elements which vanish in the given matrix. This
leads to a decomposition

LL t

A = + R ( 4 . 6 )

with an error matrix in which R ij = 0.

This preconditioning method is often faster than the one using SSOR relax-
ation. However, there does not seem to be a general rule for deciding in which
cases SSOR or ICC is more effective.
There are many variants of the method, and often filling in of elements in the
neighborhood of the diagonal is allowed. In the so-called modified incomplete de-
composition due to Meijerink and van Vorst [1977], instead of suppressing matrix
elements, they are moved onto the main diagonal.
Gustafsson [1978] developed a preconditioning method for the standard five-
point stencil for the Laplace equation. While in general there is only empirical
evidence for the improvement of the conditioning, in this case he proved that the
condition number is reduced from

0 only appears if A ij =

O (h − 1 ) .
It is crucial for the proof that the diagonal elements can be increased by a small
amount. Let ζ> 0. In view of Friedrichs' inequality, we can estimate the quadratic
forms a(u, u) =| u |

O (h − 2 ) to

2 2

1

2

1 and

| u | + ζ u

0 in terms of each other. The discretization