Inexact Krylov Subspace Methods for Linear Systems

Abstract

There is a class of linear problems for which the computation of the matrix-vector
\nproduct is very expensive since a time consuming method is necessary to approximate it with
\nsome prescribed relative precision. In this paper we investigate the impact of approximately computed
\nmatrix-vector products on the convergence and attainable accuracy of several Krylov subspace
\nsolvers. We will argue that the sensitivity towards perturbations is mainly determined by the underlying
\nway the Krylov subspace is constructed and does not depend on the optimality properties of the
\nparticular method. The obtained insight is used to tune the precision of the matrix-vector product in
\nevery iteration step in such a way that an overall efficient process is obtained. Our analysis confirms
\nthe empirically found relaxation strategy of Bouras and Frayss´e for the GMRES method proposed
\nin [A Relaxation Strategy for Inexact Matrix-Vector Products for Krylov Methods, Technical Report
\nTR/PA/00/15, CERFACS, France, 2000]. Furthermore, we give an improved version of a strategy
\nfor the conjugate gradient method of Bouras, Frayss´e, and Giraud used in [A Relaxation Strategy for
\nInner-Outer Linear Solvers in Domain Decomposition Methods, Technical Report TR/PA/00/17,
\nCERFACS, France, 2000].