2017/08/31 by François Le Gall, Florent Urrutia · 3 citations
Computer Science · Mathematics · #Arithmetic #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Geometry #Mathematics #Matrix (chemical analysis) #Matrix multiplication #Multiplication (music) #Parallel Computing and Optimization Techniques #Physics #Pure mathematics #Square (algebra) #Square matrix #Symmetric matrix #Tensor (intrinsic definition) #Tensor decomposition and applications #Tensor product #acm:65F60 #acm:68Q25 #cs.CC #cs.DS #msc:65F60 #msc:68Q25
paper · pdf · doi:10.1137/1.9781611975031.67
published as Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1029-1046, 2018 · 30 pages
arxiv created 2017/11/06 · openalex publication_date 2018/01/01 · arxiv updated 2021/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 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× 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.