Quadratic Sparse Matrix Multiplication Algorithm

Question

I optimize the code, which largely depends on the custom Matrix library (which will not be excluded from the project because it is everywhere. It's not nice, but it's a fact ...) Many calculations are performed using matrices from 10-20 rows and columns, many calculations include a quadratic form like

C = A*B*A' 

I realized that often A is sparse, and I would like to take advantage of this fact. Therefore, I am looking for an algorithm that will handle this case. Numerical stability is important. Is there anything I can use? (I did not write our library, so I do not know if there are any pitfalls that I should consider?)

As "our" simple method of multiplying O (n ^ 3) is faster than Eigen 3 on the target platform, since I need numerical stability and the matrices are not very large, I think that the Strassen algorithm, as well as the Coppersmith- Winograd algorithm is not what i'm looking for. Instead, it's just multiplying a quadratic form so that I can easily check the zeros in A.

Thanks for any suggestions!

Answer 1

There is this document dedicated to fast sparse matrix multiplication. The developed algorithm divides the sparse matrix into two parts: dense and sparse, and uses the fast multiplication algorithm on it. So for me it looks like it doesn’t depend on the size of the matrix, as you mentioned in relation to Strassen, but because it is sparse.

Answer 2

There are ways to implement a sparse matrix in ways that make it more compressed than a dense matrix. One way to do this:

 [0 0 0 0 0] [0 1 2 0 9] [0 0 0 2 0] [0 1 0 0 0] 

becomes a linear array of nonzero elements

 typedef struct { int row; int col; double entry; } Element; typedef SparseMatrix Element*; 

So, now the matrix has spatial complexity O (n) instead of O (n ^ 2) For A * B, where A and B are matrices, you only need to cross each array to match the elements (e.g. a-> row == b- > col & a-> col == b-> row), and possibly add a few together (internal product). This algorithm would be more complicated than O (n ^ 2), not O (n ^ 3). This is because you can skip the unreasonable operation of taking an internal product that will result in zero.

Answer 3

check Highly sparse matrix-matrix multiplication matrix algorothm