Rafael LAGO
Inexact Block GMRES with Deflation

CERFACS 42 Avenue Gaspard Coriolis
31057 Toulouse Cedex 1
France
lago@cerfacs.fr
Serge GRATTON
Xavier VASSEUR

We address the solution of linear systems with multiple right-hand sides given at once:

$$A~X=B, \quad X, B \in\mathbb{C}^{n\times p}, \quad A\in\mathbb{C}^{n\times n},$$

when matrix-vector products with $A$ are performed only approximately. Given $V\in\mathbb{C}^{n\times q}$ the matrix-matrix product is thus represented as $(A+E)V$ , where $E$ is a ``perturbation matrix'' allowed to change at each application (we always suppose that the spectral norm of $E$ is controllable). This kind of situation arises for instance when we do not dispose of $A$ , but of a function which approximates $AV$ based on a threshold $\varepsilon$ .

In the single right-hand side case ($p=1$ ) previous works (e.g. [8], [4], and [3]) have shown that variants of GMRES [7] allow $\vert\vert E\vert\vert _2$ to grow with the number of iterations, provided that some bounds are respected. Supposing that the cost of approximating $AV$ is inversely proportional to the chosen threshold $\varepsilon$ , controlling $\vert\vert E\vert\vert _2$ at each iteration potentially reduces the computational cost.

In the multiple right-hand side case, rather than solving the systems in sequence (that is, applying the chosen algorithm for each right hand-side) we could treat them in a ``block wise'' manner and use a variant of block GMRES [9]. Indeed the literature has shown the interest of using block Krylov subspace methods in such a situation; see, e.g., [5], [6] and [1]. The latter two mainly rely on the singular value decomposition of the block residual to perform ``deflation'', a mechanism which has been considered crucial for the reduction of the computational cost of block iterative solvers. This deflation strategy aims at detecting when a linear combination of the systems has approximately converged.

In this talk we will thus analyze an inexact block GMRES with deflation. Our concern arises from the fact that inexact matrix-vector product introduces a perturbation in the residual computation. First we analyze the impact of the perturbation $E$ on the block residual and on its singular values and study the behavior of two algorithms proposed in [6] and [1] in the presence of inexact matrix-vector product. Then we show some numerical experiments with well-known problems from University of Florida collection [2] and discuss the results obtained so far.