{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T22:10:48Z","timestamp":1792015848483,"version":"4.4.0"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100014600","name":"MathWorks","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100014600","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["267526"],"award-info":[{"award-number":["267526"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/I01912X\/1"],"award-info":[{"award-number":["EP\/I01912X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P020720\/1"],"award-info":[{"award-number":["EP\/P020720\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Iterative refinement is a long-standing technique for improving the accuracy of a computed solution to a nonsingular linear system $Ax = b$ obtained via LU factorization. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix $A$ has condition number safely less than the reciprocal of the unit roundoff, $u$. We identify a mechanism that allows iterative refinement to produce solutions with normwise relative error of order $u$ to systems with condition numbers of order $u^{-1}$ or larger, provided that the update equation is solved with a relative error sufficiently less than 1. A new rounding error analysis is given, and its implications are analyzed. Building on the analysis, we develop a GMRES (generalized minimal residual)-based iterative refinement method (GMRES-IR) that makes use of the computed LU factors as preconditioners. GMRES-IR exploits the fact that even if $A$ is extremely ill conditioned the LU factors contain enough information that preconditioning can greatly reduce the condition number of $A$. Our rounding error analysis and numerical experiments show that GMRES-IR can succeed where standard refinement fails, and that it can provide accurate solutions to systems with condition numbers of order $u^{-1}$ and greater. Indeed, in our experiments with such matrices---both random and from the University of Florida Sparse Matrix Collection---GMRES-IR yields a normwise relative error of order $u$ in at most three steps in every case.<\/jats:p>","DOI":"10.1137\/17m1122918","type":"journal-article","created":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T11:55:15Z","timestamp":1512561315000},"page":"A2834-A2856","source":"Crossref","is-referenced-by-count":116,"title":["A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems"],"prefix":"10.1137","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9469-7467","authenticated-orcid":true,"given":"Erin","family":"Carson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5956-4976","authenticated-orcid":true,"given":"Nicholas J.","family":"Higham","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,12,6]]},"reference":[{"key":"atypb2","first-page":"31","volume":"33","author":"Arioli M.","year":"2009","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/060661545"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01731978"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.3390\/math3020337"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-015-0547-z"},{"key":"atypb7","volume-title":"MIMS EPrint","author":"Carson E.","year":"2017"},{"key":"atypb9","first-page":"1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"ACM Trans. Math. Software"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1141885.1141894"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01732607"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992202"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/050629598"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/nag.1012"},{"key":"atypb15","first-page":"1737","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, JMLR: Workshop and Conference Proceedings 37","author":"Gupta S.","year":"2015"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008153532043"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/17.4.495"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/1731022.1731027"},{"key":"atypb20","volume-title":"IEEE Computer Society","author":"Floating-Point Arithmetic IEEE","year":"2008"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.14495\/jsiaml.7.1"},{"key":"atypb22","first-page":"374","volume":"7","author":"Kobayashi Y.","year":"2016","journal-title":"IEICE"},{"key":"atypb23","first-page":"1","volume-title":"Proceedings of the 1998 ACM\/IEEE Conference on Supercomputing, IEEE Computer Society","author":"Li X. S.","year":"1998"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-17689-5_9"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1038\/srep40863"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/090754376"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/BF03186544"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/050630416"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2013.0391"},{"key":"atypb30","unstructured":"S. M. Rump,\n                      Approximate Inverses of Almost Singular Matrices Still Contain Useful Information\n                      , Technical Report 90.1, Hamburg University of Technology, 1990,https:\/\/doi.org\/10.15480\/882.319."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF03186534"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0914028"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.enganabound.2010.05.011"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1980-0572859-4"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0913048"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0909010"},{"key":"atypb38","volume-title":"National Physical Laboratory","author":"Wilkinson J. H.","year":"1977"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1122918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:39:07Z","timestamp":1787333947000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1122918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/17M1122918"],"URL":"https:\/\/doi.org\/10.1137\/17m1122918","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}