Barriers for rectangular matrix multiplication
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
我们研究乘以长方形的大矩阵的算法问题。 我们证明,已经用于构建矩形矩阵乘法的最快算法的方法不能给出具有复杂度的 n^p + 1 for n × n× n by n × n^p matrix 乘法的算法。 事实上,我们证明了这种方法的精确数值障碍。 我们的屏障改善了以前已知的障碍,无论是在数字意义上,还是在其一般性。 特别是,我们证明,通过大铜匠-温格勒张量器的矩阵乘法α双分位值上的任何下限不能超过0.6218。
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 algorithms with complexity n^p + 1 for n × n by n × n^p matrix multiplication. 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. In particular, we prove that any...