PaperlayerView exact revision on arXiv

Source-linked AI summary

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

arXiv:1810.08671v1cs.CCcs.DS

TL;DR

Determining the matrix-multiplication exponent remains a central problem, while prior limitations covered particular methods, tensor classes, or fixed parameter values. The paper develops tools for broader lower bounds and proves a universal barrier above 2 for generalized Coppersmith–Winograd tensors under the Galactic method.

  • Problem

    Earlier limitations were specific to attacks or tensor classes, leaving open whether analyzing CWq as q→∞ could establish ω=2.

    Source: §1 · pp. 2–3

  • Method

    The paper develops partitioning tools for lower-bounding ωg(T) and relates group-tensor bounds to tri-colored sum-free sets in powers of groups.

    Source: §2 · p. 6

  • Results

    A universal constant ℓ>2 satisfies ωg(T)≥ℓ for every generalized CWq tensor, independent of q.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Complementary results constrain small-order group embeddings of CWq, recover current ω bounds from finite-group tensors when their asymptotic rank is sufficiently small, and establish new tri-colored sum-free constructions.

    Source: §1 · p. 4

    Earlier lower bounds were limited to particular methods or tensor classes, and fixed-q results left the q→∞ case open.

    Source: §1 · pp. 2–3

Abstract

from arXiv · show

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the value of $\omega$, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors $T$ and the Galactic method. Some of our techniques exploit `local' properties of $T$, like finding a sub-tensor of $T$ which is so `weak' that $T$ itself couldn't be used to achieve a good bound on $\omega$, while others exploit `global' properties, like $T$ being a monomial degeneration of the structural tensor of a group algebra. Our main result is that there is a universal constant $\ell>2$ such that a large class of tensors generalizing the Coppersmith-Winograd tensor $CW_q$ cannot be used within the Galactic method to show a bound on $\omega$ better than $\ell$, for any $q$. We give evidence that previous lower-bounding techniques were not strong enough to show this. We also prove a number of complementary results along the way, including that for any group $G$, the structural tensor of $\mathbb{C}[G]$ can be used to recover the best bound on $\omega$ which the Coppersmith-Winograd approach gets using $CW_{|G|-2}$ as long as the asymptotic rank of the structural tensor is not too large.

1 Introduction

The paper asks how known approaches can lower the matrix-multiplication exponent, ω, and broadens the embeddings they analyze. It proves that generalized Coppersmith–Winograd tensors cannot yield ω arbitrarily close to 2 through the Galactic method.

1 Introduction

  • Earlier limitations targeted specific methods or tensor classes; some applied only to rotated CWq or fixed q, leaving the q→∞ possibility open.The cited limitations include on Laser Method with Merging, and [BCC+17b] on group-theoretic methods, and on specified tensors.Source: §1 · pp. 2–3
  • Known algorithms seek to embed matrix multiplication into large tensor powers of a tensor with known asymptotic rank, thereby bounding ω.A larger matrix dimension N relative to the tensor-power exponent n yields a smaller bound on ω.Source: §1 · p. 3
  • The Solar method considers zeroing outs and subsumes the Laser and group-theoretic approaches; Galactic allows monomial degenerations, while Universal allows general degenerations.For the same starting tensor, Universal can in principle give better bounds than Solar or Galactic.Source: §1 · pp. 3–4
  • A universal constant ℓ>2 bounds ωg(T) from below for every generalized CWq tensor T, so the Galactic method cannot prove ω=2 from this class.The bound is independent of q.Source: §1 · p. 4
  • The paper develops combinatorial tools for proving lower bounds on ωg(T) for structured tensors.The tools are described as relatively simple arguments that can still establish strong lower bounds.Source: §1 · p. 4
  • For abelian groups of order below 2q, CWq is not a subtensor of the group-algebra structural tensor; the same holds for non-abelian groups when q is 3–9.For these cases, CWq is also not a monomial degeneration, limiting straightforward use of tri-colored sum-free-set and group-tensor techniques.Source: §1 · p. 4
  • Every finite group G has a monomial degeneration to a generalized CW tensor with q=|G|−2, which can recover current best ω bounds when the group tensor’s asymptotic rank is sufficiently small.Source: §1 · p. 4
  • For every finite group G, powers of G have tri-colored sum-free sets of size at least |G|^(c_|G| n−o(n)), with c_|G|>2/3.The constant depends only on |G| and is larger than 2/3 for moderate group sizes.Source: §1 · p. 4

2 Overview of Results and Proofs

The paper develops tools for lower-bounding the exponent achievable by the Galactic method, using both local tensor structure and global connections to group tensors. It applies these tools to generalized Coppersmith–Winograd tensors and finite-group structural tensors.

The Main Result

  • A universal c>2 bounds the ω achievable by the Galactic method on generalized Coppersmith–Winograd tensors for every q.For small q the bound follows from Corollary 5.1; as q grows, Theorem 5.1 or 5.3 gives a bound that increases rather than decreases.Source: §2 · pp. 4–6

Step 1: The Relationship Between Matrix Multiplication and Independent Tensors

  • If ωg(T)=2, then ˜I(T)=˜R(T); if ˜I(T)<˜R(T)^s for fixed s<1, then ωg(T) is bounded below by a constant greater than 2.The lower-bound constant increases as s decreases.Source: §2 · p. 5

Step 2: Partitioning Tools for Upper Bounding ˜I

  • A restricted tensor A with ˜I(A) sufficiently below the size of its selected X-variable set forces ˜I(T)<|X|≤˜R(T), ruling out ωg(T)=2 for any completion T.This is the local obstruction of Theorem 5.1.Source: §2 · p. 5
  • When ˜I(T) is close to ˜R(T), each X, Y, and Z variable must receive nearly equal probability mass; corner terms can violate this condition and force ˜I(T)<˜R(T).Theorem 5.3 also bounds ˜I(T) by the sum of (µ(Ti))^2/3 when the terms are partitioned into tensors Ti.Source: §2 · pp. 5–6

Bounds on ˜I for Group Tensors

  • For every finite group G, ˜I(TG)<|G|≤˜R(TG), so the Galactic method on any fixed group tensor TG cannot yield ω=2.The proof connects lower bounds on ˜I(TG) to tri-colored sum-free sets in powers of G.Source: §2 · p. 6
  • Coppersmith–Winograd tensors cannot always be represented as subtensors of relatively small group tensors, so group-tensor bounds alone do not cover every tensor of interest.The paper therefore also needs combinatorial partitioning techniques.Source: §2 · p. 7

Lower Bounds on ˜I(TG)

  • Every finite group tensor TG has a monomial degeneration to a generalized Coppersmith–Winograd tensor of parameter |G|−2, enabling recovery of its known best ω bound when ˜R(TG)=|G|.The paper also derives ˜I(TG)≥|G|^c_|G| for some c_|G|>2/3 and a resulting tri-colored sum-free set lower bound in Gn.Source: §2 · p. 7

3.1 Tensor Notation and Definitions

This section establishes notation for tensors and their supports, then defines rank, restrictions, degenerations, and structural properties used in the paper.

3.1 Tensor Notation and Definitions

  • A tensor over variable sets X, Y, Z is a trilinear form; its support is the set of index triples with nonzero coefficients, and each such triple is a term.Tensor powers are repeated tensor products, whose variables can be viewed as tuples of the original variables.Source: §3.1 · pp. 7–8

3.1.1 Tensor Rank

  • Rank is the fewest rank-one tensors summing to T, while asymptotic rank is the limit of the nth roots of the ranks of T⊗n.An independent tensor of size r is equivalent, up to index permutation, to ⟨r⟩.Source: §3.1.1 · pp. 8–9

3.1.2 Sub-Tensors and Degenerations

  • A subtensor removes support triples, a restriction applies linear maps to the three variable spaces, and zeroing out selects subsets of variables in each space.A degeneration is a border-rank-preserving limit operation; a monomial degeneration restricts the transformations to monomials in λ.Source: §3.1.2 · p. 9

3.1.3 Structural Properties of Tensors

  • A tensor is concise when its three associated linear maps are injective, and its border rank is then at least the largest of the three variable-set sizes.A partition divides the support into disjoint parts whose tensors sum to T; a direct sum additionally uses disjoint variable sets.Source: §3.1.3 · pp. 9–10

3.2 The Matrix Multiplication Tensor and Methods for Analyzing ω

The exponent ω is determined by the asymptotic rank of square matrix multiplication tensors, but that rank is difficult to analyze directly. The paper organizes approaches by how they embed matrix multiplication into powers of a tensor with known asymptotic rank.

3.2 The Matrix Multiplication Tensor and Methods for Analyzing ω

  • Known methods start with a tensor of known asymptotic rank and embed matrix multiplication into its large tensor powers to bound ω.The embedding can also produce a direct sum of smaller matrix multiplication tensors, to which the asymptotic sum inequality applies.Source: §3.2 · p. 10
  • Zeroing out is a restricted border-rank-preserving embedding, while arbitrary degeneration is the most general embedding described here.The passage notes that every border-rank-q tensor is a degeneration of the structure tensor for addition modulo q.Source: §3.2 · p. 10
  • The Universal method would seek arbitrary degenerations of tensor powers into large matrix multiplication tensors, but current techniques do not find good ones.The paper calls this a hypothetical method because finding such degenerations remains beyond current techniques.Source: §3.2 · p. 10
  • The Galactic method optimizes monomial degenerations, whereas the Solar method optimizes zeroing outs and subsumes both the Laser and Group Theoretic approaches.The paper says monomial degenerations appear easier to reason about than arbitrary degenerations, although no known techniques improve on zeroing outs.Source: §3.2 · p. 11
  • Solar, Galactic, and Universal methods offer successively more power on specific tensors, while all yield the same ω bound when applied to matrix multiplication tensors themselves.The distinctions matter because the asymptotic rank of matrix multiplication tensors is not well understood.Source: §3.2 · p. 11

3.3 The Laser Method

The Laser method partitions a starting tensor into blocks, then zeroes out variables in its tensor powers to obtain matrix multiplication tensors. The Coppersmith-Winograd approach uses structured block tensors and combinatorial selection to extract direct sums and bound ω.

3.3 The Laser Method

  • The Laser method partitions a starting tensor’s variable sets into blocks and forms subtensors by retaining variables from chosen blocks.The starting tensor is taken to have known asymptotic rank, with the number of variables in one set matching that rank.Source: §3.3 · p. 11
  • Variables in tensor powers must be zeroed out by matching block sequences, so each such sequence is either kept throughout or removed throughout.After zeroing, the method seeks a direct sum of matrix multiplication tensors and applies the asymptotic sum inequality.Source: §3.3 · p. 11
  • The asymptotic sum inequality turns a direct sum of matrix multiplication tensors with bounded border rank into an upper bound on ω.Schönhage’s proof can be viewed as taking tensor powers of the direct sum and zeroing out to obtain independent copies of one matrix multiplication tensor.Source: §3.3 · p. 12
  • In the Coppersmith-Winograd partitioning, the relevant subtensors are matrix multiplication tensors whose block indices sum to 2.The CW_q tensor has border rank, and therefore asymptotic rank, q + 2.Source: §3.3 · p. 12
  • The CW approach uses progression-free sets to select blocks in tensor powers, producing direct sums of large matrix multiplication tensors for the asymptotic sum inequality.The standard analysis optimizes at q = 6; later related analyses used CW_5.Source: §3.3 · p. 12
  • Coppersmith-Winograd block tensors need not themselves be matrix multiplication tensors, but their Value is used to assess their support for matrix multiplication.The analysis applies to blockings in which every relevant triple of block indices has the same sum.Source: §3.3 · pp. 11–13
  • The CW approach uses little beyond each block tensor’s Value, permitting replacement by a same-Value tensor when the full tensor’s border rank is preserved.For matrix multiplication blocks, the replacement dimensions must use the same variables and preserve the product of the three dimensions.Source: §3.3 · p. 13
  • The generalized CW family contains permutations of the CW constituent terms, and any family member of border rank q + 2 yields the same CW-method bound on ω.The rotated CW_q example retains rank q + 2 and the same upper bound.Source: §3.3 · p. 13

3.4 Group-theoretic approach

The group-theoretic approach uses a group tensor, whose asymptotic rank is bounded through representation theory, and zeroing outs to obtain matrix multiplication tensors. Group properties determine which zeroings are available, while representation theory supplies the rank bound.

3.4 Group-theoretic approach

  • The group tensor T_G is the structure tensor of the group algebra C[G], and the group-theoretic approach was introduced by Cohn and Umans.The paper uses T_G as shorthand for the structure tensor.Source: §3.4 · p. 13
  • Representation theory bounds T_G’s asymptotic rank using the dimensions of G’s irreducible representations.The passage states that T_G degenerates from a direct sum of ⟨d_u⟩ tensors, where d_u are the character degrees.Source: §3.4 · p. 13
  • The triple product property yields a zeroing out into one matrix multiplication tensor, while its simultaneous version yields a direct sum of such tensors.The group properties provide the zeroing out; representation theory provides the rank bound, and the approach seeks groups whose properties yield large tensors.Source: §3.4 · p. 14

3.5 Independent Tensors

The paper studies zeroing outs and monomial degenerations from a tensor to independent tensors. It defines an independence number and gives a variable-count upper bound for it and its asymptotic counterpart.

3.5 Independent Tensors

  • The paper places these quantities in the study of zeroing outs and monomial degenerations from tensors to independent tensors ⟨r⟩.It introduces the corresponding definitions for that setting.Source: §3.5 · p. 14
  • The independence number I(T) is the largest independent tensor obtainable from T by zeroing out variables.The paper also defines an asymptotic independence number.Source: §3.5 · p. 14
  • Zeroing out cannot increase any variable-set size, so I(T) and its asymptotic counterpart are at most min{|X|, |Y|, |Z|}.The paper states that matrix multiplication tensors attain equality in this bound.Source: §3.5 · p. 14

3.6 Tri-colored Sum-free Sets

The paper generalizes the connection between matrix-multiplication lower bounds and tri-colored sum-free sets, using bounds on these sets to constrain the Galactic method for many tensors.

3.6 Tri-colored Sum-free Sets

  • A tri-colored sum-free set in a group consists of triples satisfying ab = c, with no nontrivial cross-combination satisfying the same relation.The paper notes that such sets are also called multiplicative matchings.Source: §3.6 · pp. 14–15
  • For every nontrivial finite group G, tri-colored sum-free sets in G^n have size at most (δ|G|)^n for some δ < 1.The cited bound applies for every positive integer n.Source: §3.6 · p. 15
  • The paper uses this bound, and stronger known bounds for some groups, to prove lower bounds on the Galactic-method exponent for a wide range of tensors.It expands the connection between matrix-multiplication lower bounds and tri-colored sum-free sets.Source: §3.6 · pp. 14–15

3.7 Comparison with Slice Rank Bounds

Slice-rank bounds on powers of group tensors can limit the matrix-multiplication exponent achievable by the Universal method, but the group-dependent bound does not rule out approaching 2 across a sequence of groups.

3.7 Comparison with Slice Rank Bounds

  • A degeneration of a tensor T to an independent tensor D implies |D| ≤ slice-rank(T), so bounds on slice-rank(T^⊗n) can constrain the Universal-method exponent for T.The paper cites Tao16 and TS16 for the degeneration-to-independent-tensor bound.Source: §3.7 · p. 15
  • For each fixed group G, Sawin's result gives slice-rank(T_G^⊗n) < (δ|G|)^n for some δ < 1, implying ωu(T_G) > 2.This generalizes the paper's result that ωg(T_G) > 2.Source: §3.7 · p. 15
  • Because δ depends on G, these bounds do not rule out Universal-method bounds approaching 2 along a sequence of groups.Source: §3.7 · p. 15
  • Slice-rank upper bounds do not readily extend to CW_q: slice-rank is not generally submultiplicative, and powers of CW_5 can have slice-rank at least 5.15^n − o(n).The paper says it is unclear how to upper-bound slice-rank(CW_q^⊗n) in general.Source: §3.7 · p. 15

4 Matrix Multiplication and Independent Tensors

This section relates the Galactic method to the asymptotic independence number: monomial degenerations can yield independent tensors, and bounds on this number support lower bounds on the achievable matrix-multiplication exponent.

4 Matrix Multiplication and Independent Tensors

  • To lower-bound ωg(T), the framework upper-bounds the asymptotic independence number Ĩ(T), while ωg(T) is the best exponent bound obtainable by the Galactic method using T.Source: §4 · pp. 15–16
  • Every matrix multiplication tensor ⟨a,b,c⟩ has a monomial degeneration to an independent tensor of size 3/4 · abc.The construction uses a zero-sum condition on indices so that any one variable determines the other two.Source: §4 · p. 16
  • If T^⊗n has a monomial degeneration to an independent tensor of size f, then Ĩ(T) ≥ f^(1/n).A monomial degeneration to f independent triples yields, after tensor powering and zeroing out, f^(n)−o(n) independent triples.Source: §4 · p. 17
  • Monomial degeneration preserves the ordering of asymptotic independence numbers: if A is a monomial degeneration of B, then Ĩ(A) ≤ Ĩ(B).Source: §4 · p. 17
  • For any positive integers a, b, c, the asymptotic independence number of F ⊙ ⟨a,b,c⟩ is Fabc.The upper bound counts x-variables; the matching lower bound uses tensor powers and monomial degenerations.Source: §4 · p. 17
  • For concise tensors, Theorem 4.1 derives a lower bound on ωg(T) from the relationship between Ĩ(T) and the asymptotic rank of T.Its proof uses monomial degenerations of tensor powers into F ⊙ ⟨a,b,c⟩ and bounds from variable counts.Source: §4 · pp. 17–18
  • If ωg(T) = 2, then Ĩ(T) = R̃(T); moreover, if Ĩ(T) ≤ R̃(T)^s for a constant s < 1, then ωg(T) is bounded below by some constant w > 2.Source: §4 · p. 18

5 Partitioning Tools for proving lower bounds

The section develops partition-based tools for bounding the asymptotic independence number, including bounds from sparse variables, near-uniform term distributions, corner terms, and tensor measure.

5 Partitioning Tools for proving lower bounds

  • The paper's tools target tensors with partitions whose pieces have low asymptotic independence, even though Ĩ is neither additive nor multiplicative in general.The Coppersmith-Winograd tensor is partitioned into three pieces, each with asymptotic independence number 1; nevertheless, Ĩ(CW_q) grows with q.Source: §5 · p. 18
  • If deleting a sparse variable x1 leaves a tensor B whose asymptotic independence number is sufficiently below q − 1, then the original tensor T has a nontrivial upper bound on Ĩ(T), regardless of the terms containing x1.The theorem assumes x1 occurs in at most q terms; when Ĩ(B) is mildly below q − 1, the resulting bound on Ĩ(T) is strictly below q.Source: §5 · p. 19
  • A large Ĩ(T) for a tensor with q variables in each set guarantees a probability distribution on its terms with approximately balanced marginal mass for each variable.Theorem 5.2 states that for each fixed variable index, the total probability of terms containing it is at least 1 − κ.Source: §5 · p. 20
  • If T contains the specified two corner terms, with xq and yq appearing nowhere else, then Ĩ(T) is bounded by a constant cq < q depending only on q.The condition holds regardless of the rest of T's terms.Source: §5 · p. 21
  • The measure μ(T) is the product of the sizes of its minimal variable sets, and Ĩ(T) ≤ μ(T)^(1/3).The bound generalizes: if T is partitioned into parts P_i, then Ĩ(T) ≤ Σ_i μ(P_i)^(1/3).Source: §5 · p. 22
  • The partition theorem bounds Ĩ(T) by the sum of the cube roots of the measures of its parts.Its proof weights the parts by their cube-root measures while tracking independent triples across tensor coordinates.Source: §5 · pp. 22–23

6 Lower Bounds for Group Tensors

Group-tensor structure gives global lower bounds for the Galactic method: every finite group tensor has ωg(TG) > 2, and the same bound applies to certain monomial degenerations. The section also limits how directly CWq can be embedded in group tensors, while leaving sequences of groups as a possible route to ω = 2.

6 Lower Bounds for Group Tensors

  • A zeroing out of TG into an independent tensor of size |D| yields a tri-colored sum-free set in G of the same size.This connects tensor independence to a group-theoretic object used in the lower-bound argument.Source: §6 · p. 23
  • ωg(TG) > 2 for every finite group G, and the same-measure monomial degenerations of group tensors also have ωg(T) > 2.The argument bounds the asymptotic independence number below the group order for these tensors.Source: §6 · p. 23
  • No fixed group tensor is ruled out as a route to ω = 2 by this result; a sequence of groups with ωg(TGi) approaching 2 remains possible.The paper notes that some natural sequences have separately been ruled out, and those arguments can also be combined with the Galactic-method result.Source: §6 · p. 24
  • CWq is not a sub-tensor of an abelian group tensor of order below 2q, and for q = 3 through 9 it is not a sub-tensor of any group tensor of order q + 2.The abelian result also rules out a monomial degeneration at those group orders; the small-q cases are relevant because best-known bounds use q < 7.Source: §6 · pp. 24–25
  • For q = 2^k+1, the abelian-group size bound is tight: C2^k × C4 contains CWq as a sub-tensor and a monomial degeneration.This is an example of equality in the group-order threshold.Source: §6 · p. 25

7 Applications of our Lower Bound Techniques

The applications use the paper’s lower-bounding tools on generalized Coppersmith-Winograd tensors, group tensors, and lower-triangular tensors. They establish a universal barrier above 2 for generalized CW tensors, give group-tensor constructions and bounds, and characterize when lower-triangular tensors have maximal asymptotic independence number.

7.1 Generalized CW tensors

  • There is a universal constant c > 2 such that every generalized Coppersmith-Winograd tensor, for any parameter q, has ωg(T) ≥ c.The proof combines a per-q bound with a separate bound for sufficiently large q.Source: §7.1 · p. 25
  • For q ≥ 6, the second proof obtains a bound independent of the permutation σ; at q = 6 it gives ˜I(CWσ6) ≤ 7.9973.The proof uses Theorem 5.1 after bounding ˜I(A) by 5.07905.Source: §7.1 · p. 27

7.2 ˜I and tri-colored sum-free set constructions for all finite groups

  • Every finite group G of order |G| has a monomial degeneration from TG to a generalized Coppersmith-Winograd tensor with parameter |G| − 2.The construction chooses a nonidentity group element and a permutation on the remaining elements.Source: §7.2 · pp. 27–28
  • When ˜R(TG) = |G|, applying the Galactic method to TG recovers the best known upper bound on ω obtained from CW|G|−2.The paper notes this could support more practical algorithms if a suitable group has efficient operations.Source: §7.2 · p. 28
  • For every finite group G, ˜I(TG) ≥ |G|^c|G| for some c|G| > 2/3, yielding tri-colored sum-free sets in Gn of size at least |G|^c|G|n−o(n).The constant depends only on |G|; the stated construction applies to abelian and non-abelian finite groups.Source: §7.2 · p. 29

7.3 Tq lower triangular

  • For every q ≥ 2, the lower-triangular cyclic-group tensor T lower q has ωg(T lower q) > 2, but the bound’s constant cannot be made independent of q using only its asymptotic independence number.The cited prior result gives limq→∞ logq(˜I(T lower q)) = 1.Source: §7.3 · p. 29

7.4 Lower Triangular Tensors

  • The section provides a strong characterization of lower-triangular tensors that could potentially prove ω = 2 within the Galactic method.Its stated criterion is the presence of q disjoint-in-z diagonal terms, equivalent to ˜I(T) = q.Source: §7.4 · pp. 29–30
  • A lower-triangular tensor has ˜I(T) = q exactly when it has q diagonal terms with no shared z-variables.Such terms can be isolated by a monomial degeneration to an independent tensor of size q.Source: §7.4 · p. 30
Loading 1810.08671v1…