# 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. Sep 14, 2010 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, 2015 at 14:33