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)