Bastien Vieublé

The Generalized Minimal Residual method (GMRES) for the solution of general square linear systems Ax=b is often combined with a preconditioner to improve the convergence speed of the method. Successful mixed precision implementations for the application of the preconditioner inside GMRES have been previously proposed: certain strategies prescribe to apply the preconditioner in low precision to reduce overall time and memory consumption, and other strategies propose to apply the matrix A and the preconditioner in higher precision to improve robustness and accuracy. These existing studies tend to focus on one kind of preconditioner combined with one kind of preconditioning technique (left-, right-, and flexible-preconditioning). In this article, we wish to unify most of the state-of-the-art mixed precision implementations for preconditioned GMRES under the same comprehensive theory, give a clear and exhaustive list of the possible strategies to set the precisions, and explain how these strategies compare numerically. To achieve this, we derive rounding error analyses with generic preconditioners for the left-, right-, and flexible-preconditioned GMRES processes in mixed precision and obtain descriptive bounds for the attainable forward errors of the computed solutions. Specifically, we substantially improve the sharpness of the right- and flexible-preconditioned GMRES forward error bounds compared with the existing literature. From the study of these bounds, we discover new meaningful mixed precision implementations that were not previously known; these new strategies achieve new tradeoffs between the employment of computationally effective low precision and accuracy. Moreover, we also uncover critical differences in robustness and accuracy between left-, right-, and flexible-preconditioning for a same given set of precisions: the choice among the three preconditioning techniques therefore has higher stakes in mixed precision. We substantiate our theoretical findings with a comprehensive experimental study on random dense and real-life sparse matrices from the SuiteSparse collection with various preconditioners: low precision LU factorization, incomplete LU, sparse approximate inverse, and polynomial preconditioners.

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.