Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Five-Precision GMRES-based iterative refinement

Abstract : GMRES-based iterative refinement in three precisions (GMRES-IR3) uses a low precision LU factorization to accelerate the solution of a linear system without compromising numerical stability or robustness. GMRES-IR3 solves the update equation using GMRES preconditioned by the LU factors, where all operations within GMRES are carried out in the working precision u, except for the matrix-vector products and the application of the preconditioner, which require the use of extra precision u 2. The use of extra precision can be expensive, and is especially unattractive if it is not available in hardware; for this reason, existing implementations have not used extra precision, despite the absence of an error analysis for this approach. We relax the requirements on the precisions used within GMRES, allowing the use of arbitrary precisions up (for applying the preconditioner) and ug (for the rest of the operations). We obtain the five-precision GMRES-based iterative refinement (GMRES-IR5) algorithm. We carry out a rounding error analysis that generalizes that of GMRES-IR3, obtaining conditions under which the forward and backward errors converge to their limiting values. Our analysis makes use of a new result on the backward stability of MGS-GMRES in two precisions. On hardware where up to five arithmetics are available, the number of possible combinations of precisions in GMRES-IR5 is extremely large, but our analysis identifies a small subset of relevant combinations. By choosing from within this subset one can achieve different levels of tradeoff between cost and robustness, which allows for a finer choice of precisions depending on the problem difficulty and the available hardware. Our numerical experiments on both random dense matrices and real-life sparse matrices from a wide range of applications show that the practical behavior of GMRES-IR5 is in good agreement with our theoretical analysis. GMRES-IR5 therefore has the potential to solve relatively badly conditioned problems in less time and memory than GMRES-IR3, thanks to the use of lower precision arithmetic in the GMRES iterations.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03190686
Contributor : Bastien Vieublé Connect in order to contact the contributor
Submitted on : Tuesday, April 6, 2021 - 2:50:28 PM
Last modification on : Tuesday, October 19, 2021 - 2:24:24 PM
Long-term archiving on: : Wednesday, July 7, 2021 - 6:39:01 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03190686, version 1

Citation

Patrick Amestoy, Alfredo Buttari, Nicholas Higham, Jean-Yves l'Excellent, Théo Mary, et al.. Five-Precision GMRES-based iterative refinement. 2021. ⟨hal-03190686⟩

Share

Metrics

Record views

300

Files downloads

194