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