<p>I was reluctant to answer this, because the only theoretical result I know of along these lines has my name on the paper...</p>

<p>Theoretically, it is possible to preprocess a dense $n \times n$ Boolean matrix $A$ so that sparse matrix-vector multiplications with $A$ (over the semiring of OR and AND) can be done faster than the naive running time. Probably a significant amount of hacking would be needed to implement it in practice, but I do think it would fare well in practice for large enough $n$ and the right implementation. </p>

<p>(Note: this algorithm is only really useful for the case where one matrix is dense and the other is sparse. This case comes up a lot though, e.g., when computing transitive closure of a sparse graph, the transitive closure matrix will eventually get dense compared to the original adjacency matrix.)</p>

<p>The paper is</p>

<blockquote>
  <p>Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) 2008: 108-120</p>
</blockquote>

<p>and the relevant result from the paper is that for every $\varepsilon > 0$, there is an $O(n^{2+\varepsilon})$ time algorithm that, given any $n \times n$ 0-1 matrix $A$, the following operations are supported:</p>

<p>-- For any vector $v$ with only $t$ nonzeroes, $A v$ can be computed in $O(n(t/k + n/\ell)/\log n)$ time, where $\ell$, $k$ are free parameters satisfying ${\ell \choose k} \leq n^{\varepsilon}$. (One nice setting is $\ell=\log^c n$ and $k=\varepsilon(\log n)/\log \log n$, so that the running time is about $nt/\log n + n^2/\log^c n$ for any desired constant $c$.</p>

<p>-- Row and column updates to $A$ can be computed in $O(n^{1+\varepsilon})$ time.</p>

<p>We used this data structure to give faster theoretical algorithms for APSP in sparse unweighted graphs.</p>

CC BY-SA 3.0
2018-04-19T02:00:54.407Z
Ryan Williams -- I have a quick question: are you aware of, or have you explored any method that generalises to sparse $\{-1, 0, 1\}$-valued matrices (rather than simply Boolean)?
Alexandre Cassagne
CC BY-SA 2.5
2010-10-07T07:22:25.123Z
I just noticed that you also assume that the *output* of the matrix multiplication is also sparse. In that case, there are even faster algorithms; do a web search for "output-sensitive matrix multiplication".
Ryan Williams
CC BY-SA 2.5
2010-10-07T06:35:01.393Z
2010-10-07T06:35:01.393Z
Ryan Williams
<p>I think what you call is a "hypersparse" matrix (nnz &lt; n). I wrote a paper a few years back on how to multiply them. Essentially, it's an outer-product join with a clever multi-way merging to eliminate the realization of intermediate triples.</p>

<p>Buluc and Gilbert, IPDPS 2008:
<a href="http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf" rel="noreferrer">http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf</a> </p>

CC BY-SA 3.0
2011-08-27T21:49:44.633Z
2011-08-27T21:49:44.633Z
Aydin Buluc
<p>What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)?</p>

<p>Actually, I have the advantage that when I'm multiplying A by B, the B's are predefined and I can do arbitrarily complex preprocessing on them. I also know that the results of products are always as sparse as the original matrices.</p>

<p>The "rather naive" algorithm (scan A by rows; for each 1 bit of the A-row, OR the result with the corresponding row of B) turns out very efficient and requires only a couple thousand of CPU instructions to compute a single product, so it won't be easy to surpass it, and it's only surpassable by a constant factor (because there are hundreds of one bits in the result). But I'm not losing hope and asking the community for help :)</p>

CC BY-SA 2.5
2010-10-05T14:29:52.947Z
I doubt we can significantly beat a constant of 10 machine instructions per word of output. Is it possible that some implicit form of the output would be acceptable?
Warren Schudy
CC BY-SA 2.5
2010-10-05T17:46:42.580Z
Yes as long as it can be multiplied by Bs further.
jkff
CC BY-SA 2.5
2010-10-05T21:52:45.347Z
What are the addition and multiplication operations (for bits) that matrix multiplication is defined based on? Your naive algorithm suggests the answer is "or" and "and" respectively, but that's a rather weird matrix multiplication since those don't define a field. Do you mean "xor" instead of "or"?
Warren Schudy
CC BY-SA 2.5
2010-10-06T05:54:39.847Z
No, I mean "or" and "and". I don't need the operations to define a field, that's actually a graph reachability-like problem (I'm computing the composition of several one-to-many functions).
jkff
<ds.algorithms><matrix-product><sparse-matrix><boolean-matrix><implementation>
Fast sparse boolean matrix product with possible preprocessing
jkff
# Fast sparse boolean matrix product with possible preprocessing

(Asked by: username_0 on 2010-10-05)

What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)?

