文章基本信息

标题：Limits on the Universal Method for Matrix Multiplication
本地全文：下载
作者：Josh Alman
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2021
卷号：17
期号：1
页码：1-30
DOI：10.4086/toc.2021.v017a001
语种：English
出版社：University of Chicago
摘要：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 CWq cannot yield a bound on ω, 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 CWq 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 ω=2 if and only if it is possible for the Universal Method applied to T to achieve ω=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 ω≤2.376, by applying the Laser Method to CWq. By our result, the fact that they did not achieve ω=2 implies a lower bound on the Universal Method applied to CWq.
关键词：matrix multiplication; algebraic complexity