In this section we discuss parallel aspects of iterative methods for solving large linear systems. For a good mathematical introduction to a class of successful and popular methods, the so-called Krylov subspace methods, see [79]. There are many such methods and new ones are frequently proposed. Fortunately, they share enough properties that to understand how to implement them in parallel it suffices to examine carefully just a few.
For the purposes of parallel implementation there are two classes
of methods: those with short recurrences, i.e. methods that
maintain only a very limited number of search direction vectors, and those
with long recurrences.
The first class includes
CG (Conjugate Gradients), CR (Conjugate Residuals), Bi-CG, CGS (CG squared),
QMR (Quasi Minimum Residual),
GMRES
for small m (Generalized Minimum
Residual),
truncated ORTHOMIN (Orthogonal Minimum Residual), Chebychev iteration,
and so on.
We could further distinguish between methods with fixed iteration parameters
and methods with dynamical parameters, but we will not do so; the
effects of this aspect will be clear from our discussion.
As the archetype for this class we will consider CG;
the parallel implementation issues for this method apply to most
other short recurrence methods.
The second class of methods includes
GMRES, GMRES(m) with larger m, ORTHOMIN,
ORTHODIR (Orthogonal Directions), ORTHORES (Orthogonal Residuals),
and EN (Eirola--Nevanlinna's Rank-1 update method).
We consider GMRES in detail, which is a popular method in this class.
This section is organized as follows. In Section 9.1 we will discuss the parallel aspects of important computational kernels in iterative schemes. From the discussions it should be clear how to combine coarse-grained and fine-grained approaches, for example when implementing a method on a parallel machine with vector processors. The implementation for such machines, in particular those with shared memory, is given much attention in [8]. In Section 9.2, coarse-grained parallel and data-locality issues of CG will be discussed, while in Section 9.3 the same will be done for GMRES.
