A Residual Replacement Strategy for Improving the Maximum Attainable Accuracy of $s$-Step Krylov Subspace Methods
Authors:
- Erin CarsonECErin Carson
- James DemmelJDJames Demmel
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 35 (1) , 22-43
Abstract
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)\Vert A \Vert\Vert x\Vert$. 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)\Vert A\Vert\Vert x\Vert$ with a small number of residual replacement steps, reflecting improvements of up to seven orders of magnitude.
Keywords
This publication has 23 references indexed in Scilit:
- Avoiding Communication in Nonsymmetric Lanczos-Based Krylov Subspace MethodsSIAM Journal on Scientific Computing, 2013
- Accuracy of Two Three-term and Three Two-term Recurrences for Krylov Space SolversSIAM Journal on Matrix Analysis and Applications, 2000
- Estimating the Attainable Accuracy of Recursively Computed Residual MethodsSIAM Journal on Matrix Analysis and Applications, 1997
- Parallel iterative S-step methods for unsymmetric linear systemsParallel Computing, 1996
- A Newton basis GMRES implementationIMA Journal of Numerical Analysis, 1994
- Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problemMathematics of Computation, 1994
- Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: TheoryInternational Journal of Computer Mathematics, 1992
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchyParallel Computing, 1989
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989
- On the Impact of Communication Complexity on the Design of Parallel Numerical AlgorithmsIEEE Transactions on Computers, 1984