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)
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