PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster Matrix Multiplication via Asymmetric Hashing

Ran Duan, Hongxun Wu, Renfei Zhou

arXiv:2210.10173v5cs.DS

TL;DR

The paper addresses limitations in laser-method analyses of Coppersmith–Winograd tensors for determining the matrix-multiplication exponent ω. It identifies combination loss and compensates for it with asymmetric hashing, obtaining ω < 2.371866 from the eighth power and breaking the prior 2.3725 barrier. The approach nevertheless remains subject to broader algorithmic barriers.

  • Problem

    The exact matrix-multiplication exponent ω is unknown, while higher-power Coppersmith–Winograd analyses are not tight and face a 2.3725 limitation under previous approaches.

  • Method

    The paper identifies combination loss across adjacent analysis levels and compensates for it using asymmetric hashing applied to Coppersmith–Winograd tensor powers.

  • Results

    ω < 2.371866 is obtained by analyzing the eighth power of the Coppersmith–Winograd tensor, improving the previous bound and breaking the 2.3725 lower bound.

  • Takeaways & Limitations

    The asymmetric-hashing analysis provides an improved fast matrix multiplication bound beyond the 2.3725 limitation reached by previous higher-power analyses.

  • Takeaways & Limitations

    The approach remains subject to broader barriers, including a 2.3078 limitation proved for a wider class of algorithms.

Abstract

from arXiv · show

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $ω$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a "combination loss", and we partially compensate for it using an asymmetric version of CW's hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $ω<2.371866$, which improves the previous best bound of $ω<2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of $2.3725$ in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.

1 Introduction

Fast matrix multiplication seeks the unknown exponent ω, whose value affects matrix operations and combinatorial algorithms. Recent laser-method analyses of Coppersmith–Winograd tensors improve bounds, but higher powers incur losses that this paper addresses with asymmetric hashing.

  • Motivation: The matrix-multiplication exponent ω remains unknown, despite more than 50 years of study and broad implications for related algorithms.Fast matrix multiplication has similar complexity to operations such as matrix inversion and determinant computation, and can accelerate problems including transitive closure and shortest paths.
  • Prior methods: Recent best bounds apply Strassen’s laser method to Coppersmith–Winograd tensors and reach ω < 2.3728596.The laser method raises a tensor to a power, zeroes selected variables, and degenerates the result into independent matrix-multiplication tensors.
  • Limitations: Higher-power analyses improve ω bounds but remain non-tight because their recursive structure and hash-modulus losses constrain the analysis.The bound for one power depends on the previous power, while refined laser methods compensate for extra loss in hash moduli.
  • Contribution: The paper identifies a combination loss arising from the structure of adjacent recursion levels rather than from a single level.It uses asymmetric hashing to compensate for this loss, improving the second-power analysis to ω < 2.374631 and higher-power analysis to ω < 2.371866.
  • Contribution: Prior work showed that analyzing lower powers with previous approaches could not improve the upper bound beyond ω < 2.3725, even at arbitrarily high powers.The paper’s approach addresses this limitation through improved lower-power analyses, while remaining subject to broader barriers.

2 Technical Overview

The paper exposes a hidden combination loss in higher-power analyses of the Coppersmith-Winograd tensor and compensates for it with asymmetric hashing. This approach extends the laser method to obtain improved bounds, including ω < 2.371866 from the eighth power.

  • Combination Loss: The combination loss arises from the structure of adjacent analysis levels, rather than from a single recursion level.Opening the structure of subtensors makes this loss visible.
  • Two-Level Analysis: In the second-power construction, level-2 subtensors are formed by coarsening products of level-1 variable partitions, but T1,1,2 and its permutations are not matrix multiplication tensors.Other listed components, including T0,0,4, T0,1,3, and T0,2,2 and their permutations, are matrix multiplication tensors.
  • Laser Method: The laser method takes tensor powers, zeroes selected variables, and leaves independent matrix multiplication tensors to which Schönhage’s τ theorem applies.The starting tensor is CWq, whose asymptotic rank is q + 2.
  • Combination Loss: The original second-power analysis has an exponentially large gap between |Z′| and |ZM| because λ and µ differ by a constant when ω > 2.The paper identifies this gap as the combination loss that may be compensated.
  • Asymmetric Hashing: Asymmetric hashing creates more level-2 X- and Y-blocks than Z-blocks, allowing each Z-block to match multiple X,Y pairs while X- and Y-blocks remain unique.Uniqueness of X- and Y-blocks is needed to remove interfering terms.
  • Beyond the Second Power: ω < 2.371866 is obtained from the eighth power after compensating for combination loss at each level, breaking the 2.3725 limitation for earlier analyses.The same repeated-variable-block idea already improves several level-3 subtensors.

