Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
复制标题
DOI：
10.1137/1.9781611975031.67
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
F. Gall;Florent Urrutia
中科院分区：
文献类型：
--
作者：
F. Gall;Florent Urrutia
在过去的几年里，通过开发新的方法来分析库珀史密斯-维诺格拉德张量（三十年前引入的基本结构）的幂，方阵乘法的渐近复杂性得到了连续的改进。在本文中，我们展示了如何通过开发一个以非对称方式分析张量幂的框架来推广这种方法，以在矩形矩阵乘法的复杂性方面取得进展。通过将此方法应用于 Coppersmith-Winograd 张量的四次方，我们成功地提高了矩形矩阵乘法的复杂性。令 $\alpha$ 表示最大值，使得对于任何 $\epsilon>0$，$n\times n^\alpha$ 矩阵与 $n^\alpha\times n$ 矩阵的乘积可以通过 $O(n^{2+\epsilon})$ 算术运算来计算。通过使用我们的方法分析 Coppersmith-Winograd 张量的四次方，我们获得了新的下界 $\alpha>0.31389$，这改进了 Le Gall (FOCS'12) 五年前通过分析 Coppersmith-Winograd 张量的二次方获得的先前下界 $\alpha>0.30298$。更一般地说，我们给出更快的算法，计算 $n\times n^k$ 矩阵与 $n^k\times n$ 矩阵的乘积，对于任何值 $k\neq 1$。 （在 $k=1$ 的情况下，我们恢复最近获得的方阵乘法的边界）。这些改进立即导致了许多基本问题的复杂性的提高，这些问题的瓶颈是矩形矩阵乘法，例如计算具有有界权重的有向图中的全对最短路径。
In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we show how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, we succeed in improving the complexity of rectangular matrix multiplication. Let $\alpha$ denote the maximum value such that the product of an $n\times n^\alpha$ matrix by an $n^\alpha\times n$ matrix can be computed with $O(n^{2+\epsilon})$ arithmetic operations for any $\epsilon>0$. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound $\alpha>0.31389$, which improves the previous lower bound $\alpha>0.30298$ obtained five years ago by Le Gall (FOCS'12) from the analysis of the second power of the Coppersmith-Winograd tensor. More generally, we give faster algorithms computing the product of an $n\times n^k$ matrix by an $n^k\times n$ matrix for any value $k\neq 1$. (In the case $k=1$, we recover the bounds recently obtained for square matrix multiplication). These improvements immediately lead to improvements in the complexity of a multitude of fundamental problems for which the bottleneck is rectangular matrix multiplication, such as computing the all-pair shortest paths in directed graphs with bounded weights.