Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor

Introduction

Matrix multiplication is one of the most important problems in mathematics and computer science. In 1969, Strassen discovered the first algorithm with subcubic complexity computing the product of two square matrices . In modern notation, Strassen’s result can be stated as an upper bound $\omega<2.81$ on the exponent of square matrix multiplication $\omega$, defined as the minimum value such that two $n\times n$ matrices can be multiplied using $O(n^{\omega+\epsilon})$ arithmetic operations for any constant $\epsilon<0$. Strassen’s breakthrough initiated intense work on the complexity of matrix multiplication, which in a span of a few decades lead to several improvements, culminating in the celebrated $O(n^{2.376})$-time algorithm for square matrix multiplication by Coppersmith and Winograd , i.e., the upper bound $\omega<2.376$ on the exponent of square matrix multiplication. This algorithm is obtained from a basic construction, which is nowadays often called the Coppersmith-Winograd tensor. Coppersmith and Winograd showed that analyzing this tensor gives the upper bound $\omega<2.388$, and next showed that analyzing the second power of this tensor gives the improved upper bound $\omega<2.376$.

A natural question, already mentioned in Coppersmith and Winograd’s paper , was whether higher powers of the Coppersmith-Winograd tensor can lead to further improvement to the complexity of matrix multiplication. Most efforts to investigate this direction quickly stopped after discovering that the third power does not seem to lead to any further improvement. More than twenty year later, however, Stothers (see also ) and Vassilevska Williams showed that the fourth power does give an improvement: the fourth power leads to the upper bound $\omega\leq 2.373$. The technically challenging analysis of the fourth power was made possible by the introduction of powerful general recursive techniques to analyze powers of tensors. Extending these techniques, Vassilevska Williams and then Le Gall succeeded in analyzing higher powers up to the 32nd power, which gave additional small improvements and lead to the current best known upper bound on the exponent of square matrix multiplication $\omega<2.3728639$. Table 1 summarises all these results. Ambainis et al. finally showed that further improving this upper bound will be hard: they showed that analyzing higher powers of the Coppersmith-Winograd tensor (e.g., powers 64, 128,…) using the same methodology cannot give any further significant improvement on $\omega$ (in particular it cannot lead to a proof of the popular conjecture $\omega=2$).

Besides square matrix multiplication, rectangular matrix multiplication plays a central role in many algorithms as well. In addition to natural applications to computational problems in linear algebra, typical examples of application include the construction of fast algorithms for the all-pairs shortest paths problem , dynamic computation of the transitive closure , detection of subgraphs , speed-up of sparse square matrix multiplication and algorithms for bounded-difference min-plus square matrix multiplication . Rectangular matrix multiplication has also been used in computational complexity and computational geometry .

The typical problem considered when studying rectangular matrix multiplication is computing the product of an $n\times\left\lceil n^{k}\right\rceil$ matrix by an $\left\lceil n^{k}\right\rceil\times n$ matrix, for some parameter $k\geq 0$. Note that a basic result in algebraic complexity theory states that the algebraic complexities of the following three problems are the same: computing the product of an $n\times\left\lceil n^{k}\right\rceil$ matrix by an $\left\lceil n^{k}\right\rceil\times n$ matrix, computing the product of an $\left\lceil n^{k}\right\rceil\times n$ matrix by an $n\times n$ matrix, and computing the product of an $n\times n$ matrix by an $n\times\left\lceil n^{k}\right\rceil$ matrix. In this paper for concreteness we discuss only the first type of products, but all our bounds naturally hold for the two other types as well. In analogy to the square case, the exponent of rectangular matrix multiplication, denoted $\omega(k)$, is defined as the minimum value such that this product can be computed using $O(n^{\omega(k)+\epsilon})$ arithmetic operations for any constant $\epsilon>0$. Also note that for $k=1$ (i.e., for square matrices), we have $\omega(1)=\omega$.

Coppersmith showed in 1982 that $\omega(0.172)=2$. This surprising result means that the product of an $n\times\left\lceil n^{0.172}\right\rceil$ matrix by an $\left\lceil n^{0.172}\right\rceil\times n$ matrix can be computed in time almost linear in the size of the output (which contains $n^{2}$ entries). This discovery lead to the introduction of the following quantity $\alpha$:

