The Input/Output Complexity of Sparse Matrix Multiplication

We consider the problem of multiplying sparse matrices (over a semiring) where the number of non-zero entries is larger than main memory. In the classical paper of Hong and Kung (STOC '81) it was shown that to compute a product of dense U × U matrices, Theta left(U3 / (B √M) right) I/Os are necessary and sufficient in the I/O model with internal memory size M and memory block size B. In this paper we generalize the upper and lower bounds of Hong and Kung to the sparse case. Our bounds depend of the number N = mathttnnz(A)+mathttnnz(C) of nonzero entries in A and C, as well as the number Z = mathttnnz(AC) of nonzero entries in AC. We show that AC can be computed using tildeO left(tfracNB minleft(√tfracZM,tfracNMright) right) I/Os, with high probability. This is tight (up to polylogarithmic factors) when only semiring operations are allowed, even for dense rectangular matrices: We show a lower bound of Omega left(tfracNB minleft(√tfracZM,tfracNMright) right) I/Os. While our lower bound uses fairly standard techniques, the upper bound makes use of ``compressed matrix multiplication'' sketches, which is new in the context of I/O-efficient algorithms, and a new matrix product size estimation technique that avoids the ``no cancellation'' assumption.