billx - 6 months ago 82

C++ Question

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.

Answer

There is not much to expect for such small matrices as this would decrease vectorization opportunities and instruction pipelining. You 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.