Since proving that $\alpha=1$ is equivalent to proving that $\omega=2$, the quantity $\alpha$ is sometimes called the dual exponent of matrix multiplication. Coppersmith’s result then corresponds to the bound $\alpha\geq 0.172$. Coppersmith later showed that $\alpha>0.29462$ by analyzing the Coppersmith-Winograd tensor in the context of rectangular matrix multiplication. Fifteen years later, Le Gall showed that the second power of the Coppersmith-Winograd tensor can also be analyzed in the context of rectangular matrix multiplication, which lead to the improved lower bound $\alpha>0.30298$. This analysis was actually much more general and gave bounds on $\omega(k)$ that improved prior bounds for any $k\neq 1$. (For $k=1$, i.e., square matrix multiplication, this approach recovered the upper bound $\omega<2.376$ from ). The results from are presented in Table 2.

2 Our results

In view of the recent progress in square matrix multiplication algorithms obtained by analyzing higher powers of the Coppersmith-Winograd tensor, it is natural to ask whether the same approach can be applied to obtain further improvements on the complexity of rectangular matrix multiplication as well. We investigate this question in this paper, and present a framework to extend the analysis of higher powers to the case of rectangular matrix multiplication. We concretely focus on the analysis of the fourth power of the Coppersmith-Winograd tensor and show that this analysis leads to non-negligible improvements. The new upper bounds we obtain on the exponent of rectangular matrix multiplication $\omega(k)$ are given in Table 3 and the values for $k\leq 1$ are plotted in Figure 1. Note that the curve of Figure 1 has the same shape as the curve for the second power given in . We obtain in particular the new lower bound

on the dual exponent of matrix multiplication, as stated in the following theorem.

The product of an $n\times\left\lceil n^{0.31389}\right\rceil$ matrix by an $\left\lceil n^{0.31389}\right\rceil\times n$ matrix can by computed with $O(n^{2+\epsilon})$ arithmetic operations for any constant $\epsilon>0$.

This new bound improves the previous best known lower bound $\alpha>0.30298$ by Le Gall . For other values of $k$ as well, our new upper bounds on $\omega(k)$ are systematically better than those of , as can be seen by comparing Table 2 and Table 3. For instance we obtain ${\omega(3)\leq 4.199712}$, which improves the previous upper bound ${\omega(3)\leq 4.207372}$. Note that for $k=1$ (i.e., for square matrix multiplication), we obtain the same upper bound $\omega\leq 2.372927$ on the exponent of square matrix multiplication as the bound obtained by analyzing the fourth power . Indeed, for $k=1$ our analysis becomes essentially the same as the analysis for the square case in those prior works.

A surprising, or at least unexpected, aspect of the result of Theorem 1.1 is that the improvement from the second power to the fourth power (from $\alpha>0.30298$ to $\alpha>0.31389$) exceeds the improvement known from the first power to the second power (from $\alpha>0.29462$ to $\alpha>0.30298$). This is completely different from the improvements achieved on $\omega$ when analyzing successive powers of the Coppersmith-Winograd tensor, which are decreasing, as summarized in Table 1. Actually, all the numerical results we have obtained confirm that for any fixed value of $k$ the improvements on $\omega(k)$ decrease similarly to the square case when analyzing successive powers. For instance for $k=0.8$ and $k=2$ the first power gives $\omega(0.8)<2.2356$ and $\omega(2)<3.2699$; by examining Tables 2 and 3 we observe that the improvement is larger from the first power to the second power. The situation happens to be different, however, for lower bounds on $\alpha$. Since the curves representing the upper bounds on $\omega(k)$ have horizontal asymptotes at the lower bound on $\alpha$ (see Figure 1 of the present paper and Figure 1 in ), even small improvements on $\omega(k)$ can lead to fairly significant improvements on $\alpha$, as our results show.

The most pressing question is now to investigate what will happen for even higher powers of the Coppersmith-Winograd tensor (e.g., power 8 or 16). We believe that this question is important since, besides its theoretical interest, further significant improvements for $\alpha$ may be obtained in this way. A concrete approach would be to adapt to the rectangular case the numerically efficient methods based on convex optimization developed, in the setting of square matrix multiplication, to study high powers of the Coppersmith-Winograd tensor . In the other direction, it may be possible to show some limitations on the improvements achievable when studying higher powers, by generalizing the recent approach developed for the square case .

Our new bounds can be used to improve essentially all the known algorithms based on rectangular matrix multiplication algorithms (e.g., the algorithms in ). Following , we discuss below one concrete example.

