PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster Algorithms for Rectangular Matrix Multiplication

François Le Gall

arXiv:1204.1111v2cs.DScs.CCcs.SC

TL;DR

Rectangular matrix multiplication needs stronger exponent bounds because it underlies numerous algorithms beyond dense square multiplication. The paper analyzes F_q ⊗ F_q directly in the rectangular setting, proving a higher α threshold and improved bounds for all k ≠ 1 while recovering the Coppersmith–Winograd bound at k = 1. These results improve applications including all-pairs shortest paths and sparse square matrix multiplication.

  • Problem

    The paper addresses limited exponent bounds for rectangular matrix multiplication, whose complexity affects graph algorithms, sparse multiplication, and other computational tasks.

  • Method

    The paper uses the tensor power F_q ⊗ F_q as a basic construction and analyzes it in a rectangular-multiplication framework formulated as a nonlinear optimization problem.

  • Results

    α > 0.30298, improving Coppersmith’s α > 0.29462; for k > 0.29462 and k ≠ 1, the algorithm beats all known rectangular algorithms, while k = 1 recovers ω(1, 1, 1) < 2.375477.

  • Takeaways & Limitations

    The new rectangular bounds improve algorithms relying on rectangular multiplication, including a randomized O(n^2.5302) all-pairs shortest-path algorithm and sparse square matrix multiplication.

  • Takeaways & Limitations

    Extending the analysis to higher tensor powers is more difficult because the construction is nonsymmetric and the smaller parts lack the square-case value analysis.

Abstract

from arXiv · show

Let α be the maximal value such that the product of an n x n^α matrix by an n^α x n matrix can be computed with n^{2+o(1)} arithmetic operations. In this paper we show that α>0.30298, which improves the previous record α>0.29462 by Coppersmith (Journal of Complexity, 1997). More generally, we construct a new algorithm for multiplying an n x n^k matrix by an n^k x n matrix, for any value k\neq 1. The complexity of this algorithm is better than all known algorithms for rectangular matrix multiplication. In the case of square matrix multiplication (i.e., for k=1), we recover exactly the complexity of the algorithm by Coppersmith and Winograd (Journal of Symbolic Computation, 1990). These new upper bounds can be used to improve the time complexity of several known algorithms that rely on rectangular matrix multiplication. For example, we directly obtain a O(n^{2.5302})-time algorithm for the all-pairs shortest paths problem over directed graphs with small integer weights, improving over the O(n^{2.575})-time algorithm by Zwick (JACM 2002), and also improve the time complexity of sparse square matrix multiplication.

1 Introduction

The paper develops faster algorithms for rectangular matrix multiplication by applying the Coppersmith–Winograd framework to tensor powers and analyzing the resulting constructions directly in the rectangular setting. It improves the exponent threshold α, yields stronger bounds across rectangular shapes, and translates these gains into faster graph and sparse-matrix algorithms.

  • Motivation: Matrix multiplication is a central computational problem whose complexity affects linear algebra and many graph algorithms.The standard cubic algorithm was improved by Strassen, motivating continued work on matrix-multiplication exponents.
  • Applications: The bounds improve downstream algorithms, including sparse matrix multiplication and all-pairs shortest paths in weighted directed graphs.They yield O(n^2.087) for sparse products with m = n^(4/3) and a randomized O(n^2.5302) all-pairs shortest-path algorithm for bounded integer weights.
  • Approach: The new algorithm uses F_q ⊗ F_q as its basic construction and analyzes it through a rectangular-matrix-multiplication framework.The analysis produces a nonlinear optimization problem that gives upper bounds on ω(1, 1, k) for any k.
  • Results: α > 0.30298, improving Coppersmith’s previous record α > 0.29462 for near-quadratic rectangular multiplication.For every k < 0.3029805, the product of an n × n^k matrix by an n^k × n matrix takes O(n^(2+ε)) arithmetic operations for any constant ε > 0.
  • Results: At k = 1, the method recovers ω(1, 1, 1) < 2.375477, matching the Coppersmith–Winograd square-matrix bound.The approach can also be combined with ω < 2.3727 to obtain slightly improved bounds near k = 1.
  • Results: For k > 0.29462 and k ≠ 1, the algorithm has lower complexity than all previously known rectangular matrix-multiplication algorithms.For 0.30298 < k < 1, its bounds are significantly better than those obtained from simple interpolation between α > 0.30298 and ω < 2.375477.
  • Techniques and limitations: The key technical contribution is a global laser-method analysis that combines complementary C-tensors from T112, T121, and T211.For higher tensor powers, the nonsymmetric construction and the lack of a square-case value analysis require additional techniques for a systematic framework.

