ETNA Volume 37, pp. 202-213, 2010. Copyright.pdfVIP

Electronic Transactions on Numerical Analysis. ETNA Volume 37, pp. 202-213, 2010. Kent State University Copyright  2010, Kent State University. ISSN 1068-9613. ON A NON-STAGNATION CONDITION FOR GMRES AND APPLICATION TO SADDLE POINT MATRICES∗ VALERIA SIMONCINI† Abstract. In Simoncini and Szyld [Numer. Math., 109 (2008), pp. 477–487] a new non-stagnation condition for the convergence of GMRES on indefinite problems was proposed. In this paper we derive an enhanced strategy leading to a more general non-stagnation condition. Moreover, we show that the analysis also provides a good setting to derive asymptotic convergence rate estimates for indefinite problems. The analysis is then explored in the context of saddle point matrices, when these are preconditioned in a way so as to lead to nonsymmetric and indefinite systems. Our results indicate that these matrices may represent an insightful training set towards the understanding of the interaction between indefiniteness and stagnation. Key words. saddle point matrices, large linear systems, GMRES, stagnation. AMS subject classifications. 65F10, 65N22, 65F50. 1. Introduction. A real n × n matrix A is said to be positive definite (or positive real) if x⊤Ax 0 for any real nonzero vector x of length n, where x⊤ is the transpose of x. A similar definition holds for negative definite matrices. Large nonnormal real linear systems of the form Ax = b are known to be particularly difficult to solve by iterative Krylov subspace methods whenever A is not definite, that is when the quantity x⊤Ax changes sign depending on x; in fact, full stagnation is possible for as many as n − 1 iterations [ 1, 20].