Barriers for fast matrix multiplication from irreversibility

Introduction

Determining the asymptotic algebraic complexity of matrix multiplication is a central open problem in algebraic complexity theory. Several methods for constructing fast matrix multiplication algorithms have been developed, but at a high level they typically consist of two parts: an efficient reduction of matrix multiplication to an intermediate problem (some bilinear map, i.e. some 3-tensor) and an efficient algorithm for the intermediate problem. Recent results have shown barriers for such constructions to yield fast matrix multiplication algorithms [AFLG15, BCC+17a, BCC+17b, AW18a, AW18b]. We give a barrier, based on a new notion called irreversibility, that is more general and in some cases stronger than the barriers from previous work.

2. Matrix multiplication barriers

The matrix multiplication exponent $\omega$ is defined as the infimum over all real numbers $\beta$ such that any two $n\times n$ matrices can be multiplied with $\mathcal{O}(n^{\beta})$ algebraic operations, and thus $\omega$ represents the asymptotic algebraic complexity of matrix multiplication. The bounds $2\leq\omega\leq 3$ hold trivially. Strassen published the first non-trivial upper bound $\omega\leq\log_{2}7$ in 1969 [Str69]. In the decades that followed, through the development of several ingenious methods by various people, the upper bound was improved to the state-of-the-art bound $\omega\leq 2.37..$, and the pursuit to prove whether $\omega=2$ or $\omega>2$ has been ongoing [CW90, Sto10, Wil12, LG14, CU03, CU13]. As mentioned before, these upper bound methods typically consist of a reduction of matrix multiplication to an intermediate problem and an efficient algorithm for the intermediate problem.

Ambainis, Filmus and Le Gall [AFLG15], for the first time, proved a barrier result for some collection of such methods. Namely, they showed that a variety of methods that go via the big Coppersmith–Winograd tensor as an intermediate problem cannot give $\omega=2$, and in fact not even $\omega\leq 2.30..$. We call any lower bound for all upper bounds on $\omega$ that can be obtained by some method, a barrier for that method. In general, barriers in the sense of limitations to proof methods have a long history in computational complexity theory and recognizing barriers is a natural step towards finding proof methods that do solve the problem at hand.

Next, Alman and Williams [AW18a, AW18b] extended the realm of barriers beyond the scope of the Ambainis et al. barrier, to a larger collection of methods. Also Blasiak, Church, Cohn, Grochow, Naslund, Sawin, and Umans [BCC+17a] and Blasiak, Church, Cohn, Grochow, and Umans [BCC+17b] studied barriers, namely barriers for a subset of the group-theoretic method. Both the Blasiak et al. and the Alman and Williams barriers rely on studying versions of asymptotic subrank of an intermediate problem.

We give a barrier that applies more generally than all previous barriers and that is in some cases stronger. Our barrier also relies on studying versions of asymptotic subrank, which together with the notion of asymptotic rank we combine into a single parameter called irreversibility. Our barrier simplifies and generalizes previous barriers and tightly connects the barrier literature to central notions from the framework of Strassen [Str87, Str88, Str91, CVZ18]. Alman [Alm19] reported very similar independent results shortly after our manuscript appeared on the arXiv, which we jointly presented at the Computational Complexity Conference 2019 in New Brunswick. For all the tensors mentioned, the barriers of Alman are identical to ours. A subtle difference between the works is that Alman considers asymptotic slice rank instead of asymptotic subrank.

3. Our barrier: informal explanation

Our barrier relies on two ideas: (i) we think of computational problems as resources that can be reduced to one another and (ii) such reductions satisfy a triangle inequality which limits the possible chains of reductions. An informal explanation of our barrier is as follows. The matrix multiplication exponent $\omega$ is the optimal rate at which the problem of multiplying matrices can be reduced to the problem of multiplying numbers, or in other words, the optimal rate at which the problem of multiplying numbers can be transformed into the problem of multiplying matrices,

By this we mean that for any $n$ the problem of multiplying $n\times n$ matrices can be reduced to the problem of multiplying $n^{\omega+o(1)}$ pairs of numbers (and some additions, but they do not have an influence on the complexity). We will make these notions precise later. For now, we stick to the high-level picture. Rates of transformation naturally satisfy a triangle inequality. Therefore, upper bounds on $\omega$ can be obtained by combining the rate of transformation $\alpha_{1}$ from the problem of multiplying numbers to some intermediate problem and the rate of transformation $\alpha_{2}$ from the intermediate problem to the problem of multiplying matrices; this is the two-component approach alluded to earlier,