2 Preliminaries

The preliminaries introduce trilinear forms and tensors, then develop degeneration, direct sums, C-tensors, and combinatorial degenerations as tools for bounding rectangular matrix multiplication.

  • Trilinear forms and tensors: Trilinear forms are represented as tensors over three vector spaces, with coefficients indexed by basis elements.The tensor format is (u, v, w), and the tensor for multiplying an m × n matrix by an n × p matrix is denoted ⟨m, n, p⟩.
  • Degeneration and asymptotic inequalities: A degeneration approximately converts one tensor into another while preserving essentially the same computational complexity.Degenerations are defined using polynomial matrix transformations and underpin border-rank arguments.
  • Degeneration and asymptotic inequalities: Schönhage’s asymptotic sum inequality converts a degeneration into a direct sum of rectangular matrix-multiplication tensors into an exponent bound.If t degenerates into c copies of ⟨m, m, m^k⟩, then c · m^ω(1,1,k) ≤ R(t).
  • C-tensors and combinatorial degeneration: A C-tensor is decomposed into components indexed by triples, and its support records exactly which components are nonzero.For matrix multiplication, the complete decomposition yields a support indexed by compatible triples of matrix indices.

3 Coppersmith-Winograd’s construction

This section presents the Coppersmith-Winograd construction and its tensor-square basis, whose components are analyzed as matrix products or as more difficult forms requiring the paper’s new techniques.

  • Construction: The paper uses Coppersmith and Winograd’s construction as the basis for its rectangular matrix-multiplication algorithm.The construction is the tensor product Fq ⊗ Fq, together with properties needed for later analysis.
  • Construction: Fq is a trilinear form with q + 2 variables in each of the x, y, and z variable families.Its variables are indexed x0,…,xq+1 and analogously for y and z.
  • Construction: Fq contains the cyclic products x0yizi + xiy0zi + xiyiz0 and three additional terms involving index q + 1.The displayed expression also includes x0y0zq+1, x0yq+1z0, and xq+1y0z0.
  • Tensor square: The tensor-square construction Fq ⊗ Fq uses (q + 2)^2 multiplications and decomposes into indexed forms Tijk.Its terms include T004, T040, T400, T013, T031, T103, T130, T301, and T310, with other terms generated by permutations.
  • Tensor-square components: Most forms Tijk correspond directly to matrix products, but T112, T121, and T211 require separate analysis.For example, T220 is isomorphic to ⟨1, q^2 + 2, 1⟩, while T013 represents multiplying a scalar by a 1 × 2q row.

4 Graph-Theoretic Problems

This section formulates graph-theoretic pruning problems that support the paper’s rectangular matrix-multiplication algorithms. Its generalizations use restricted vertex removals to obtain either large edgeless subgraphs or disjoint unions of large 1-cliques.

  • Graph construction: Distinct vertices in Λ cannot agree under more than one coordinate function, a fact used to characterize graph edges.The coordinate functions and the associated fibers define the graph’s structure.
  • Graph construction: The graph G connects two vertices exactly when they agree under one of the three coordinate functions, and allowed removals delete vertices sharing a specified sequence at one position.These removals model setting variables to zero in trilinear forms.
  • First pruning result: The first generalization converts G, using only removal operations, into an edgeless graph whose remaining vertices all lie in U*.Theorem 4.2 extends the earlier result and includes it when U* = U.
  • Second pruning result: The second generalization produces many large 1-cliques in U*, with no edges between distinct cliques after pruning.At least Ω(T1/N^ε) cliques have size Ω(N*1/N2), according to the stated theorem.
  • Compatibility and pruning: Compatibility is defined by requiring all three hash values bi(fi(u)) to lie in a Salem-Spencer set Γ, enabling the pruning analysis.The paper shows equivalently that two distinct hash values agreeing on an element of Γ imply compatibility across all three coordinates.
  • Compatibility and pruning: The pruning procedure greedily selects isolated compatible vertices, and a suitable random choice of hash weights yields the required edgeless or clique-union subgraphs.The argument bounds removed vertices through the edge set and then fixes a weight choice attaining the expectation.

