1
$\begingroup$

There are some great libraries with linear solvers for sparse matrices - SuiteSparse is the obvious one. The methods work on sparse matrices with scalar entries.

However, often in optimization problems, the matrices consist of dense sub-blocks within a sparse structure. Are there any solver libraries that define block sparse matrix structures, and have solvers that take advantage of the structure?

In particular, I have a system of normal equations from bundle adjustment, which generates a symmetric sparse matrix with some blocks of side-length 9 and and others of side-length 3. I'd like to use the CHOLMOD algorithm to solve this, but exploiting the block structure. Do any libraries do this?

Improve this question
$\endgroup$
4
  • $\begingroup$ Out of curiosity, with blocks these small, how do traditional sparse solver perform? I imagine that with such small blocks, a lot of low-level work could be done on optimizing distributed memory for matvecs in a Krylov routine. $\endgroup$
    – whpowell96
    Sep 6 at 0:59
  • $\begingroup$ pretty sure Julia has this $\endgroup$
    – Oscar Smith
    Sep 6 at 4:21
  • $\begingroup$ @OscarSmith I'm using Julia and haven't found such a thing. Please can you provide a link in an answer? $\endgroup$
    – user664303
    Sep 6 at 8:08
  • 1
    $\begingroup$ github.com/JuliaLinearAlgebra/BlockBandedMatrices.jl works as long as the blocks exist in a banded structure (but you can generally ensure that by pivoting) $\endgroup$
    – Oscar Smith
    Sep 6 at 14:12

2 Answers 2

Reset to default
1
$\begingroup$

Most modern direct sparse solvers, including CHOLMOD, exploit block structure in performing a factorization. Such solvers are usually described as "supernodal" or "multifrontal". At each stage of the factorization the solver identifies groups of equations that have the same structure and then uses dense matrix functions of perform operations on these groups (blocks). Due to fill-in, the remaining part of the matrix usually becomes denser as the factorization proceeds, i.e. larger and larger blocks can be found. The size of the final block in the factorization is often a significant percentage of the total number of equations.

Finally, some solvers exploit the idea of "relaxed supernodes" where groups of equations don't have precisely the same structure but there are few enough zeros that it is computationally more efficient to treat them as one large block instead of multiple smaller ones.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, Bill. I’m aware of this. I appreciate the answer, but it’s not answering the question I asked. I suspect that using block sparse matrices (with simpler indexing and more contiguous dense blocks) would still be more efficient within these algorithms. If your answer is that they wouldn’t, then I’d love to see a reference or test confirming this. $\endgroup$
    – user664303
    Sep 6 at 14:22
  • $\begingroup$ Perhaps it wasn’t clear what I meant by block sparse matrix. I mean that the underlying data structure (and methods) exploits the blocks, so as to be more efficient. $\endgroup$
    – user664303
    Sep 6 at 14:25
1
$\begingroup$

OpenAI released a block-sparse matrix library here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 👍 though sadly it only supports matrix multiplication and convolution (not solving/inverting), and only on GPU $\endgroup$
    – user664303
    Sep 7 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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