Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions

DOI10.1137/17M1140819zbMath1453.65067OpenAlexW2752879223WikidataQ56998582 ScholiaQ56998582MaRDI QIDQ4610143

Erin Claire Carson, Nicholas J. Higham

Publication date: 5 April 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1140819

zbMATH Keywords

linear systempreconditioningGMRESbackward errorrounding error analysisiterative refinementmultiple precisionmixed precisionforward error

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Roundoff error (65G50) Numerical computation of matrix norms, conditioning, scaling (65F35) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Mixed precision algorithms in numerical linear algebra, A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems, On the use of the infinity computer architecture to set up a dynamic precision floating-point arithmetic, Mixed-precision explicit stabilized Runge-Kutta methods for single- and multi-scale differential equations, A Note on Inexact Inner Products in GMRES, Convergence Analysis of a Mixed Precision Parareal Algorithm, Mixed Precision Iterative Refinement with Sparse Approximate Inverse Preconditioning, A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems, A mixed precision LOBPCG algorithm, Five-Precision GMRES-Based Iterative Refinement, A Class of Fast and Accurate Summation Algorithms, Acceleration of iterative refinement for singular value decomposition, Adaptive Precision Sparse Matrix–Vector Product and Its Application to Krylov Solvers, Numerical stability of algorithms at extreme scale and low precisions, GMRES algorithms over 35 years, A new iterative refinement for ill-conditioned linear systems based on discrete gradient, Mixed Precision Block Fused Multiply-Add: Error Analysis and Application to GPU Tensor Cores, Random Matrices Generating Large Growth in LU Factorization with Pivoting, Algebraic Error Analysis for Mixed-Precision Multigrid Solvers, Discretization-Error-Accurate Mixed-Precision Multigrid Solvers, A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error, Mixed-precision iterative refinement using tensor cores on GPUs to accelerate solution of linear systems, A numerical study of fractional linear algebraic systems, Enclosing Chebyshev Expansions in Linear Time, Reproducibility strategies for parallel preconditioned conjugate gradient, Performance and energy consumption of accurate and mixed-precision linear algebra kernels on GPUs, A Hamiltonian decomposition for fast interior-point solvers in model predictive control, Squeezing a Matrix into Half Precision, with an Application to Solving Linear Systems, A New Approach to Probabilistic Rounding Error Analysis, Hierarchical algorithms on hierarchical architectures, Numerical algorithms for high-performance computational science, Simulating Low Precision Floating-Point Arithmetic, Algebraic Error Analysis for Mixed-Precision Multigrid Solvers, Discretization-Error-Accurate Mixed-Precision Multigrid Solvers, Three-Precision GMRES-Based Iterative Refinement for Least Squares Problems, Generating Extreme-Scale Matrices With Specified Singular Values or Condition Number, Exploiting Lower Precision Arithmetic in Solving Symmetric Positive Definite Linear Systems and Least Squares Problems, Matrices with Tunable Infinity-Norm Condition Number and No Need for Pivoting in LU Factorization

Uses Software

• LAPACK
• mctoolbox
• MAGMA
• PLASMA
• HSL_MA79

Cites Work

• Unnamed Item
• Unnamed Item
• Chebyshev acceleration of iterative refinement
• Using FGMRES to obtain backward stability in mixed precision
• Binary cascades iterative refinement in doubled-mantissa arithmetics
• Iterative refinement for linear systems in variable-precision arithmetic
• Iterative refinement enhances the stability of \(QR\) factorization methods for solving linear equations
• The worst-case GMRES for normal matrices
• Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
• Newton's Method in Floating Point Arithmetic and Iterative Refinement of Generalized Eigenvalue Problems
• A fast and robust mixed-precision solver for the solution of sparse symmetric linear systems
• Fast Hybrid Solution of Algebraic Systems
• A Note on GMRES Preconditioned by a Perturbed $L D L^T$ Decomposition with Static Pivoting
• Recycling Krylov Subspaces for Sequences of Linear Systems
• LAPACK Users' Guide
• Iterative Refinement Implies Numerical Stability for Gaussian Elimination
• Use of Iterative Refinement in the Solution of Sparse Linear Systems
• Iterative refinement implies numerical stability
• Iterative refinement for linear systems and LAPACK
• Faster numerical algorithms via exception handling
• A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems
• Solving Sparse Linear Systems with Sparse Backward Error
• Accuracy and Stability of Numerical Algorithms
• On the Stability of Cholesky Factorization for Symmetric Quasidefinite Systems
• Any Nonincreasing Convergence Curve is Possible for GMRES
• Modified Gram-Schmidt (MGS), Least Squares, and Backward Stability of MGS-GMRES
• Iterative Refinement in Floating Point
• On the Compatibility of a Given Solution With the Data of a Linear System
• Modern Error Analysis
• Linear algebra software for large-scale accelerated multicore computing
• NOTES ON THE SOLUTION OF ALGEBRAIC LINEAR SIMULTANEOUS EQUATIONS