5 Algorithm for Rectangular Matrix Multiplication

The algorithm raises rectangular matrix-multiplication bounds to a nonlinear optimization over parameterized tensor constructions. Tensor powers are restricted and zeroed to produce many disjoint, isomorphic forms that can be converted into direct sums of matrix multiplications.

  • Construction: The construction starts from (Fq ⊗ Fq)⊗N and parameterizes tensor types using rational values aijk satisfying normalization and feasibility conditions.The parameters define sequence types A and B and the admissible multiplicities of the fifteen index combinations.
  • Restriction: Zeroing variables by prescribed sequence types leaves precisely those forms whose indices satisfy the selected type constraints.The remaining forms have first index of type A and second and third indices of type B, yielding equal counts NY = NZ.
  • Counting and optimization: The number of admissible parameter choices is polynomially bounded in N, while the relevant counts are approximated using Stirling’s formula and optimized through concavity.The logarithm of the objective is concave on a convex domain, so a local optimum is a global maximum.
  • Direct-sum conversion: The graph-theoretic framework converts variable-removal operations into a direct sum of forms with disjoint indices.Disjoint indices ensure that no variable appears in more than one form, so the resulting sum is direct.
  • Result: Theorem 5.1 shows that (Fq ⊗ Fq)⊗N can be converted, for any ε > 0, into a direct sum of many forms of the chosen type.The theorem applies to positive rational parameters satisfying the stated conditions.

6 Upper Bounds on the Exponent of Rectangular Matrix Multiplication

The smaller tensor components are transformed into C-tensors whose supports and components encode rectangular matrix products. Combining these transformations with the asymptotic sum inequality yields an upper bound on ω(1, 1, k) dependent on the construction parameters.

  • Component analysis: All smaller forms except T112, T121, and T211 directly correspond to matrix multiplications; the three exceptional forms require separate analysis.The section analyzes the exceptional forms before assembling the full bound.
  • T211: T211 tensor powers yield C-tensors with support isomorphic to suppc(⟨1, 1, H⟩) and components isomorphic to ⟨q2bm, q2bm, q2(1−b)m⟩.This follows after decomposing T211 and zeroing variables according to sequence-count constraints.
  • T112 and T121: Permuting variable roles gives analogous C-tensor decompositions for T112 and T121, with supports ⟨1, H, 1⟩ and ⟨H, 1, 1⟩.Their components are rectangular matrix multiplications with the corresponding permuted dimensions.
  • Main bound: The main theorem converts the original tensor into a direct sum of r1r2 matrix multiplications and derives an upper bound on ω(1, 1, k) from the resulting quantities.The bound is obtained after applying the asymptotic sum framework to the direct-sum decomposition.

7 Optimization

The paper evaluates its parameterized upper bound through nonlinear optimization and obtains numerical bounds for rectangular multiplication, while matching the Coppersmith–Winograd square-multiplication exponent. A separate constrained analysis establishes α > 0.30298.

  • Square matrix multiplication: For square multiplication, symmetry reduces the parameters, and choosing q = 6 with the stated values gives ω(1, 1, 1) < 2.375477.The paper states that this is exactly the same upper bound obtained by Coppersmith and Winograd.
  • Square matrix multiplication: The square-case optimization becomes exactly the same optimization problem as in Coppersmith and Winograd’s analysis.The equality follows from the symmetric parameter choices and the resulting specialization of the theorem.
  • Rectangular bounds: The rectangular bounds are obtained by solving the theorem’s nonlinear optimization problem numerically, including ω(1, 1, 0.5302) < 2.060396, ω(1, 1, 0.75) < 2.190087, and ω(1, 1, 2) < 3.256689.The paper reports exact parameter values for these examples in Table 2.
  • The value α: The α analysis imposes the equality MQ2 = (q + 2)2 and determines most parameters analytically before optimizing the remaining ones.The equality condition is required to establish the desired n^{2+ε} arithmetic-operation regime.
  • The value α: Using q = 5 and the stated parameter values gives α ≥ log R / log Q > 0.30298.A higher-precision Maple optimization is also used to refine the lower bound.
Loading 1204.1111v2…