A Residual Replacement Strategy for Improving the Maximum Attainable Accuracy of s-step Krylov Subspace Methods

Krylov subspace methods are a popular class of iterative methods for solving linear
systems with large, sparse matrices. On modern computer architectures, both sequential and parallel
performance of classical Krylov methods is limited by costly data movement, or communication,
required to update the approximate solution in each iteration. These motivated communication-
avoiding Krylov methods, based on s-step formulations, reduce data movement by a factor of O(s)
by reordering the computations in classical Krylov methods to exploit locality. Studies on the finite
precision behavior of communication-avoiding Krylov methods in the literature have thus far been
empirical in nature; in this work, we provide the first quantitative analysis of the maximum attainable
accuracy of communication-avoiding Krylov subspace methods in finite precision. Following the
analysis for classical Krylov methods, we derive a bound on the deviation of the true and updated
residuals in communication-avoiding conjugate gradient and communication-avoiding biconjugate
gradient in finite precision. Furthermore, an estimate for this bound can be iteratively updated
within the method without asymptotically increasing communication or computation. Our bound
enables an implicit residual replacement strategy for maintaining agreement between residuals to
within O(epsilon)*norm(A)*norm(x). Numerical experiments on a small set of test matrices verify
that, for cases where the updated residual converges, the residual replacement strategy can enable accuracy of O(epsilon)*norm(A)*norm(x) with a small number of residual replacement steps,
reflecting improvements of up to seven orders of magnitude.


Publication Date: January 2014
Conference: SIAM J. Matrix Anal. Appl., v. 35, n. 1, pp 22-43, 21