Inexact matrix-vector products in Krylov methods for solving linear systems:: A relaxation strategy

Embedded iterative linear solvers are being used more and more often in linear algebra. An important issue is how to tune the level of accuracy of the inner solver to guarantee the convergence of the outer solver at the best global cost. As a first step towards the challenging goal of controlling embedded linear solvers, inexact Krylov methods are used as a model of inner-outer iterations with external Krylov scheme. This paper experimentally shows that Krylov methods for solving linear systems can still perform very well in the presence of carefully monitored inexact matrix-vector products. This surprising behavior of inexact Krylov methods, as opposed to Newton-like methods, is investigated in detail, and potentially important applications are mentioned. A new relaxation strategy for the inner accuracy is proposed for Krylov methods with inexact matrix-vector products; its efficiency is supported by a wide range of numerical experiments on different algorithms and contrasted against other potential approaches.