Zwick has shown how to use rectangular matrix multiplication to compute the all-pairs shortest paths in weighted direct graphs where the weights are bounded integers. The time complexity obtained by Zwick for graphs with constant weights is $O(n^{2+\mu+\epsilon})$, for any constant $\epsilon>0$, where $\mu$ is the solution of the equation $\omega(\mu)=1+2\mu$. The results from (see Table 2) show that $\omega(0.5302)<2.0604$, which gives the upper bound $\mu<0.5302$. The results of the present paper (see Table 3) show that $\omega(0.5286)<2.0572$, which gives the upper bound $\mu<0.5286$.

3 Overview of our approach

Before presenting an overview of the techniques used in this paper, we give an informal description of algebraic complexity theory (a more detailed presentation of these notions is given in Section 2).

The matrix multiplication of an $m\times n$ matrix by an $n\times p$ matrix can be represented by the following trilinear form, denoted as $\langle m,n,p\rangle$:

where $x_{rs}$, $y_{st}$ and $z_{rt}$ are formal variables. This form can be interpreted as follows: the $(r,t)$-th entry of the product of an $m\times n$ matrix $M$ by an $n\times p$ matrix $M^{\prime}$ can be obtained by setting $x_{ij}=M_{ij}$ for all $(i,j)\in[m]\times[n]$ and $y_{ij}=M^{\prime}_{ij}$ for all $(i,j)\in[n]\times[p]$, setting $z_{rt}=1$ and setting all the other $z$-variables to zero. One can then think of the $z$-variables as formal variables used to record the entries of the matrix product.

More generally, a trilinear form $t$ is represented as

A sum $\sum_{i}t_{i}$ of trilinear forms is a direct sum if the $t_{i}$’s do not share variables. Informally, Schönhage’s asymptotic sum inequality for rectangular matrix multiplication states that, if the form $t$ can be converted into a direct sum of $c$ trilinear forms, each form being isomorphic to $\langle m,m,m^{k}\rangle$, then

This implies that to obtain good upper bounds on the exponent of rectangular matrix multiplication, it is enough to find a tensor $t$ of low border rank that can be converted into many independent (i.e., not sharing any variables) products of large enough rectangular matrices.

Overview of the analysis of the second power.

We now give a brief overview of the analysis of the second power of the Coppersmith-Winograd tensor given in to derive the upper bounds on $\omega(k)$ of Table 2. The Coppersmith-Winograd tensor is a trilinear form $F_{q}$ introduced in . Here $q$ is a parameter (concretely, $q$ is an integer between 2 and 10). Its second power $F_{q}\otimes F_{q}$ can actually be written as a sum of fifteen terms $T_{uvw}$:

In order to apply Schönhage’s asymptotic sum inequality, this sum must first be converted into a direct sum. This is done using a powerful general technique known as the laser method, first introduced by Strassen and then successively generalized and refined . The first step is to take the $N$-th tensor product of the basic construction, where $N$ is a large integer, and then zero variables so that the remaining terms do not share variables. Since we want each remaining term to be isomorphic to a rectangular matrix product in order to obtain an upper bound on $\omega(k)$ via Schönhage’s asymptotic sum inequality, the choice of zeroed variables has to be done carefully. The laser method allows us, for any choice of the fifteen parameters $a_{uvw}\in$ satisfying specific constraints, to convert the $N$-th tensor product of the basic construction into a direct sum of many terms (the number of these terms depending on the values of the $a_{uvw}$’s), each isomorphic to

The next step is to analyze each term (1) and show that it corresponds to a direct sum of matrix products of the form $\langle m,m,m^{k}\rangle$ (the number of terms in the direct sum and the value of $m$ will depend on the values of the $a_{uvw}$’s and $q$). Some of the $T_{uvw}$’s (more precisely, all the $T_{uvw}$’s except $T_{112}$, $T_{121}$ and $T_{211}$) can be analyzed in a straightforward way, since they correspond to matrix products. The main technical contribution of the approach from was to show that each of the remaining three terms can be converted into a large number of objects called “$\mathscr{C}$-tensors” in Strassen’s terminology . This conversion is done again via the laser method, which introduces additional parameters. Finally, Ref. explained how to convert these $\mathscr{C}$-tensors into a direct sum of matrix multiplication tensors. Combining the analysis of these fifteen terms shows that (1) corresponds to a direct sum of matrix products of the form $\langle m,m,m^{k}\rangle$, as wanted. Schönhage’s asymptotic sum inequality then gives the upper bound on $\omega(k)$ presented in Table 2 by numerically optimizing the choice of the parameters (the choice of $q$, the $a_{uvw}$’s and the additional parameters arising in the second extraction).

