Faster Matrix Multiplication via Asymmetric Hashing

Introduction

The time complexity of multiplying two $n\times n$ matrices is usually denoted by $O(n^{\omega+o(1)})$ for some real number $\omega$. (It is easy to see that $2\leq\omega\leq 3$.) Although it has been studied for more than 50 years, the exact value of $\omega$ is still unknown, and many people believe that $\omega=2$. The determination of the constant $\omega$ would have wide implications. Not only do many matrix operations have similar complexities as fast matrix multiplication (FMM) algorithms, such as LUP decomposition, matrix inversion, determinant [AH74, BH74], algorithms for many combinatorial problems can also be accelerated by FMM algorithms, including graph problems like transitive closure (see [AH74]), unweighted all-pair shortest paths [Sei95, Zwi02], all-pair bottleneck path [DP09], and other problems such as context-free grammar parsing [Val75] and RNA-folding [BGSW19].

In this paper, we identify a more implicit “combination loss”, which is our main contribution. Such loss arises not from a single recursion level, but from the structure of adjacent levels. To demonstrate that this observation indeed leads to an improved algorithm, we compensate for this loss using an asymmetric hashing method. This improves the analysis of the second power by Coppersmith and Winograd [CW90] to $\omega<2.374631$. We also generalize it to higher powers and obtain the improved bound of $\omega<2.371866$.This bound is slightly better than the previous version of this paper due to more flexibility in optimizing parameters. A similar asymmetric hashing method was used in [CW90] to analyze an asymmetric tensor. Fast rectangular matrix multiplication algorithms (e.g. [Cop82, Cop97, HP98, LG12, LGU18]) also use asymmetric hashing to degenerate the tensor power $T^{\otimes N}$ in the laser method into independent rectangular matrix multiplications. In this paper, we use asymetric hashing for a different purpose, that is, to compensate for the “combination loss”.

Another approach to fast matrix multiplication is the group theoretical method of Cohn and Umans [CU03, CKSU05, CU13]. There are also works on its limitations [ASU12, BCC+16, BCC+17, BCG+22].

In Section 2, we will first give an overview of the laser method and our improved algorithm. In Section 3, we introduce the concepts and notations that we will use in this paper, as well as some basic building blocks, for example, the asymmetric hashing method. To better illustrate our ideas, in Section 4, we give an improved analysis of the second power of the CW tensor. In Sections 5, 6, and 7, we will extend the analysis to higher powers. In Section 8, we discuss our optimization program and give the numerical results.

Technical Overview

It is helpful to start with a high-level description of Coppersmith-Winograd [CW90]. Our exposition here differs a little from their original work. Specifically, their work uses the values of subtensors in a black-box way. We open up this black box and look at the structure inside those subtensors. This change will make the combination loss visible.

In the following, we will assume some familiarity with the Coppersmith-Winograd Algorithm. For an exposition of their algorithm, the reader may also refer to the excellent survey by Bläser [Blä13].

For $\widetilde{X}=X\times X$, the product of two level-1 partitions gives $\widetilde{X}=\bigcup_{i^{\prime},i^{\prime\prime}}X_{i^{\prime}}\times X_{i^{\prime\prime}}$. We define the level-2 partition to be a coarsening of this. For each $i\in\{0,1,2,3,4\}$, we define

For example, $\widetilde{X}_{2}=(X_{0}\times X_{2})\cup(X_{1}\times X_{1})\cup(X_{2}\times X_{0})$. The level-2 partition is given by $\widetilde{X}=\widetilde{X}_{0}\cup\widetilde{X}_{1}\cup\cdots\cup\widetilde{X}_{4}$, $\widetilde{Y}=\widetilde{Y}_{0}\cup\widetilde{Y}_{1}\cup\cdots\cup\widetilde{Y}_{4}$, and $\widetilde{Z}=\widetilde{Z}_{0}\cup\widetilde{Z}_{1}\cup\cdots\cup\widetilde{Z}_{4}$.

For example, $T_{1,1,2}=T_{1,1,0}\otimes T_{0,0,2}+T_{0,0,2}\otimes T_{1,1,0}+T_{1,0,1}\otimes T_{0,1,1}+T_{0,1,1}\otimes T_{1,0,1}$.For notational convenience, we let $T_{i,j,k}=0$ if any of $i,j,k$ is negative.

The Laser Method.

These subtensors are supported on disjoint variables.

Such a single-level analysis gives a bound of $\omega<2.38719$. By considering the second power, Coppersmith and Winograd [CW90] get an improved bound of $\omega<2.375477$. Note in the analysis above, for any two non-independent matrix multiplication tensors, only one of them will survive the zeroing-out. Looking ahead, the two-level analysis will further exploit the tensor power structure and “merge” some non-independent matrix multiplication tensors into a larger one.

Variable Blocks.

Two-level Analysis.

We are now ready to describe the two-level analysis of Coppersmith-Winograd in detail.

