Publications

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 standard LU factorization-based solution process for linear systems can be enhanced in speed or accuracy by employing mixed-precision iterative refinement. Most recent work has focused on dense systems. We investigate the potential of mixed-precision iterative refinement to enhance methods for sparse systems based on approximate sparse factorizations. In doing so, we first develop a new error analysis for LU- and GMRES-based iterative refinement under a general model of LU factorization that accounts for the approximation methods typically used by modern sparse solvers, such as low-rank approximations or relaxed pivoting strategies. We then provide a detailed performance analysis of both the execution time and memory consumption of different algorithms, based on a selected set of iterative refinement variants and approximate sparse factorizations. Our performance study uses the multifrontal solver MUMPS, which can exploit block low-rank factorization and static pivoting. We evaluate the performance of the algorithms on large, sparse problems coming from a variety of real-life and industrial applications showing that mixed-precision iterative refinement combined with approximate sparse factorization can lead to considerable reductions of both the time and memory consumption.

GMRES-based iterative refinement in three precisions (GMRES-IR3), which has been introduced and studied in \citecahi17,cahi18, 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 of iterative refinement 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. In this article, we propose to relax the requirements on the precisions used within GMRES, allowing the use of arbitrary precisions u_p (for applying the preconditioned matrix–vector product) and u_g (for the rest of the operations). We obtain the five-precision GMRES-based iterative refinement (GMRES-IR5) algorithm which has the potential to solve relatively badly conditioned problems in less time and memory than GMRES-IR3. The essence of this work is to carry out an extensive numerical study of GMRES-IR5. In that regard, our article contains the following contributions. We develop 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 three or more arithmetics are available, which is becoming very common, the number of possible combinations of precisions in GMRES-IR5 is extremely large. We provide an analysis of our theoretical results that identifies a relatively 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. We carry out numerical experiments on both random dense matrices and real-life matrices from a wide range of applications to validate our theoretical analysis.

Bathymetry is an important factor in determining wave and current transformation in coastal and surface areas but is often poorly understood. However, its knowledge is crucial for hydro-morphodynamic forecasting and monitoring. Available for a long time only via in-situ measurement, the advent of video and satellite imagery has allowed the emergence of inversion methods from surface observations. With the advent of methods and architectures adapted to big data, a treatment via a deep learning approach seems now promising. This article provides a first overview of such possibilities with synthetic cases and its potential application on a real case.

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.