PaperlayerView exact revision on arXiv

Source-linked AI summary

Powers of Tensors and Fast Matrix Multiplication

François Le Gall

arXiv:1401.7714v1cs.DScs.CCcs.SC

TL;DR

The paper addresses how to derive upper bounds on the exponent ω of square matrix multiplication from powers of trilinear forms. It develops a polynomial-time convex-optimization method and applies it to the Coppersmith–Winograd construction, obtaining ω < 2.3728639.

  • Problem

    The central question is determining the exponent ω, the minimal asymptotic exponent for multiplying two n × n matrices over a field.

  • Method

    The paper modifies an existing framework so that analyzing tensor powers reduces to polynomially many convex optimization problems with polynomially many variables.

  • Results

    ω < 2.3728639 is obtained by analyzing the 32nd power using both algorithms.

  • Takeaways & Limitations

    The method also applies to trilinear forms with similar structure and can analyze tensor powers through recursively constructed tight-support decompositions.

  • Takeaways & Limitations

    Two described generalizations do not seem to improve ω when applied to existing constructions.

Abstract

from arXiv · show

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic constructions also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches, this method is based on convex optimization, and thus has polynomial-time complexity. As an application, we use this method to study powers of the construction given by Coppersmith and Winograd [Journal of Symbolic Computation, 1990] and obtain the upper bound $ω<2.3728639$ on the exponent of square matrix multiplication, which slightly improves the best known upper bound.

1 Introduction

The paper develops a polynomial-time convex-optimization framework for analyzing tensor powers and applies it to improve upper bounds on the matrix-multiplication exponent ω.

  • Matrix multiplication has subcubic algorithms, and the central question is determining the exponent ω, widely conjectured to equal 2.The naive algorithm uses O(n^3) operations, while Strassen’s algorithm uses O(n^2.81).
  • Coppersmith and Winograd’s construction achieved the bound ω < 2.3754770 by analyzing its second tensor power.
  • Higher tensor powers produced further progress, with the fourth power improving the bound through a non-convex optimization problem.
  • The paper modifies the existing framework so computing Vρ(t⊗m) reduces to polynomially many convex optimization problems with polynomially many variables.Solutions can be found in polynomial time, and dual problems can certify optimality.
  • The analyzed powers produce improved upper bounds, while powers beyond 32 are expected to yield only negligible improvements.
  • The method applies to structurally similar trilinear forms and is illustrated on an asymmetric form in the appendix.

2 Algebraic Complexity Theory

This section introduces tensors and the algebraic-complexity framework connecting degeneration, border rank, tensor value, and upper bounds on ω.

  • Trilinear forms: A trilinear form, or tensor, is an element of U ⊗ V ⊗ W and can be represented as a three-dimensional array over a field.
  • Matrix multiplication: Matrix multiplication corresponds to a trilinear form whose coefficients encode compatible indices from the two input matrices and the output matrix.
  • Tensor operations: Tensor direct sums and tensor products define additive and multiplicative constructions, with repeated products denoted t⊗c.
  • Border rank and degeneration: A tensor’s border rank characterizes the number of arithmetic operations needed to compute it, while degeneration formalizes conversion between tensor computations.
  • The exponent of matrix multiplication: Schönhage’s theorem links a tensor of small border rank that degenerates into matrix-multiplication tensors to upper bounds on ω.
  • Tensor value: The tensor value Vρ is monotone under degeneration and superadditive and supermultiplicative under direct sums and tensor products.
  • The exponent of matrix multiplication: If Vρ(t) ≥ R(t) for 2 ≤ ρ ≤ 3, then ω ≤ ρ.

3 Preliminaries and Notations