We will zero out some level-2 blocks to obtain independent copies of $\mathcal{T}^{\alpha}$. By the symmetry of X, Y, and Z variables, we can assume that ${\alpha}_{\scriptscriptstyle\textup{X}}={\alpha}_{\scriptscriptstyle\textup{Y}}={\alpha}_{\scriptscriptstyle\textup{Z}}$. So we only focus on Z-variable blocks. Let $N_{\textup{BZ}}$ be the number of $Z_{K}$’s that obey ${\alpha}_{\scriptscriptstyle\textup{Z}}$. In order to make the Z blocks of all isomorphic copies of $\mathcal{T}^{\alpha}$ independent, there can be at most $N_{\textup{BZ}}$ copies of them.

In fact, using an elegant construction using hashing and the Salem-Spencer set [SS42, Beh46], Coppersmith and Winograd [CW90] showed that one could get $N_{\textup{BZ}}^{1-o(1)}$ such independent tensors. The $o(1)$ factor is negligible for our purpose.

Here, each $\mathcal{T}_{1,1,2}^{\widetilde{\alpha},m}$ is a subtensor of $T_{1,1,2}^{\otimes m}$ that splits according to $\widetilde{\alpha}^{(1,1,2)}$. A single $T_{1,1,2}^{\otimes m}$ contains many such isomorphic copies. We also get $\widetilde{\alpha}^{(1,2,1)}$ and $\widetilde{\alpha}^{(2,1,1)}$ from the symmetry under rotation, which defines $\mathcal{T}_{1,2,1}^{\widetilde{\alpha},m}$ and $\mathcal{T}_{2,1,1}^{\widetilde{\alpha},m}$.

For concreteness, let us first specify the minimum number of parameters that determine $\widetilde{\alpha}^{(1,1,2)}$. Since there is a symmetry between $T_{0,0,2}\otimes T_{1,1,0}$ and $T_{1,1,0}\otimes T_{0,0,2}$, we can w.l.o.g. assume that $\widetilde{\alpha}^{(1,1,2)}(0,0,2)=\widetilde{\alpha}^{(1,1,2)}(1,1,0)=\mu$ and $\widetilde{\alpha}^{(1,1,2)}(0,1,1)=\widetilde{\alpha}^{(1,1,2)}(1,0,1)=1/2-\mu$ for some $0\leq\mu\leq\frac{1}{2}$.

In $T_{1,2,1}^{\otimes m}$ and $T_{2,1,1}^{\otimes m}$, the marginal distribution for Z-variables is $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,2,1)}(0)=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,2,1)}(1)=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,1,1)}(0)=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,1,1)}(1)=1/2$. In $T_{1,1,2}^{\otimes m}$, the marginal for Z-variables is $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}(0)=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}(2)=\mu,\;\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}(1)=1-2\mu$.

many independent matrix multiplication tensors with $(q+2)^{2n}$ many multiplications. The distributions $\alpha$ and $\widetilde{\alpha}^{(1,1,2)}$ are carefully chosen to balance between the size of each matrix multiplication tensor and the total number of them.

Merging after splitting.

Essentially, this can be equivalently viewed as (1) splitting them into non-independent matrix multiplication subtensors and (2) merging these non-independent subtensors back into a single matrix multiplication tensor. As pointed out by [AFLG15], such merging is the reason why higher power analyses improve the bound of $\omega$.

In our algorithm, we cannot view $T_{0,j,k}$ as a large matrix multiplication, since we need its split distribution $\widetilde{\alpha}^{(0,j,k)}$. Hence we have to split it and merge it back. This gives a result as good as directly treating $T_{0,j,k}$ as a single matrix multiplication tensor.

Let us simply look at $T_{0,2,2}$ as an example. Let $m=\alpha(0,2,2)n$. We know that $T_{0,2,2}^{\otimes m}$ is isomorphic to the matrix multiplication tensor $\langle 1,1,(q^{2}+2)^{m}\rangle$.

Now we are going to split it. First, choose a distribution $\widetilde{\alpha}^{(0,2,2)}$ over $\{(0,0,2),(0,2,0),(0,1,1)\}$. We pick $\widetilde{\alpha}^{(0,2,2)}(0,0,2)=\widetilde{\alpha}^{(0,2,2)}(0,2,0)=\lambda$, and $\widetilde{\alpha}^{(0,2,2)}(0,1,1)=1-2\lambda$ for some $0\leq\lambda\leq\frac{1}{2}$. Then, the tensor $T_{0,2,2}^{\otimes m}$ alone contains $N_{022}=\binom{m}{\lambda m,\lambda m,(1-2\lambda)m}$ many (non-disjoint) isomorphic copies of

We need the fact that each $T_{0,0,2}$ is isomorphic to the matrix multiplication tensor $\langle 1,1,1\rangle$ while each $T_{0,1,1}$ is isomorphic to the matrix multiplication tensor $\langle 1,1,q\rangle$. This implies each $T^{\widetilde{\alpha},m}_{0,2,2}$ is isomorphic to the matrix multiplication tensor $\langle 1,1,q^{2(1-2\lambda)}\rangle$.

After zeroing out all the X, Y, and Z variables that do not obey our choice of $\widetilde{\alpha}^{(0,2,2)}$, we merge all these $N_{022}$ non-disjoint isomorphic copies back into a matrix multiplication tensor $\langle 1,1,N_{022}\cdot q^{2(1-2\lambda)}\rangle$. Taking $\lambda=\frac{1}{2+q^{2}}$, we get $\langle 1,1,N_{022}\cdot q^{2(1-2\lambda)}\rangle=\langle 1,1,(q^{2}+2)^{m(1-o(1))}\rangle$, which is as good as $\langle 1,1,(q^{2}+2)^{m}\rangle$ when $m$ goes to infinity.

