The Generalized Minimum Residual (GMRES) method is designed to solve nonsymmetric linear systems (see Saad and Schultz ). 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  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.