Actually, I have the advantage that when I'm multiplying A by B, the B's are predefined and I can do arbitrarily complex preprocessing on them. I also know that the results of products are always as sparse as the original matrices.

The "rather naive" algorithm (scan A by rows; for each 1 bit of the A-row, OR the result with the corresponding row of B) turns out very efficient and requires only a couple thousand of CPU instructions to compute a single product, so it won't be easy to surpass it, and it's only surpassable by a constant factor (because there are hundreds of one bits in the result). But I'm not losing hope and asking the community for help :)

**Tags:** ds.algorithms, matrix-product, sparse-matrix, boolean-matrix, implementation
> **Comments:**
> **username_1**: I doubt we can significantly beat a constant of 10 machine instructions per word of output. Is it possible that some implicit form of the output would be acceptable?  
> **username_0**: Yes as long as it can be multiplied by Bs further.  
> **username_1**: What are the addition and multiplication operations (for bits) that matrix multiplication is defined based on? Your naive algorithm suggests the answer is "or" and "and" respectively, but that's a rather weird matrix multiplication since those don't define a field. Do you mean "xor" instead of "or"?  
> **username_0**: No, I mean "or" and "and". I don't need the operations to define a field, that's actually a graph reachability-like problem (I'm computing the composition of several one-to-many functions).  

---

## 2 answers

### Answer by username_2 on 2010-10-07. Score: 12

I was reluctant to answer this, because the only theoretical result I know of along these lines has my name on the paper...

Theoretically, it is possible to preprocess a dense $n \times n$ Boolean matrix $A$ so that sparse matrix-vector multiplications with $A$ (over the semiring of OR and AND) can be done faster than the naive running time. Probably a significant amount of hacking would be needed to implement it in practice, but I do think it would fare well in practice for large enough $n$ and the right implementation.

(Note: this algorithm is only really useful for the case where one matrix is dense and the other is sparse. This case comes up a lot though, e.g., when computing transitive closure of a sparse graph, the transitive closure matrix will eventually get dense compared to the original adjacency matrix.)

The paper is

> Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) 2008: 108-120

and the relevant result from the paper is that for every $\varepsilon > 0$, there is an $O(n^{2+\varepsilon})$ time algorithm that, given any $n \times n$ 0-1 matrix $A$, the following operations are supported:

-- For any vector $v$ with only $t$ nonzeroes, $A v$ can be computed in $O(n(t/k + n/\ell)/\log n)$ time, where $\ell$, $k$ are free parameters satisfying ${\ell \choose k} \leq n^{\varepsilon}$. (One nice setting is $\ell=\log^c n$ and $k=\varepsilon(\log n)/\log \log n$, so that the running time is about $nt/\log n + n^2/\log^c n$ for any desired constant $c$.

-- Row and column updates to $A$ can be computed in $O(n^{1+\varepsilon})$ time.

We used this data structure to give faster theoretical algorithms for APSP in sparse unweighted graphs.

> **Comments:**
> **username_2**: I just noticed that you also assume that the *output* of the matrix multiplication is also sparse. In that case, there are even faster algorithms; do a web search for "output-sensitive matrix multiplication".  
> **username_3**: Ryan Williams -- I have a quick question: are you aware of, or have you explored any method that generalises to sparse $\{-1, 0, 1\}$-valued matrices (rather than simply Boolean)?  

---

### Answer by username_4 on 2011-08-27. Score: 5

I think what you call is a "hypersparse" matrix (nnz < n). I wrote a paper a few years back on how to multiply them. Essentially, it's an outer-product join with a clever multi-way merging to eliminate the realization of intermediate triples.

Buluc and Gilbert, IPDPS 2008:
<http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf>


---

