New conditions for non-stagnation of minimal residual methods

In the solution of large linear systems, a condition guaranteeing that a minimal residual Krylov subspace method makes some progress, i.e., that it does not stagnate, is that the symmetric part of the coefficient matrix be positive definite. This condition results in a well-established worst-case bound for the convergence rate of the iterative method, due to Elman. This bound has been extensively used, e.g., when the linear system comes from discretized partial differential equations, to show that the convergence of GMRES is independent of the underlying mesh size. In this paper we introduce more general non-stagnation conditions, which do not require the symmetric part of the coefficient matrix to be positive definite, and that guarantee, for example, the non-stagnation of restarted GMRES for certain values of the restarting parameter. Work on this paper was supported in part by the U.S. Department of Energy under grant DE-FG02-05ER25672.