Source-linked AI summary
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
François Le Gall, Florent Urrutia
TL;DR
Rectangular matrix multiplication lacks the analogous advances achieved for square multiplication through higher powers of the Coppersmith-Winograd tensor. This paper develops an asymmetric framework and applies it to the fourth power, obtaining improved bounds with applications to algorithms such as all-pairs shortest paths.
Problem
Rectangular matrix multiplication is central to linear-algebra algorithms and applications, motivating whether higher-power Coppersmith-Winograd analyses can improve its complexity.
Method
The paper analyzes the fourth power of the Coppersmith-Winograd tensor asymmetrically, combining terms through the laser method and recursive second and third extractions.
Results
The resulting upper bounds on ω(k) systematically improve prior bounds for values of k other than 1, including ω(3) ≤4.199712 versus 4.207372 previously.
Takeaways & Limitations
These bounds improve algorithms whose bottleneck is rectangular matrix multiplication, including all-pairs shortest paths in directed graphs with bounded weights.
Takeaways & Limitations
The paper discusses only the first type of matrix product for concreteness, although it states that the bounds naturally hold for the other two types.
Abstract
from arXiv · showhide
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\times n^α$ matrix by an $n^α\times 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\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.
1 Introduction
This paper extends higher-power Coppersmith-Winograd analyses to rectangular matrix multiplication, obtaining improved exponent bounds and applications. Its fourth-power analysis yields a stronger dual-exponent bound and systematically faster rectangular products.
- Background: Rectangular matrix multiplication underlies algorithms for shortest paths, transitive closure, subgraph detection, sparse multiplication, computational geometry, and related problems.The rectangular exponent ω(k) measures the arithmetic complexity of multiplying an n×n^k matrix by an n^k×n matrix.
- Our results: The fourth power of the Coppersmith-Winograd tensor extends recent square-multiplication progress to rectangular products through an asymmetric analysis framework.The paper focuses on upper bounds for ω(k), with results summarized in Table 3 and Figure 1.
- Our results: ω(3) ≤4.199712 improves the previous ω(3) ≤4.207372, while the square case recovers ω ≤2.372927.For k=1, the rectangular analysis becomes essentially the prior fourth-power square analysis.
- Our results: The α improvement from the second to fourth power exceeds the first-to-second-power improvement because small ω(k) gains can produce larger α gains near horizontal asymptotes.The paper reports that this pattern differs from the decreasing improvements observed for successive powers in square multiplication.
- Future directions: Higher powers such as 8 or 16 remain an important direction for potentially improving α, while methods may also establish limits on achievable gains.The paper suggests adapting convex-optimization methods from square multiplication to the rectangular setting.
- Applications: The bounds improve essentially all known algorithms based on rectangular multiplication, including bounded-weight all-pairs shortest paths.For Zwick’s shortest-path algorithm, the reported bound changes from μ < 0.5302 to μ < 0.5286.
- Overview of our approach: The approach analyzes all fourth-power terms together with the laser method, using global constraints and recursively applying further extractions.The second extraction decomposes terms into products of fifteen second-power terms; a third extraction analyzes their combined contribution.
2 Preliminaries
This section introduces the notation and tensor concepts used to relate tensor restrictions, degenerations, and border rank to rectangular matrix multiplication. It also presents the laser-method extraction framework used to obtain direct sums suitable for the asymptotic sum inequality.
- General notations and definitions: P(X) denotes rational probability distributions on a finite set X whose values lie strictly between 0 and 1.
- General notations and definitions: A type records the frequency with which each element of a finite set occurs in a mapping.A mapping has type t when each element x occurs exactly t(x)N times.
- Tensors, matrix multiplication and the asymptotic sum inequality: A tensor is represented as a trilinear form over three vector spaces, with formal x, y, and z variables.The matrix multiplication tensor ⟨m, n, p⟩ represents multiplying an m × n matrix by an n × p matrix.
- Tensors, matrix multiplication and the asymptotic sum inequality: A restriction, approximation, or degeneration provides an exact or approximate conversion between tensors that preserves an associated computational relationship.Restrictions are obtained through linear maps, while degenerations are approximations of restrictions.
- Tensors, matrix multiplication and the asymptotic sum inequality: The border rank of a tensor underlies the definition of rectangular matrix-multiplication exponents ω(k), with ω(1) equal to the square-multiplication exponent.
- Tensors, matrix multiplication and the asymptotic sum inequality: Schönhage’s asymptotic sum inequality converts a tensor containing many rectangular matrix-multiplication tensors into an upper bound on ω(k).The paper uses this inequality after extracting a direct sum of isomorphic tensors.
- Coppersmith-Winograd tensor: The fourth power of the Coppersmith-Winograd tensor is organized into terms indexed by triples in S8, with decompositions based on pairs of S4 triples.The tensor is formed from the fourth power Fq^⊗4 and is regrouped into terms Tijk.
- Extraction from a tensor: The laser method extracts direct sums by zeroing variables or tensor terms until the remaining terms no longer share variables.In the graph formulation, extraction removes vertices until the graph becomes edgeless, optionally retaining vertices from a specified subset.
3 First extraction
The first extraction restricts F^⊗N by selecting sequence types with prescribed projections, then uses concavity and symmetry constraints to maximize the surviving direct-sum size. Theorem 3.1 formalizes the resulting restriction into many isomorphic trilinear forms.
- Extraction: The extraction zeros variables so only tensors T_IJK with I, J, and K of types A, B, and C remain.The three variable families are filtered successively according to their corresponding sequence types.
- Counting: The surviving tensors are indexed by mappings a with fixed projections, and their counts are estimated using sequence-type enumerations.The analysis counts both total sequences and sequences of the desired type, using Stirling’s formula asymptotically.
- Optimization: ln g is concave on a convex projection-preserving domain, so every critical point gives a global maximum of g.The projection constraints reduce the optimization to 21 variables, while symmetry reduces the critical-point conditions to 10 nonlinear equations.
- Result: Theorem 3.1 states that, under constraints (C1), (C2), and (C3), F^⊗N restricts to a direct sum of r1 isomorphic trilinear forms.The theorem applies for any positive integer q and any ε > 0.
4 Second extraction
The second extraction analyzes the fourth-power components jointly rather than independently. It imposes global symmetry and type constraints to obtain a direct sum of isomorphic tensors while avoiding constraints that are too strong for rectangular improvement.
- Setup: Components with indices containing zero already represent matrix products, while the remaining components require further extraction.The difficult components include T233, T323, and T332, which are treated separately from the easier terms.
- Joint extraction: Independent term-by-term extractions impose constraints that are too strong, so the method performs a global joint extraction across the fourth-power components.The joint approach couples parameters across terms rather than analyzing each component in isolation.
- Multi-types: For each component, variables are retained only when their sequences have prescribed types, producing tensors V[IJK] of a specified multi-type.The same procedure is applied to x, y, and z variables using multi-types ẼA, ẼB, and ẼC.
- Result: Theorem 4.1 gives a direct sum of r2 tensors isomorphic to the target tensor under constraints (C1), (D1), (D2), and (D3).The constraints include symmetry conditions and relations among the extraction counts.
5 Third extraction
The third extraction handles T211, T121, and T112, the remaining nontrivial components after earlier stages. It uses parameterized type assignments and a joint extraction to convert them into many identical rectangular matrix-product forms.
- Target tensors: The final nontrivial components are T211, T121, and T112, while the other fourth-power components correspond to matrix products.The three remaining tensors are analyzed together after the preceding extractions.
- T211 extraction: T211 is decomposed into t011, t101, t110, and t200, then filtered using type parameters b and 1−b.The x, y, and z variables are retained according to the corresponding projected types.
- Symmetry: T112 and T121 are analyzed by permuting the roles of the x, y, and z variables.The symmetry conditions imply α112 = α121.
- Joint result: A joint extraction combines the three tensors under constraint (E3), yielding a direct sum of trilinear forms with a common matrix-product structure.The number of terms is bounded using N211,X ≤ 4^α211N and N112,X = N121,X ≤ 4^α112N.
6 The full extraction
The full extraction combines the three stages into many identical rectangular matrix products and applies Schönhage’s asymptotic sum inequality. Numerical optimization of the resulting parameter constraints yields upper bounds on ω(k).
- Combination: The three extractions produce r1r2r3 isomorphic trilinear forms, all representing the same matrix product.By the symmetry constraints, the common product has the form ⟨Q^N, Q^N, R^N⟩.
- Asymptotic bound: Schönhage’s asymptotic sum inequality converts the direct sum of rectangular products into an inequality involving ω(k), Q, R, and the extraction parameters.The resulting formal bound is stated in Theorem 6.1.
- Theorem 6.1: Theorem 6.1 supplies the general inequality for parameters satisfying the symmetry, extraction, and type constraints.The theorem applies to q, a, the component functions a_uvw, and rational parameters b and b̃.
- Numerical optimization: Numerical optimization using Maple yields the reported upper bounds on ω(k) and the lower bound on α.The optimization searches over q and all parameters subject to the theorem’s constraints.