Overview of our analysis of the fourth power.

The fourth power of the Coppersmith-Winograd tensor can be written as a sum of 45 terms $T_{uvw}$:

For conciseness, this tensor will be denoted $F$ through the paper. Similarly to the analysis of the second power, the laser method allows us, for any choice of parameters $a_{uvw}\in$ satisfying specific constraints, to convert the $N$-th tensor product of the basic construction into a direct sum of many terms, each isomorphic to

We call this process the first extraction, which is explained in detail in Section 3. Note that while this extraction is more complicated than for the second power since the number of variables is larger and deriving the constraints that the parameters should satisfy is more complex, conceptually the analysis is fairly standard.

The main technical contribution of this work is a methodology to analyze each term (2). A natural strategy would be to mimic the analysis done in for the second power and analyze each component $T_{uvw}$ individually. While this leads to some improvement over the second power when $k$ is close to 1 (in particular, this leads to the same upper bound $\omega<2.372927$ as in prior works analyzing the fourth power in the context of square matrix multiplication ), this strategy does not give any improvement for smaller values of $k$ (in particular, no improved lower bound on the dual exponent of matrix multiplication $\alpha$). Our strategy, instead, is to analyze all the terms $T_{uvw}$ together via the laser method. As in the term-by-term analysis done for the second power in , this introduces a set of new parameters for each term and a set of constraints that these parameters should satisfy. A difference is that now some of the constraints are global: they can involve the parameters of all the 45 terms. We call this process the second extraction, which is explained in detail in Section 4. Note that this methodology appears to be more powerful than the term-by-term conversion to $\mathscr{C}$-tensors done in : First, as already mentioned, the latter approach does not seem to lead to any improvement on $\alpha$ for the fourth power. Second, our new methodology, when applied to the analysis of the second power in replacement of the conversion into $\mathscr{C}$-tensors done in , already leads to upper bounds on $\omega(k)$ slightly better than those found in for some values of $k$ (more precisely, we observed such improvements for values in the range $k\in[0.37,0.46]$).

The second extraction outlined in the previous paragraph actually does not completely analyze (2): it simply decomposes each term $T_{uvw}$ into a direct sum of products of the fifteen terms arising in the analysis of the second power. To complete the analysis, we recursively apply the same strategy as for the second extraction and analyse the contribution of all these fifteen terms together, again using the laser method (which introduce two additional parameters). We call this process the third extraction, which is explained in detail in Section 5.

Finally, combining our three extractions, we conclude that the tensor $F^{\otimes N}$ can be converted into a direct sum of $c$ trilinear forms, each form being isomorphic to $\langle m,m,m^{k}\rangle$, for some values $c$ and $m$ depending on all the parameters introduced. Applying Schönhage’s asymptotic sum inequality then gives an inequality involving $\omega(k)$ and all these parameters (the formal statement is Theorem 6.1 in Section 6). Optimizing numerically the choice of parameters, under the constraints derived on those parameters, gives the upper bounds of Table 3 and the lower bound on $\alpha$ of Theorem 1.1.

Preliminaries

We present various known results and tools related to matrix multiplication. Two good references for an extensive treatment of this topic are and .

We define the notion of type. A type can be seen as a frequency vector.

2 Tensors, matrix multiplication and the asymptotic sum inequality

Let $t\in U\otimes V\otimes W$ and $t^{\prime}\in U^{\prime}\otimes V^{\prime}\otimes W^{\prime}$ be two tensors. The direct sum $t\oplus t^{\prime}$, is a tensor in $(U\oplus U^{\prime})\otimes(V\oplus V^{\prime})\otimes(W\oplus W^{\prime})$. The tensor product $t\otimes t^{\prime}$ is a tensor in $(U\otimes U^{\prime})\otimes(V\otimes V^{\prime})\otimes(W\otimes W^{\prime})$. For any positive $c$, we will denote the tensor $t\oplus\cdots\oplus t$ (with $c$ occurrences of $t$) by $c\cdot t$ and the tensor $t\otimes\cdots\otimes t$ (with $c$ occurrences of $t$) by $t^{\otimes c}$.

where $i$ spans $[\![1,m]\!]\times[\![1,n]\!]$, $j$ spans $[\![1,n]\!]\times[\![1,p]\!]$, $k$ spans $[\![1,m]\!]\times[\![1,p]\!]$ and

