论文标题
通过非对称哈希的更快矩阵乘法
Faster Matrix Multiplication via Asymmetric Hashing
论文作者
论文摘要
快速矩阵乘法是算法研究中最根本的问题之一。矩阵乘法的最佳时间复杂性的指数通常用$ω$表示。本文讨论了改善快速矩阵乘法的激光方法的新想法。我们观察到，对Coppersmith-Winograd Tensor的较高力量的分析[Coppersmith＆Winograd 1990]会导致“组合损失”，并且我们使用CW的Hashing方法的不对称版本对其进行了部分补偿。通过分析CW张量的第八功率，我们提供了$ω<2.371866 $的新限制，这改善了以前的最佳限制$ω<2.372860 $ [Alman＆Vassilevska Williams 2020]。我们的结果破坏了[Ambainis，Filmus＆Le Gall 2015]的$ 2.3725 $的下限，这是由于分析组件（组成）张量的新方法。
Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $ω$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a "combination loss", and we partially compensate for it using an asymmetric version of CW's hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $ω<2.371866$, which improves the previous best bound of $ω<2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of $2.3725$ in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.
