{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T11:57:47Z","timestamp":1791287867840,"version":"4.3.0"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/120893057","type":"journal-article","created":{"date-parts":[[2014,1,21]],"date-time":"2014-01-21T11:13:38Z","timestamp":1390302818000},"page":"22-43","source":"Crossref","is-referenced-by-count":31,"title":["A Residual Replacement Strategy for Improving the Maximum Attainable Accuracy of $s$-Step Krylov Subspace Methods"],"prefix":"10.1137","volume":"35","author":[{"given":"Erin","family":"Carson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,1,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1994-1201066-7"},{"key":"atypb2","unstructured":"Z. Bai, D. Day, J. Demmel, and J. Dongarra,\n                      A test matrix collection for non-hermitian eigenvalue problems\n                      , Technical Report CS-97-355, Department of CS, University of Tennessee, Knoxville, TN, 1997."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/14.4.563"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/120881191"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90062-8"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90045-9"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(96)00022-1"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"atypb9","unstructured":"J. Demmel, M. Hoemmen, M. Mohiyuddin, and K. Yelick,\n                      Avoiding Communication in Computing Krylov Subspaces\n                      , Technical Report UCB\/EECS-2007-123, EECS Department, U.C. Berkeley, Berkeley, CA, 2007."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676393"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895284944"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897331862"},{"key":"atypb13","unstructured":"A. Hindmarsh and H. Walker,\n                      Note on a Householder Implementation of the GMRES Method\n                      , Technical Report UCID-20899, Lawrence Livermore National Laboratory, Livermore, CA, 1986."},{"key":"atypb14","unstructured":"M. Hoemmen,\n                      Communication-avoiding Krylov Subspace Methods\n                      , Ph.D. thesis, EECS Deppartment, U.C. Berkeley, Berkeley, CA, 2010."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1080\/00207169208804107"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1473"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"G. Meurant,\n                      The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations\n                      , SIAM, Philadelphia, 2006.","DOI":"10.1137\/1.9780898718140"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1017\/S096249290626001X"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. Mohiyuddin, M. Hoemmen, J. Demmel, and K. Yelick,\n                      Minimizing communication in sparse matrix solvers\n                      , in Proc. ACM\/IEEE Conference on Supercomputing, 2009.","DOI":"10.1145\/1654059.1654096"},{"key":"atypb20","unstructured":"A. Neumaier,\n                      Iterative regularization for large-scale ill-conditioned linear systems\n                      , Oral presentation, Numerical Linear Algebra Meeting, Oberwolfach, 1994."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/050630416"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2010.12.009"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02309342"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00057-7"},{"key":"atypb26","unstructured":"S. Toledo,\n                      Quantitative Performance Modeling of Scientific Computations and Creating Locality in Numerical Algorithms\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1995."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-99-01171-0"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599353865"},{"key":"atypb29","unstructured":"J. Van Rosendale,\n                      Minimizing Inner Product Data Dependencies in Conjugate Gradient Iteration\n                      , Technical Report 172178, ICASE-NASA, Hampton, VA, 1983."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/0909010"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120893057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:23:02Z","timestamp":1787332982000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120893057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120893057"],"URL":"https:\/\/doi.org\/10.1137\/120893057","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}