7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Guido Kanschat Aug 1 '13 at 6:58
  • $\begingroup$ @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. $\endgroup$ – Jed Brown Aug 4 '13 at 15:24
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I should have known Trilinos would have this! $\endgroup$ – Jack Poulson Aug 1 '13 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.