<p>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.</p>
<p>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%</p>
<p><a href="https://i.sstatic.net/2nzlp.png" rel="noreferrer"><img src="https://i.sstatic.net/2nzlp.png" alt="" /></a><br />
<sub>(source: <a href="http://yaroslavvb.com/upload/save/sparse2.png" rel="noreferrer">yaroslavvb.com</a>)</sub><br />
<a href="https://i.sstatic.net/xCMQ8.png" rel="noreferrer"><img src="https://i.sstatic.net/xCMQ8.png" alt="" /></a><br />
<sub>(source: <a href="http://yaroslavvb.com/upload/save/sparse3.png" rel="noreferrer">yaroslavvb.com</a>)</sub></p>
<p>this took 3 minutes on my laptop <a href="http://yaroslavvb.com/upload/save/sparse-matrices.nb" rel="noreferrer">using</a> standard matrix multiplication</p>

CC BY-SA 4.0
2011-01-06T06:13:07.783Z
2019-02-21T09:09:54.487Z
2020-06-17T09:38:08.363Z
Yaroslav Bulatov
<p>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.</p>

<p>Are there any matrix chain product algorithms that work particularly fast in this case?</p>

<p>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.</p>

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

CC BY-SA 3.0
2015-08-28T14:33:47.440Z
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
CC BY-SA 2.5
2010-09-14T15:32:40.017Z
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
<ds.algorithms><automata-theory><matrix-product><sparse-matrix>
Fast sparse boolean matrix chain product
jkff
# Fast sparse boolean matrix chain product

(Asked by: username_0 on 2010-09-09)

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)

**Tags:** ds.algorithms, automata-theory, matrix-product, sparse-matrix

> **Comments:**
> **username_2**: 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.  
> **username_1**: 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  

---

## 1 answers

### Answer by username_3 on 2011-01-06. Score: 10

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%

[![](https://i.sstatic.net/2nzlp.png)](https://i.sstatic.net/2nzlp.png)  
(source: [yaroslavvb.com](http://yaroslavvb.com/upload/save/sparse2.png))  
[![](https://i.sstatic.net/xCMQ8.png)](https://i.sstatic.net/xCMQ8.png)  
(source: [yaroslavvb.com](http://yaroslavvb.com/upload/save/sparse3.png))

this took 3 minutes on my laptop [using](http://yaroslavvb.com/upload/save/sparse-matrices.nb) standard matrix multiplication


---

