PaperlayerView exact revision on arXiv

Source-linked AI summary

A Refined Laser Method and Faster Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

arXiv:2010.05846v2cs.DScs.CCmath.CO

TL;DR

The paper addresses how to improve bounds on the matrix multiplication exponent obtained through the laser method. It introduces a refined laser method that improves tensor value bounds for most sufficiently large tensors and obtains ω < 2.3728596, improving the prior bound of 2.37287.

  • Problem

    The paper studies how to improve the best upper bound on the matrix multiplication exponent ω, whose prior bound was ω < 2.37287.

  • Method

    The paper introduces a refined version of the laser method for lower-bounding the value of tensors used to design matrix multiplication algorithms.

  • Results

    ω < 2.3728596 is obtained, improving the prior bound of 2.37287.

  • Takeaways & Limitations

    The refined method improves laser-method value bounds for almost any sufficiently large tensor, including most tensors arising in prior bounds on ω.

Abstract

from arXiv · show

The complexity of matrix multiplication is measured in terms of $ω$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n^{ω+ε})$ field operations for all $ε>0$; the best bound until now is $ω<2.37287$ [Le Gall'14]. All bounds on $ω$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $ω$, and we indeed obtain the best bound on $ω$ to date: $$ω< 2.37286.$$ The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.

A Refined Laser Method

The supplied section identifies a work on faster matrix multiplication and a refined laser method.

  • The paper concerns faster matrix multiplication.
  • The paper is authored by Josh Alman and Virginia Vassilevska Williams.
  • Its listed keywords include matrix multiplication, algorithms, the laser method, tensors, and omega.

1. Introduction

The paper refines the laser method for bounding the value of tensors used in matrix multiplication, improving the best known exponent bound to ω < 2.3728596. Its improvement applies broadly to sufficiently large tensors, while the refined method retains known limitations for some tensor families.

  • Motivation: ω is the smallest real number for which n×n matrices can be multiplied using O(n^(ω+ε)) field operations for every ε > 0.
  • The Laser Method and Our Improvement: The laser method lower-bounds tensor value by zeroing variables in T^⊗n so the remainder becomes a direct sum of consistent matrix multiplication subtensors.
  • Results: The method improves prior laser-method results for almost any sufficiently large tensor, including most tensors used in previous bounds on ω.
  • Results: ω < 2.3728596 is the paper’s resulting bound, improving the prior bound of 2.37287.
  • Limitations: The laser method and its refined version cannot achieve ω < 2.3725 for the tensor families covered by the cited limitation result.
  • Motivation: Fast matrix multiplication algorithms since the 1980s have used an intermediate tensor together with an algorithm for computing it and a high-value matrix multiplication restriction.
  • The Laser Method and Our Improvement: The refined method addresses a marginal-distribution condition in the laser method and improves the number of retained consistent subtensors by a factor of Θ(√m).

2. Preliminaries

This section introduces notation for tensors as trilinear forms, along with operations such as sums, direct sums, rotations, Kronecker products, and tensor powers.

  • Tensor notation: A tensor over variable sets X, Y, and Z is a trilinear form whose coefficients come from the field F.The paper focuses especially on tensors whose coefficients are 0 or 1.
  • Tensor operations: Tensor sums combine coefficients over shared variable sets, while direct sums first make the variable sets disjoint.The direct sum is the sum over disjoint unions of the corresponding variable sets.
  • Tensor operations: Isomorphic tensors differ only by variable renaming through bijections on their three variable sets.The notation T ≡ T′ denotes this equivalence.
  • Tensor operations: The rotation T^r cyclically reorders the variable sets, and T^rr applies the corresponding second rotation.The coefficient associated with x_i y_j z_k is preserved under the cyclic reordering.
  • Tensor operations: The Kronecker product multiplies tensors over paired variable sets, and T^⊗n denotes its n-fold product over X^n, Y^n, and Z^n.Indices such as x_I represent elements of the corresponding Cartesian-power variable set.

2.4 Tensor Rank

This section defines tensor rank and asymptotic rank, then connects matrix multiplication tensors and their rank bounds to arithmetic circuits and the exponent ω.

  • Tensor rank: A rank-1 tensor has coefficients a_ijk = α_i · β_j · γ_k, and tensor rank R(T) is the minimum number of rank-1 tensors summing to T.This is analogous to matrix rank.
  • Tensor rank: Tensor rank is subadditive under sums and submultiplicative under Kronecker products.These properties follow by combining rank expressions and using that the Kronecker product of rank-1 tensors remains rank 1.
  • Tensor rank: The asymptotic rank R̃(T) captures the limiting rank growth of tensor powers and is bounded above by (R(T^⊗m))^(1/m).Its well-definedness follows from Fekete’s lemma.
  • Matrix multiplication tensors: The a×b×c matrix multiplication tensor ⟨a,b,c⟩ encodes multiplying an a×b matrix by a b×c matrix.Its trilinear form produces the entries of the matrix product.
  • Matrix multiplication tensors: Rank bounds for matrix multiplication tensors yield arithmetic circuits and bounds on ω, including ω ≤ log_2(7) < 2.81 from R(⟨2,2,2⟩) ≤ 7.Rectangular tensor rank bounds can be converted to square matrix multiplication bounds using symmetry and Kronecker products.

2.6 Sch¨onhage’s Asymptotic Sum Inequality

Schönhage’s framework reduces bounds on ω to asymptotic rank bounds for direct sums, while the laser method lower-bounds tensor values through structured restrictions.

  • Asymptotic sum inequality: Bounding the asymptotic rank of a direct sum of matrix multiplication tensors suffices to upper-bound ω.This extends the strategy beyond bounding a single matrix multiplication tensor.
  • Restrictions: Restrictions and zeroing outs discard variables while preserving a selected tensor structure, and asymptotic rank cannot increase under restriction.A zeroing out retains coefficients on selected variable subsets and sets the remaining variables to zero.
  • Laser method: The laser method selects a tensor whose power restricts to a large direct sum of matrix multiplication tensors while its asymptotic rank remains small.This is the central strategy behind recent progress on ω.
  • Tensor value: The τ-value V_τ(T) is multiplicative over Kronecker products and additive over direct sums, with V_τ(⟨a,b,c⟩) = (abc)^τ.The paper uses a symmetric tensor form involving T, T^r, and T^rr when it can increase value for asymmetric tensors.
  • Tensor value: If V_τ(T) ≥ R̃(T) for τ ∈ [2/3, 1], then ω ≤ 3τ, motivating lower bounds on tensor values.The paper develops a recursive approach that bounds a structured tensor’s value using the values of its subtensors.

2.8 Coppersmith-Winograd Tensors

This section introduces the Coppersmith–Winograd tensor, explains its decomposition and asymptotic rank, and motivates improving its value bounds with progression-free subsets.

  • Definition: The Coppersmith–Winograd tensor CW_q is defined over three variable sets indexed from 0 through q+1.Its explicit tensor expression is introduced in the surrounding definition.
  • Definition: CW_q is the sum of three matrix multiplication tensors and three corner terms.This decomposition is the structural basis for applying the laser method to the tensor.
  • Rank and value: The asymptotic rank of CW_q is q + 2, matching the relevant upper and lower bounds described in the paper.The cited footnote notes that border rank is at most q + 2 and upper-bounds asymptotic rank.
  • Rank and value: Bounds on ω since Coppersmith and Winograd’s work have been obtained by proving value lower bounds for CW_q.The paper’s improvement continues this value-bound approach.
  • Progression-free restrictions: The paper uses large subsets of Z_M without nontrivial three-term arithmetic progressions to construct useful tensor restrictions.For odd prime M, the tensor C_M is zeroed out outside such a subset.
  • Progression-free restrictions: Zeroing out indices outside the progression-free set A in C_M produces the restriction used in the tensor interpretation.The selected variables are x_i, y_i, and z_i for indices i in A.

3. Diagonalizing Arbitrary Tensors with Zeroing Outs

The section develops zeroing-out tools that isolate many diagonal subtensors of arbitrary tensors, then proves that the resulting √m dependence is nearly optimal for constructed examples.

  • Theorem 3.1: Theorem 3.1 generalizes an earlier tensor bound to retain many diagonal subtensors while zeroing out all other subtensors.It retains Ω(n/√m) diagonal tensors from a tensor with m·n additional subtensors.
  • Theorem 3.1: A probabilistic zeroing-out argument selects a subset I whose expected surviving diagonal structure is sufficiently large.The construction samples elements independently, removes indices implicated by off-diagonal triples, and chooses a favorable random outcome.
  • Limits and scope: These constructions show that the √m factor in Theorem 3.1 is essentially tight, while further improvement may remain possible for more structured tensors.The paper notes that tensors used later have additional structure beyond freeness and leaves possible improvements open for that setting.
  • Theorem 3.2: Theorem 3.2 constructs triple systems showing that subsets I of size n log n/√m cannot avoid containing a selected triple.A greedy covering argument removes candidate subsets until none remain, proving the required covering property.
  • Theorem 3.3: Theorem 3.3 constructs free tensors whose triple systems satisfy both limited pairwise overlap and the same covering threshold.Distinct triples intersect in at most one element, while every sufficiently large subset contains a triple.

4. Refined Laser Method

The refined laser method strengthens value lower bounds for partitioned tensors by adding a final zeroing-out step after the standard laser construction. Its analysis combines hashing, Salem-Spencer sets, and collision control.

  • Theorem 4.1: Theorem 4.1 gives a refined value lower bound for P-partitioned tensors.A P-partitioned tensor has nonzero subtensors whose partition indices satisfy i+j+k=P.
  • Proof strategy: The method applies the tensor-power construction, filters blocks consistent with selected marginal distributions, and then sparsifies the surviving block triples.The construction considers T⊗n⊗T^r⊗n⊗T^rr⊗n and divides the proof into four main steps.
  • Proof strategy: The new proof idea is a final application of Theorem 3.1 as a zeroing-out step not present in earlier laser-method analyses.The first three steps largely follow prior work, while step 4 uses the arbitrary-tensor diagonalization tool.
  • Hashing and sparsification: Random hash functions and a large Salem-Spencer set retain blocks whose hash values satisfy the required additive relation.The set A excludes nontrivial three-term arithmetic progressions, so surviving compatible hash values must coincide.
  • Hashing and sparsification: The analysis tracks consistent triples, shared-block collision pairs, and total surviving triples to obtain a collision-free family after further zeroing.The expected bound on C1−2C2 yields many surviving triples, which are then made disjoint in their block usage.

5. Algorithms and Heuristics for Applying Theorem 4.1

The paper develops recursive and heuristic procedures for applying Theorem 4.1, using convex optimization for fixed marginals and practical approximations for difficult global choices.

  • Recursive application: The refined bound is applied recursively to tensor powers and their subtensors, requiring choices of partitionings and distributions at each level.The procedure recursively bounds subtensor values and then applies Theorem 4.1 to combine them.
  • Heuristics: The globally optimal distribution is computationally difficult to find, so the paper replaces exact optimization with several heuristics.The authors introduce nonlinear surrogate constraints and test multiple heuristic choices of γ.
  • Convex optimization: Optimizing over distributions with fixed marginals reduces to two convex programs with linear constraints and concave objectives.These programs can be solved efficiently with convex optimization software.
  • Heuristics: The first heuristic slightly improves prior Algorithm B and guarantees a value at least γ_V·γ_B, with a potentially better result from optimizing α.The paper also exploits tensor symmetries to reduce the optimization search space.
  • Heuristics: The heuristics run quickly enough for the tensors analyzed, and Heuristic 3 gives the best bounds for most tensors.The tested parameter λ ranges from 0 to 107, with larger values appearing favorable experimentally.

6. Bounding 𝑽𝝉(𝑪𝑾𝒒)

The paper applies the refined method to Coppersmith-Winograd tensors, using structured partitions, tensor powers, recursive decomposition, and merging to improve value bounds.

  • Coppersmith-Winograd structure: Coppersmith-Winograd tensors have a natural 2-partitioning whose nonzero subtensors satisfy i+j+k=2, enabling Theorem 4.1.The basic subtensors include unit-value tensors and tensors with value q^τ.
  • Tensor powers: The analysis applies the refined method to powers of Coppersmith-Winograd tensors rather than only to the original tensor.For powers, coordinate sequences are partitioned by their sums, producing larger structured subtensors.
  • Merging: A merging phenomenon combines several subtensors into larger matrix multiplication tensors, yielding higher value bounds.This is identified as the key reason that applying Theorem 4.1 to higher powers can improve values.
  • Computation: The recursive procedure is implemented in software using optimization tools and code based on Le Gall’s implementation.The code computes Theorem 4.1 bounds and the heuristics for the analyzed tensor powers.

A. Rounding 𝜶in the proof of Theorem 4.1

The section establishes rounding properties for α and α′ over the constant-sized set S, handling integer-multiple and non-integer cases with asymptotic estimates.

  • Lemma A.1 asserts the existence of an α′ ∈ D satisfying the required condition for every (i, j, k) ∈ S.
  • The proof isolates S′, the subset where α_ijk is not an integer multiple of 1.
  • The non-integer case uses rounding down to the next integer multiple of 1/n and the expansion log(1 + x) = x − O(x^2) as x → 0+.
  • Because S is constant-sized, the argument reduces verification to each fixed (i, j, k) ∈ S.
  • When α_ijk is an integer multiple of 1/n, including zero, the rounded value α′ is handled directly.
  • The proof separately notes the cases δ > 0 and δ < 0, with the positive case completed before addressing the negative case.

B. Lemma for Section 4.4

This section proves Lemma B.1, a positive-real inequality used in Section 4.4, by reducing it to an intermediate bound and applying power-mean and Cauchy–Schwarz inequalities.

  • The lemma is applied to an argument in Section 4.4, with randomness choices indexed by i and determined by w_0, …, w_2n.
  • Lemma B.1 assumes positive integer c and positive real numbers A, B, a_1, …, a_c, b_1, …, b_c.
  • The proof first reduces the target statement to proving an intermediate inequality labeled (3).
  • If (3) holds, the pigeonhole principle yields an index i achieving the required bound.
  • The inequality is derived by applying the power mean inequality and then combining it with Cauchy–Schwarz.
  • The proof then cubes both sides and later takes square roots to transform the resulting inequalities.
Loading 2010.05846v2…