2 Combination Loss

The key insight in our paper is that this analysis is actually wasteful. To see this, let us first summarize all the zeroing-outs we performed in the above analysis.

Taking the merging point of view for $T_{0,j,k}$’s, we get the following procedure:

Fix any $X_{I},Y_{J},Z_{K}$ and the corresponding subtensor $\mathcal{T}_{I,J,K}$. Consider level-1 blocks $X_{\widehat{I}}\in X_{I},\;Y_{\widehat{J}}\in Y_{J},\;Z_{\widehat{K}}\in Z_{K}$. For sequence $\widehat{K}$, we define its split distribution over set $S$ as

Let $S_{i,j,k}=\{t\mid i_{t}=i,j_{t}=j,k_{t}=k\}$ be the set of positions that belong to $T_{i,j,k}$. We say $Z_{\widehat{K}}$ obeys $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}$ if and only if for all $i,j,k$, we have $\textsf{split}(\widehat{K},S_{i,j,k})(\widehat{k}^{\prime},k-\widehat{k}^{\prime})=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(i,j,k)}(\widehat{k}^{\prime})$.For simplicity, we write $\textsf{split}(\widehat{K},S_{i,j,k})=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(i,j,k)}$ when there is no ambiguity. (Since we are taking the merging viewpoint, $T_{0,1,1}$ and $T_{0,0,2}$ have their split distributions as well.)

First, we zero out all the blocks $Z_{\widehat{K}}$ that do not obey $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}$. Same for the X and Y blocks. Then we further zero out some level-1 blocks according to hashing and the Salem-Spencer set. Note that this hashing is only over indices in $S_{1,1,2}\cup S_{1,2,1}\cup S_{2,1,1}$ because $T_{0,j,k}$’s are handled differently.

The subtensor of $\mathcal{T}_{I,J,K}$ over each remaining triple $(X_{I},Y_{J},Z_{K})$ is an isomorphic copy of

where $\mathcal{T}_{1,1,2}^{\widetilde{\alpha},m}$ (and $\mathcal{T}_{1,2,1}^{\widetilde{\alpha},m}$, $\mathcal{T}_{2,1,1}^{\widetilde{\alpha},m}$) is defined in (2) and other $\mathcal{T}_{0,j,k}^{\widetilde{\alpha},m}$’s are defined in the same way as (4). Finally, some copies of $\mathcal{T}^{\widetilde{\alpha}}$ are merged together, and we get independent matrix multiplication tensors.

Fix any remaining level-2 triple $M=(X_{I},Y_{J},Z_{K})$. We will show that many level-1 Z-blocks $Z_{\widehat{K}}\in Z_{K}$ are actually not used.

To answer this, note that in the second step, we zeroed out the blocks $Z_{\widehat{K}}$’s that do not obey $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}$. By definition, all remaining $Z_{\widehat{K}}$’s satisfy the following:

We let $Z^{M}=\{Z_{\widehat{K}}\in Z_{K}\mid\eqref{equ:split_condition}\text{ holds for }\widehat{K}\}$ denote this set of $Z_{\widehat{K}}$’s. This is the set of $Z_{\widehat{K}}$’s that we actually used in $M=(X_{I},Y_{J},Z_{K})$. We will argue that there are some other level-1 Z-blocks outside $Z^{M}$, that in a certain sense, is as “useful” as those in $Z^{M}$. To identify these blocks, we first define the average split distribution of $k$ as

Let $S_{k}=\cup_{i+j=4-k}\,S_{i,j,k}$ be the set of positions where $Z_{t}=k$. By definition, the condition (5) implies the following weaker condition which is independent of $I$ and $J$:

Let $Z^{\prime}=\{Z_{\widehat{K}}\in Z_{K}\mid\eqref{equ:avg_condition}\text{ holds for }\widehat{K}\}$ be the set of level-1 Z-blocks that satisfy this weaker condition. Clearly, $Z^{M}\subseteq Z^{\prime}$; below we will further show that $|Z^{M}|=|Z^{\prime}|\cdot 2^{-\Theta(n)}$. However, all $Z_{\widehat{K}}\in Z^{\prime}$ are “equivalent” in the sense that they are isomorphic up to a permutation over $[2n]$. We could take a bold guess: Those $Z_{\widehat{K}}$’s in $Z^{\prime}\setminus Z^{M}$ should be as useful as those in $Z^{M}$! We call such ratio $|Z^{\prime}|/|Z^{M}|$ the combination loss.

A Closer Look.

How large is the combination loss, $|Z^{\prime}|/|Z^{M}|$? In order to affect the bound on $\omega$, the loss needs to be exponentially large. Let us examine the number of ways to split $K$ according to (5), and compare it with that of (6). Recall that $S_{i,j,k}=\{t\mid i_{t}=i,j_{t}=j,k_{t}=k\}$ and $S_{k}=\cup_{i+j=4-k}\,S_{i,j,k}$. We use $h(p)$ to denote the binary entropy function $h(p)=-p\log p-(1-p)\log(1-p)$.

