The Time Complexity of Fully Sparse Matrix Multiplication

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 × n b by n b × n c matrices. We discover that when m out = Θ(m r in ) the time complexity of sparse matrix multiplication is O(m σ+ϵ in ), for all ϵ > 0, where σ is the solution to the equation ω

turns out to be, and for all r ∈ (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 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.