PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Matrix Multiplication: Limitations of the Laser Method

Andris Ambainis, Yuval Filmus, François Le Gall

arXiv:1411.5414v1cs.CCcs.DS

TL;DR

The paper asks whether higher tensor powers of the Coppersmith–Winograd identity can yield algorithms approaching the conjectured matrix-multiplication exponent of 2. It analyzes an extended laser-method framework that includes prior approaches and their variants. The analysis rules out specific exponent bounds for these methods and explains the gains from taking tensor powers.

  • Problem

    The paper asks whether higher tensor powers of the Coppersmith–Winograd identity can yield algorithms proving the conjecture that ω = 2.

    Source: §1 · p. 2

  • Method

    The paper presents an analyzable framework extending the laser method to encompass prior approaches and variants, including zeroing variables and merging surviving tensors.

    Source: §1 · pp. 2–3, §2.4 · p. 10

  • Results

    The exact tensor-power approach cannot yield O(n^2.3725), and a wider class of variants cannot yield O(n^2.3078).

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework is the first to explain what is gained by taking tensor powers of the Coppersmith–Winograd identity.

    Source: §1 · p. 2

    For q = 5, the canonical recursive approach using the 64th and higher powers cannot give ω < 2.3725; laser-method merging on T cannot prove ω = 2.

    Source: §5.4 · p. 34, §7 · p. 36

Abstract

from arXiv · show

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time $O(n^{2.3725})$, and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078})$; in particular, this approach cannot prove the conjecture that for every $\epsilon > 0$, two $n\times n$ matrices can be multiplied in time $O(n^{2+\epsilon})$. We describe a new framework extending the original laser method, which is the method underlying the previously mentioned algorithms. Our framework accommodates the algorithms by Coppersmith and Winograd, Stothers, Vassilevska-Williams and Le Gall. We obtain our main result by analyzing this framework. The framework is also the first to explain why taking tensor powers of the Coppersmith-Winograd identity results in faster algorithms.

1 Introduction

The paper frames recent matrix-multiplication gains as repeated analyses of tensor powers of the Coppersmith–Winograd identity, then introduces a laser method with merging that encompasses prior approaches. It proves limits for the exact recursive approach and broader variants, while explaining what tensor powers gain.

1 Introduction

  • O(n^2.3725) is unattainable by taking any 2^N tensor power of the Coppersmith–Winograd identity under the exact prior approach.The paper states that analyzing any power recursively as in prior works cannot yield this running time.Source: §1 · pp. 2, 4
  • O(n^2.3078) cannot be reached for any tensor power even when the framework accounts for additional degrees of freedom.These include analyzing powers other than powers of 2 and varying how the tensor square is analyzed.Source: §1 · p. 2
  • The laser method with merging formalizes zeroing variables and merging surviving tensors, and accommodates the methods used by Coppersmith and Winograd, Stothers, Vassilevska-Williams, and Le Gall.The merged tensors are made disjoint and suitable for applying the asymptotic sum inequality.Source: §1 · p. 3
  • Merging explains why analyzing higher powers can improve bounds: parts of the tensor can be combined before applying the laser method.The tensor-square construction merges thirty-six smaller tensors into fifteen non-disjoint tensors.Source: §1 · p. 3
  • The paper's limitation methodology is designed to quantify what the laser method with merging cannot achieve, not to efficiently convert its constructions into algorithms.The authors say they do not know how to systematically and efficiently perform that conversion.Source: §1 · p. 3
  • Across the reported powers, recursive laser-method bounds improve, while laser-method-with-merging limits worsen as the power increases.Table 1 reports upper bounds from the laser method and limits on bounds obtainable using the laser method with merging.Source: §1 · p. 4, Table 1 · p. 4

2 Summary of results and techniques

The section traces tensor-based matrix multiplication bounds through recursive laser analysis and introduces merging as a generalization for analyzing gains from tensor powers. It bounds the capabilities of these methods using merging-value limits, extending the analysis to higher tensor powers, coherent mergings, and broader tensor settings.

2.1 Fast matrix multiplication

  • In the standard algebraic complexity model, ω is the matrix multiplication exponent, and tensor-rank algorithms yield upper bounds on ω.The definition permits an arbitrarily small additive ε in the complexity bound O(n^(ω+ε)).Source: §2 · p. 5, §2.1 · p. 6

