论文标题
精制激光方法和更快的矩阵乘法
A Refined Laser Method and Faster Matrix Multiplication
论文作者
论文摘要
矩阵乘法的复杂性是用$ω$的，最小的实际数字，因此可以使用$ o（n^{ω+ε}）$ field of to乘以$ε> 0 $的两个$ n \ times n $矩阵；到目前为止，最好的界限是$ω<2.37287 $ [le gall'14]。自1986年以来，使用所谓的激光方法获得了$ω$的所有界限，这是一种在设计矩阵乘法算法时降低张量的“值”的方法。本文的主要结果是对激光方法的改进，该方法改善了最大张量的最大值绑定的结果。因此，即使在计算任何特定值之前，很明显，我们在$ω$上实现了改进的限制，并且我们确实获得了迄今为止$ω$的最佳限制：$$ω<2.37286。$ $ $$的改进与以前的[vassilevska w.'12]获得的[le gall'14]相同的改进与[le gall'14]的进步相同。我们对激光方法的改进非常笼统，我们认为它将在算术复杂性中进一步应用。
The complexity of matrix multiplication is measured in terms of $ω$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n^{ω+ε})$ field operations for all $ε>0$; the best bound until now is $ω<2.37287$ [Le Gall'14]. All bounds on $ω$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $ω$, and we indeed obtain the best bound on $ω$ to date: $$ω< 2.37286.$$ The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.