That is, $\alpha_{1}\alpha_{2}\geq\omega$. We define the irreversibility of the intermediate tensor, roughly speaking, as the optimal rate of transformation from the problem of multiplying numbers to the intermediate problem and back to the problem of multiplying numbers. Strassen [Str88] (see Section 2.1) showed that the transformation rate from the matrix multiplication problem to the problem of multiplying numbers is $\tfrac{1}{2}$, so we can extend the chain in (2) to

Using the triangle inequality again we see that $\alpha_{1}\alpha_{2}/2$ is at least the irreversibility of the intermediate problem, and hence the irreversibility of the intermediate problem provides limitations on the upper bounds $\alpha_{1}\alpha_{2}\geq\omega$ that can be obtained from (2). This is formalized in Theorem 17.

4. Explicit numerical barriers

To exemplify our barrier we show that the support functionals [Str91] and quantum functionals [CVZ18] give (so far, the best) lower bounds on the irreversibility of the following families of intermediate problems. These intermediate problems are encoded as tensors. A tensor is a 3-dimensional array of numbers. We use $e_{i,j,k}$ to denote the tensor that is zero everywhere except for a one in coordinate $(i,j,k)$. We will discuss tensors in more details later. The families of intermediate tensors we consider are:

the reduced polynomial multiplication tensors

Our irreversibility lower bounds lead to the following explicit barriers (Section 5.1 and Section 5.2), rounded to five decimal places.

5. Comparison and other applications

Compared to [AFLG15], whose barriers apply to the laser method, our barriers are valid for a larger class of approaches (and naturally we obtain lower barriers). Compared to [AW18b], whose barriers apply to what we call monomial degeneration, our barriers are valid for a larger class of approaches but our barriers are also higher. As a variation on our barrier we introduce a monomial version. Compared to [BCC+17a] and [BCC+17b] our monomial barriers are valid for a class of approaches that includes their simultaneous triple product property (STPP) approach, and thus we provide a uniform view on the barriers that have appeared in the literature. We have not tried to optimize the barriers that we obtain, but focus instead on introducing the barrier itself. The barrier in [Alm19] is very similar to ours, except for using asymptotic slice rank instead of asymptotic subrank.

It will become clear to the reader during the development of our ideas that they not only apply to the problem of fast matrix multiplication, but extend to give barriers for the more general problem of constructing fast rectangular matrix multiplication algorithms (see the follow-up results on barriers for rectangular matrix multiplication in [CGLZ20]) or even transformations between arbitrary powers of tensors. Such transformations may represent, for example, asymptotic SLOCC (stochastic local operations and classical communication) reductions among multipartite quantum states [BPR+00, DVC00, VDDMV02, HHHH09].

We define irreversibility in Section 2. In Section 3 we discuss how irreversibility implies a barrier. In Section 4 we discuss methods to analyze irreversibility. Finally, in Section 5 we exhibit explicit irreversibility barriers.

Irreversibility of tensors

We begin by introducing some standard terminology and results regarding tensors and matrix multiplication. Then we discuss a useful notion called the relative exponent of two tensors and we define the irreversibility of a tensor. After that we introduce the monomial versions of these ideas. Finally, we discuss what values the irreducibility can take.

and the asymptotic subrank of $t$ is defined as

