Theory



next up previous contents index
Next: Implementation Up: Generalized Minimal Residual Previous: Generalized Minimal Residual

Theory

 

The Generalized Minimum Residual (GMRES) method is designed to solve nonsymmetric linear systems (see Saad and Schultz [189]). 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 steps (assuming exact arithmetic). Of course this is of no practical value when is large; moreover, the storage and computational requirements in the absence of restarts are prohibitive. Indeed, the crucial element for successful application of GMRES() revolves around the decision of when to restart; that is, the choice of . Unfortunately, there exist examples for which the method stagnates  and convergence takes place only at the th step. For such systems, any choice of less than fails to converge.

Saad and Schultz [189] 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 may be selected. Implications of the choice of are discussed below.



Jack Dongarra
Mon Nov 20 08:52:54 EST 1995