We also consider the tensor of format $(n,n,n)$ which represents $n$ independent scalar products. It is denoted by $\langle n\rangle$ and is defined as $\langle n\rangle=\sum\limits_{l=1}^{n}x_{l}y_{l}z_{l}$.

The intuition behind this notion is that the restriction of a tensor is easier to compute than the original tensor, in the sense that an algorithm computing a tensor $t$ can be converted into an algorithm computing a tensor $t^{\prime}\leq t$ with the same complexity.

This is analogous to the notion of approximate computation.

Note that by definition, $t^{\prime}\leq t\Longrightarrow t^{\prime}\unlhd t$. The notion of degeneration can be seen as an approximate conversion. It has the following property.

Let $t_{1},t_{1}^{\prime},t_{2}$ and $t_{2}^{\prime}$ be four tensors. Suppose that $t^{\prime}_{1}\unlhd t_{1}$ and $t^{\prime}_{2}\unlhd t_{2}$. Then $t^{\prime}_{1}\oplus t^{\prime}_{2}\unlhd t_{1}\oplus t_{2}$ and $t^{\prime}_{1}\otimes t^{\prime}_{2}\unlhd t_{1}\otimes t_{2}$.

The notion of border rank enables us to formally define the exponent of rectangular matrix multiplication, as follows. For any $k\geq 0$,

The exponent of square matrix multiplication is $\omega=\omega(1)$.

Similarly to almost all recent works on matrix multiplications, our main tool for proving lower bounds on $\omega(k)$ will be Schönhage’s asymptotic sum inequality (see for the version of the inequality given below).

Let $k$, $m$ and $c$ be three positive integers. Let $t$ be a tensor such that $c\cdot\langle m,m,m^{k}\rangle\unlhd t$. Then

3 The fourth power of Coppersmith-Winograd tensor

For any positive integer $q$, the Coppersmith-Winograd tensor is the tensor of format ${(q+2,q+2,q+2)}$ defined as

Coppersmith and Winograd showed that $\underline{R}(F_{q})\leq q+2$.

Define the tensors $x_{ii^{\prime}}y_{jj^{\prime}}z_{kk^{\prime}}=x_{i}y_{j}z_{k}\otimes x_{i^{\prime}}y_{j^{\prime}}z_{k^{\prime}}$. By regrouping terms, we can write

and the other eleven terms are obtained by permuting the indexes of the $x$ variables, the $y$ variables and $z$ variables in the above expressions (e.g., $T_{040}=x_{0,0}y_{q+1,q+1}z_{0,0}$ and $T_{400}=x_{q+1,q+1}y_{0,0}z_{0,0}$). Note that $\underline{R}(F_{q}^{\otimes 2})\leq(q+2)^{2}$ from the submultiplicativity of the border rank.

Let us now consider the fourth power of the Coppersmith-Winograd tensor $F_{q}$ (already studied, in the context of square matrix multiplication, in Refs. ). For any $(i,j,k)\in S_{8}$ define the set

By regrouping terms, the fourth power of $F_{q}$, which hereafter we simply denote $F$ (the value of $q$ will be implicit until the very end of the paper), can be written as

Note that $\underline{R}(F)\leq(q+2)^{4}$, again from the submultiplicativity of the border rank.

When later working with the terms $T_{ijk}$, we will sometimes consider the equivalent decomposition

Notice that we define $T_{IJK}$ only for triple $(I,J,K)$ from the set

Finally, for any triple $(a,b,c)\in S_{8}$ and any triple $(I,J,K)=(I(l),J(l),K(l))_{l\in[\![1,N]\!]}\in\overline{S}_{abc}^{N}$, we define

4 Extraction from a tensor

In this subsection we explain our main tool to realize an extraction from a sum of tensors. An extraction consists in assigning some variables to zero in a tensor (thus eliminating all their contributions to the sum). If a tensor $T^{\prime}$ is extracted from $T$, then $T^{\prime}\leq T$ trivially holds. Our primary goal is to guarantee that the resulting tensor $T^{\prime}$ is a direct sum of isomorphic tensors, so that the asymptotic sum inequality can be used.