2.2 Laser method

  • The laser method takes high tensor powers, zeros variables to obtain disjoint tensors, and applies the asymptotic sum inequality; choosing q = 6 gives ω < 2.3872.The construction uses the Coppersmith–Winograd identity, whose border rank is at most q + 2.Source: §2.2 · pp. 7–8

2.3 Recursive laser method

  • Recursive analysis of T⊗2 assigns values to its non-matrix-multiplication constituents and reaches ω < 2.3755; fourth-power analysis reaches 2.3730, with higher powers improving it by less than 10^-3.The higher-power analyses include the fourth, eighth, sixteenth, and thirty-second powers.Source: §2.3 · p. 9

2.4 Laser method with merging

  • The gain from analyzing tensor powers comes from merging non-disjoint matrix multiplication tensors into larger ones; the generalized laser method allows such merging and subsumes analyses of all Coppersmith–Winograd identity powers.After zeroing variables, surviving tensors may be merged when their sum is equivalent to a matrix multiplication tensor; only matrix multiplication tensors are merged.Source: §2.4 · p. 10

2.5 Our results

  • For any N, the paper gives a merging-value result for T⊗N calculated along the lines of prior analyses but with more degrees of freedom.The prior analyses fold parts in a prescribed way when passing from T⊗N to T⊗2N.Source: §2.5 · p. 10
  • The method permits arbitrary repartitioning and tensor-power sequences such as T, T^⊗2, T^⊗3, and applies broadly beyond the Coppersmith–Winograd tensor.Other promising tensor examples were not known at the time described.Source: §2.5 · pp. 10–11
  • The merging-value bound ρ((T^⊗N1)^⊗N2) limits recursive-laser bounds on ω from T^⊗N1, while ρ(T^⊗2N) constrains all T^⊗2M for M ≥ N.These limits follow from upper bounds on the merging value.Source: §2.5 · p. 11
  • For q = 5, no analysis of any power of T, even with the stated degrees of freedom, can yield a bound better than ω < 2.3078.The upper bound on the merging value gives ρ > 2.3078 for q = 5.Source: §2.5 · p. 11
  • For powers T^⊗2N, no analysis along previous lines yields a bound better than ω < 2.3725, so higher powers cannot significantly improve the existing ω < 2.3729 bound.The limitation includes considering the 64th, 128th, 256th, and higher powers of the Coppersmith–Winograd identity.Source: §2.5 · p. 11
  • The upper bound applies to tensors whose possible mergings are coherent, a condition met by current laser-method approaches and used to obtain the general bound.A merging is coherent when, at each tensor coordinate, at least one of its three indices is zero throughout the merging set.Source: §2.5 · pp. 11–12

3 Background

This background develops complexity, tensor, and partitioned-restriction tools for analyzing matrix multiplication, including the laser method’s value framework. It describes recursive laser and Coppersmith–Winograd constructions, their bounds, and choices motivating broader frameworks, including the paper’s nonrecursive variant.

3 Background

  • The section equips the analysis with the recursive laser method used in prior matrix-multiplication bounds, so the new nonrecursive variant can be shown to subsume earlier work.The section also introduces a general first-power Coppersmith–Winograd bound and abstracts parts of that construction.Source: §3 · p. 12

3.1 Bilinear complexity

  • Tensor rank connects trilinear forms to matrix multiplication complexity, while Schönhage’s asymptotic sum inequality provides a fundamental vehicle for upper bounds on the exponent.The section also defines border rank, which is needed to state the inequality.Source: §3.1 · pp. 13–14

3.2 The value of a tensor

  • The value of a tensor generalizes volume to arbitrary tensors and supports a generalized asymptotic sum inequality; for symmetric tensors, its definition can use tensor powers directly.The value depends on the parameter ρ, and Stothers showed its defining limit exists.Source: §3.1 · p. 15, §3.2 · p. 16

3.3 Partitioned tensors and the Coppersmith–Winograd identity

  • The Coppersmith–Winograd tensor is a tight partitioned tensor, whose annotated constituents organize tensor powers into index triples for laser-method selection.Tightness is necessary for current laser-method techniques that prove lower bounds on partitioned-tensor value.Source: §3.3 · p. 17
  • A partitioned restriction is formed by zeroing groups of variables, and all constructions below use this specific form of degeneration.Source: §3.3 · pp. 17–18

