# The Time Complexity of Fully Sparse Matrix Multiplication

Preprint · Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann

- Archive id: arxiv:2309.06317
- Published: 2023-09-12
- arXiv: https://arxiv.org/abs/2309.06317
- Source URL: https://arxiv.org/abs/2309.06317
- PDF: https://arxiv.org/pdf/2309.06317
- Provenance: arxiv

## Abstract

What is the time complexity of matrix multiplication of sparse integer matrices with $m\_{in}$ nonzeros in the input and $m\_{out}$ nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of $m\_{in}$ vs. $m\_{out}$, and provides evidence that these new bounds might be optimal up to further progress on fast matrix multiplication. Our main contribution is a new algorithm that reduces sparse matrix multiplication to dense (but smaller) rectangular matrix multiplication. Our running time thus depends on the optimal exponent $ω(a,b,c)$ of multiplying dense $n^a\\times n^b$ by $n^b\\times n^c$ matrices. We discover that when $m\_{out}=Θ(m\_{in}^r)$ the time complexity of sparse matrix multiplication is $O(m\_{in}^{σ+ε})$, for all $ε\> 0$, where $σ$ is the solution to the equation $ω(σ-1,2-σ,1+r-σ)=σ$. No matter what $ω(\\cdot,\\cdot,\\cdot)$ turns out to be, and for all $r\\in(0,2)$, the new bound beats the state of the art, and we provide evidence that it is optimal based on the complexity of the all-edge triangle problem. In particular, in terms of the input plus output size $m = m\_{in} + m\_{out}$ our algorithm runs in time $O(m^{1.3459})$. Even for Boolean matrices, this improves over the previous $m^{\\frac{2ω}{ω+1}+ε}=O(m^{1.4071})$ bound \[Amossen, Pagh; 2009\], which was a natural barrier since it coincides with the longstanding bound of all-edge triangle in sparse graphs \[Alon, Yuster, Zwick; 1994\]. We find it interesting that matrix multiplication can be solved faster than triangle detection in this natural setting. In fact, we establish an equivalence to a special case of the all-edge triangle problem.

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