3 Preliminaries

This section introduces tensors, their operations and ranks, and the connection between asymptotic rank and the matrix multiplication exponent ω.

  • Tensors: A tensor over variable sets X, Y, and Z is a multilinear sum whose coefficients lie in a field F.
  • Tensor operations: Tensor operations include direct sums, tensor products, summation, rotation, swapping, and symmetrization.
  • Symmetrization: 3-symmetrization cyclically rotates the tensor variables, while 6-symmetrization additionally incorporates swapping of the first two dimensions.
  • Ranks: Tensor rank is the minimum number of rank-one terms in a decomposition, and asymptotic rank captures its growth under tensor powers.
  • Connection to matrix multiplication: Schönhage’s τ theorem converts a suitable asymptotic-rank bound for a direct sum of matrix multiplication tensors into an upper bound ω ≤ 3τ.

3.2 Restrictions, Degenerations, and Values

This section defines restrictions, degenerations, zeroing out, identifications, and tensor values used to transform tensors while controlling asymptotic rank.

  • Restrictions: A restriction maps each variable set linearly into the span of another tensor’s variables and produces the target tensor.
  • Degenerations: A degeneration uses polynomial mappings in a formal variable and preserves the inequality eR(T′) ≤ eR(T).
  • Zeroing out: Zeroing out restricts a tensor by setting variables outside selected subsets X′, Y′, and Z′ to zero.
  • Identifications: An identification degenerates a direct sum of tensors on disjoint but corresponding variable copies into their sum on shared variables.
  • Values: Tensor values measure the asymptotic matrix-multiplication power of symmetrized tensors, with 6-symmetrized values needed for technical reasons here.

3.3 Partitions of a Tensor

This section organizes tensors into components through partitions, emphasizing P-partitioned tensors and the structured partition of the Coppersmith-Winograd tensor.

  • Tensor partitions: A partition divides each variable set into disjoint blocks and decomposes the tensor into subtensors indexed by block triples.
  • P-partitioned tensors: A P-partitioned tensor has nonzero components only when the three component indices sum to P.
  • Partitions of tensor powers: Tensor powers inherit block partitions through Cartesian products of the base blocks, producing indexed variable blocks.
  • Coppersmith-Winograd tensor: CWq has asymptotic rank eR(CWq) = q + 2, and its partition structure enables the laser method.

3.5 Leveled Partitions of CW Tensor Power

Leveled partitions regroup the same Coppersmith-Winograd tensor power at multiple granularities, enabling analysis of higher-power components and relationships between adjacent levels.

  • Motivation: Prior work improves bounds on ω by applying the laser method to tensor powers CWq⊗2^ℓ.
  • Level-ℓ partitions: For a fixed tensor power, a level-ℓ partition groups variables according to sums of blocks from the finer level-1 partition.
  • Level-ℓ components: A level-ℓ component Ti,j,k is nonzero only when i + j + k = 2^ℓ.
  • Tensor-power partitions: The induced level-ℓ partition of a tensor power consists of variable blocks indexed by sequences of component indices.
  • Relations between levels: Adjacent levels are related by adding consecutive entries in the finer index sequence, so each coarser block contains multiple finer blocks.

3.6 Distributions and Entropy

The paper represents tensor components and their index sequences with joint and marginal distributions, then uses entropy and split distributions to organize recursive higher-power analysis.

  • Component and marginal distributions: A component distribution assigns frequencies to level-ℓ components T_i,j,k, while its marginals record the corresponding X-, Y-, and Z-index frequencies.These distributions characterize triples of variable blocks in tensor powers.
  • Joint distributions: At level 1, specified marginal distributions uniquely determine the joint component distribution when it exists.At higher levels, the same marginals can correspond to multiple joint distributions.
  • Joint distributions: D_α collects joint distributions sharing α’s marginals, and D*(α_X, α_Y, α_Z) selects one with maximum entropy.This separates fixed marginal information from the choice of joint distribution used in analysis.
  • Split distributions: Higher-level marginal distributions do not generally determine joint distributions, causing a loss in moduli that the refined laser method can reduce.The paper’s split-distribution framework tracks this inter-level structure explicitly.
  • Split distributions: A level-ℓ component splits into two level-(ℓ−1) components, and a split distribution specifies the frequencies of these decompositions.The split distribution is constrained by the component indices and preserves their total sums.

