# The Input/Output Complexity of Sparse Matrix Multiplication

Preprint · Rasmus Pagh, Morten Stöckel

- Archive id: arxiv:1403.3551
- Published: 2014-03-14
- arXiv: https://arxiv.org/abs/1403.3551
- Source URL: https://arxiv.org/abs/1403.3551
- PDF: https://arxiv.org/pdf/1403.3551
- Provenance: arxiv

## Abstract

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 \\times U$ matrices, $Θ\\left(U^3 / (B \\sqrt{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 = \\mathtt{nnz}(A)+\\mathtt{nnz}(C)$ of nonzero entries in $A$ and $C$, as well as the number $Z = \\mathtt{nnz}(AC)$ of nonzero entries in $AC$. We show that $AC$ can be computed using $\\tilde{O} \\left(\\tfrac{N}{B} \\min\\left(\\sqrt{\\tfrac{Z}{M}},\\tfrac{N}{M}\\right) \\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 $Ω\\left(\\tfrac{N}{B} \\min\\left(\\sqrt{\\tfrac{Z}{M}},\\tfrac{N}{M}\\right) \\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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.