13
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Sep 14, 2010 at 15:32
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Aug 28, 2015 at 14:33

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.