12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Warren Schudy Oct 5 '10 at 14:29
  • $\begingroup$ Yes as long as it can be multiplied by Bs further. $\endgroup$ – jkff Oct 5 '10 at 17:46
  • $\begingroup$ 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"? $\endgroup$ – Warren Schudy Oct 5 '10 at 21:52
  • $\begingroup$ 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). $\endgroup$ – jkff Oct 6 '10 at 5:54
11
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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". $\endgroup$ – Ryan Williams Oct 7 '10 at 7:22
  • $\begingroup$ 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)? $\endgroup$ – Alexandre Cassagne Apr 19 '18 at 2:00
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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