When $k_{t}\in\{0,4\}$, there is only one way to split it (i.e., $0=0+0,\;4=2+2$). So such $t$ has no contributionHere “contribution” means giving a multiplicative factor to $|Z^{\prime}|$ or $|Z^{M}|$. $|Z^{\prime}|$ equals the product of all contributions to it; so does $|Z^{M}|$. to either $|Z^{\prime}|$ or $|Z^{M}|$.

When $k_{t}\in\{1,3\}$, there are two symmetric ways to split it (i.e., $1=0+1=1+0$ and $3=1+2=2+1$). By this symmetry, we know $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(i,j,k)}$ is simply the uniform distribution, half and half. Fix $k=1$ or $3$, the contribution to $|Z^{M}|$ from all $t\in[n]$ such that $k_{t}=k$ is

which equals their contribution to $|Z^{\prime}|$. So in this case, their contributions to $|Z^{\prime}|$ and $|Z^{M}|$ are equal.

The only nontrivial case is when $k_{t}=2$. There are three ways to split it: $2=0+2=1+1=2+0$. Taking its symmetry into account, there is still one degree of freedom. Recall that $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(0,2,2)}(0)=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(0,2,2)}(2)=\lambda$ and $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(0,2,2)}(1)=1-2\lambda$, while $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}(0)=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}(2)=\mu,\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}(1)=1-2\mu$.

Each $t\in S_{0,2,2}\cup S_{2,0,2}$ is either $0+2$ or $2+0$ with probability $2\lambda$ and is $1+1$ with probability $1-2\lambda$. So the logarithm of their contribution to $|Z^{M}|$ approximately equals the entropy $h(2\lambda)\cdot|S_{0,2,2}\cup S_{2,0,2}|$. Similarly, the logarithm of the contribution of $t\in S_{1,1,2}$ to $|Z^{M}|$ is approximately $h(2\mu)\cdot|S_{1,1,2}|$. In total, the contribution of all $t\in S_{2}$ to $|Z^{M}|$ is approximately

On the other hand, let $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{p}=\frac{\lambda|S_{0,2,2}\cup S_{2,0,2}|+\mu|S_{1,1,2}|}{|S_{2}|}$ be the weighted average of $\lambda$ and $\mu$. (That is, $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}(0)=\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}(2)=\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{p}$ and $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}(1)=1-2\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{p}$.) The contribution of all $t\in S_{2}$ to $|Z^{\prime}|$ is approximately

This is larger than their contribution to $Z^{M}$ because the even distribution has the maximum entropy.

In the analysis of Coppersmith and Winograd, $\lambda=\frac{1}{2+q^{2}}$, $\mu=\frac{1}{2+q^{3\tau}}$ (where $\tau=\frac{\omega}{3}$). So there is a constant gap between $\lambda$ and $\mu$ when $\omega>2$. This implies an exponential gap between $|Z^{\prime}|$ and $|Z^{M}|$. The combination loss is indeed exponentially large. Hence, compensating for such loss might improve $\omega$.

3 Compensate for Combination Loss

As we discussed above, since a level-2 variable block $Z_{K}$ is in only one independent copy of $\mathcal{T}^{\alpha}$, some index $2$’s in it will split according to $\lambda$ while other $2$’s will split according to $\mu$. This causes the combination loss. The same holds for all X, Y and Z dimensions. One natural attempt to compensate for it is to match a level-2 variable block multiple times, i.e., to let it appear in multiple triples.

During the hashing step, we randomly match a level-2 Z-variable block $Z_{K}$. Any index 2 in $Z_{K}$ will be in the parts of $T_{0,2,2}$, $T_{2,0,2}$, or $T_{1,1,2}$ randomly. Those index 2 of $Z_{K}$ in $T_{0,2,2}$ and $T_{2,0,2}$ parts will split according to $\lambda$ while those in $T_{1,1,2}$ part will split according to $\mu$. Even if $Z_{K}$ is matched multiple times, since each time the positions of these three parts are different, we will be using different level-1 blocks in $Z_{K}$. This observation allows us to obtain a subtensor that is mostly disjoint from other subtensors from each matching.

Asymmetric Hashing.

In the original two-level analysis (Section 2.1), the marginal distributions ${\alpha}_{\scriptscriptstyle\textup{X}}={\alpha}_{\scriptscriptstyle\textup{Y}}={\alpha}_{\scriptscriptstyle\textup{Z}}$ are picked to balance the number of level-2 blocks and the number of variables in a block. So after zeroing-out, every remaining block can only be in one triple. We carefully pick ${\alpha}_{\scriptscriptstyle\textup{X}}={\alpha}_{\scriptscriptstyle\textup{Y}}$ and ${\alpha}_{\scriptscriptstyle\textup{Z}}$ so that there will be more level-2 X and Y-blocks than Z-blocks. (This asymmetric hashing method also appears in [CW90], but the base tensor is Strassen’s tensor [Str86, Pan78].) In return, in each level-2 Z-block, we can now have more variables. We will match each Z-variable block to multiple pairs of X and Y-blocks while keeping the matching for each X and Y-block unique, that is, every remaining X or Y-block is only in one triple but a remaining Z-block can be in multiple triples. Such uniqueness for X and Y-blocks is necessary for our method of removing the interfering terms.

