Source-linked AI summary
Barriers for fast matrix multiplication from irreversibility
Matthias Christandl, Péter Vrana, Jeroen Zuiddam
TL;DR
Finding the matrix multiplication exponent remains a central open problem, and prior construction methods have faced barrier results. This paper introduces tensor irreversibility and a reduction-based barrier, showing that it is more general and sometimes stronger than earlier barriers.
Problem
Determining the asymptotic algebraic complexity of matrix multiplication is a central open problem, and prior barrier results limit several approaches to fast matrix multiplication.
Source: §1 · p. 1Method
The paper models computational problems as resources connected by reductions and uses a triangle inequality for reductions to formulate a barrier based on tensor irreversibility.
Source: §1 · p. 1, §1.3 · p. 2Results
The irreversibility-based barrier is more general and, in some cases, stronger than barriers from previous work.
Source: §1 · p. 1Takeaways & Limitations
For the matrix multiplication tensor ⟨2, 2, 2⟩, ω = 2 if and only if the tensor is reversible, which the paper identifies as the source of its barrier.
Source: §2.3 · p. 8The characterization of irreversibility does not provide a practical way to compute or lower-bound it for a general tensor, because knowledge of the asymptotic spectrum is limited.
Source: §4.1 · p. 15
Abstract
from arXiv · showhide
Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent $\omega$, is a central problem in algebraic complexity theory. The best upper bounds on $\omega$, leading to the state-of-the-art $\omega \leq 2.37..$, have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on $\omega$. We introduce a new and more general barrier, providing stronger limitations than in previous work. Concretely, we introduce the notion of "irreversibility" of a tensor and we prove (in some precise sense) that any approach that uses an irreversible tensor in an intermediate step (e.g., as a starting tensor in the laser method) cannot give $\omega = 2$. In quantitative terms, we prove that the best upper bound achievable is lower bounded by two times the irreversibility of the intermediate tensor. The quantum functionals and Strassen support functionals give (so far, the best) lower bounds on irreversibility. We provide lower bounds on the irreversibility of key intermediate tensors, including the small and big Coppersmith--Winograd tensors, that improve limitations shown in previous work. Finally, we discuss barriers on the group-theoretic approach in terms of "monomial" irreversibility.
1. Introduction
The paper introduces irreversibility as a basis for barriers on methods that reduce matrix multiplication to an intermediate tensor. Its reduction-rate argument limits the bounds achievable through such intermediates, and the introduction applies it to prominent tensor families and related approaches.
1. Introduction
- The barrier addresses the open problem of determining matrix multiplication’s asymptotic algebraic complexity, typically approached through a reduction to an intermediate bilinear map and an algorithm for that map.The paper describes the matrix multiplication exponent ω as the measure of this asymptotic complexity.Source: §1 · p. 1, §1.2 · p. 2
1.3. Our barrier: informal explanation.
- The intermediate tensor’s irreversibility limits achievable matrix-multiplication bounds: the product of the two reduction rates, divided by 2, is at least its irreversibility.The argument uses a triangle inequality for rates of transformation between computational problems.Source: §1.3 · pp. 2–3
1.4. Explicit numerical barriers.
- The paper gives explicit barriers for Coppersmith–Winograd and reduced polynomial multiplication tensors; the former approach 3 as q grows, while the latter approaches 2 as n grows.The paper notes that tensor families whose barriers approach 2 may be crucial for proving ω = 2.Source: §1.4 · pp. 3–4
1.5. Comparison and other applications.
- Earlier barriers covered particular methods, while this irreversibility barrier applies to a larger class and, in some cases, is stronger.The comparison includes the laser-method barriers, monomial-degeneration barriers [AW18b], and group-theoretic approaches [BCC+17a] [BCC+17b].Source: §1.2 · p. 2, §1.5 · p. 4
- The paper’s ideas also extend to barriers for rectangular matrix multiplication and transformations between tensor powers, including asymptotic SLOCC reductions.The cited applications include transformations among multipartite quantum states [DVC00] [VDDMV02].Source: §1.5 · p. 4
2. Irreversibility of tensors
This section develops tensor restriction and relative exponent as foundations for irreversibility, extending the framework to monomial restrictions and relating irreversibility to matrix multiplication. It examines bounds via asymptotic rank and subrank, distinctions involving flattening rank and balanced tensors, and examples including the small Coppersmith–Winograd tensor.
2.1. Tensors and matrix multiplication.
- The restriction preorder characterizes tensor rank and defines subrank; for matrix multiplication tensors, Q(⟨h, h, h⟩) = h^2−o(1) asymptotically.Subrank is the largest diagonal tensor that restricts from a given tensor.Source: §2.1 · pp. 5–7
2.2. Relative exponent.
- Relative exponent is a rate-like measure of asymptotic conversion between tensors, with identity ω(t, t) = 1 and a triangle inequality.The notion is presented as a versatile version of Strassen’s asymptotic preorder.Source: §2.2 · pp. 7–8
2.3. Irreversibility.
- A tensor’s irreversibility is the product of the relative exponents in both conversion directions, equivalently the ratio of the logarithms of its asymptotic rank and subrank, and is at least 1.A tensor is reversible when its irreversibility equals 1 and irreversible otherwise.Source: §2.3 · p. 8
- The matrix multiplication tensor ⟨2, 2, 2⟩ is reversible if and only if the matrix multiplication exponent ω equals 2.The same equivalence holds for ⟨n, n, n⟩ for any n.Source: §2.3 · p. 8
- The tensor W = e0,0,1 + e0,1,0 + e1,0,0 has irreversibility 1.088.., demonstrating that irreversible tensors exist.The passage derives this value from its asymptotic subrank.Source: §2.3 · p. 8
2.4. Monomial relative exponent and monomial irreversibility.
- For every field F, the structure tensor of Z/3Z has monomial irreversibility 1.08.. and is monomially irreversible.Its asymptotic rank is 3, while its monomial asymptotic subrank is 2.755....Source: §2.4 · p. 10
2.5. Upper bounds on irreversibility.
- The final subsection introduces the possible values of irreversibility and notes that the matrix multiplication exponent provides bounds on irreversibility for arbitrary tensors.This passage states the subsection’s aim but gives no specific bounds.Source: §2.5 · p. 10
- For n × n × n tensors, irreversibility is infinite if any flattening has rank at most 1; otherwise it is finite, and asymptotic rank is at most n^(4/3).The section notes that asymptotic subrank is bounded below by an absolute constant when no flattening rank is at most 1.Source: §2.5 · p. 10
- For the Example 13 tensor, asymptotic rank is n and irreversibility approaches 2 from below as n grows.The tensor is defined in the cited passage, which attributes the asymptotic-rank result to [Str91, Equation (6.19)].Source: §2.5 · p. 11
- Balanced tensors are generic over an algebraically closed field, include matrix multiplication tensors, and satisfy 1 ≤ irreversibility ≤ 2 if ω = 2.Balancedness requires all three flattenings to have full rank and, for each flattening, some input whose image has full matrix rank; balanced tensors are also called 1-generic [LM17].Source: §2.5 · p. 11
- The upper bound in Proposition 15 is tight: the small Coppersmith–Winograd tensor cwq has irreversibility tending to 1.5 as q grows.The passage says this limit follows from Theorem 25.Source: §2.5 · p. 11
3. Irreversibility implies barriers
The paper bounds what matrix-multiplication upper bounds can be obtained through an intermediate tensor, using its irreversibility as a barrier. The barrier becomes stronger for catalytic or monomial-restriction approaches, while low asymptotic rank and high asymptotic subrank are proposed as qualities to seek.
3.1. The irreversibility barrier.
- If an intermediate tensor has irreversibility i(t) > 1, the bound rules out proving ω = 2 through that tensor, though a sequence with irreversibility tending to 1 could still suffice.Theorem 17 bounds the product of the transformation rates by at least 2i(t).Source: §3.1 · p. 12
- Low asymptotic rank and high asymptotic subrank are the heuristic qualities to seek in an intermediate tensor; the barrier does not identify a specific tensor.The result serves to exclude poor choices rather than prescribe a particular one.Source: §3.1 · p. 12
3.2. Better barriers when the method has more structure.
- For methods with more structure, the authors refine the heuristic: seek tensors with small irreversibility while also requiring less catalysis.The paper describes catalysis as a commonly used strategy and formalizes a further barrier for such approaches.Source: §3.2 · p. 12, §3.1 · p. 12
- For the specified catalytic approach, the barrier depends on both the intermediate tensor’s irreversibility and the amount of catalysis, so using less catalysis can improve the bound.Catalysis is represented by α > 0 in the stated method; the paper says this approach includes Coppersmith–Winograd upper bounds and follow-ups.Source: §3.2 · p. 13
- For a method using the Schönhage τ-theorem, the barrier can be expressed using the cyclic symmetrization cyc(t); for cyclically symmetric t, i(cyc(t)) equals i(t).For general t, the paper states i(t) ≥ i(cyc(t)).Source: §3.2 · p. 14
3.3. Better barriers through monomial irreversibility.
- When the transformation from the intermediate tensor to the matrix-multiplication tensor is restricted to monomial restriction, the authors derive corresponding barriers using monomial irreversibility.The paper states separate results for the basic, catalytic, and Schönhage τ-theorem approaches under this constraint.Source: §3.3 · pp. 14–15
4. Methods for lower bounding irreversibility
The section characterizes tensor irreversibility through the asymptotic spectrum, then develops Strassen support functionals as practical tools for bounding it. The support functionals can improve on flattening-rank bounds, though the general relation to asymptotic subrank is not fully characterized.
4.1. The asymptotic spectrum of tensors.
- The asymptotic spectrum gives a concise characterization of irreversibility, but limited knowledge of the spectrum for general tensor families prevents practical computation or lower bounds.The flattening ranks provide the best known lower bound on asymptotic rank in this setting.Source: §4.1 · p. 15
4.2. The support functionals.
- Support functionals upper-bound asymptotic subrank and thereby provide lower bounds on irreversibility.The paper uses them to obtain explicit bounds for selected tensors.Source: §4.2 · pp. 16–17
- Support functionals interpolate between the three flattening ranks, and their minimum can be strictly smaller than the minimum flattening rank.The passages note examples of strict improvement, while whether the corresponding equality holds in general is not established.Source: §4.2 · p. 16
- For the tight W-tensor, the support functional at θ = (1/3, 1/3, 1/3) gives an upper bound of 1.88... on asymptotic subrank.The computation uses the symmetric distribution over the three support elements, whose marginal entropy is h(1/3).Source: §4.2 · p. 17
5. Explicit barriers
The section applies irreversibility bounds to Coppersmith–Winograd tensors, reduced polynomial multiplication tensors, and group-algebra tensors. The resulting barriers depend on the tensor and, for some bounds, on additional assumptions or the restriction to monomial methods.
5.1. Irreversibility of Coppersmith–Winograd tensors.
- The small Coppersmith–Winograd tensor yields a barrier of at least 2.02.. for q > 2, while q = 2 does not rule out ω = 2.Under the additional assumption ω(⟨2⟩, cwq) = log2(q+2), the barrier has minimum 2.27.. at q = 6.Source: §5.1 · p. 18
- For the big Coppersmith–Winograd tensors, the stated bound has a minimum of 2.16.. at q = 1.The section also gives a bound in terms of log2 q and checks a laser-method setting with a specified outer structure, where the barrier matches the resulting upper bound.Source: §5.1 · pp. 18–20
5.2. Irreversibility of reduced polynomial multiplication tensors.
- Reduced polynomial multiplication tensors are individually irreversible, but their irreversibility converges to 1 as n increases.The paper describes this family as reversible in the limit.Source: §5.2 · pp. 20–21
5.3. Monomial irreversibility of structure tensors of finite group algebras.
- Every nontrivial finite group’s structure tensor is monomially irreversible, yielding nontrivial monomial barriers for each fixed group.These results rule out monomial restrictions from powers of a single group; the section distinguishes that scope from approaches using varying group families.Source: §5.3 · p. 21
- The ordinary irreversibility barrier does not rule out obtaining ω = 2 via the complex group-algebra structure tensor.The passage attributes this to its isomorphism to a direct sum of matrix multiplication tensors.Source: §5.3 · p. 22
6. Outlook for further barriers
The outlook identifies quantum and support functionals, along with asymptotic slice rank, as tools for bounding asymptotic subrank and hence irreversibility. It compares their strength and describes cases where the bounds coincide.
6. Outlook for further barriers
- The authors expect two other approaches to upper-bounding asymptotic subrank to be at least as powerful as support functionals, and potentially stronger on some examples.The section then discusses quantum functionals and asymptotic slice rank.Source: §6 · p. 22
6.1. The quantum functionals.
- For complex tensors, quantum functionals belong to the asymptotic spectrum and, together with flattening ranks, lower-bound irreversibility.The quantum functionals are defined for probability vectors θ; the moment polytope Π(t) is used in their definition.Source: §6.1 · p. 22
- Quantum functionals are at least as powerful as support functionals for upper-bounding asymptotic subrank; whether the inequality can be strict and whether quantum functionals are efficiently computable remain open.Unlike support functionals, quantum functionals are defined as convex programs.Source: §6.1 · p. 22
6.2. Asymptotic slice rank.
- Asymptotic slice rank upper-bounds asymptotic subrank, and known analyses reduce its evaluation to minimizing the support functionals; the authors know no example with a strict inequality.For oblique tensors the right-most inequality is an equality (see also [Zui18, Section 4.6]); for tight tensors both inequalities are equalities.Source: §6.2 · p. 23
- For complex tensors, minimizing the quantum functional over θ equals asymptotic slice rank, while for free tensors the right-most inequality is an equality [CVZ18].Slice rank is the minimum number of slice-rank-one tensors summing to the tensor.Source: §6.2 · p. 23
Appendix A. Code to verify the numerical examples
The appendix provides code to generate the paper’s barrier values at arbitrary precision and for arbitrary parameters q and n.
Appendix A. Code to verify the numerical examples
- The Mathematica code generates the barrier values in Section 1 to arbitrary precision for arbitrary q and n.This appendix passage describes the code’s scope, not the numerical outputs.Source: Appendix A · p. 23
A.1. Small Coppersmith–Winograd tensor cwq.
The appendix gives a Mathematica expression for evaluating a formula across q values from 2 through 7.
A.2. Small Coppersmith–Winograd tensor cwq.
- The code evaluates 2 Log2[q + 1]/(Log2[3] - 2/3 + (2/3) Log2[q]) for q from 2 through 7.The supplied passage gives the expression and range but does not state the resulting values.Source: §A.1 · p. 23
A.2. Big Coppersmith–Winograd tensor CWq.
The appendix includes formula fragments and tensor definitions that distinguish oblique and free tensors.
A.2. Big Coppersmith–Winograd tensor CWq.
- An oblique tensor has support forming an antichain in the product of natural orders, and matrix multiplication tensors are examples.The definition is stated for the support in some basis.Source: §A.2 · p. 23
- A tensor is free if, in some basis, every pair of distinct support elements differs in at least two entries.Every tight tensor is oblique, and every oblique tensor is free.Source: §A.2 · p. 23