To see how $\langle n,n,n\rangle$ encodes multiplication of $n\times n$ matrices, let $E_{i,j}$ be the $n\times n$ matrix that is all-zero except for a 1 at coordinate $(i,j)$, so that the $E_{i,j}$ form the standard basis of the vector space of $n\times n$ matrices. Note that $E_{i,j}E_{j,k}=E_{i,k}$ and that $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}A_{(i,j)}B_{(j,k)}E_{i,k}=AB$. Thus suitable contractions of $\langle n,n,n\rangle$ with the matrices $A$ and $B$ produces the product $AB$. It is a standard result ([Blä13, Section 4]) that the tensor rank of $\langle n,n,n\rangle$ equals, up to a constant factor, the arithmetic complexity of multiplying two $n\times n$ matrices. The argument is roughly as follows. Tensor rank upper bounds lead directly to matrix multiplication algorithms by the aforementioned contractions. On the other hand, any arithmetic matrix multiplication algorithm can be made into an arithmetic circuit with an addition layer followed by a bilinear multiplication layer followed by an addition layer, in such a way that the number of bilinear multiplication nodes is at most twice the number of multiplications in the arithmetic algorithm. The blow-up by a factor of two is because we only allow bilinear multiplications in our arithmetic circuit. This representation leads directly to a tensor rank upper bound. As we said before, the matrix multiplication exponent $\omega$ is defined as the infimum over all $\beta$ for which the arithmetic complexity of multiplying two $n\times n$ matrices is at most $\mathcal{O}(n^{\beta})$. Matrix multiplication tensors are multiplicative in the sense that $\langle a,b,c\rangle\otimes\langle d,e,f\rangle$ is isomorphic to $\langle ad,be,cf\rangle$. From the multiplicativity of the matrix multiplication tensors it is easy to derive that $\omega$ is characterized by the asymptotic rank of $\langle 2,2,2\rangle$ as follows.

$\omega=\log_{2}\operatorname{\underaccent{\wtilde}{R}}(\langle 2,2,2\rangle)$.

The difficulty of determining the asymptotic rank of $\langle 2,2,2\rangle$ is to be contrasted with the situation for the asymptotic subrank; to put it in Strassen’s words: Unlike the cynic, who according to Oscar Wilde knows the price of everything and the value of nothing, we can determine the asymptotic value of $\langle h,h,h\rangle$ precisely.

For completeness of the paper we give a proof of Proposition 2. The proof we provide here is based on Salem–Spencer sets and is slightly different from the proof in [Str88]. However, the two proofs become very similar when the construction of Salem–Spencer sets is unrolled.

That is, $F=E\cap(W_{1}\times W_{2}\times W_{3})$. Then

Indeed, a priori, $((i,j),(j,k),(k,i))\in F$ if and only if

We remarked before that Strassen’s proof of Proposition 2 in [Str88] takes a slightly different route. Namely, it makes use of an approximative relaxation of subrank called border subrank, which is denoted by $\operatorname{\underline{Q}}$. He shows that $\operatorname{\underline{Q}}(\langle m,m,m\rangle)\geq\lceil\tfrac{3}{4}m^{2}\rceil$. (This lower bound, and all Strassen’s lower bounds for $\operatorname{\underline{Q}}(\langle a,b,c\rangle)$, are in fact tight [KMZ20].) Strassen then relates the border subrank to the asymptotic subrank via a simple polynomial interpolation argument to get that $\operatorname{\underaccent{\wtilde}{Q}}(\langle m,m,m\rangle)=m^{2}$.

2. Relative exponent

For a clean exposition of our barrier we will use the notion of relative exponent, which we will define in this section. This notion is inspired by the notion of rate from information theory and alternatively can be seen as a versatile version of the notion of the asymptotic preorder for tensors of StrassenThe asymptotic preorder $\gtrsim$ is defined as follows: $s\gtrsim t$ if $s^{\otimes n+o(n)}\geq t^{\otimes n}$ when $n\to\infty$.. In the context of tensors, the relative exponent previously appeared in [YGD14],[VC15] and [CVZ19].

To avoid technicalities, we will from now on, without further mentioning, only consider tensors that are not of tensor rank one or zero. This assumption is explicitly used in the proof of Proposition 5(i) and its applications.

The limit is a supremum by Fekete’s lemma. Let us briefly relate the relative exponent to the basic notions and results stated earlier. The reader verifies directly that the identities

hold by approximating integers by powers of 2, or see [CVZ19, Proposition 1.1.16] for a proof. From the fact that $\omega\coloneqq\log_{2}\operatorname{\underaccent{\wtilde}{R}}(\langle 2,2,2\rangle)$ (Proposition 1) it follows that

We know from (7) that $\operatorname{\underaccent{\wtilde}{Q}}(\langle 2,2,2\rangle)=4$ and so

The relative exponent has the following two basic properties.

$\operatorname{\omega}(s,t)\operatorname{\omega}(t,u)\geq\operatorname{\omega}(s,u)$ (triangle inequality).

