# Fast sparse boolean matrix chain product

So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually stay as sparse at each step.

Are there any matrix chain product algorithms that work particularly fast in this case?

On a higher level, the problem is to compute the composition of a series of one-to-many mappings on a reasonably small graph (transition functions of an NFA), where most elements map to no more than 0-3.

(please note that this is not the usual "matrix chain product" problem, because all matrices are of the same size and I don't have to choose the optimal parenthesizing)

• actually, the order you multiply them in might affect the sparsity of the intermediate results, so it might still be an important issue in any such fast algorithm. – Joshua Grochow Sep 14 '10 at 15:32
• from your other question you seem to be using 0/1 semiring AND/ OR operations, not addition/ multiplication (as the problem seems to state), please make this clear in the question – vzn Aug 28 '15 at 14:33

This was too long to be a comment -- I wonder if those matrices have structure that make them behave differently from random matrices. Products of random sparse matrices go to zero or become non-sparse quickly.

Here's a simple experiment -- take 200 random binary 50x50 matrices, and plot number of non-zeros as a function of number of matrices multiplied. Plots below show standard deviation over 2000 runs. First plot is for 2% sparsity, second plot is for 3%

(source: yaroslavvb.com)

(source: yaroslavvb.com)

this took 3 minutes on my laptop using standard matrix multiplication