KIT | KIT-Bibliothek | Impressum | Datenschutz

The Time Complexity of Fully Sparse Matrix Multiplication

Abboud, Amir; Bringmann, Karl; Fischer, Nick; Künnemann, Marvin 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

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×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 $ω(σ−1,2−σ,1+r−σ)=σ$. No matter what $ω(⋅,⋅,⋅)$ 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})$. ... mehr


Volltext §
DOI: 10.5445/IR/1000170471
Veröffentlicht am 06.05.2024
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2023
Sprache Englisch
Identifikator ISBN: 978-1-61197-791-2
KITopen-ID: 1000170471
Umfang 46 S.
Vorab online veröffentlicht am 12.09.2023
Nachgewiesen in arXiv
Dimensions
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page