All recent progresses on square or rectangular matrix multiplication have been obtained by performing extractions based on the so-called laser method . Le Gall introduced the following convenient framework to interpret such reductions in the rectangular case. In this framework, a sum of tensors corresponds to a graph whose vertices are the tensors in the sum. There is an edge between two vertices in the graph if and only if the two corresponding terms in the sum of tensors share a variable. Let $G$ denote this graph, and $U$ denote its set of vertices. Zeroing a term in the sum corresponds to removing one vertex from the graph. As mentioned above, however, terms can be zeroed only by zeroing the variables it contains. This means that such a zeroing operation may actually remove more than one vertex from the graph. Extracting a direct sum from the original tensor is then equivalent to removing vertices from the graph by such zeroing operations and reaching an edgeless graph. When using this methodology, we will like to additionally guarantee that the vertices remaining in the final graph are from a specified subset $U^{\ast}\subseteq U$. Concretely, the set $U^{*}$ will be the set of vertices of terms matching a certain type, which will ensure that all the tensors remaining after the extraction are of this type. In our extractions we will use the following theorem from , which is tailored for this goal and was already used for the analysis of the second power of the Coppersmith-Winograd tensor.

Let $\tau$ be a fixed positive integer. Let $N$ be a large integer and define the set

Define the three coordinate functions $f_{1},f_{2},f_{3}\colon[\tau]^{N}\times[\tau]^{N}\times[\tau]^{N}\to[\tau]^{N}$ as follows.

Let $U$ be a subset of $\Lambda$ such that there exist integers $\mathcal{N}_{1},\mathcal{N}_{2}$ and $\mathcal{N}_{3}$ for which the following property holds: for any $I\in[\tau]^{N}$,

Let $\mathcal{T}_{1}=|f_{1}(U)|$, $\mathcal{T}_{2}=|f_{2}(U)|$ and $\mathcal{T}_{3}=|f_{3}(U)|$. Let $G$ be the (simple and undirected) graph with vertex set $U$ in which two distinct vertices $u$ and $v$ are connected if and only if there exists one index $i\in\{1,2,3\}$ such that $f_{i}(u)=f_{i}(v)$.

Assume there exists a set $U^{\ast}\subseteq U$ such that

$|f_{i}(U^{\ast})|=\mathcal{T}_{i}$ for each $i\in\{1,2,3\}$;

there exist integers $\mathcal{N}^{\ast}_{1},\mathcal{N}^{\ast}_{2}$ and $\mathcal{N}^{\ast}_{3}$ such that

for each $I\in[\tau]^{N}$ and each $i\in\{1,2,3\}$.

Define a removal operation as removing all the vertices $u$ (if any) such that $f_{i}(u)=I$, for a fixed sequence $I\in[\tau]^{N}$ and a fixed position $i\in\{1,2,3\}$ Then, for any constant $\epsilon>0$, the graph $G$ can be converted, with only removal operations, into an edgeless graph with

vertices, all of them being in $U^{\ast}$.

First extraction

In this section we describe our first extraction.

Let us consider any function $a\in\mathcal{P}(S_{8})$. For any $(i,j,k)\in S_{8}$ we will often write $a(ijk)$ instead of $a(i,j,k)$. Given $a$, we define the following three mappings:

$A$,$B$,$C$ are the projections of $a$ on each of the three coordinates. We thus have

we are left only with tensors $T_{IJK}$ where $(I,J,K)$ is of type $a$, i.e, tensors isomorphic to

First notice that for any ${(I,J,K),(I^{\prime},J^{\prime},K^{\prime})\in S_{8}^{N}}$ such that $I\neq I^{\prime}$, the $x$ variables in $T_{IJK}$ and in $T_{I^{\prime}J^{\prime}K^{\prime}}$ are disjoint. We set to zero all the $x$ variables except the ones which appear in a $T_{IJK}$ where $I$ is of type $A$, that is to say we set to zero all variables which appear in a $T_{IJK}$ with $I$ not of type $A$. We are thus left with only the tensors $T_{IJK}$ with $I$ of type $A$.

The number of sequences $I\in[\!\!]^{N}$ of type $A$ is

as choosing a sequence $I$ of type $A$ is equivalent to choose the location of the $A(i)$ elements $i$ for $i\in[\!\!]$. Using the Stirling formula, we get, with the $A(i)$ fixed and $N\longrightarrow\infty$,

Similarly, we define the number of sequences $J\in[\!\!]^{N}$ of type $B$ as $\mathcal{T}_{Y}$ and the number of sequences $K\in[\!\!]^{N}$ of type $C$ as $\mathcal{T}_{Z}$.

