Limits on the Universal method for matrix multiplication
Limits on the Universal method for matrix multiplication
复制标题
矩阵乘法通用方法的限制
DOI：
10.4230/lipics.ccc.2019.12
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Josh Alman
中科院分区：
文献类型：
--
作者：
Josh Alman
在这项工作中，我们证明了设计矩阵乘法算法的已知方法的局限性。理论方法[9]。我们的证明使用新工具用于上限的不对称切片等级，我们的主要结果是应用于任何Coppersmith-Winograd tensor CWQ无法在ω上产生一个比矩阵乘法的指数， 2.16805。 （原则上，这是通用方法的高度特殊情况）并证明它是矩阵乘法算法的“完整”：当它适用于张量t时，它才能达到ω= 2，并且仅在可能的情况下才能实现。通用方法应用于t，以实现ω= 2。因此，最初用作算法工具的激光方法也可以看作是一个下限工具。 Winograd [12]通过将激光方法应用于CWQ，达到了ω≤2.376的结合应用于CWQ的通用方法可以实现ω= 2，然后Coppersmith和Winograd应用激光方法将达到ω= 2。
In this work, we prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams [2] recently defined the Universal Method, which substantially generalizes all the known approaches including Strassen's Laser Method [20] and Cohn and Umans' Group Theoretic Method [9]. 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 for upper bounding 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. By comparison, it was previously only known that the weaker "Galactic Method" applied to CWq could not achieve an exponent of 2. We also study the Laser Method (which is, in principle, a highly 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 bounding tool. For example, in their landmark paper, Coppersmith and Winograd [12] 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. Indeed, if it were possible for the Universal Method applied to CWq to achieve ω = 2, then Coppersmith and Winograd's application of the Laser Method would have achieved ω = 2.
DOI：
10.4230/lipics.itcs.2018.25
发表时间：
2018
期刊：
9th Innovations in Theoretical Computer Science Conference (ITCS 2018
影响因子：
--
作者：
Alman, J.;Vassilevska Williams, V.
通讯作者：
Vassilevska Williams, V.