INEXACT KRYLOV SUBSPACE METHODS FOR LINEAR SYSTEMS ∗

Abstract. There is a class of linear problems for which the computation of the matrix-vector product is very expensive since a time consuming approximation method is necessary to compute it with some prescribed relative precision. In this paper we investigate the impact of approximately computed matrix-vector products on the convergence and attainable accuracy of several Krylov subspace solvers. We will argue that the success of a relaxation strategy depends on the underlying way the Krylov subspace is constructed and not on the optimality properties of the particular method. The obtained insight is used to tune the precision of the matrix-vector product in every iteration step in such a way that an overall efficient process is obtained. Our analysis confirms the empirically found relaxation strategy of Bouras and Frayssé for the GMRES method proposed in [2]. Furthermore, we give an improved version of a strategy of Bouras, Frayssé, and Giraud [3] for the Conjugate Gradient method. 1. Introduction. Ther