(i) Clearly $\omega(t,t)\leq 1$ by reflexivity of the restriction preorder $\geq$. Since $t$ is not of rank 1, we can flatten $t$ into a matrix in one of the three directions, so that the matrix rank is some number $r>1$. It follows from multiplicativity of matrix rank, that if $t^{\otimes m}\geq t^{\otimes n}$, then $r^{m}\geq r^{n}$ and so $m\geq n$. This implies the claim. (ii) follows from the transitivity of the restriction preorder $\geq$. ∎

3. Irreversibility.

Our barrier framework relies crucially on the irreversibility of a tensor, a new notion that we define now.

We define the irreversibility of a tensor $t$ as the product of the relative exponent from $\langle 2\rangle$ to $t$ and the relative exponent from $t$ to $\langle 2\rangle$, i.e.

Thus $\operatorname{\mathbf{i}}(t)$ measures the extent to which the asymptotic conversion from $\langle 2\rangle$ to $t$ is irreversible, explaining the name. Equivalently, the irreversibility is the ratio of the logarithms of the asymptotic rank and the asymptotic subrank, i.e.

From the basic properties of the relative exponent (Proposition 5) it follows directly that the inequality $\operatorname{\mathbf{i}}(t)=\operatorname{\omega}(\langle 2\rangle,t)\operatorname{\omega}(t,\langle 2\rangle)\geq\operatorname{\omega}(\langle 2\rangle,\langle 2\rangle)=1$ holds. ∎

We call a tensor $t$ reversible if $\operatorname{\mathbf{i}}(t)=1$ and irreversible otherwise (in which case it holds that $\operatorname{\mathbf{i}}(t)>1$ by Proposition 7).

Irreversible tensors do in fact exist. For example, the tensor $W=e_{0,0,1}+e_{0,1,0}+e_{1,0,0}$ is irreversible. Namely, it is known that $\log_{2}\operatorname{\underaccent{\wtilde}{R}}(W)=1$ and that $\log_{2}\operatorname{\underaccent{\wtilde}{Q}}(W)=h(1/3)=0.918..$ [Str91, Theorem 6.7], so $\operatorname{\mathbf{i}}(W)=1.088..>1$. In Section 5 we will compute lower bounds on the irreversibility of the small and big Coppersmith–Winograd tensors (which play a crucial role in the best upper bounds on $\omega$).

4. Monomial relative exponent and monomial irreversibility

We stress that the monomial irreversibility uses the monomial asymptotic subrank, but the regular asymptotic rank. This is in fact what is used in practice. We note that monomial (asymptotic) rank is a useless concept, since any monomial restriction of a unit tensor is again a unit tensor. In other words, using the monomial asymptotic rank is too restrictive and gives bad algorithms from the start. In particular, monomial irreversibility depends on the tensor and not only on its support.

There exist tensors that are reversible and monomially irreversible. We give an example.

Regarding matrix multiplication, Strassen’s construction for (13) (see also our proof of Proposition 2) in fact shows that

5. Upper bounds on irreversibility

We finish this section by discussing the possible values that the irreversibility can take, as a first step towards a systematic understanding of where we may find reversible tensors or almost reversible tensors. We will see that, surprisingly at first sight, the matrix multiplication exponent $\omega$ provides bounds on the irreversibility of arbitrary tensors.

for some absolute constant $d$. This gives us an idea of the order of magnitude of the irreversibility. We will refine this upper bound in the rest of this discussion.

As the first step towards gaining more control on the possible values of the irreversibility, we note that for asymptotic rank we have the following general upper bound.

Proposition 12 gives us some control over the possible values of the irreversibility. As the next step in that direction we must understand how small the asymptotic subrank can be. First, we give an example of a tensor for which the asymptotic subrank and the asymptotic rank are relatively far apart.

The claim follows from the following two ingredients. The first ingredient is the general upper bound $\operatorname{\underaccent{\wtilde}{R}}(t)\leq n^{2\omega/3}$ from Proposition 12. The second ingredient is the lower bound $\operatorname{\underaccent{\wtilde}{Q}}(t)\geq n^{2/3}$ [Str88, Proposition 3.6] for balanced tensors. We give a sketch of the argument. From the balancedness assumption it follows that $\langle n,1,1\rangle\leq t$ and $\langle 1,n,1\rangle\leq n$ and $\langle 1,1,n\rangle\leq t$. By multiplying these inequalities we get $\langle n,n,n\rangle\leq t^{\otimes 3}$. Therefore, using Proposition 2, we have $n^{2}\leq\operatorname{\underaccent{\wtilde}{Q}}(\langle n,n,n\rangle)\leq\operatorname{\underaccent{\wtilde}{Q}}(t)^{3}$. ∎