The preliminaries define tight supports, probability distributions, marginal compatibility, invariance, and the compatibility degree used in the paper’s optimization framework.

  • Tightness: For a finite set S ⊂ Z^3, tightness requires all coordinate sums to equal a common integer.
  • Tightness: A set is b-tight when its coordinates additionally lie in {0, 1, ..., b − 1}, implying |S| ≤ b^2.
  • Probability distributions: D(S) denotes the probability distributions on S, and each distribution has three marginal distributions associated with the coordinate maps.
  • Invariance: A function is G-invariant when applying every permutation in subgroup G leaves it unchanged.
  • Compatibility degree: The compatibility degree χ(S, G) is defined from the invariant function space with zero marginal functions.
  • Symmetry: Coordinate permutations can induce symmetries of S through L-symmetry, where L is a subgroup of the three-coordinate permutation group.
  • Compatibility: Two probability distributions are compatible when their three marginal distributions agree coordinatewise.

4 General Theory

The paper reduces lower-bound computation for the value of tensors with tight support to convex optimization, then uses this framework to analyze symmetries and an alternative optimization approach.

  • 4.1 Derivation of lower bounds on the value: Theorem 4.1 reduces a lower bound on log(Vρ(t)) for a tight-support decomposition to an optimization problem over probability distributions on its support.The framework applies for ρ ∈[2, 3] and incorporates the tensor’s component values through the function Ψt,ρ.
  • 4.2 Solving the optimization problem: The optimization is generally non-convex because of ΓS(P), but fixing P makes computing −ΓS(P) a strictly convex problem with a unique solution.The resulting distribution provides a lower bound through Ψt,ρ, although its tightness depends on the initial choice of P.
  • 4.2 Solving the optimization problem: Algorithm A takes a tight support, ρ, and component values as input and outputs a lower bound on log(Vρ(t)).Its two optimization problems are convex and have at most |S| variables, so standard methods solve them to accuracy ε in time polynomial in |S| and log(1/ε).
  • 4.2 Solving the optimization problem: Symmetries can reduce Algorithm A’s variables because invariant decompositions admit invariant solutions to the relevant convex optimization problems.The same principle applies to subgroup-invariant distributions and to the decomposition symmetries used in the paper.
  • 4.3 Another approach: Algorithm B uses a subgroup-invariant distribution satisfying Proposition 4.1’s conditions, ensuring ΓS(P)=0 and yielding log(Vρ(t)) ≥ Ψt,ρ(P).It outputs Ψt,ρ(˜P) after solving an optimization problem over the invariant distributions.

5 Powers of Tensors

The paper recursively analyzes tensor powers by constructing tight-support decompositions and computing component-value lower bounds with convex optimization, yielding polynomial-size optimization procedures for powers of two.

  • 5 Powers of Tensors: The method analyzes Vρ(t⊗t′) from tight-support decompositions of t and t′, using known lower bounds for their component values.The construction also applies recursively when t′ is a tensor power of t.
  • 5 Powers of Tensors: For t′=t, the procedure constructs a tight-support decomposition of t⊗2 and lower-bounds the value of every component.This information is reused to analyze t⊗4, and iteration extends the approach to t⊗2^r.
  • 5 Powers of Tensors: The recursive procedure requires at most r(2 + 2|supp(t⊗2^r)|) convex optimization problems, each with at most |supp(t⊗2^r)| variables.If supp(t) is b-tight, then supp(t⊗2^r) is (b2^r)-tight and has size at most (b2^r)^2.
  • 5 Powers of Tensors: Theorem 5.1 states that for any r ≥1, a lower bound on Vρ(t⊗2^r) is computable using poly(b, 2^r) convex optimizations, each with poly(b, 2^r) variables.The assumptions are a b-tight support and known lower bounds on every component value.
  • 5 Powers of Tensors: Decomposition symmetries are preserved through tensor-power recursion and can reduce the distributions’ optimization domains.The construction preserves {id, π}-invariance and more general L-invariance when the original support has the corresponding symmetry.
  • 5 Powers of Tensors: The framework generalizes to non-power-of-two tensor products and alternative linear dependences in the support definition, but these extensions do not seem to improve ω for existing constructions.The latter scope boundary is explicitly reported for the proposed generalizations.

6 Application