3.4 The laser method

  • The laser method lower-bounds tensor value by taking partitioned restrictions of rotated tensor powers with strongly disjoint support and maximizing estimated constituent values.The estimates must not exceed the corresponding constituent values for the partition-restricted value to provide a valid bound.Source: §3.4 · pp. 18–19
  • For the Coppersmith–Winograd tensor, the compatibility penalty is zero for every distribution, and the partition-restricted-value analysis yields ω < 2.3872 for T(6).The passage identifies this as the optimal bound obtainable using the partition-restricted value for T(6).Source: §3.4 · p. 19

3.5 Recursive Coppersmith–Winograd construction

  • Coppersmith and Winograd’s recursive repartitioning of T⊗2 yields ω ≤ 2.3755, while their next-stage construction and analysis achieves ω < 2.37293.The recursive analysis treats non-matrix-multiplication constituents as estimated tight partitioned tensors and applies the laser-method bounds.Source: §3.5 · pp. 20–21
  • The canonical recursive construction obtains ω < 2.37293; further iterations yield slightly better bounds, including a reported bound of ω < 2.37287.Vassilevska-Williams iterated once more for ω < 2.37287, and Le Gall iterated twice more, improving only the seventh decimal digit.Source: §3.5 · p. 21
  • Recursive constructions allow choices in how tensor products are repartitioned and which tensors are multiplied; analyzing T⊗3 does not improve the bound.The paper’s Section 4 method subsumes these multiplication schemes, and the paper introduces a value notion for recursively repartitioned tensors.Source: §3.5 · pp. 21–23

4 Merging

The merging value generalizes the merging of matrix multiplication tensors and subsumes analyses of tensor powers. It also subsumes recursive repartitioning, bounding what those analyses can achieve.

4 Merging

  • The merging value permits merging matrix multiplication tensors and subsumes analysis of all powers of T.It is introduced to explain why analyzing higher powers can improve bounds.Source: §4 · p. 24
  • A consistent restriction groups constituent tensors while requiring distinct resulting tensors to have disjoint x-, y-, and z-variables.The general definition also requires each constituent of the restriction to be a consistent sum, with each restricted constituent used exactly once.Source: §4 · p. 25
  • The merging value has a well-defined limit, is super-multiplicative and super-additive, and lower-bounds the value under the stated constituent-value condition.The limit follows from Lemma 4.1; Theorem 4.3 gives the lower bound.Source: §4 · pp. 25–26

4.1 Merging subsumes recursive repartitioning

  • The square of T’s merging value upper-bounds the partitioned value of any repartitioning of T⊗T.This bound limits the ω bound obtainable by analyzing such a repartitioning.Source: §4.1 · p. 26
  • More generally, merging-value bounds limit ω from recursive repartitionings and subsume the recursive laser method.The paper states that every bound from recursive repartitioning can also be obtained using the merging-value inequality.Source: §4.1 · p. 27

5 Upper bound on the value with merging

The section establishes upper bounds on merging values by characterizing consistent sums of distinct zero-sequences, then applies them to the Coppersmith–Winograd tensor, a broader tensor class, and canonical tensor powers. Its numerical analysis shows that for q = 5, higher tensor powers cannot yield an upper bound on ω below 2.3725.

5.1 Structure of consistent sums

  • For symmetric Coppersmith–Winograd-like tensors, any consistent sum of distinct zero-sequences must be coherent.Coherence means the coordinates can be partitioned so that each coordinate is fixed to zero in the same one of the three indices across the sum.Source: §5.1 · p. 28

5.2 Upper bound for the Coppersmith–Winograd tensor

  • For the Coppersmith–Winograd tensor, Theorem 5.2 derives an upper bound on merging value by decomposing restrictions into coherent lines and bounding their contributions.The analysis classifies lines and constituent tensors by types before combining the resulting bounds.Source: §5.2 · pp. 30–32

5.3 Upper bound for Coppersmith–Winograd-like tensors

  • For estimated symmetric Coppersmith–Winograd-like tensors and ρ in [2, 3], Theorem 5.3 gives an upper bound on the merging value.The proof reduces the worst case to symmetric distributions and typical lines, then bounds the limiting logarithm of the value.Source: §5.3 · pp. 33–34

