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, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Theta \left( U^3 / (B \sqrt{M}) \right)$\end{document} 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 = nnz(A)+nnz(C) of nonzero entries in A and C, as well as the number Z =nnz(AC) of nonzero entries in AC.

We show that using \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O} \left( \tfrac{N}{B} \min\left(\sqrt{\tfrac{Z}{M}},\tfrac{N}{M}\right) \right)$\end{document} I/Os, AC can be computed 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega \left( \tfrac{N}{B} \min\left(\sqrt{\tfrac{Z}{M}},\tfrac{N}{M}\right) \right)$\end{document} 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.