# Question

Are there libraries out there that implement block Krylov subspace methods? (I was not able to find any from a simple Google search.)

# Background

Right now, I am working with a code that solves several systems of the form

\begin{align} Ax_{i} = b_{i}, \end{align}

where $A$ is $n$ by $n$, $i = 1, \ldots, m$, and in general, $n \gg m$ ($n$ is at least 10 times larger than $m$, and could be several orders of magnitude larger than $m$). In addition, $A$ is large enough that iterative methods are preferable.

Currently, the code solves $Ax_{i} = b_{i}$ with a Krylov subspace method for each separate right-hand side with a given preconditioner, and this approach seems to work well enough. (The code also recomputes the preconditioner, which is unnecessary.)

To speed up the code, it seems like it could be worth looking at solving

\begin{align} AX = B \end{align}

instead, where $B = [b_{1}\, b_{2}\, \ldots\, b_{m}]$ is an $n$ by $m$ matrix gathering up all of the $b_{i}$, and $X$ is also an $n$ by $m$ matrix gathering up the $x_{i}$.

I'd like to try out solving $AX = B$ with block Krylov subspace methods (using the same preconditioner as before) to see if it outperforms the current approach of solving $Ax_{i} = b_{i}$ and looping over $i$. It is both possible and unlikely that the solution to $Ax_{i} = b_{i}$ could then be used as a guess for the system $Ax_{j} = b_{j}$ for $i \neq j$; I don't expect there to be a relationship among the various systems.

• Since a well implemented block Krylov-space method uses the same Krylov space for all vectors, you should expect your total number of matrix-vector multiplications to drop considerably. So, it is worthwhile, but like Jack I am not aware of any. Aug 1 '13 at 6:58
• @GuidoKanschat There is no guarantee that the number of iterations will be reduced. It might, but this depends on the spectral properties of the (preconditioned) matrix and of the right hand sides. Aug 4 '13 at 15:24

Here's at least a partial answer, after a few hours of searching:

There is an implementation of block Krylov subspace methods buried within the Belos package of Trilinos that contains:

• Block CG
• Block GMRES
• Block flexible GMRES
• Block GCRODR (block recycling GMRES)

Supposedly, MATLAB implementations of some of these methods exist, but I haven't yet come across them.

• I should have known Trilinos would have this! Aug 1 '13 at 8:21

Quite old post, but I found this MATLAB implementation, I haven' tried it https://github.com/rowanc1/blockIterativeSolvers

• Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
– Community Bot
Oct 11 at 12:54

Take a look at DUNE (Distributed and Unified Software Envvironment).

I have never worked with these methods in particular, but I think they were implemented within the dune solver Framework ISTL:

DUNE project

paper

paper