# The Input/Output Complexity of Sparse Matrix Multiplication

arXiv: https://arxiv.org/abs/1403.3551 · HTML: https://mlsanity.com/paper/1403.3551/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2014.

## Built on by (most cited first, 1 of 1)

- [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024)

## Abstract (arXiv)

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.