Sanity Check.

As a sanity check, let us first try to match a level-2 variable block $Z_{K}$ twice. (Recall that we defined the notations for variable blocks in Section 2.1.) We say $Z_{K}$ can be matched to $X_{I}$ and $Y_{J}$ with respect to $\alpha$ if and only if (1) $i_{t}+j_{t}+k_{t}=4$ for all $t\in[n]$; and (2) the distribution $[(i_{t},j_{t},k_{t})]_{t\in[n]}$ equals $\alpha$.

Let $Z^{M}$ be the set of level-1 Z-variable blocks in $\mathcal{T}^{\widetilde{\alpha}}_{M}$, and let $Z^{M^{\prime}}$ be that of $\mathcal{T}^{\widetilde{\alpha}}_{M^{\prime}}$. Our key observation is that $Z^{M}$ and $Z^{M^{\prime}}$ are mostly disjoint. Recall that $S_{i,j,k}=\{t\in[n]\mid(i_{t},j_{t},k_{t})=(i,j,k)\}$ is the positions of the $T_{i,j,k}$ part in $M$. Similarly, let $S^{\prime}_{i,j,k}$ be that of $M^{\prime}$. (See Figure 1.) For any set $S\subseteq[n]$ and a level-1 Z-variable block $Z_{\widehat{K}}=Z_{(\widehat{k}_{1},\widehat{k}_{2},\dots,\widehat{k}_{2n})}$, we use $\textsf{split}(\widehat{K},S)$ to denote the split distribution for $Z_{(\widehat{k}_{1},\widehat{k}_{2},\dots,\widehat{k}_{2n})}$ restricted to set $S$. Recall that it is defined as

Fix any $Z_{\widehat{K}}\in Z^{M}$. We claim that, by the randomness of $S^{\prime}_{1,1,2}$, w.h.p. $\textsf{split}(\widehat{K},S^{\prime}_{1,1,2})=\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}$ which is the average split distribution. On the contrary, for any $Z_{\widehat{K}^{\prime}}\in Z^{M^{\prime}}$, we must have $\textsf{split}(\widehat{K}^{\prime},S^{\prime}_{1,1,2})=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}$. Since $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}\neq\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}$, this shows w.h.p. $Z_{\widehat{K}}\not\in Z^{M^{\prime}}$, which implies that $Z^{M}$ and $Z^{M^{\prime}}$ are mostly disjoint.

Now let us justify our claim. Since we uniformly sampled the pair $(X_{I^{\prime}},Y_{J^{\prime}})$, by symmetry, $S^{\prime}_{1,1,2}$ is uniform among all $\alpha(1,1,2)n$-sized subsets of $S_{2}=\{t\in[n]\mid k_{t}=2\}$. Regardless of whether a position $t\in S_{2}$ is in $S_{0,2,2},S_{2,0,2},$ or $S_{1,1,2}$, such position is in $S^{\prime}_{1,1,2}$ with equal probability. As we fixed $Z_{\widehat{K}}\in Z^{M}$, the corresponding split distribution $\textsf{split}(\widehat{K},S^{\prime}_{1,1,2})$ is mostly likely to be the weighted average of $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(0,2,2)}$, $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,0,2)}$, and $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(1,1,2)}$, i.e., the average distribution $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}$.

The idea above is generalized in our main algorithm so that each level-2 Z-block can be matched in $2^{\Theta(n)}$ triples. However, there are two remaining challenges:

In order to be independent, being mostly disjoint is not sufficient. $\mathcal{T}^{\widetilde{\alpha}}_{M}$ and $\mathcal{T}^{\widetilde{\alpha}}_{M^{\prime}}$ has to be completely disjoint. An easy fix would be zeroing out the intersecting variables. But this introduces missing Z-variables in the final matrix multiplication tensors we get. We use a random shuffling technique similar to that of [KK19] to fix these “holes” in Z-variables.

Moreover, even being perfectly disjoint does not guarantee independence. There is also a second condition in the definition of independence: no additional terms, i.e., we have to make sure that we get exactly $\mathcal{T}^{\widetilde{\alpha}}_{M}+\mathcal{T}^{\widetilde{\alpha}}_{M^{\prime}}$ without any extra terms. For example, let $X_{\widehat{I}^{\prime}},Y_{\widehat{J}^{\prime}},Z_{\widehat{K}}$ be level-1 blocks in $X_{I^{\prime}}$, $Y_{J^{\prime}}$, and $Z^{M}$, respectively, then the subtensor of $\mathcal{T}^{\widetilde{\alpha}}_{M\cup M^{\prime}}$ over these level-1 blocks should be zero. Vice versa for level-1 blocks in $X_{I},Y_{J}$, and $Z^{M^{\prime}}$. If these conditions are not satisfied, $T_{M}^{\widetilde{\alpha}}$ and $T_{M^{\prime}}^{\widetilde{\alpha}}$ are not independent.

Fixing Holes.

