Iterative linear system solvers with approximate matrix-vector products

There are classes of linear problems for which a matrix-vector product is a time consuming operation because an expensive approximation method is required to compute it to a given accuracy. One important example is simulations in lattice QCD with Neuberger fermions where a matrix multiply requires the product of the matrix sign function of a large sparse matrix times a vector. The recent interest in these type of applications has resulted in research efforts to study the effect of errors in the matrix-vector products on iterative linear system solvers. In this paper we give a very general and abstract discussion of this issue and try to provide insight into why some iterative system solvers are more sensitive than others. Preprint 1293, Dep. Math., University Utrecht (December, 2003). In QCD and Numerical Analysis III, the Proceedings of the Third International Workshop on Numerical Analysis and Lattice QCD, Edinburgh, June/July 2003, Lecture Notes in Computational Science and Engineering, A. Borici, A. Frommer, B. Joo, A.D. Kennedy, and B. Pendleton (Eds), Lecture Notes in Computational Science and Engineering, Vol. 47, 2005, pp. 133-141. Springer-Verlag, Heidelberg, German