The claim follows directly from combining $\operatorname{\underaccent{\wtilde}{Q}}(t)\geq n^{2/3}$, which follows from balancedness as we saw in the proof of Proposition 14, and the assumption $\operatorname{\underaccent{\wtilde}{R}}(t)\leq n$. ∎

Irreversibility implies barriers

With the new notion of irreversibility available, we present a barrier for approaches to upper bound $\omega$ via an intermediate tensor $t$. As we have discussed before, all recent successful upper bounds on $\omega$ have been obtained with constructions via an intermediate tensor. The results in this section tell us which tensors not to use as intermediate tensors and what necessary quality a good intermediate tensor has.

holds by the triangle inequality. Any such approach to upper bound $\omega$ respects the following barrier in terms of the irreversibility $\operatorname{\mathbf{i}}(t)$ of $t$.

By the triangle inequality (Proposition 5),

Therefore, using the fact $\omega(\langle 2,2,2\rangle,\langle 2\rangle)=\tfrac{1}{2}$ from (13), we have

Theorem 17, in particular, implies that if $\operatorname{\mathbf{i}}(t)>1$, then $\operatorname{\omega}(\langle 2\rangle,t)\operatorname{\omega}(t,\langle 2,2,2\rangle)>2$. In other words, we cannot prove $\omega=2$ via an irreversible intermediate tensor. However, it is possible that there exists a sequence of irreversible intermediate tensors with irreversibility converging to 1 that can be used to prove $\omega=2$.

To conclude, the barrier just introduced describes what quality makes a tensor a good intermediate tensor, or put differently what intermediate tensors definitely not to use when we want to prove good upper bounds on $\omega$. Of course the barrier does not tell us explicitly which intermediate tensor to pick, but it provides a strong heuristic of what to look for, namely low asymptotic rank and high asymptotic subrank.

2. Better barriers when the method has more structure

The barrier discussed in Section 3.1 does not tell the full story, and we will now discuss the natural and more subtle continuation. Namely, not only will we lose the game when the intermediate tensor is irreversible, we lose even more when we use this intermediate tensor in a catalytic fashion, meaning that our algorithm is obtained from transforming a diagonal tensor to the tensor product of a diagonal tensor and a matrix multiplication tensor (via the intermediate tensor). We will explain this more, but for now it is important to know that this strategy is commonly used in the literature (with great success). However, as we will see in this section, such a catalytic approach boosts the previous barrier even more. Thus this section gives rise to a more precise heuristic which says that, while looking for intermediate tensors with small irreversibility, we may at the same time want to think about intermediate tensors that require less use of catalysis.

Catalysis in the general context of tensors is the phenomenon that for tensors $s$, $t$ and $u$, the inequality $s\geq t$ may be false, while the inequality $s\otimes u\geq t\otimes u$ may be true. The latter inequality is called catalytic with the tensor $u$ acting as a catalyst.

Catalysis is widely used in matrix multiplication algorithms albeit not under this explicit terminology. We will now discuss more quantitatively what we mean when we say that an approach to upper bound $\omega$ uses catalysis. Without loss of generality we may impose that the final step of any construction of a matrix multiplication algorithm is an application of the Schönhage $\tau$-theorem. The Schönhage $\tau$-theorem (Strassen’s general version [Str88]) says that

In particular, for $a_{i}=b_{i}=c_{i}=a$, it holds that

This inequality (29) is a method for upper bounding $\omega$ and we say that it is catalytic when $\alpha>0$, the catalyst being the tensor $\langle 2\rangle^{\alpha}$. In fact, upper bounds coming from the approach in the Coppersmith–Winograd paper and its follow-ups take the form of this inequality for specific $t$, $\alpha$ and $\beta$. The following barrier in terms of $\alpha,\beta$ and the irreversibility $\operatorname{\mathbf{i}}(t)$ of $t$ for any method of the form (29) says that catalysis boosts the irreversibility barrier.

One verifies that $\operatorname{\mathbf{i}}(t)\geq\operatorname{\mathbf{i}}(\operatorname{cyc}(t))$. If $t$ is cyclically symmetric, then $\operatorname{cyc}(t)=t^{\otimes 3}$ and we have the equality $\operatorname{\mathbf{i}}(t)=\operatorname{\mathbf{i}}(\operatorname{cyc}(t))$.