We now address the first challenge. Suppose we have a broken matrix multiplication tensor of size $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{N}\times\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{M}\times\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{P}$ (i.e., it corresponds to the matrix multiplication of an $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{N}\times\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{M}$ matrix and an $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{M}\times\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{P}$ matrix), in which half of the Z-variables are zeroed out. Let us denote the two multiplying matrices as $X$ and $Y$. The product is $(XY)_{i,j}:=\sum_{k=1}^{\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{M}}X_{i,k}Y_{k,j}$, but we can only get half of the entries in $XY$. If we randomly select three permutations $\pi_{1},\pi_{2},\pi_{3}$ of $[\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{N}],[\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{M}],[\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{P}]$, respectively, and fill in $X_{i,k}\leftarrow A_{\pi_{1}\!(i),\pi_{2}\!(k)},\;Y_{k,j}\leftarrow B_{\pi_{2}\!(k),\pi_{3}\!(j)}$ instead, we would get the correct answer to a random half of the entries in $AB$. Then we just repeat this multiple times using other broken matrix multiplication tensors. Combine the answers to the entries in $AB$ together, we would get the correct answer for $AB$ with high probability. In other words, we solve the first challenge by “gluing” many randomly permuted broken matrix multiplication tensors together.

Compatibility.

For the second challenge, we need the following key observation. Let $X_{\widehat{I}^{\prime}}\in X_{I^{\prime}},\;Y_{\widehat{J}^{\prime}}\in Y_{J^{\prime}},\;Z_{\widehat{K}}\in Z^{M}$ be three level-1 blocks. If there is an interfering term involving variables in $X_{\widehat{I}^{\prime}}$, $Y_{\widehat{J}^{\prime}}$ and $Z_{\widehat{K}}$, for those $t\in S^{\prime}_{2,0,2}$, we must have $(\widehat{i}^{\prime}_{2t-1},\widehat{i}^{\prime}_{2t})=(2-\widehat{k}_{2t-1},\,2-\widehat{k}_{2t})$, because $\widehat{j}^{\prime}_{2t-1}=\widehat{j}^{\prime}_{2t}=0$ and $(\widehat{i}^{\prime}_{2t-1},\widehat{i}^{\prime}_{2t})+(\widehat{j}^{\prime}_{2t-1},\widehat{j}^{\prime}_{2t})+(\widehat{k}_{2t-1},\widehat{k}_{2t})=(2,2)$. This implies

If this holds, we say $\textsf{split}(\widehat{I}^{\prime},S^{\prime}_{2,0,2})$ agrees with $\textsf{split}(\widehat{K},S^{\prime}_{2,0,2})$.

We claim that for any fixed $X_{\widehat{I}^{\prime}}\in X_{I^{\prime}}$, $Y_{\widehat{J}^{\prime}}\in Y_{J^{\prime}}$, and $Z_{\widehat{K}}\in Z^{M}$ that are retained in $\mathcal{T}^{\widetilde{\alpha}}_{M\cup M^{\prime}}$, the condition (2.3) is not satisfied with high probability:

$\textsf{split}(\widehat{I}^{\prime},S^{\prime}_{2,0,2})$ agrees with $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,0,2)}$, the split distribution of Z indices for $T_{2,0,2}$. This is a necessary condition for $X_{\widehat{I}^{\prime}}$ to form a triple with $Z_{\widehat{K}}\in Z^{M^{\prime}}$, because $\textsf{split}(\widehat{K},S^{\prime}_{2,0,2})=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,0,2)}$ holds for all $Z_{\widehat{K}}\in Z^{M^{\prime}}$. Otherwise, if this condition does not hold, $X_{\widehat{I}^{\prime}}$ cannot form any triple with Z-blocks $Z_{\widehat{K}}\in Z^{M^{\prime}}$, so it has been zeroed out before forming $\mathcal{T}^{\widetilde{\alpha}}_{M\cup M^{\prime}}$. (In this argument, it is crucial that $X_{I^{\prime}}$ is only matched in a unique triple $M^{\prime}$.)

$\textsf{split}(\widehat{K},S^{\prime}_{2,0,2})$ is equal to $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}$, the average split distribution of index 2, with high probability. This can be deduced from a similar argument as in the sanity check.

These two arguments, combined with the fact that $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}\neq\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,0,2)}$, concludes that (2.3) is unlikely to hold.

Similarly, one could also look at the positions $S^{\prime}_{0,2,2}$, which is symmetric to the case above.The same argument would not work with $t\in S^{\prime}_{1,1,2}$, because now $(\widehat{j}^{\prime}_{2t-1},\widehat{j}^{\prime}_{2t})$ could be either $(1,0)$ or $(0,1)$. This degree of freedom prevents us from getting a compatibility constraint between $\textsf{split}(\widehat{I}^{\prime},S^{\prime}_{1,1,2})$ and $\textsf{split}(\widehat{K},S^{\prime}_{1,1,2})$. For any level-2 blocks $X_{I}$, ${Y}_{J}$, and level-1 block $Z_{\widehat{K}}\in Z^{M}$ where $M=(X_{I},Y_{J},Z_{K})$, when $\textsf{split}(\widehat{K},S_{2,0,2})$ and $\textsf{split}(\widehat{K},S_{0,2,2})$ are both equal to $\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(2,0,2)}$ ($S_{2,0,2}$ and $S_{0,2,2}$ are defined w.r.t. $M$), we say $Z_{\widehat{K}}$ is compatible with $X_{I}$ and ${Y}_{J}$. Our argument above shows that w.h.p. a level-1 block will only be compatible with one pair of $X_{I}$ and ${Y}_{J}$, and there is no interfering term involving $Z_{\widehat{K}}$ and $X_{I}$, ${Y}_{J}$ if they are not compatible. If $Z_{\widehat{K}}$ happens to be compatible with two pairs, we will zero out $Z_{\widehat{K}}$ and leave it as a hole. Then it will be fixed by our hole-fixing technique. See Section 4 and Section 5 for more details.

