Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions
Top Cited Papers
Open Access
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 40 (2) , A817-A847
Abstract
We propose a general algorithm for solving an $n\times n$ nonsingular linear system $Ax = b$ based on iterative refinement with three precisions. The working precision is combined with possibly different precisions for solving for the correction term and for computing the residuals. Via rounding error analysis of the algorithm we derive sufficient conditions for convergence and bounds for the attainable forward error and normwise and componentwise backward errors. Our results generalize and unify many existing rounding error analyses for iterative refinement. With single precision as the working precision, we show that by using LU factorization in IEEE half precision as the solver and calculating the residuals in double precision it is possible to solve $Ax = b$ to full single precision accuracy for $\infty$-norm condition numbers $\kappa_{\infty}(A) \le 10^4$, with the $O(n^3)$ part of the computations carried out entirely in half precision. We show further that by solving the correction equations by GMR...
Keywords
Funding Information
- MathWorks
- Engineering and Physical Sciences Research Council (EP/P020720/1)
This publication has 31 references indexed in Scilit:
- A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear SystemsSIAM Journal on Scientific Computing, 2017
- Linear algebra software for large-scale accelerated multicore computingActa Numerica, 2016
- Chebyshev acceleration of iterative refinementNumerical Algorithms, 2013
- Numerical linear algebra on emerging architectures: The PLASMA and MAGMA projectsJournal of Physics: Conference Series, 2009
- A Note on GMRES Preconditioned by a Perturbed $L D L^T$ Decomposition with Static PivotingSIAM Journal on Scientific Computing, 2007
- On the Stability of Cholesky Factorization for Symmetric Quasidefinite SystemsSIAM Journal on Matrix Analysis and Applications, 1996
- Faster numerical algorithms via exception handlingIEEE Transactions on Computers, 1994
- Fast Hybrid Solution of Algebraic SystemsSIAM Journal on Scientific and Statistical Computing, 1990
- Solving Sparse Linear Systems with Sparse Backward ErrorSIAM Journal on Matrix Analysis and Applications, 1989
- NOTES ON THE SOLUTION OF ALGEBRAIC LINEAR SIMULTANEOUS EQUATIONSQuarterly Journal of Mechanics and Applied Mathematics, 1948