Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
François Le Gall, Florent Urrutia · Society for Industrial and Applied Mathematics eBooks · 2018
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 α denote the maximum value such that the product of an n × nα matrix by an nα × n matrix can be computed with O(n2+∊) arithmetic operations for any ∊ > 0. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound α > 0.31389, which improves the previous lower bound α > 0.30298 obtained 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 × nk matrix by an nk × n matrix for any value k ≠ 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.