4 Beyond the Second Power

In the analysis of higher and higher powers of the CW tensor, because we can perform merging for $T_{0,j,k}$ at each level, we get better and better upper bounds of $\omega$. Together with such gain, we also incur combination loss at each level. Our approach generalizes to high powers as well. For higher powers of the CW tensor, we apply this method to analyze both the global value (i.e., the value of the CW tensor) and the component values (e.g., the values of $T_{1,2,5},T_{1,3,4},T_{2,2,4},T_{2,3,3}$ and their permutations for the 4th power). Same as in previous works, we optimize all parameters by a computer program to obtain an upper bound of $\omega$.

Recall that in our two-level analysis, we obtained a subtensor $\mathcal{T}^{\widetilde{\alpha}}_{M}$ for each retained level-2 triple $M=(X_{I},Y_{J},Z_{K})$, in which some Z-blocks $Z_{\widehat{K}}\in Z^{M}$ are zeroed out and become holes. We first pretend there are no holes, zeroing out these tensors $\mathcal{T}^{\widetilde{\alpha}}_{M}$ to form matrix multiplication tensors, and then fix the holes in the matrix multiplication tensors. However, for higher powers, this approach meets a difficulty: The process of transforming $\mathcal{T}^{\widetilde{\alpha}}_{M}$ to matrix multiplication tensors is more involvedIt will be a more general degeneration instead of just zeroing out., so it is not clear how one can control the number of holes in the final matrix multiplication tensors.

To solve this difficulty, we will fix the holes in $\mathcal{T}^{\widetilde{\alpha}}_{M}$ before transforming them to matrix multiplication tensors. Suppose all $\mathcal{T}^{\widetilde{\alpha}}_{M}$ are isomorphic to some tensor $\mathcal{T}^{*}$ except for the holes in their Z-variables. As long as $\mathcal{T}^{*}$ has a desired symmetric structure, we can shift the holes in each copy $\mathcal{T}^{\widetilde{\alpha}}_{M}$ to random places, like we did in Section 2.3 to repair the holes in matrix multiplication tensors. Then, by gluing several copies together, we can fix all the holes, resulting in a copy of $\mathcal{T}^{*}$ without holes. In Section 5, we will show how to fix the holes: We will first define the desired tensor structure $\mathcal{T}^{*}$ which will naturally appear in Sections 6 and 7, then define a group of permutations used to move the holes, and finally fix the holes in $\mathcal{T}^{*}$ using the idea we discussed above.

Compatibility for higher powers.

Recall that in Section 2.3, we defined the compatibility for the second power. A level-1 Z-block $Z_{\widehat{K}}$ is compatible with $X_{I},Y_{J}$, if the following conditions hold:

$\textsf{split}(\widehat{K},S_{0,2,2})=\textsf{split}(\widehat{K},S_{2,0,2})=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(0,2,2)}$, where $S_{0,2,2}$ and $S_{2,0,2}$ are defined with respect to the triple $(X_{I},Y_{J},Z_{K})$;

$\textsf{split}(\widehat{K},S_{2})=\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(2)}$.

Here, we can make a constraint for the split distribution of $T_{0,2,2}$ because the index 0 ensures a one-to-one correspondence between the split distributions of Y and Z-indices. Similar for $T_{2,0,2}$. We generalize this definition to higher powers, creating a similar constraint for every component $T_{i,j,k}$ with $i=0$ or $j=0$:

For all components $T_{i,j,k}$ with $i=0$ or $j=0$, $\textsf{split}(\widehat{K},S_{i,j,k})=\widetilde{\alpha}_{\scriptscriptstyle\textup{Z}}^{(i,j,k)}$, where $S_{i,j,k}$ is defined with respect to the triple $(X_{I},Y_{J},Z_{K})$.

$\textsf{split}(\widehat{K},S_{k})=\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{\scriptscriptstyle\textup{Z}}^{(k)}$ for all $k$.

Based on this definition, we will show in Section 6 that there are no interfering terms between $Z_{\widehat{K}}$ and $X_{I},Y_{J}$ that are incompatible. Once some $Z_{\widehat{K}}$ is compatible with two remaining triples, we zero it out as we did in Section 2.3.

Analyzing component values.

like in previous works, we would have $N_{\textup{BX}}=N_{\textup{BY}}=N_{\textup{BZ}}$ since X, Y, Z variables are symmetric. Our solution is to pick three different numbers $A_{1},A_{2},A_{3}$ and apply hashing on

This makes Z-variables asymmetric from X and Y. Starting with this tensor $\mathcal{T}$ and performing similar analysis as in Section 6, we obtain desired lower bounds for the components.

Why did we break the 2.3725 lower bound?

