Block Sparse Matrix with Eigen library

2
votes

I would like to speed up a library I'm working on. Most of the matrices are of rather small size (say up to 10x40). Most are block sparse, with a sparsity pattern known at run time. I want to make use of sparsity to speed up linear algebra operations.

Additionally to the basic linear algebra operations, I use an SVD decomposition. Block sparse matrix would help detecting columns / rows of zero and block diagonal matrix, which can decrease decomposition time.

Is there a specific reason why sparse matrix are implemented only coefficient wise and not block wise?

I mean that the current implementation is efficient for large matrices with a few non-zero elements, but not for matrices with comparable number of non-zero and zero.

I had a look at the so-bogus library which implements sparse block matrix using Eigen library.

1
c++sparse-matrixeigen
Is there a specific reason why sparse matrix are implemented only coefficient wise and not block wise? Probably because it's simpler, but we'll have to wait for ggael for a definitive answer. Other than that, do you have an actual question? Also, for small (you're talking about up to 400 elements), matrices it's probably faster to just use the dense algorithms. Make sure that you have an actual need, and not just prematurely optimizing, which may lead to a slowdown. – Avi Ginsburg
Do you know other libraries for this? is considered off-topic for SO (see item 4 here). – Avi Ginsburg
@AviGinsburg: Probably because it's simpler, this was my guess. I could find only a few posts on the topic so I was wondering if there was another reason (like it is not worth). – billx
I bet, this has merely historic reasons. There are at least two use-cases where block sparse matrices are helpful. Inverse of the block-diagonal is typically a much better preconditioner than the inverse of the diagonal. If the matrix is already in block sparse form, the preconditioner is cheaper to compute. Also, generic sparse non-linear least squares solver such as g2o or ceres save the matrices internally in-terms of sparse blocks (e.g. for efficientl Schur complement computation) and only convert to standard CSC form when interfacing with external libraries (Suitespare etc.). – B0rk4

1 Answers

1
votes

There is not much to expect for such small matrices as this would decrease vectorization opportunities and instruction pipelining. You can check by yourself by comparing the performance of a triangular matrix * vector versus full matrix * vector for a 10x10 matrix.

Then, regarding SVD, the situation is even worse because for such a small matrix JacobiSVD is preferred and the structure of the zeros will likely be completely lost during the first sweep unless it has a very special structure which could be exploited, like a block diagonal structure.