论文标题
矩形基质乘法的障碍
Barriers for rectangular matrix multiplication
论文作者
论文摘要
我们研究了将矩形大型矩阵乘以算法问题。我们证明，用于构建矩形矩阵乘法最快算法的方法不能给出最佳的算法。实际上，我们证明了此方法的精确数值障碍。我们的障碍在数值方面都改善了以前已知的障碍，以及它的通用性。我们使用张量的渐近光谱证明了我们的结果。更确切地说，我们至关重要地利用具有特殊代数特性的两个真实张量参数的家族：量子功能和支持功能。特别是，我们证明，通过大铜匠 - 沃尼格拉张量的矩阵乘法$α$的双重指数上的任何下限都不能超过0.625。
We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. We prove our result using the asymptotic spectrum of tensors. More precisely, we crucially make use of two families of real tensor parameters with special algebraic properties: the quantum functionals and the support functionals. In particular, we prove that any lower bound on the dual exponent of matrix multiplication $α$ via the big Coppersmith-Winograd tensors cannot exceed 0.625.
