Previous: Wavefronts in the Gauss-Seidel and Conjugate Gradient methods
Up: Parallelism
Previous Page: Wavefronts in the Gauss-Seidel and Conjugate Gradient methods
Next Page: Remaining topics

Blocked operations in the GMRES method

In addition to the usual matrix-vector product, inner products and vector updates, the preconditioned GMRES method (see §) has a kernel where one new vector, , is orthogonalized against the previously built orthogonal set {, ,..., }. In our version, this is done using Level 1 BLAS, which may be quite inefficient. To incorporate Level 2 BLAS we can apply either Householder orthogonalization or classical Gram-Schmidt twice (which mitigates classical Gram-Schmidt's potential instability; see Saad [179]). Both approaches significantly increase the computational work, but using classical Gram-Schmidt has the advantage that all inner products can be performed simultaneously; that is, their communication can be packaged. This may increase the efficiency of the computation significantly.

Another way to obtain more parallelism and data locality is to generate a basis {, , ..., } for the Krylov subspace first, and to orthogonalize this set afterwards; this is called m-step GMRES(m) (see Kim and Chronopoulos [137]). (Compare this to the GMRES method in §, where each new vector is immediately orthogonalized to all previous vectors.) This approach does not increase the computational work and, in contrast to CG, the numerical instability due to generating a possibly near-dependent set is not necessarily a drawback.