Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor

08/18/2017
by   François Le Gall, et al.
0

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(n^2+ϵ) 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 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× n^k matrix by an n^k× 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset