Theory of Computing
-------------------
Title : Limits on the Universal Method for Matrix Multiplication
Authors : Josh Alman
Volume : 17
Number : 1
Pages : 1-30
URL : http://www.theoryofcomputing.org/articles/v017a001
Abstract
--------
We prove limitations on the known methods for designing matrix
multiplication algorithms. Alman and Vassilevska Williams (FOCS'18)
recently defined the _Universal Method_, which generalizes all the
known approaches, including Strassen's Laser Method (J. reine angew.
Math., 1987) and Cohn and Umans's Group Theoretic Method (FOCS'03). We
prove concrete lower bounds on the algorithms one can design by
applying the Universal Method to many different tensors. Our proofs
use new tools to give upper bounds on the _asymptotic slice rank_ of a
wide range of tensors. Our main result is that the Universal Method
applied to any Coppersmith--Winograd tensor CW_q cannot yield a
bound on \omega, the exponent of matrix multiplication, better than
2.16805. It was previously known (Alman and Vassilevska Williams,
FOCS'18) that the weaker "Galactic Method" applied to CW_q could not
achieve an exponent of 2.
We also study the Laser Method (which is a special case of the
Universal Method) and prove that it is "complete" for matrix
multiplication algorithms: when it applies to a tensor T, it
achieves \omega = 2 if and only if it is possible for the Universal
Method applied to T to achieve \omega = 2. Hence, the Laser
Method, which was originally used as an algorithmic tool, can also be
seen as a lower-bound tool for a large class of algorithms. For
example, in their landmark paper, Coppersmith and Winograd (J.
Symbolic Computation, 1990) achieved a bound of \omega \leq 2.376,
by applying the Laser Method to CW_q. By our result, the fact that
they did not achieve \omega=2 _implies_ a lower bound on the
Universal Method applied to CW_q.
--------------
A conference version of this paper appeared in the
34th Computational Complexity Conference, 2019.
Supported in part by NSF grants CCF-1651838 and CCF-1741615.
The work reported here was done while the author was
a Ph.D. student at MIT.