Session III.1 - Numerical Linear Algebra
Tuesday, June 20, 17:00 ~ 17:30
A new backward error analysis framework for GMRES
Bastien Vieublé
The University of Manchester, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
GMRES is a well-known iterative solver for the solution of linear systems $Ax=b$. Its combination with approximate computing techniques such as low precision or randomization has recently brought much attention. This is because these techniques can offer significant gains in speed and energy and enlarge the scale of problems we are able to solve. GMRES can employ approximate computing in many different ways: at the preconditioner level, at the restart level, at the orthogonalization level, etc. Moreover, considering the wide variety of preconditioners that can be used (e.g., ILU, polynomial, Jacobi, iterative solver, etc.) and the different orthogonalization algorithms and their variants (e.g., Householder, MGS, CGS2, etc.), the combinatory of possibilities is gigantic. Generally, existing backward error analyses of GMRES are specialized to one of these combinations and cannot be extended to others. For this reason, in this talk, we present a general framework for backward error analysis of GMRES that aims at gathering all these combinations inside a common and coherent analysis, in addition to deriving specialized bounds on the backward and forward errors of a given GMRES algorithm. We finally show how to apply these tools on a new mixed precision preconditioned restarted GMRES algorithm that uses six independent precision parameters and applies the preconditioner in a lower precision than the matrix-vector product with $A$. We motivate this new mixed precision scheme by numerical experiments on real-life SuiteSparse matrices.
Joint work with Alfredo Buttari (IRIT, France), Nicholas J. Higham (The University of Manchester, UK) and Théo Mary (LIP6, France).