The paper applies its optimization framework to powers of the Coppersmith–Winograd trilinear form, obtaining progressively improved upper bounds on ω. Algorithm A enables polynomial-time analysis, while combining Algorithms A and B reaches ω < 2.3728639 for the 32nd power.

  • Construction: The Coppersmith–Winograd form t has border rank R(t) = q + 2 and a decomposition with six support components.Its decomposition is organized through three-way direct-sum splittings and has tight support S.
  • Algorithm A: ω < 2.38719 is recovered for t, and ω < 2.3754770 for t⊗2, matching previously reported bounds.The bounds follow by combining lower bounds on Vρ with Theorem 2.2 and the relevant rank inequalities.
  • Algorithm A: ω < 2.3729372 is obtained for t⊗4 using Algorithm A with q = 5 and ρ = 2.3729372.Component lower bounds are computed using Lemma 6.1 and Algorithm A, with optimal probability distributions reported in Table 3.
  • Algorithms A and B: ω < 2.3729269 is obtained for t⊗4 using Algorithm B, whose two additional constraints are highly non-convex but remain tractable.For t⊗8, the corresponding non-convex optimization uses 30 variables and 14 non-convex constraints and gives ω < 2.3728642.
  • Algorithms A and B: ω < 2.3728640 and ω < 2.3728639 are obtained for t⊗16 and t⊗32 by combining Algorithm A with Algorithm-B component bounds from t⊗8.The higher-power analysis avoids directly solving Algorithm B’s apparently intractable non-convex problems.

A Proof of Theorem 4.1

The appendix prepares a proof of Theorem 4.1 by restricting attention to rational probability distributions and approximating the resulting combinatorial quantities using entropy and Stirling’s formula.

  • Preliminaries: The proof introduces 1/N-valued distributions, whose probabilities are integer multiples of 1/N.This restriction supports finite combinatorial counting in the proof.
  • Preliminaries: The quantities Φℓ,N(P) and Φ′ℓ,N(P, Q) are integers because they can be rewritten as multinomial-coefficient products.Stirling’s approximation is then used to control their asymptotic behavior.
  • Preliminaries: For sufficiently large N, Lemma A.1 bounds the normalized logarithms of these combinatorial quantities using marginal entropies, up to an arbitrarily small δ.The bound applies uniformly to compatible 1/N-valued distributions.

A.2 A combinatorial lemma

The combinatorial lemma extracts a large subset with injective coordinate projections from structured tuples satisfying balanced fiber conditions.

  • Setup: The construction starts with a finite support S and a set Λ of tuples whose coordinatewise entries lie in S.The maps β1, β2, and β3 record the three coordinate projections of Λ.
  • Assumptions: Conditions (i)–(iii) require matching coordinate images and controlled-to-one fiber sizes for Λ and its subset Λ∗.These assumptions provide the regularity needed for the extraction argument.
  • Conclusion: Lemma A.2 produces sets F1, F2, and F3 whose induced set Δ is contained in Λ∗ and has unique coordinate projections.For sufficiently large M, Δ can additionally be chosen to retain the required size up to an ε-dependent loss.

A.3 Proof of Theorem 4.1

The proof of Theorem 4.1 classifies tensor-power terms by empirical distributions, prunes incompatible terms, and extracts a direct sum whose value is controlled by entropy and component values.

  • Type classification: A rational distribution P is made 1/N-valued, and terms in t⊗N are classified by the frequency distribution Q of their coordinate triples.The three marginals P1, P2, and P3 determine the permitted coordinate sequences.
  • Pruning: The proof retains only terms whose coordinate sequences have the prescribed marginal distributions, producing a pruned form with support S̄.This form is obtained from t⊗N by zeroing variables and is therefore a degeneration of it.
  • Counting: The numbers of compatible tuples and tuples of each type are expressed through Φℓ,N(P) and Φ′ℓ,N(P, Q), with supermultiplicativity supplying component-value bounds.The resulting inequalities combine these counts with the values of tensor components.
  • Extraction: A threefold tensor construction yields a decomposition whose components have disjoint variables after applying Lemma A.2.The extracted set Δ gives the injectivity needed for the direct-sum decomposition and degeneration argument.
  • Asymptotic bound: Superadditivity, entropy estimates, and limits δ, ε → 0 and N → ∞ produce the theorem’s final lower bound on log(Vρ(t)).The proof uses the entropy inequality H(Q) ≤ log |S| before taking the asymptotic limits.

