While it is well known how to apply direct methods based on Gauss elimination to a linear system of equations with several right-hand sides, the effective solution of such systems by iterative methods is less obvious. There is a long history of generalizing Krylov space solvers like CG, BiCG, and GMRES to this situation by deriving analogous block Krylov space solvers. The formal definition of such generalizations is quite straightforward, but to make the algorithms suitable for finite-precision arithmetic often poses serious difficulties.

The residuals of the various right-hand sides naturally tend to become nearly linearly dependent, so the block size may have to be reduced on the fly, a process referred to as deflation. It is linked to the convergence of one (or several) of the systems. Deflation does not only determine whether the solutions constructed are accurate enough, but it also has a strong impact on the stability of the solution process. Allowing deflation complicates the program for a block methods such as block GMRES considerably, however.

However, block GMRES encounters yet other problems: first, it requires excessive memory since all (not yet deflated) residuals for the various right-hand sides need to be stored. Moreover, the generated block Hessenberg matrix may also become relatively large, and the solution of the corresponding least-squares problem is much more costly than for a single system.

In this talk we analyze the deflation process and compare the costs of normal and block GMRES.