Suppose that $\langle 2\rangle^{m}\geq t^{n}$. Then also $\langle 2\rangle^{m}\geq((1,2,3)\cdot t)^{n}$ and $\langle 2\rangle^{m}\geq((1,2,3)^{2}\cdot t)^{n}$. Multiplying these inequalities gives $\langle 2\rangle^{3m}\geq\operatorname{cyc}(t)^{n}$. We conclude that $m/n\geq\omega(\langle 2\rangle,\operatorname{cyc}(t)^{1/3})$. By a similar argument we find that

Note that we are using real powers of tensors here inside the relative exponent $\omega(\cdot,\cdot)$. This is justified by taking powers of the relevant tensors and taking a limit. Using both inequalities and then applying Theorem 18 gives

This proves the statement of the theorem. ∎

3. Better barriers through monomial irreversibility

Finally, we impose as an extra constraint that the transformation from the intermediate tensor $t$ to the matrix multiplication tensor happens via monomial restriction (Section 2.4), that is, we consider the approach

The proofs in the previous sections can be directly adapted to prove:

Methods for lower bounding irreversibility

We have seen how lower bounds on irreversibility imply barriers. By definition of irreversibility, such lower bounds come from lower bounds on asymptotic rank and upper bounds on asymptotic subrank. In this section we discuss lower bounding irreversibility from four points of view: the asymptotic spectrum of tensors, the support functionals, the quantum functionals and the asymptotic slice rank. We will use the support functionals to compute explicit barriers in Section 5; the rest of this section serves as a survey and to provide comparison.

Strassen proved in [Str88] that for any tensor $t\in S$ it holds that $\operatorname{\underaccent{\wtilde}{Q}}(t)=\min_{F\in\Delta(S)}F(t)$ and $\operatorname{\underaccent{\wtilde}{R}}(t)=\max_{F\in\Delta(S)}F(t)$. From this we directly obtain the following concise characterization of irreversibility in terms of the asymptotic spectrum of tensors $\Delta(S)$.

This characterization is clean but does not lead to a practical way of computing, or even lower bounding, the irreversibility $\operatorname{\mathbf{i}}(t)$ for a general tensor $t$. This is because our knowledge of $\Delta(S)$ is very limited for any general family of tensors $S$. Namely, a priori we only know that for every $i\in$ the function $t\mapsto\operatorname{R}(t_{i})$ is in $\Delta(S)$, where $t_{i}$ is the flattening as described in Section 2.5. Thus we have the inequalities $\operatorname{\underaccent{\wtilde}{Q}}(t)\leq\min_{i}\operatorname{R}(t_{i})$ and $\operatorname{\underaccent{\wtilde}{R}}(t)\geq\max_{i}\operatorname{R}(t_{i})$. In fact, $\max_{i}\operatorname{R}(t_{i})$ is the best lower bound on $\operatorname{\underaccent{\wtilde}{R}}(t)$ that we know of. We will keep using this lower bound on the asymptotic rank in the coming, more practical, sections. There are, however, more powerful tools than the flattening ranks $\operatorname{R}(t_{i})$ to upper bound $\operatorname{\underaccent{\wtilde}{Q}}(t)$, which we will discuss now.

2. The support functionals

(We note that we believe that the name support functional derives from the general concept of support functions in convex analysis, rather than the support of tensors.) The minimization over all $s$ isomorphic to $t$ appearing in the definition of $\rho^{\theta}(t)$ is generally not well understood, but, fortunately, for the sake of upper bounding $\zeta^{\theta}(t)$ it suffices to find one good $s$ isomorphic to $t$. Note that the Shannon entropy $H$ is a concave function and thus the weighted marginal entropy $\sum_{i=1}^{3}\theta_{i}H(P_{i})$ is a concave function of $P$. Therefore, the analysis of the maximization over $P$, being a convex program over an explicitly given domain, is usually straightforward.

It is not hard to see that the three flattening ranks $\operatorname{R}(t_{i})$ are among the support functionals, namely when we set $\theta$ to $(1,0,0)$, $(0,1,0)$ or $(0,0,1)$. Thus the support functionals can be thought of as interpolations between the three flattening ranks. Strassen proves in [Str91] the fundamental property that