By compensating for the combination loss at each level, we get the new upper bound of $\omega<2.37187$ from the eighth power of the CW tensor. In the paper by Ambainis, Filmus, and Le Gall [AFLG15], they proved that certain algorithms could not give a better upper bound than $\omega<2.3725$. These algorithms include previous improvements in analyzing higher powers and the refined laser method [AW21b]. Our algorithm is the first algorithm to break this lower bound.

In their lower bound, they start with an estimated partitioned tensor, which is a partitioned tensor with an estimated value for each subtensor. Then they defined the merging value of it, which, roughly speaking, is the maximum value one can get from (1) zeroing it out into independent subtensors; and (2) merging non-independent subtensors that are matrix multiplication tensors into larger matrix multiplications.

Preliminaries

In this paper, $\log x$ means $\log_{2}x$ by default, and $[n]=\{1,\ldots,n\}$. For a sequence $a_{1},\ldots,a_{k}$ which sums to 1, $\binom{n}{a_{1}n,\,\cdots,a_{k}n}$ can be written as $\binom{n}{[a_{i}n]_{i\in[k]}}$, or simply $\binom{n}{[a_{i}n]}$ if there is no ambiguity. The notation $A_{1}\sqcup A_{2}\sqcup\cdots\sqcup A_{k}$ means the disjoint union of sets $A_{1},\ldots,A_{k}$.

Most of our notations about tensors are similar to [AW21b].

The matrix multiplication tensor $\langle n,m,p\rangle$ is a tensor over sets $\{x_{i,j}\}_{i\in[n],j\in[m]}$, $\{y_{j,k}\}_{j\in[m],k\in[p]}$, and $\{z_{k,i}\}_{k\in[p],i\in[n]}$, defined as

Tensor isomorphisms.

If two tensors $T$ and $T^{\prime}$ are equal up to a renaming of their variables, we say they are isomorphic or equivalent, denoted as $T\cong T^{\prime}$. Formally, we have the following definition.

Let $T$ be a tensor over variables $X,Y,Z$, written as

and $T^{\prime}$ be a tensor over variables $X^{\prime},Y^{\prime},Z^{\prime}$. We say $T$ is isomorphic to $T^{\prime}$ if there are bijections

$\phi=(\phi_{1},\phi_{2},\phi_{3})$ is called an isomorphism from $T$ to $T^{\prime}$, denoted by \phi\big{(}T\big{)}=T^{\prime}.

Moreover, an isomorphism $\phi$ from $T$ to itself is called an automorphism of $T$. All automorphisms of $T$ form a group, called the group of automorphisms of $T$, written $\textup{Aut}(T)$.

Tensor operations.

Let $T$ and $T^{\prime}$ be two tensors over $X,Y,Z$ and $X^{\prime},Y^{\prime},Z^{\prime}$, respectively, written as

The direct sum $T\oplus T^{\prime}$ is a tensor over $(X\sqcup X^{\prime}),(Y\sqcup Y^{\prime})$, and $(Z\sqcup Z^{\prime})$, defined as

When performing the direct sum $T\oplus T^{\prime}$, we always regard the variables in $T$ and $T^{\prime}$ as distinct variables. Specifically, $T^{\oplus n}$ is defined as $T\oplus T\oplus\cdots\oplus T$, i.e., the direct sum of $n$ copies of $T$.

The tensor product $T\otimes T^{\prime}$ is a tensor over $(X\times X^{\prime}),~{}(Y\times Y^{\prime}),~{}(Z\times Z^{\prime})$ defined as

Specifically, the tensor power $T^{\otimes n}$ is defined as the tensor product $T\otimes T\otimes\cdots\otimes T$ of $n$ copies.

The summation $T+T^{\prime}$ is well-defined only when $(X,Y,Z)=(X^{\prime},Y^{\prime},Z^{\prime})$. We define $T+T^{\prime}$ to be a tensor over $X,Y,Z$:

Rotation, swapping, and symmetrization.

be a tensor over $X=\left\{x_{1},\ldots,x_{n}\right\}$, $Y=\left\{y_{1},\ldots,y_{m}\right\}$, and $Z=\left\{z_{1},\ldots,z_{p}\right\}$. We define the rotation of $T$, denoted by $T^{\textup{rot}}$, as

over $X^{\prime}=\left\{x_{1},\ldots,x_{m}\right\}$, $Y^{\prime}=\left\{y_{1},\ldots,y_{p}\right\}$, and $Z^{\prime}=\left\{z_{1},\ldots,z_{n}\right\}$. Intuitively, rotation is changing the order of dimensions from $(|X|,|Y|,|Z|)$ to $(|Y|,|Z|,|X|)$ while keeping the structure of the tensor unchanged.

Similarly, we define the swapping of $T$, denoted by $T^{\textup{swap}}$, as

over $X^{\prime}=\left\{x_{1},\ldots,x_{m}\right\}$, $Y^{\prime}=\left\{y_{1},\ldots,y_{n}\right\}$, and $Z^{\prime}=\left\{z_{1},\ldots,z_{p}\right\}$. Swapping is changing the order of dimensions from $(|X|,|Y|,|Z|)$ to $(|Y|,|X|,|Z|)$, i.e., swapping X and Y dimensions.