next up previous

9.3 Parallelism and Data Locality in GMRES

GMRES, proposed by Saad and Schultz [107], is a CG-like method for solving general nonsingular linear systems Ax=b. GMRES minimizes the residual over the Krylov subspace , with . This requires, as with CG, the construction of an orthogonal basis of this space. Since we do not require A to be symmetric, we need long recurrences: each new vector must be explicitly orthogonalized against all previously generated basis vectors. In its most common form GMRES orthogonalizes using Modified Gram--Schmidt [4]. In order to limit memory requirements (since all basis vectors must be stored), GMRES is restarted after each cycle of m iteration steps; this is called GMRES. A slightly simplified version of GMRES with preconditioning K is as follows (for details, see [108]):