Combining Sparse Approximate Factorizations with Mixed-precision Iterative Refinement

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 s...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on mathematical software 2023-03, Vol.49 (1), p.1-29, Article 4
Main Authors: Amestoy, Patrick, Buttari, Alfredo, Higham, Nicholas J., L’Excellent, Jean-Yves, Mary, Theo, Vieublé, Bastien
Format: Article
Language:English
Subjects:
Computations on matrices
Computer Science
Computing methodologies
floating-point arithmetic
GMRES
Iterative refinement
Linear algebra algorithms
linear system
Mathematical Software
Mathematical software performance
Mathematics
MATHEMATICS AND COMPUTING
Mathematics of computing
mixed precision
multifrontal method
multiple precision
Numerical Analysis
parallelism
pre-conditioning
rounding error analysis
Solvers
sparse direct solver
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0098-3500
1557-7295
DOI:10.1145/3582493