# Fast sparse boolean matrix product with possible preprocessing

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

• 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 Oct 5 '10 at 14:29
• Yes as long as it can be multiplied by Bs further. – jkff Oct 5 '10 at 17:46
• 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 Oct 5 '10 at 21:52
• 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 Oct 6 '10 at 5:54

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.

• 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 Oct 7 '10 at 7:22
• 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 Apr 19 '18 at 2:00

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