There are numerous examples where $\min_{\theta}\zeta^{\theta}(t)<\min_{i}\operatorname{R}(t_{i})$, of which we will see some later. It is not known whether the equality $\operatorname{\underaccent{\wtilde}{Q}}(t)=\min_{\theta}\zeta^{\theta}(t)$ holds in general. Strassen proved that equality holds for the family of tight tensors [Str91].A tensor $t$ is called tight if for some choice of basis there are injective maps $\alpha_{1},\alpha_{2},\alpha_{3}$ such that for every $a\in\operatorname{supp}(t)$ it holds that $\alpha_{1}(a_{1})+\alpha_{2}(a_{2})+\alpha_{3}(a_{3})=0$. Tight tensors play an important role in the laser method for constructing matrix multiplication algorithms, as the laser method requires the outer structure of the intermediate tensor to be tight. We conclude that we have the following lower bound on the irreducibility in terms of the flattening ranks and the support functionals:

We will use the method of the support functionals to lower bound the irreversibility of some explicit tensors in Section 5.

Since we are primarily interested in using the support functionals to upper bound the asymptotic subrank, it is worth to observe that by the von Neumann minimax theorem we may for any fixed tensor $t$ express $\min_{\theta}\rho^{\theta}(t)$ in the concise form

Indeed, the function $(\theta,P)\mapsto\sum_{i}\theta_{i}H(P_{i})$ is convex in $\theta$ and concave in $P$ so the minimax theorem allows us to swap the maximization over $P$ and the minimization over $\theta$. Moreover, $\min_{\theta}\sum_{i}\theta_{i}H(P_{i})$ is clearly attained when $\theta$ is one of the vertices $(1,0,0)$, $(0,1,0)$, $(0,0,1)$.

To further familiarize ourselves with the definition of $\zeta^{\theta}$, we discuss a simple example. For this example let $t$ be the so-called W-tensor $t=e_{1,2,2}+e_{2,1,2}+e_{2,2,1}$. We will upper bound $\zeta^{\theta}(t)$ for $\theta=(1/3,1/3,1/3)$. In the evaluation of $\rho^{\theta}(t)$ we take $s$ to be equal to $t$. (This turns out to be optimal in this case, since $t$ is tight [Str91].) Then the support of $s$ is the set

Explicit barriers

We exhibit explicit barriers by computing lower bounds on the irreversibility of well-known intermediate tensors that play a crucial role in the best upper bounds on the matrix multiplication exponent $\omega$. These tensors are the small and big Coppersmith–Winograd tensors. Then we discuss the reduced polynomial multiplication tensors. Finally we discuss monomial irreversibility of structure tensors of finite group algebras and relations to the group-theoretic approach.

We now compute lower bounds for the irreversibility of the Coppersmith–Winograd tensors. As mentioned, we will use the support functionals of Strassen [Str91] in our computation to upper bound the asymptotic subrank.

(Upper bounds on the asymptotic subrank of complex tensors may be obtained, not only from the Strassen support functionals, but also from the quantum functionals. For the tensors in Theorem 25 and Theorem 28, however, it is known that the quantum functionals will give the same bound as the support functionals, since these tensors are free tensors [CVZ18, Section 4.3].)

For any integer $q\geq 2$, the irreversibility of the small Coppersmith–Winograd tensor

The right-hand side of (54) has a minimum value of

with minimum value of 2.40… These barriers in fact match the upper bound

that was obtained by Coppersmith and Winograd by applying the laser method in the way described above. Thus our sanity check succeeds. Other intermediate tensors with a given outer structure may be analyzed similarly.

For any integer $q\geq 1$ the irreversibility of the big Coppersmith–Winograd tensor

which evaluates to the bound in the claim. ∎

The lowest value of the right-hand side of (60) is $2.16..$ attained at $q=1$. See the table in Section 1 for more values and see Appendix A for code to compute any values.

2. Irreversibility of reduced polynomial multiplication tensors

The reduced polynomial multiplication tensors $t_{n}$ are an example of a natural family of tensors in which each tensor is irreversible, but where the irreversibility converges to 1 when $n$ goes to infinity. The irreversibility of the tensors $t_{n}$ can be computed directly from the computation of the asymptotic rank and asymptotic subrank of $t_{n}$ in [Str91, Theorem 6.7], which uses the support functionals. Namely, Strassen shows that