3.8 Salem-Spencer Set

The Salem-Spencer set supplies a large modular set without nontrivial three-term arithmetic progressions, supporting the hashing step used to isolate independent matrix products.

  • Role in the laser method: Prior analyses use Salem-Spencer sets to construct independent matrix products after hashing and zeroing out incompatible variable blocks.The set’s progression-free property enforces matching hash values across retained triples.
  • Salem-Spencer property: For every positive integer M, a Salem-Spencer set A ⊂ {0, …, M−1} has size M^(1−o(1)) and no nontrivial three-term arithmetic progression modulo M.If a + c ≡ 2b (mod M) for elements of A, then a = b = c.

3.9 Restricted-Splitting Tensor Power

Restricted-splitting tensor powers constrain how a component is split across lower-level components, creating values that support the paper’s recursive analysis of higher powers.

  • Restricted-splitting values: Restricted-splitting values measure a subtensor’s ability to realize tensor powers under a prescribed splitting restriction.The restriction is treated as a predetermined input when evaluating the value.
  • Restricted-splitting tensor powers: The restricted-splitting tensor power is formed by retaining lower-level variable blocks compatible with a specified marginal split distribution and zeroing out the others.The construction is introduced as a new concept in the paper and can restrict X, Y, or Z blocks.
  • Recursive analysis: Restricted-splitting values replace ordinary component values as the interface between adjacent levels in the recursive analysis.Prior work lower-bounded each level-ℓ component using values from level ℓ−1 components.
  • Recursive analysis: The splitting restriction differs from the component and split distributions, which are variables selected to optimize a lower bound.The restriction is fixed in advance rather than optimized alongside those distributions.

3.10 Hashing Methods

The hashing methods retain many distribution-consistent triples while resolving collisions among variable blocks. The paper generalizes symmetric hashing with an asymmetric variant that permits shared Z-blocks and improves utilization.

  • Asymmetric hashing: Asymmetric hashing removes collisions on X- and Y-blocks while allowing Z-blocks to occur in multiple retained triples.A greedy process zeroes out involved X or Y blocks until no such sharing remains.
  • Symmetric hashing: Symmetric hashing instead eliminates sharing among X-, Y-, and Z-blocks so that every retained variable block belongs to at most one triple.This is the setting used in most previous work.
  • Hashing setup: The method first keeps triples consistent with a chosen joint distribution α, called good triples, while zeroing out blocks inconsistent with α’s marginals.The numbers of blocks and good triples are tracked through N_BX, N_BY, N_BZ, and N_α.
  • Hashing setup: Hashing maps variable blocks to modular buckets and retains triples whose three hash values coincide in a large Salem-Spencer set.The progression-free property forces equal bucket values for retained triples.
  • Hashing guarantees: The expected number of retained good triples is at least N_BX N_α / N_{αX,αY,αZ} · 2^(−o(n)) under a typical choice of M.The choice M = Θ(N_{αX,αY,αZ}/N_BX) balances hashing and collision losses.
  • Hashing guarantees: Hash loss measures the wasted fraction of X-blocks when R = N_α/N_{αX,αY,αZ} is exponentially small rather than 2^(−o(n)).When α maximizes the number of triples among distributions with fixed marginals, the loss is only polynomially small.

4 Improving the Second Power of CW Tensor

The second-power analysis replaces symmetric hashing with an asymmetric method to compensate for combination loss, while preserving a degeneration into independent matrix multiplication tensors. This yields progressively improved bounds, reaching ω < 2.374631 for the second power.

  • Second-power framework: ω < 2.375234 improves the previous second-power bound ω < 2.375477 through new theoretical ideas rather than better optimization.The optimization for the second power was previously solvable exactly by hand.
  • Second-power framework: The analysis applies four stages: lower-bound component values, choose a symmetric component distribution, hash and zero out variable blocks, then degenerate retained triples into matrix multiplication tensors.Schönhage’s τ theorem is then used to obtain an upper bound on ω.
  • Symmetric hashing: Symmetric hashing retains independent triples consistent with the chosen distribution, but it can incur hash loss when that distribution is not maximum entropy for its marginals.Zeroing out distinguishes marginal distributions but not joint distributions.
  • Asymmetric hashing: The asymmetric method allows each level-2 Z-block to occur in multiple retained triples, compensating for the combination loss that limits the symmetric analysis.Additional zeroing out ensures incompatible variables are removed while preserving the required structure.
  • Asymmetric hashing: After additional zeroing out, each retained triple becomes an unbroken copy of the target tensor and can be degenerated into matrix multiplication tensors despite initially broken copies.The procedure fixes all holes while losing only a factor of O(n) in the number of matrix multiplication tensors.
  • Second-power result: ω < 2.374631 is obtained from the second power by choosing parameters that make each Z-block shareable across more retained triples.The paper presents this as the generalizable form of the improvement for higher powers.