5.4 Numerical calculations

  • The numerical analysis applies Theorem 5.3 to canonical tensor powers T⊗2r and uses Theorem 3.5’s upper estimate for constituent values, which can only deteriorate the calculated bounds.The calculations cover several values of r ≥ 0.Source: §5.4 · p. 34
  • For q = 5, analyzing the 64th, 128th, 256th, or higher powers of T cannot give an upper bound on ω smaller than 2.3725.The analysis identifies the best value obtainable from the canonical T^(⊗2r) and its powers.Source: §5.4 · p. 34
  • The numerical values are the best values obtainable from the canonical T^(⊗2r) and its powers.This interpretation is stated for the value α given by Theorem 5.3.Source: §5.4 · p. 34
  • For several r and q, Table 3 reports α(T^(⊗2r)) = (q + 2)^(2r), rounded down to five decimal digits.For given r and q, the corresponding table value is the solution α described in the numerical analysis.Source: §5.4 · p. 34, Table 3 · p. 34

6 Generalizations

The section extends limitation analysis of current laser-method implementations beyond Coppersmith–Winograd-like tensors. It uses coherent merging to represent restrictions constructed by known implementations.

6 Generalizations

  • The limitation analysis extends to a large class of partitioned tensors, beyond Coppersmith–Winograd-like tensors.The class includes tensors that are not tight.Source: §6 · p. 35
  • The paper introduces coherent merging as a distinct version of merging for its generalization to arbitrary tensors.Unlike the earlier definition, it requires all consistent sums to be coherent.Source: §6 · p. 35
  • Coherent merging models what current laser-method implementations can do because all known implementations construct coherent restrictions.The paper notes that no general technique is known for constructing restrictions with consistent but non-coherent sums of zero-sequences.Source: §6 · p. 35

7 Discussion

The paper limits what laser methods with merging can achieve on the Coppersmith–Winograd tensor, while identifying unresolved gaps in its bounds. The authors suggest new identities as a promising research direction and propose using their lower-bound techniques to screen them.

7 Discussion

  • The laser method with merging applied to T cannot prove ω = 2.The authors believe the technique could still improve known bounds on ω.Source: §7 · p. 36
  • Allowing the merging width 2r to vary with N could potentially yield a better lower bound on V_mρ,N(T).The discussed bound uses a fixed merging width.Source: §7 · p. 36
  • For q ≥ 1, the limit on possible bounds for ω worsens as q decreases; known constructions work best at q = 5, or q = 6 without merging.The authors suspect their upper bound on the merging value is not tight and leave its correct value open.Source: §7 · p. 36
  • The upper bound depends only on disjoint constituent variables and is tight without the partitioned-restriction requirement, leaving construction of a qualifying T′ as the lower-bound difficulty.The authors conjecture the lower bound for the partition-restricted value is tight, but report a gap at r = 2.Source: §7 · p. 36
  • The authors favor finding new identities and suggest their lower-bound techniques could rule out unpromising identities and their powers, even under repartitioning.They note that powers of the basic Coppersmith–Winograd identity may have border rank below the known upper bound, though no new bounds are known.Source: §7 · p. 36

A Proofs of results from Section 3.2

These proofs establish the existence of the relevant asymptotic value despite rounding and relate partition-restricted values to the tensor value. They use symmetrization for the lower-bound argument and entropy to bound the number of supported terms.

A Proofs of results from Section 3.2

  • The limit exists even though the relevant inequality can fail under rounding, because it holds approximately and Fekete’s lemma applies.Additivity is straightforward when the rounded vectors satisfy the stated compatibility condition.Source: A Proofs of results from Section 3.2 · p. 38
  • Taking the product of the three cyclically related restrictions allows the proof to use matching distributions for T, T^C, and T^C2.The proof then uses a symmetric distribution formed by averaging the cyclic permutations.Source: A Proofs of results from Section 3.2 · pp. 38–39
  • Theorem 3.4 follows by bounding the value of a tensor power using a partitioned degeneration with strongly disjoint support, then taking the limit.The proof obtains Vρ(T) ≥ Vprρ(T).Source: A Proofs of results from Section 3.2 · p. 38
  • For the upper bound, the proof bounds the number of supported terms by the sum of the three marginal entropies and takes the limit.For symmetric T, averaging cyclic permutations gives a symmetric distribution that maximizes the bound.Source: A Proofs of results from Section 3.2 · p. 39
Loading 1411.5414v1…