{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,30]],"date-time":"2026-10-30T08:37:10Z","timestamp":1793349430644,"version":"4.5.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,6,1]],"date-time":"2006-06-01T00:00:00Z","timestamp":1149120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p>We present the design and testing of an algorithm for iterative refinement of the solution of linear equations where the residual is computed with extra precision. This algorithm was originally proposed in 1948 and analyzed in the 1960s as a means to compute very accurate solutions to all but the most ill-conditioned linear systems. However, two obstacles have until now prevented its adoption in standard subroutine libraries like LAPACK: (1) There was no standard way to access the higher precision arithmetic needed to compute residuals, and (2) it was unclear how to compute a reliable error bound for the computed solution. The completion of the new BLAS Technical Forum Standard has essentially removed the first obstacle. To overcome the second obstacle, we show how the application of iterative refinement can be used to compute an error bound in any norm at small cost and use this to compute both an error bound in the usual infinity norm, and a componentwise relative error bound.We report extensive test results on over 6.2 million matrices of dimensions 5, 10, 100, and 1000. As long as a normwise (componentwise) condition number computed by the algorithm is less than 1\/<jats:sub>max{10,<jats:italic>\u221an<\/jats:italic>}\u03b5<jats:sub><jats:italic>w<\/jats:italic><\/jats:sub><\/jats:sub>, the computed normwise (componentwise) error bound is at most 2 max{10,<jats:italic>\u221an<\/jats:italic>} \u00b7 \u03b5<jats:sub><jats:italic>w<\/jats:italic><\/jats:sub>, and indeed bounds the true error. Here,<jats:italic>n<\/jats:italic>is the matrix dimension and \u03b5<jats:sub><jats:italic>w<\/jats:italic><\/jats:sub>= 2<jats:sup>-24<\/jats:sup>is the working precision. Residuals were computed in double precision (53 bits of precision). In other words, the algorithm always computed a tiny error at negligible extra cost for most linear systems. For worse conditioned problems (which we can detect using condition estimation), we obtained small correct error bounds in over 90% of cases.<\/jats:p>","DOI":"10.1145\/1141885.1141894","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"325-351","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":60,"title":["Error bounds from extra-precise iterative refinement"],"prefix":"10.1145","volume":"32","author":[{"given":"James","family":"Demmel","sequence":"first","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yozo","family":"Hida","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Kahan","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoye S.","family":"Li","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sonil","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Oracle, Redwood Shores, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E. Jason","family":"Riedy","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK Users' Guide Release 3.0. SIAM Philadelphia PA. 407 pages. Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK Users' Guide Release 3.0. SIAM Philadelphia PA. 407 pages.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_2_1","first-page":"754","article-title":"IEEE Standard for Binary Floating Point Arithmetic","year":"1985","journal-title":"Std"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rck \u00c5. 1990. Iterative refinement and reliable computing. In Reliable Numerical Computation M. Cox and S. Hammarling Eds. Oxford University Press 249--266. Bj\u00f6rck \u00c5. 1990. Iterative refinement and reliable computing. In Reliable Numerical Computation M. Cox and S. Hammarling Eds. Oxford University Press 249--266.","DOI":"10.1093\/oso\/9780198535645.003.0016"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Blackford L. S. Choi J. Cleary A. D'Azevedo E. Demmel J. Dhillon I. Dongarra J. Hammarling S. Henry G. Petitet A. Stanley K. Walker D. and Whaley R. C. 1997. ScaLAPACK Users' Guide. SIAM Philadelphia PA. 325 pages. Blackford L. S. Choi J. Cleary A. D'Azevedo E. Demmel J. Dhillon I. Dongarra J. Hammarling S. Henry G. Petitet A. Stanley K. Walker D. and Whaley R. C. 1997. ScaLAPACK Users' Guide. SIAM Philadelphia PA. 325 pages.","DOI":"10.1137\/1.9780898719642"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF02162559","article-title":"Handbook series linear algebra: Solution of real and complex systems of linear equations","volume":"8","author":"Bowdler H.","year":"1966","journal-title":"Numerische Mathematik"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s10208001004","article-title":"On the complexity of computing error bounds","volume":"1","author":"Demmel J.","year":"2001","journal-title":"Found. Comp. Math."},{"key":"e_1_2_1_7_1","volume-title":"Tech. Rep. UCB\/CSD-04\/1344, Computer Science Division","author":"Demmel J.","year":"2004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Dongarra J. Bunch J. R. Moler C. B. and Stewart G. W. 1979. LINPACK Users' Guide. SIAM Philadelphia PA. Dongarra J. Bunch J. R. Moler C. B. and Stewart G. W. 1979. LINPACK Users' Guide. SIAM Philadelphia PA.","DOI":"10.1137\/1.9781611971811"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1177\/10943420020160010101","article-title":"Basic linear algebra subprograms technical (BLAST) forum standard I","volume":"16","author":"Forum B. T.","year":"2002","journal-title":"Int. J. High Perform. Comput. Applic."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1177\/10943420020160020101","article-title":"Basic linear algebra subprograms technical (BLAST) forum standard II","volume":"16","author":"Forum B. T.","year":"2002","journal-title":"Int. J. High Perform. Comput. Applic."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1029112"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/50063.214386"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0911047"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Higham N. J. 2002. Accuracy and Stability of Numerical Algorithms 2nd Ed. SIAM Philadelphia PA. Higham N. J. 2002. Accuracy and Stability of Numerical Algorithms 2nd Ed. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898718027"},{"key":"e_1_2_1_15_1","unstructured":"Intel Corporation 2004. IA-32 Intel#8482; Architecture Software Developer's Manual Volume 1: Basic Architecture. Intel Corporation. Intel Corporation 2004. IA-32 Intel#8482; Architecture Software Developer's Manual Volume 1: Basic Architecture. Intel Corporation."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01934074","article-title":"Iterative refinement for linear systems in variable-precision arithmetic","volume":"21","author":"Kielbasi\u0144ski A.","year":"1981","journal-title":"BIT"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567808"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character 140","author":"Mallock R. R. M.","year":"1933"},{"key":"e_1_2_1_20_1","unstructured":"MathWorks Inc. Matlab#8482; MathWorks Inc. Matlab#8482;"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321394"},{"key":"e_1_2_1_22_1","unstructured":"NAG Ltd 2005. NAG Fortran Library Manual Mark 21. NAG Ltd Oxford UK. NAG Ltd 2005. NAG Fortran Library Manual Mark 21. NAG Ltd Oxford UK."},{"key":"e_1_2_1_23_1","volume-title":"A New Approach to Scientific Computation","author":"Rump S."},{"key":"e_1_2_1_24_1","first-page":"S439","article-title":"Verified computation of the solution of large sparse linear systems","volume":"75","author":"Rump S.","year":"1995","journal-title":"Zeitschrift f\u00fcr Angewandte Mathematik und Mechanik (ZAMM)"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0612049"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Snyder J. N. 1955. On the improvement of the solutions to a set of simultaneous linear equations using the ILLIAC. J. Math. Tables other Aids Comput. 9 52 177--184. Snyder J. N. 1955. On the improvement of the solutions to a set of simultaneous linear equations using the ILLIAC. J. Math. Tables other Aids Comput. 9 52 177--184.","DOI":"10.1090\/S0025-5718-1955-0074097-6"},{"key":"e_1_2_1_27_1","unstructured":"Stewart G. W. 1973. Introduction to Matrix Computations. Academic Press New York NY. Stewart G. W. 1973. Introduction to Matrix Computations. Academic Press New York NY."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian Elimination is not optimal","volume":"13","author":"Strassen V.","year":"1969","journal-title":"Numer. Math."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611023"},{"key":"e_1_2_1_31_1","volume-title":"New York","author":"Wilkinson J. H.","year":"1963"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141885.1141894","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1141885.1141894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:23Z","timestamp":1750259663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141885.1141894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1145\/1141885.1141894"],"URL":"https:\/\/doi.org\/10.1145\/1141885.1141894","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]},"assertion":[{"value":"2006-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}