B Another Application

This appendix applies the paper’s framework to the asymmetric trilinear form u and summarizes the resulting upper bounds on ω.

  • B Another Application: The form u was proposed by Coppersmith and Winograd and is asymmetric because its decomposition is not S3-invariant.The appendix uses u to illustrate how the techniques apply to asymmetric forms.
  • B Another Application: The upper bounds on ω obtained by studying powers of u are summarized in Table 6.The table reports bounds derived from analyses of the m-th tensor powers of u.
  • B Another Application: The bounds obtained from u are worse than those obtained from t, but they demonstrate the framework’s application to asymmetric forms.This comparison is explicitly stated as the purpose of the appendix application.

B.1 Construction

The construction defines an asymmetric trilinear form u on three (q+1)-dimensional vector spaces and uses its decomposition to derive an upper bound on ω.

  • B.1 Construction: The construction takes three vector spaces U, V, and W of dimension q+1 over an arbitrary field F, with specified bases.The bases are {x1, …, xq+1}, {y0, …, yq}, and {z0, …, zq}.
  • B.1 Construction: Coppersmith and Winograd showed that the border rank of u is q+1.The border-rank value is used with the value lower bound to obtain an exponent bound.
  • B.1 Construction: The decomposition induced by the subspaces U1, U2, V0, V1, W0, and W1 has tight support.The subspaces split the basis directions into the components used in the analysis.
  • B.1 Construction: For ρ ∈[2, 3], the component values satisfy Vρ(u(2, 0, 0)) = 1 and Vρ(u(1, 1, 0)) = Vρ(u(1, 0, 1)) ≥ q^ρ/3.These component bounds feed into the optimization-based lower bound for Vρ(u).
  • B.1 Construction: With q = 4, a1 = 0.0302, a2 = a3 = 0.4849, and ρ = 2.46015, the analysis gives Vρ(u) > 5.0000005 and concludes ω < 2.46015.The probability distribution is parameterized by a1, a2, and a3 through the stated marginals.

B.2 Analyzing the powers using Algorithm A

The powers of u are analyzed by exploiting symmetry in their supports, recursively estimating component values, and applying Algorithm A to the resulting optimization problems.

  • B.2 Analyzing the powers using Algorithm A: The support of u⊗2r consists of triples (a, b, c) with a ∈{2r, . . . , 2r+1}, b,c ∈{0, . . . , 2r}, and a + b + c = 2r+1.The decomposition is invariant under swapping the second and third coordinates.
  • B.2 Analyzing the powers using Algorithm A: This {id, (2 3)}-invariance restricts the optimization to distributions satisfying P(a, b, c) = P(a, c, b).The restricted distributions are then parametrized for the optimization.
  • B.2 Analyzing the powers using Algorithm A: Lower bounds for component values are computed recursively with Algorithm A, while cases with a = 0, b = 0, or c = 0 can be handled analytically.Lemma B.1 provides the analytic bounds for those boundary cases.
  • B.2 Analyzing the powers using Algorithm A: The global optimization problems for r ∈{1, 2, 3, 4, 5} differ in variable count and compatibility degree, and Algorithm A is demonstrated for r = 1, 2, 3.The parameter summary appears in Table 7.
  • B.2 Analyzing the powers using Algorithm A: ω < 2.44998 is obtained for u⊗2 from Vρ(u⊗2) > 16.00002 at q = 3 and ρ = 2.44998.The calculation uses a specified probability distribution over the support components.
  • B.2 Analyzing the powers using Algorithm A: ω < 2.44303 is obtained for u⊗4 using Algorithm A with q = 3 and ρ = 2.44303.The component values and optimal probability distributions are summarized in Table 9.
  • B.2 Analyzing the powers using Algorithm A: ω < 2.44278 is obtained for u⊗8 using Algorithm A with q = 3 and ρ = 2.44278.The corresponding component values and optimal probability distributions are summarized in Table 10.
Loading 1401.7714v1…