For any fixed sequence $I$ of type $A$, the number of remaining forms $T_{IJK}$ of type $a$ is

while the total number of remaining forms $T_{IJK}$ is

Define, the function $g$ which associates to any mapping $x:~S_{8}\longrightarrow~]0,1[~~(i,j,k)\longmapsto x(ijk)$ the value $g(x)=\left(\prod\limits_{(i,j,k)\in S_{8}}x(ijk)^{x(ijk)}\right)^{-1}$. Using Stirling’s formula, and the fact that $|S_{8}|=\sum\limits_{l=1}^{9}l=45$, we get that

Similarly, for any sequence $J$ of type $B$, the number of remaining forms $T_{IJK}$ of type $a$ and the total number of remaining forms $T_{IJK}$ are

and for any sequence $K$ of type $C$, the number of remaining forms $T_{IJK}$ of type $a$ and the total number of remaining forms $T_{IJK}$ are

Using the framework presented in Subsection 2.4, we get by Theorem 2.2 that for any $\epsilon>0$ we can further extract from the remaining $T_{IJK}$ a direct sum of

tensors $T_{IJK}$, all of which are of type $a$. We want the number of tensors is this direct sum to be high. For this to happen, we now formulate some conditions on $a$.

Conditions on aa.

We first observe that $\ln g$ can actually be written as a (concave) function of only $21$ variables, namely $\overline{a}(215)$, $\overline{a}(224)$, $\overline{a}(233)$, $\overline{a}(242)$, $\overline{a}(251)$, $\overline{a}(260)$, $\overline{a}(314)$, $\overline{a}(323)$, $\overline{a}(332)$, $\overline{a}(341)$, $\overline{a}(350)$, $\overline{a}(413)$, $\overline{a}(422)$, $\overline{a}(431)$, $\overline{a}(440)$, $\overline{a}(512)$, $\overline{a}(521)$, $\overline{a}(530)$, $\overline{a}(611)$, $\overline{a}(620)$, $\overline{a}(710)$. This is because $\ln g$ is defined on $\widetilde{[a]}$, and the elements of $\widetilde{[a]}$ have, by definition, the same projections as $a$, and thus for any $\overline{a}\in\widetilde{[a]}$ the $\overline{a}(ijk)$ satisfy the following system of linear equations:

Resolving of the (homogeneous) linear system A Maple file deriving the symbolic solution of this system is available at . reduces the number of variables to 21, as claimed.

From now we will assume that $a$ satisfies the symmetry condition

Computing each one of the $21$ partial differential equations $\dfrac{\partial\ln g}{\partial\overline{a}(ijk)}=0$ leads, after simplification and by condition (C1), to a system of $10$ non linear equations:

Note that, as the value of any $\overline{a}\in[a]$ is fixed from the values of only $21$ variables, and as ${\forall~(i,j,k)\in S_{8},a(ijk)N\in[\![1,N]\!]}$, we have $|[a]|\leq N^{21}$. For any $a$ satisfying these $10$ equations, we have $g(a)=\max\limits_{\overline{a}\in[a]}g(\overline{a})$ and thus, $\mathcal{N}_{X}=\mathcal{O}(N^{21}\mathcal{N}^{*}_{X})$, $\mathcal{N}_{Y}=\mathcal{O}(N^{21}\mathcal{N}^{*}_{Y})$, $\mathcal{N}_{Z}=\mathcal{O}(N^{21}\mathcal{N}^{*}_{Z})$.

Final statement.

By the symmetry condition (C1), this implies that $\prod\limits_{i=0}^{8}A(i)^{A(i)}\geq\prod\limits_{k=0}^{8}C(k)^{C(k)}$. We get ${\mathcal{N}^{*}_{Y}=\mathcal{N}^{*}_{Z}=\mathcal{O}(\mathcal{N}^{*}_{X})}$, and thus we obtain ${(\mathcal{N}_{X}+\mathcal{N}_{Y}+\mathcal{N}_{Z})=\mathcal{O}(N^{21}\mathcal{N}^{*}_{X})}$ and

As by definition $\mathcal{N}^{*}_{X}\leq|S_{8}|^{N}=45^{N}$, this is equal to

Let $q$ be any positive integer. Let $a$ be any function from $\mathcal{P}(S_{8})$ satisfying the constraints (C1), (C2) and (3). Then for any $\epsilon>0$, the trilinear form $F^{\otimes N}$ admits a restriction which is a direct sum of $r_{1}$ trilinear forms, each of which is isomorphic to $\bigotimes\limits_{(i,j,k)\in S_{8}}T_{ijk}^{\otimes a(ijk)N}$.

Second extraction

As we will see later in details in Section 6, the tensors $T_{ijk}$ for $(i,j,k)\in S_{8}$ with one or more of their indices $i,j,k$ equal to $0$ are actually matrix products tensors. No further work is required for them. In contrast, the tensors $T_{ijk}$ for $(i,j,k)\in\overline{S}_{8}$ where $\overline{S}_{8}=\{(i,j,k)\in S_{8}\mid i>0,j>0,k>0\}$ do not correspond to matrix products.

We are now going to realize an extraction on all the tensors $T_{ijk},(i,j,k)\in\overline{S}_{8}$. We first study the properties of the $T_{ijk},(i,j,k)\in\overline{S}_{8}$. In Subsection 4.1, we consider the particular case of the tensors $T_{233}$, $T_{323}$ and $T_{332}$. In Subsection 4.2, we consider the remaining tensors, i.e., the tensors $T_{ijk}$ for ${(i,j,k)\in S^{\prime}_{8}=\overline{S}_{8}\setminus\{(2,3,3),(3,2,3),(3,3,2)\}}$, which are actually easier to analyze. Then, in Subsection 4.3, we explain the limitations of independent extractions and introduce our method to realize a joint extraction.

The extractions from the tensors $T_{233}$, $T_{323}$, $T_{332}$ can be realized similarly to the extraction from the tensor $F$ that we realized in Section 3. As the situation is similar for the three tensors, we only detail the extraction from the tensor $T_{233}$.

The number of sequences $I\in[\!\!]^{a(233)N}$ of type $A_{233}$ is

Define the function $g_{233}$ which associates to any mapping $x:~\overline{S}_{233}\longrightarrow~]0,1[~~(i,j,k)\longmapsto x(ijk)$ the value

For any fixed sequence $I$ of type $A_{233}$, the number of remaining forms $V_{233}[IJK]$ with $(I,J,K)$ of type $a_{233}$ is

while the total number of remaining forms $V_{233}[IJK]$ is

Similarly, for any fixed sequence $J$ of type $B_{233}$, the number of remaining forms $V_{233}[IJK]$ with $(I,J,K)$ of type $a_{233}$ is

the total number of remaining forms $V_{233}[IJK]$ is

and for any fixed sequence $K$ of type $C_{233}$, the number of remaining forms $V_{233}[IJK]$ with $(I,J,K)$ of type $a_{233}$ is $\mathcal{N}_{233,Z}=\mathcal{N}_{233,Y}$ and the total number of remaining forms $V_{233}[IJK]$ is ${\mathcal{N}_{233,Z}^{*}=\mathcal{N}_{233,Y}^{*}}$.

By studying the function $g_{233}$ in a similar way as we studied the function $g$ in Section 3, we get that $g(a_{233})=\max\limits_{\overline{a}_{233}\in[a_{233}]}g(\overline{a}_{233})$ for $a_{233}$ satisfying the constraint

Calculations show that ${\overline{a}_{233}\in[a_{233}]}$ can be written as a function of $\overline{a}_{233}(130)$ and $\overline{a}_{233}(103)$ only, and as ${\overline{a}_{233}(130),\overline{a}_{233}(103)\in[\![1,a(233)N]\!]}$, we have that ${|[a_{233}]|\leq(a(233)N)^{2}}$ and thus we obtain ${\mathcal{N}_{233,X}=\mathcal{O}((a(233)N)^{2}\mathcal{N}_{233,X}^{*})}$, ${\mathcal{N}_{233,Y}=\mathcal{O}((a(233)N)^{2}\mathcal{N}_{233,Y}^{*})}$ and ${\mathcal{N}_{233,Z}=\mathcal{O}((a(233)N)^{2}\mathcal{N}_{233,Z}^{*})}$.

The tensors $T_{323}$ and $T_{332}$ are analysed similarly. Imposing the constraints

implies that $\mathcal{N}_{323,X}=\mathcal{O}(N^{2}\mathcal{N}_{323,X}^{*})$ and $\mathcal{N}_{332,X}=\mathcal{O}(N^{2}\mathcal{N}_{332,X}^{*})$.

To summarize, when analyzing $T_{233}$, $T_{323}$ and $T_{332}$ we need to impose the following three constraints (in addition to other constraints discussed later):