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

Indefinite and Unsymmetric Matrices

We now turn to indefinite problems. First, we recall that an indefinite system
Ax = b cannot be converted into a system A 2 x = Ab with positive definite matrix
simply by multiplication by A . Indeed, since κ(A 2 ) = [ κ(A) ] 2 , the condition

number increases significantly under the transformation. This raises the question of
whether we can avoid this shortcoming by applying the minimal residual method.
This is in fact the case for problems with only a few negative eigenvalues,
and also for unsymmetric spectra. However, if the spectrum is symmetric w.r.t.
zero, then unfortunately we are faced with the same effect as squaring the matrix.

3.8 Example. Suppose we double the system Ay = b ,
A y

z

b
− b

,

=

− A

where A is positive definite. Let y 0 = z 0 . Then the residual has the form (h 0 , − h 0 ) .
Since the expression

2 2

A(y 0 + αh 0 ) − b +− A(z 0 − αh 0 ) + b assumes its

minimum at α = 0, it follows that y 1 = y 0 = z 1 = z 0 . This shows that in general,

we get an improvement only for an even number of steps, and the minimum
for x 0 + span[ Ag 0 ,A 3 g 0 ,A 5 g 0 ,... ] will be computed. Unfortunately, this again

corresponds to the calculation with the squared matrix.

Since in contrast to 3.5(2), here the gradients g 1 ,g 2 ,g 3 ,... are not linearly
independent, the formal extension of the minimal residual algorithm breaks down.
More importantly, as we shall see later in Remark 4.3, for minimal residuals, the
preconditioning generally can no longer be built into a three-term recurrence.
To treat problems with indefinite or unsymmetric matrices, we need to make
modifications; cf. Paige and Saunders [1975], Stoer [1983], Golub and van Loan
[1983]. They are still relatively simple for symmetric indefinite matrices. The
Cholesky decomposition hidden in the CG method is replaced by a QR decompo-
sition; cf. Paige and Saunders [1975]. Otherwise, we have to distinguish between
an incomplete minimization and a very short recurrence with stabilization. QM-
RES and its variants belong to the first group; see Saad and Schultz [1985] and
Saad [1993]. It generates directions which are conjugate only to the last few dif-
ference vectors. The other methods use two systems of biorthogonal vectors; see
van der Vorst [1992]. In order to avoid degeneracies as in Example 3.8, several
steps are carried out together. This is called the “look ahead strategy”; cf. Fre-
und, Gutknecht, and Nachtigal [1993]. Various studies have shown that no optimal
algorithm exists for indefinite and unsymmetric problems.
Because of this phenomenon, completely different methods based on the
Uzawa algorithm have been developed for the class of indefinite problems involv-
ing saddle point problems. They are described in §5 below.