Bastien Vieublé

The Generalized Minimal Residual methods (GMRES) for the solution of general square linear systems is a class of Krylov-based iterative solvers for which there exist backward error analyses that guarantee the computed solution in inexact arithmetic to reach certain attainable accuracies. Unfortunately, these existing backward error analyses cover a relatively small subset of the possible GMRES variants and cannot be used straightforwardly in general to derive new backward error analyses for variants that do not yet have one. We propose a backward error analysis framework for GMRES that substantially simplifies the process of determining error bounds of most existing and future variants of GMRES. This framework describes modular bounds for the attainable normwise backward and forward errors of the computed solution that can be specialized for a given GMRES variant under minimal assumptions. To assess the relevance of our framework we first show that it is compatible with the previous rounding error analyses of GMRES in the sense that it delivers (almost) the same error bounds under (almost) the same conditions. Second, we explain how to use this framework to determine new error bounds for GMRES algorithms that do not have yet a backward error analysis, such as simpler GMRES, CGS2-GMRES, mixed precision GMRES, and more.

The increasing availability of very low precisions (tfloat32, fp16, bfloat16, fp8) in hardware pushes modern high performance computing to embrace mixed precision standards. By employing mostly low precision and by making wise use of high precision, mixed precision algorithms can leverage the low precision advantages while preserving the quality of the computed solution. Mixed precision iterative refinement is one of the oldest and most famous representatives of these algorithms; this method was shown to be very effective in reducing the resource consumption of linear solvers while delivering accurate solutions in a robust way.
This thesis is dedicated to investigating the use of this algorithm for the solution of large sparse linear systems. We structure the document as follows.
Our first concern is to provide a comprehensive understanding of iterative refinement. This part of our work covers a survey listing the different research studies on this algorithm that explains its evolutions throughout time and a technical description of a selected set of state-of-the-art iterative refinement algorithms.
Then, we focus on improving sparse direct solvers with iterative refinement. We pro- ceed in two steps. First, we relax restrictive requirements on the LU-GMRES-IR3 algorithm, which is a form of iterative refinement capable of handling inaccurate factorizations for ill-conditioned problems. It leads us to propose the LU-GMRES-IR5 algorithm that has five independent precision parameters and is more suited to the solution of large sparse systems. Second, we address the parallel implementation of state-of-the-art iterative re- finement algorithms combined with state-of-the-art approximate sparse factorizations to solve real-life problems from academic and industrial applications. Our performance study demonstrates significant reductions in time and memory with respect to a standard sparse direct solver in double precision.
Finally, we use iterative refinement to improve sparse iterative solvers. We develop an analysis for a new mixed precision preconditioned GMRES (M-GMRES-IR6) that aims at covering previous existing implementations that are not yet covered by an analysis and at proposing a new mixed precision strategy based on the application of the preconditioner in a lower precision than the application of the original matrix A. Our numerical results pave the way towards promising resource savings for parallel implementations of GMRES.