5 Hole Lemma

The Hole Lemma handles broken copies of a standard form tensor by exploiting symmetry to repair zeroed-out Z-blocks. Sufficiently many non-hole fractions then yield complete copies of the tensor.

  • Standard form tensors: The standard form tensor organizes distinct level-ℓ components with parameters for multiplicities, indices, and Z-split distributions.Its lower-level variables are partitioned into small X-, Y-, and Z-blocks.
  • Broken standard form tensors: A broken copy of T* is obtained by zeroing out available small Z-blocks, called holes.The remaining available blocks are non-hole blocks, and their proportions define the hole and non-hole fractions.
  • Hole Lemma conclusion: When the sum of non-hole fractions is at least N^ℓ + 1, the broken copies degenerate into one complete copy of T*.The lemma also implies that substantially larger sums can produce multiple complete copies.
  • Hole repair: The proof randomly permutes broken copies so that each Z-block is non-hole in at least one copy.The argument uses the symmetry of T* and then applies the resulting permutations to the broken tensors.
  • Symmetry and shuffling: The shuffling group permutes paired lower-level positions and preserves available Z-blocks, block triples, and tensor terms.This establishes automorphisms that preserve the structure of the standard form tensor.

6 Improving High-Power Global Values

This section applies asymmetric hashing and additional zeroing-out to high-power CW tensors. The resulting broken tensors are repaired with the Hole Lemma and degenerated into matrix multiplication tensors.

  • Algorithm inputs and output: The algorithm optimizes a distribution over level-ℓ components using supplied restricted-splitting value bounds.Its output is a lower bound on the value of the high-power CW tensor.
  • Asymmetric hashing: Asymmetric hashing ensures retained triples have distinct X- and Y-block indices, may share Z-blocks, and obey the joint distribution α.The modulus M is chosen from an interval specified by the algorithm.
  • Compatibility and zeroing-out: Additional zeroing-out enforces compatibility between small Z-blocks and retained large triples through marginal and component-level split distributions.The resulting compatibility condition is sufficient for remaining small blocks to form triples only with compatible large triples.
  • Hole repair and degeneration: Each retained triple produces a broken copy of T* with holes in its Z-variables, which the Hole Lemma can repair before degeneration.Fixing holes first avoids introducing X/Y holes during the later symmetrization step.
  • Probability of holes: A useful Z-block has probability at most 1/8 of being a hole, enabling the construction to retain many non-hole blocks.The analysis then uses the probabilistic method to lower-bound the number of copies of T*.
  • Numerical result: ω < 2.374631 is obtained by breaking symmetry among selected level-2 components and using different restricted-splitting distributions.The parameters were found by a MATLAB program.

7 Improving Component Values

The component-value analysis introduces additional asymmetry between X/Y and Z variables and uses multiple split distributions across tensor factors. It outputs lower bounds for restricted-splitting values of higher-level components.

  • Asymmetric tensor construction: The new component analysis replaces the fully symmetric tensor with an asymmetric tensor because asymmetric hashing matches each Z-block with multiple X/Y-block pairs.X and Y remain symmetric because their blocks are still matched one-to-one.
  • Factorized construction: The construction divides the tensor into three factors with possibly different parameters A1, A2, and A3 satisfying A1 + A2 + A3 = 1.Each factor receives a potentially different split distribution, allowing asymmetry across regions.
  • Restricted split distributions: The method restricts Z-split distributions so the final tensor can be symmetrized and degenerated into matrix multiplication tensors.Without these restrictions, the required degeneration into the final tensor is unavailable.
  • Optimization: The algorithm optimizes three joint split distributions for cyclic permutations of the component indices.Their Z-marginals are constrained by the selected split distributions.
  • Output: The output is a lower bound on Vτ^(6)(Ti,j,k, eαZ) for a level-(ℓ+1) component.This bound is obtained from supplied lower-level restricted-splitting values and the optimized distributions.
  • Hole analysis: At least 2^-o(n) of useful blocks are typical, and each has Ω(1) probability of not being a hole, yielding ηI,J,K ≥ 2^-o(n).The hole probability bound used here is at most 1/8.

8 Heuristics and Numerical results

