Mixed Precision Iterative Refinement with Sparse Approximate Inverse Preconditioning
From MaRDI portal
Publication:6098511
DOI10.1137/22M1487709zbMATH Open1516.65023arXiv2202.10204OpenAlexW4379985703MaRDI QIDQ6098511FDOQ6098511
Authors: Erin Carson 
Publication date: 14 June 2023
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: With the commercial availability of mixed precision hardware, mixed precision GMRES-based iterative refinement schemes have emerged as popular approaches for solving sparse linear systems. Existing analyses of these approaches, however, are based on using full LU factorizations to construct preconditioners for use within GMRES in each refinement step. In practical applications, inexact preconditioning techniques, such as incomplete LU or sparse approximate inverses, are often used for performance reasons. In this work, we investigate the use of sparse approximate inverse preconditioners based on Frobenius norm minimization within GMRES-based iterative refinement. We analyze the computation of sparse approximate inverses in finite precision and derive constraints under which user-specified stopping criteria will be satisfied. We then analyze the behavior of and convergence constraints for a five-precision GMRES-based iterative refinement scheme that uses sparse approximate inverse preconditioning, which we call SPAI-GMRES-IR. Our numerical experiments confirm the theoretical analysis and illustrate the resulting tradeoffs between preconditioner sparsity and GMRES-IR convergence rate.
Full work available at URL: https://arxiv.org/abs/2202.10204
Recommendations
- Mixed precision incomplete and factorized sparse approximate inverse preconditioning on GPUs
- A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems
- Accelerating the solution of linear systems by iterative refinement in three precisions
- A fast and robust mixed-precision solver for the solution of sparse symmetric linear systems
- scientific article
Computational methods for sparse matrices (65F50) Preconditioners for iterative methods (65F08) Roundoff error (65G50) Computer aspects of numerical algorithms (65Y99) Iterative numerical methods for linear systems (65F10)
Cites Work
- The university of Florida sparse matrix collection
- Preconditioning techniques for large linear systems: A survey
- Title not available (Why is that?)
- Orderings for Factorized Sparse Approximate Inverse Preconditioners
- Communication-optimal parallel and sequential QR and LU factorizations
- Accuracy and Stability of Numerical Algorithms
- Factorized-sparse-approximate-inverse preconditionings of linear systems with unsymmetric matrices
- Iterative Refinement Implies Numerical Stability for Gaussian Elimination
- Factorized Sparse Approximate Inverse Preconditionings I. Theory
- Parallel Preconditioning with Sparse Approximate Inverses
- A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems
- Any Nonincreasing Convergence Curve is Possible for GMRES
- GPU-accelerated preconditioned GMRES method for two-dimensional Maxwell's equations
- Approximate inverse preconditionings for sparse linear systems
- A comparative study of sparse approximate inverse preconditioners
- Using FGMRES to obtain backward stability in mixed precision
- Three-Precision GMRES-Based Iterative Refinement for Least Squares Problems
- A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error
- Sparse Approximate-Inverse Preconditioners Using Norm-Minimization Techniques
- Iterative Refinement in Floating Point
- Frobenius norm minimization and probing for preconditioning
- Factorized sparse approximate inverses for preconditioning
- Mixed precision algorithms in numerical linear algebra
- Iterative refinement implies numerical stability
- A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems
- Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions
- Linear algebra software for large-scale accelerated multicore computing
- Solving block low-rank linear systems by LU factorization is numerically stable
- Squeezing a Matrix into Half Precision, with an Application to Solving Linear Systems
- Multistage mixed precision iterative refinement
Cited In (8)
- Approximate Generalized Inverses with Iterative Refinement for $\epsilon$-Accurate Preconditioning of Singular Systems
- Using FGMRES to obtain backward stability in mixed precision
- Avoiding breakdown in incomplete factorizations in low precision arithmetic
- Using Mixed Precision for Sparse Matrix Computations to Enhance the Performance while Achieving 64-bit Accuracy
- Multiresolution approximate inverse preconditioners
- Convergence Analysis of a Mixed Precision Parareal Algorithm
- Multilevel preconditioning and adaptive sparse solution of inverse problems
- Mixed-precision preconditionders in parallel domain decomposition solvers
This page was built for publication: Mixed Precision Iterative Refinement with Sparse Approximate Inverse Preconditioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098511)