and $g>1$ is the unique positive real solution to the equation

The limit $\lim_{n\to\infty}z(n)/n$ equals a constant, namely $0.84143...$ (see, e.g., [BCC+17a, Equation 4.11]). It follows that

Thus $t_{n}$ is “reversible in the limit”. In Appendix A we provide code to compute the values of $\operatorname{\mathbf{i}}(t_{n})$ for any $n$.

3. Monomial irreversibility of structure tensors of finite group algebras

The group-theoretic approach (in particular [CU03, Theorem 4.1]) produces an inequality of the form

It should be stressed again that although these results rule out using monomial restrictions from powers of any one single group, part of the hope of the group-theoretic approach is to use a family of groups (such as the symmetric group $S_{n}$ for increasing $n$) which is not just powers of a single starting group. For families of abelian groups of bounded exponent (even if they are not powers of a single group), [BCC+17a] rules out STPP constructions reaching $\omega=2$, and for certain families of nilpotent groups (again, even if they are not just powers of a single group) [BCC+17b] does similarly.

The results of [BCC+17a], [BCC+17b] and [Saw18], in fact, show slightly more than the aforementioned barriers for monomial restriction. While, over arbitrary fields, they only rule out monomial restrictions, over fields of bad characteristic (e.g., characteristic $p$ when $G$ is a $p$-group satisfying the relevant conditions of their theorems) they also rule out arbitrary degenerations. This is because they show slice rank upper bounds, the slice rank of a diagonal tensor equals its rank, and having slice rank at most $r$ is a Zariski-closed condition (proved in [TS16]).

Outlook for further barriers

In Section 5 we used the support functionals of Section 4 to upper bound the asymptotic subrank and thus lower bound the irreversibility of intermediate tensors. There are two other approaches to do this that we will discuss now. These approaches are at least as powerful as the support functionals for upper bounding asymptotic subrank, and we expect that there are examples where they perform better.

Let $t$ be a tensor over the complex numbers. Then

Comparing to Section 4.2, it is proved in [CVZ18] that the quantum functionals are at least as powerful as the support functionals when it comes to upper bounding the asymptotic subrank. Namely, for any tensor $t$ over the complex numbers holds that $F^{\theta}(t)\leq\zeta^{\theta}(t)$. It is an open problem whether this inequality can be strict. We note that, as opposed to the support functionals, the quantum functionals are defined as convex programs. It is an open problem whether the quantum functionals are efficiently computable.

2. Asymptotic slice rank

We finish Section 5 by discussing the asymptotic slice rank as a method to upper bound asymptotic subrank, and the relations to the support functionals and the quantum functionals. The slice rank (introduced by Tao [Tao16] in the context of the cap set problem) of a tensor $t$ is the smallest number $r$ such that $t$ can be written as a sum of $r$ slice rank one tensors. A slice rank one tensor is a tensor for which there is an $i\in$ such that the flattening $t_{i}$ has matrix rank one. The asymptotic subrank, the slice rank and the support functionals are related in the following way:

(See [CVZ18].) Thus, in an asymptotic fashion, the slice rank upper bounds the asymptotic subrank and hence lower bounds irreducibility. Any analysis of $\limsup_{n}\operatorname{slicerank}(t^{\otimes n})^{1/n}$ that we are aware of in the literature boils down to evaluating $\min_{\theta}\zeta^{\theta}(t)$. In particular, we are not aware of any example for which the right-most inequality in (68) is strict.

For freeA tensor $t$ is called free if in some basis any two different $a,b\in\operatorname{supp}(t)$ differ in at least two entries. Every tight tensor is oblique and every oblique tensor is free. tensors the right-most inequality in (69) is an equality [CVZ18].

Appendix A Code to verify the numerical examples

The following Mathematica code generates the barrier values in the tables in Section 1 to arbitrary precision and for arbitrary parameters $q$ and $n$.

Acknowledgements

MC acknowledges financial support from the European Research Council (ERC Grant Agreement No. 337603 and 81876) and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059). This research was supported by the National Research, Development and Innovation Fund of Hungary within the Quantum Technology National Excellence Program (Project Nr. 2017-1.2.1-NKP-2017-00001) and via the research grants K124152, KH129601 (PV). This material is based upon work directly supported by the National Science Foundation Grant No. DMS-1638352 and indirectly supported by the National Science Foundation Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation (JZ).

References