The optimization framework propagates value pairs across tensor components and levels, rather than optimizing component values independently. A computer program applies these bounds and obtains the global value used to certify the matrix-multiplication exponent.

  • Optimization framework: Algorithm 4 optimizes restricted-splitting value pairs across components and levels to produce a global value Vglob.The value pair combines a component’s value with its split distribution, and the global value can imply an upper bound on ω through Schönhage’s τ theorem.
  • Component analysis: Different component types receive different bounds: asymmetric hashing handles many higher-level components, while merging handles components containing a zero index.For level-2 components, the method instead uses symmetric hashing because asymmetric hashing is not applicable.
  • Heuristics: The optimization becomes more difficult for higher powers because the bounds have more complicated forms and the process slows substantially.The analysis therefore relies on heuristics to make objectives convex enough for optimization.
  • Optimization framework: Value pairs cannot be compared by component value alone because their split distributions affect subsequent levels.This dependence prevents simply decoupling the optimization into independent component subproblems.
  • Heuristics: The framework uses alternating optimization to update component and global parameters sequentially from lower to higher levels.Each iteration updates one component at a time, with the resulting parameters used in later subproblems.
  • Numerical results: The program verifies ω ≤ 2.371866 by recursively checking restricted-splitting bounds and confirms improvements for the second and fourth powers.The second- and fourth-power improvements are reported as numerical results in Table 3.

A Missing Proofs from Section 4

The section derives restricted-splitting bounds for level-2 components by zeroing inconsistent blocks, symmetrizing tensors, and applying hashing to obtain equal-sized matrix multiplication tensors.

  • Component (0,2,2): The component (0,2,2) is converted into a matrix multiplication tensor by retaining Z-blocks consistent with its split distribution.The resulting tensor uses all remaining Z-variables.
  • Component (0,2,2): The optimized parameter b′′ = 1/(2 + q2) maximizes the matrix multiplication tensor size in the (0,2,2) analysis.This choice gives the lower bound for the non-rotational restricted-splitting value.
  • Component (1,1,2): For component (1,1,2), three-way symmetrization followed by symmetric hashing yields a restricted-splitting lower bound.The construction uses the Z-marginal of the split distribution and produces the bound stated in the section.
  • Zeroing-out: Additional zeroing-out removes incompatible triples, while the component split distributions imply compatibility for the remaining blocks.The argument uses the split distributions of related components to infer compatibility in component (1,1,2).
  • Degeneration: The degeneration in Lemma 4.12 is a zeroing-out that produces a direct sum of equal-sized matrix multiplication tensors.It combines the corresponding degenerations of several factors.

B Heuristics for Section 4

The section replaces a difficult optimization with an iterative heuristic that fixes selected parameters, repeatedly solves an approximated program, and then restores feasibility before computing the final bound.

  • Approximated program: The heuristic removes a ratio that is close to one in practice and makes optimization extremely difficult.This simplifies the objective without changing the stated practical behavior of the optimal solution.
  • Approximated program: Replacing α*_P with a fixed reference value makes the approximated objective logarithmic concave.The original α_P is a complicated function of several optimization parameters.
  • Iterative heuristic: The procedure repeatedly solves the approximated program, updating α*_P from the previous solution.The final iteration’s solution is used as the result.
  • Iterative heuristic: In practice, at most five iterations are sufficient before a small perturbation enforces the feasibility constraint.The perturbation is reported to cause little loss in solution quality.
  • Final bound: After perturbation, Algorithm 1 is run to obtain the final bound.The output is based on the feasible parameter choice produced by the heuristic.

C Mising Proofs from Section 7

The section proves counting relations for useful and typical blocks in the asymmetric hashing analysis. These relations establish that strongly useful blocks are sufficiently numerous under the prescribed split distributions.

  • Useful blocks: A block is strongly useful when its marginal split distributions match the prescribed distributions across regions and components.The definition imposes split constraints for every region and relevant level component.
  • Adjacent levels: The proof organizes positions into left and right parts of higher-level components when relating adjacent levels.These position sets form a partition used to track component marginals.
  • Counting argument: The number of strongly useful blocks is obtained by multiplying counts of valid index splits over disjoint position sets.Each constraint contributes a count governed by the entropy of the target split distribution.
  • Typicality: Matching the prescribed marginal distributions makes a block both typical and strongly useful.The proof counts blocks satisfying these joint conditions and compares them with the strongly useful count.
  • Counting argument: The resulting counts agree up to a negligible factor 2^o(n), establishing the key counting relation.A parallel argument establishes the second relation used in the proof.
Loading 2210.10173v5…