Previous: Generalized Minimal Residual (GMRES)
Up: Generalized Minimal Residual (GMRES)
Next: Implementation
Previous Page: Generalized Minimal Residual (GMRES)
Next Page: Implementation

Theory

The Generalized Minimum Residual (GMRES) method is designed to solve nonsymmetric linear systems (see Saad and Schultz [185]). The most popular form of GMRES is based on the modified Gram-Schmidt procedure, and uses restarts to control storage requirements.

If no restarts are used, GMRES (like any orthogonalizing Krylov-subspace method) will converge in no more than n steps (assuming exact arithmetic). Of course this is of no practical value when n is large; moreover, the storage and computational requirements in the absence of restarts are prohibitive. Indeed, the crucial element for successful application of GMRES(m) revolves around the decision of when to restart; that is, the choice of m. Unfortunately, there exist examples for which the method stagnates and convergence takes place only at the nth step. For such systems, any choice of m less than n fails to converge.

Saad and Schultz [185] have proven several useful results. In particular, they show that if the coefficient matrix is real and nearly positive definite, then a ``reasonable'' value for m may be selected. Implications of the choice of m are discussed below.