New limits found for fast matrix multiplication methods
Multiplying matrices via polynomials: exposition and barriers
Computational Complexity
Summary
Multiplying big grids of numbers, called matrices, takes time. This paper explains a recent way to multiply matrices faster using polynomials, which are math expressions with variables. The authors show the fastest possible speed for these methods and also prove that improving them with current techniques is impossible. They use advanced math ideas about how these multiplications relate to each other in a deeper way.
What this means in practice
- •For high performance computing engineers: Design matrix multiplication routines knowing current methods cannot be improved by these polynomial degeneration techniques.
- •For machine learning systems developers: Set realistic expectations for matrix operations speed in deep learning frameworks based on proven complexity limits.
A theory result. No direct application yet.
Authors
Alimzhan Amanov, Maxim van den Berg, Jeroen Zuiddam
Abstract
We give an exposition of OpenAI's recent proof that the exponent $ω_\mathbb{C}$ of matrix multiplication over the complex numbers satisfies $ω_\mathbb{C}\leq9/4$. Our version of the proof gives $ω_\mathbb{F}\leq9/4$ over every field $\mathbb{F}$. We also treat the rectangular matrix multiplication exponent $ω_\mathbb{F}(a,b,c)$. Here we have $ω_\mathbb{F}(1,k,1)=2$ for $0\leq k\leq1/2$ and $ω_\mathbb{F}(1,k,1)\leq1+k+1/(4k)$ for $k\geq1/2$, and, for real numbers $a\geq b\geq c\geq0$, $ω_\mathbb{F}(a,b,c)=a+b$ if $c(a+b)\leq ab$ and $ω_\mathbb{F}(a,b,c)\leq(a+b+c)/2+(ab/c+ac/b+bc/a)/4$ otherwise. Our exposition is in the language of degeneration inequalities among polynomial multiplication tensors and Strassen's asymptotic spectrum duality. We moreover prove an operational barrier (which can be thought of as coming from an operational asymptotic spectrum) showing that the current analysis of all these upper bounds on $ω_\mathbb{F}$ and $ω_\mathbb{F}(a,b,c)$ is optimal and that in fact the current degeneration ingredients cannot improve the bounds.