期刊
SIAM JOURNAL ON SCIENTIFIC COMPUTING
卷 39, 期 6, 页码 A2834-A2856出版社
SIAM PUBLICATIONS
DOI: 10.1137/17M1122918
关键词
ill-conditioned linear system; iterative refinement; multiple precision; mixed precision; rounding error analysis; backward error; forward error; GMRES; preconditioning
资金
- MathWorks
- European Research Council Advanced Grant MATFUN [267526]
- Engineering and Physical Sciences Research Council [EP/I01912X/1, EP/P020720/1]
- Engineering and Physical Sciences Research Council [EP/I01912X/1, EP/P020720/1] Funding Source: researchfish
- EPSRC [EP/I01912X/1, EP/P020720/1] Funding Source: UKRI
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据