Optimal Deterministic Fully Sparse Matrix Multiplication

Abstract

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\mathrm{nnz}(A),\mathrm{nnz}(B)=O(n^{{\delta }_{\mathrm{in}}})$ and $\mathrm{nnz}(AB)=O(n^{{\delta }_{\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\left(n^{{\beta }_R({\delta }_{\mathrm{in}},\min \{{\delta }_{\mathrm{out}},2{\delta }_{\mathrm{in}}\})+\epsilon }\right)$$ operations, where ${\beta }_R({\delta }_{\mathrm{in}},\delta )$ denotes the maximum of ${\delta }_{\mathrm{in}}$ and ${\omega }_{{\delta }_{\mathrm{in}},R}(a,1,b)$ over all $a,b\in [0,1]$ satisfying $a+b=\delta$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{{\omega }_R(({\delta }_{\mathrm{out}}-1{)}_{+},1,1)+\epsilon })$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\epsilon })$, for every ${\delta }_{\mathrm{out}}\le 1.321334$, improving the previous deterministic range of ${\delta }_{\mathrm{out}}\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.