Combining Sparse Approximate Factorizations with Mixed-precision Iterative Refinement
Open Access
- 21 March 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 49 (1) , 1-29
Abstract
The standard LU factorization-based solution process for linear systems can be enhanced in speed or accuracy by employing mixed-precision iterative refinement. Most recent work has focused on dense systems. We investigate the potential of mixed-precision iterative refinement to enhance methods for sparse systems based on approximate sparse factorizations. In doing so, we first develop a new error analysis for LU- and GMRES-based iterative refinement under a general model of LU factorization that accounts for the approximation methods typically used by modern sparse solvers, such as low-rank approximations or relaxed pivoting strategies. We then provide a detailed performance analysis of both the execution time and memory consumption of different algorithms, based on a selected set of iterative refinement variants and approximate sparse factorizations. Our performance study uses the multifrontal solver MUMPS, which can exploit block low-rank factorization and static pivoting. We evaluate the performance of the algorithms on large, sparse problems coming from a variety of real-life and industrial applications showing that mixed-precision iterative refinement combined with approximate sparse factorization can lead to considerable reductions of both the time and memory consumption.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/P020720/1)
- Royal Society, and the Exascale Computing Project (17-SC-20-SC)
- National Nuclear Security Administration
This publication has 46 references indexed in Scilit:
- Verification of cardiac tissue electrophysiology simulators using an N -version benchmarkPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2011
- A fast and robust mixed-precision solver for the solution of sparse symmetric linear systemsACM Transactions on Mathematical Software, 2010
- Accelerating scientific computations with mixed precision algorithmsComputer Physics Communications, 2009
- Using Mixed Precision for Sparse Matrix Computations to Enhance the Performance while Achieving 64-bit AccuracyACM Transactions on Mathematical Software, 2008
- Mixed Precision Iterative Refinement Techniques for the Solution of Dense Linear SystemsThe International Journal of High Performance Computing Applications, 2007
- Error bounds from extra-precise iterative refinementACM Transactions on Mathematical Software, 2006
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- Iterative refinement implies numerical stability for Gaussian eliminationMathematics of Computation, 1980
- Iterative refinement implies numerical stabilityBIT Numerical Mathematics, 1977
- Iterative Refinement in Floating PointJournal of the ACM, 1967