Exploiting the Structure in Tensor Decompositions for Matrix Multiplication Conference: ; ; Thanks: ∗ M. Kauers was supported by the Austrian FWF grants 10.55776/PAT8258123, 10.55776/I6130, and 10.55776/PAT9952223 Thanks: † J. Moosbauer was supported by the Austrian FWF grant 10.55776/PAT8258123 Thanks: ‡ I. Wood was supported by the Austrian FWF grant 10.55776/PAT8258123 CCS: Computing methodologies Algebraic algorithms Manuel Kauers ∗, Jakob Moosbauer †, Isaac Wood ‡ Abstract . We present a new algorithm for fast matrix multiplication using tensor decompositions which have special features. Thanks to these features we obtain exponents lower than what the rank of the tensor decomposition suggests. In particular for 6 × 6 6\times 6 matrix multiplication we reduce the exponent of the recent algorithm by Moosbauer and Poole from 2.8075 2.8075 to 2.8016 2.8016 , while retaining a reasonable leading coefficient. 1. Introduction Since Strassen’s seminal discovery that two n\times n matrices can be multiplied in \operatorname{O}(n^{2.81}) time ( STRASSEN 1969 ) , there has been a race to reduce the upper bound on \omega , the exponent of matrix multiplication. Following Strassen’s breakthrough, Bini et al. ( Bini et al. 1979 ) introduced the concept of approximate algorithms and border rank, allowing for a small improvement on the upper bound, finding \omega\leq 2.78 . This line of research continued to Schönhage’s Asymptotic Sum Inequality (ASI) ( Schönhage 1981 ) , allowing for algorithms that compute disjoint matrix multiplications simultaneously, giving a bound of \omega\leq 2.52 . Later improvements, based on Strassen’s laser method ( Strassen 1986 ) and the Coppersmith-Winograd approach ( Coppersmith and Winograd 1990 ) , further reduced the bound on \omega to the currently best upper bound of \omega<2.371339 by Alman et al. ( Alman et al. 2024 ) . While there has been a lot of work done to reduce the exponent of matrix multiplication, approximate algorithms (like those used in all the fastest algorithms since 1979) in general either require unreasonable precision or have such large leading coefficients that they are impractical. Most current research into practical algorithms is based on exact algorithms, either trying to reduce the number of multiplications (using, e.g., flip graphs ( Kauers and Moosbauer 2022 ; Kauers and Moosbauer 2023a ; Kauers and Wood 2025b ; Kauers and Moosbauer 2023b ; Moosbauer and Poole 2025 ; Perminov 2025 ; Kauers and Wood 2025a ) , numerical optimization ( Smirnov 2013 ; Kaporin 2024 ; Novikov et al. 2025a ) , or reinforcement learning ( Fawzi et al. 2022 ) ) or reducing the number of additions (Winograd’s variant of Strassen’s algorithm, published in ( Probert 1976 ) , alternative basis algorithms ( Karstadt and Schwartz 2017 ; Beniamini and Schwartz 2019 ; Schwartz et al. 2024 ) , flip graph search ( Perminov 2025 ) , or common subexpression elimination ( Mårtensson and Wagner 2025 ) ). Schönhage’s 1981 paper ( Schönhage 1981 ) uses that an algorithm by Pan ( Pan 1984 ) has a special property. After 3 iterations, 8 of the recursive calls form a 2\times 2 matrix multiplication, which can then be computed using Strassen’s algorithm, thereby saving one multiplication. Schwartz and Zwecher ( Schwartz and Zwecher 2025 ) recently used a similar idea to improve some of Pan’s trilinear aggregation algorithms. The concept also appears in the group theoretic approach to matrix multiplication by Cohn and Umans ( Cohn and Umans 2003 ; Cohn et al. 2005 ) , who give a variant of the ASI that uses this technique recursively. Schwartz and Zwecher give an explicit algorithm with a 44\times 44 base case, that achieves the best exponent among exact algorithms with base case smaller than 1000 , while Schönhage’s and Cohn-Umans’ results are purely theoretical bounds on the exponent, with no explicit algorithm provided. In this paper we propose a new recursive matrix multiplication algorithm that uses the same idea. If some recursive calls share one of the inputs or have an output that is used in multiple positions, then they are treated as a single matrix multiplication of larger size. Applying this technique repeatedly improves the exponent of a matrix multiplication algorithm without reducing the number of multiplications over the base field. In particular, we improve the recent 6\times 6 matrix multiplication algorithm by Moosbauer and Poole ( Moosbauer and Poole 2025 ) from an exponent of 2.8075 to 2.8016 , compared to 2.8073 of Strassen’s algorithm. Our algorithm outperforms the standard algorithm for n\geq 1000 in terms of total operation count. This does not necessarily mean that in an implementation one would already observe a speedup for such matrix sizes, but it clearly puts it in the realm of practical algorithms by Pan’s definition ( Pan 1984 ) , who generously drew the line at n=10^{20} . We ran a search for such algorithms, first using a flip graph search to find algorithms using a minimal number of multiplications while retaining the special structure needed to apply our new recursive method. Then we optimize the number of additions using DeGroote actions. These steps produce an algorithm that is valid only modulo 2 , thus we apply Hensel lifting to lift the algorithm to work over the integers, and finally we reduce the number of additions further by Mårtensson and Wagner’s common subexpression elimination method ( Mårtensson and Wagner 2025 ) . We find improvements in the exponent for several small base cases including 3\times 3 matrix multiplication, where we reduce the exponent from Laderman’s 2.854 ( Laderman 1976 ) to 2.836 . 2. Background Let K be a field and R be a K -algebra, and let \mathbf{A}\in R^{n\times m},\mathbf{B}\in R^{m\times p} . Strassen’s algorithm ( STRASSEN 1969 ) uses a divide and conquer strategy to multiply matrices faster than the standard algorithm. First, it reduces the multiplication of two n\times n matrices to multiplying two 2\times 2 matrices whose entries are \frac{n}{2}\times\frac{n}{2} matrices using block matrix multiplication. Then it computes this 2\times 2 block matrix product using only 7 multiplications of the subblocks by linearly combining them in a clever way. Using this strategy recursively gives an algorithm to multiply n\times n matrices using \operatorname{O}(n^{\log_{2}(7)}) operations in R . The exponent only depends on the number of multiplications, since the cost of the recursive call dominates the cost of the linear combinations. Usually, these algorithms are written using the language of tensors. Definition 1. Let n,m,p\in\mathbb{N} and V_{1}=R^{nm},V_{2}=R^{mp},V_{3}=R^{pn} . Denote by \{a_{ij}:1\leq i\leq n,1\leq j\leq m\} the standard basis of V_{1} , \{b_{jk}:1\leq j\leq m,1\leq k\leq p\} the standard basis of V_{2} and \{c_{ki}:1\leq k\leq p,1\leq i\leq n\} the standard basis of V_{3} . We define the matrix multiplication tensor to be \langle n,m,p\rangle=\sum_{i,j,k=1}^{n,m,p}a_{ij}\otimes b_{jk}\otimes c_{ki}\in V_{1}\otimes V_{2}\otimes V_{3}. This tensor encodes matrix multiplication in the following sense: let A,B,C be matrix spaces over R with dimensions n\times m,m\times p,n\times p respectively and denote by \operatorname{Bil}(A,B;C) the space of all bilinear maps from A\times B to C . Then we can define an isomorphism \Phi\colon V_{1}\otimes V_{2}\otimes V_{3}\to\operatorname{Bil}(A,B;C) by \Phi(a_{i_{2}j_{1}}\otimes b_{j_{2}k_{1}}\otimes c_{k_{2}i_{1}})(\mathbf{A},\mathbf{B})=\mathbf{A}_{i_{2}j_{1}}\mathbf{B}_{j_{2}k_{1}}\varGamma_{i_{1}k_{2}} where \mathbf{A}\in A,\mathbf{B}\in B , \mathbf{A}_{ij},\mathbf{B}_{ij} represent the (i,j) -th entry of \mathbf{A} and \mathbf{B} respectively and \varGamma_{ij}\in C is the matrix with all zeros except for a 1 at the (i,j) -th entry. Note the c_{ij} corresponds to \mathbf{C}_{ji} in the product matrix; this is a standard convention to keep the cyclic nature of matrix multiplication. Definition 2. We call a tensor T\in U_{1}\otimes U_{2}\otimes U_{3} a restriction of T^{\prime}\in U_{1}^{\prime}\otimes U_{2}^{\prime}\otimes U_{3}^{\prime} , denoted by T\leq T^{\prime} , if there are homomorphisms \phi_{1}\colon U_{1}^{\prime}\to U_{1},\phi_{2}\colon U_{2}^{\prime}\to U_{2},\phi_{3}\colon U_{3}^{\prime}\to U_{3} with T=(\phi_{1}\otimes\phi_{2}\otimes\phi_{3})T^{\prime} . If we need to refer to the specific homomorphism \phi=(\phi_{1}\otimes\phi_{2}\otimes\phi_{3}) , we write T\leq_{\phi}T^{\prime} . If there are such isomorphisms \phi_{1},\phi_{2},\phi_{3} , we call T and T^{\prime} isomorphic and write T\cong T^{\prime} . We write the unit tensor of size k as \langle k\rangle=\sum_{i=1}^{k}e_{i}\otimes e_{i}\otimes e_{i}\in R^{k}\otimes R^{k}\otimes R^{k} where \{e_{1},\dots,e_{k}\} is the standard basis for R^{k} . If a tensor T is a restriction of a tensor T^{\prime} this means that any algorithm to compute \Phi(T^{\prime}) can be transformed into one to compute \Phi(T) by applying the linear maps \phi_{1},\phi_{2},\phi_{3} to the inputs and output. In particular, if we have a restriction of the form \langle n,m,p\rangle\leq\langle r\rangle , then we have an algorithm to multiply n\times m and m\times p matrices using r multiplications in R . A restriction of the form T\leq\langle r\rangle gives rise to a decomposition of T into r summands of the form T=\sum_{i=1}^{r}a_{i}\otimes b_{i}\otimes c_{i}. We then call r the rank of this decomposition and a tensor that can be written in the form a\otimes b\otimes c a rank-one tensor. The rank of a tensor T is defined as the smallest integer r such that T has a decomposition of rank r . Together with Strassen’s recursive block matrix multiplication strategy, this gives the following fundamental result. Theorem 3. If \langle n,m,p\rangle\leq\langle r\rangle then there is an algorithm to multiply N\times N matrices in \operatorname{O}(N^{3\log_{nmp}(r)}) operations in R . Using the decomposition Strassen found, we get \langle 2,2,2\rangle\leq\langle 7\rangle and hence \omega\leq\log_{2}(7) . Further analysis allows to compute the leading coefficient of this algorithm as well, as we will see next. While the exponent is given by the rank of a decomposition, i.e. the number of multiplications, the leading coefficient depends on the number of additions and scalar multiplications needed in the restriction. We will denote this number by A(\phi) if the restriction is given by \phi . The homomorphism for a restriction is in general not unique, but in our case every restriction is witnessed by an explicit homomorphism, so we just write A when the homomorphism is clear from the context. Using this definition, Strassen’s original algorithm has A=18 . Using this we can compute the leading coefficient of the algorithm, which is done in general in Theorem 4 . Although this result is well-known, we present its proof in detail since as it establishes the structure for the more complex proof in Section 3 . Theorem 4. For a restriction \langle n,n,n\rangle\leq_{\phi}\langle r\rangle with \omega_{0}=\log_{n}(r)<3 , the algorithm from Theorem 3 takes at most \left(2(n-1)^{3-\omega_{0}}+\frac{r(2^{\omega_{0}}-1)+4A(\phi)}{r-n^{2}}(n-1)^{2-\omega_{0}}\right)N^{\omega_{0}}+\operatorname{O}(N^{2}) operations to multiply N\times N matrices. Proof. We denote by T(N) the total number of operations the algorithm needs to multiply N\times N matrices. For 1\leq N0 , there exists an algorithm to multiply n\times n matrices using \operatorname{O}(n^{\omega_{0}+\epsilon}) operations in R . Our result is related to the following generalization of the ASI, which was first stated by Cohn and Umans ( Cohn and Umans 2003 ) . Corollary 6. If \bigoplus_{i=1}^{k}\langle n_{i},m_{i},p_{i}\rangle\leq\bigoplus_{i=k+1}^{k+q}\langle n_{i},m_{i},p_{i}\rangle, and \omega_{0} is such that \sum_{i=1}^{k}(n_{i}m_{i}p_{i})^{\frac{\omega_{0}}{3}}=\sum_{i=k+1}^{k+q}(n_{i}m_{i}p_{i})^{\frac{\omega_{0}}{3}}, then for every \epsilon>0 , there exists an algorithm to multiply n\times n matrices using \operatorname{O}(n^{\omega_{0}+\epsilon}) operations in R . While the ASI has proved very useful for finding ever tighter bounds on the exponent of matrix multiplication, it has, to our knowledge, never been used for finding fast matrix multiplication algorithms outside the purely asymptotic regime. The theorem is frequently used in the context of approximate algorithms, requiring either an unreasonable level of precision for most applications or an extremely large leading coefficient, as well as very large base cases, rendering them functionally useless in the context of practical algorithms. In this work we do not aim to improve the exponent of matrix multiplication in general, but to find algorithms which could be used in practical computations, while achieving a better complexity. This does not mean that the algorithms presented here are practical in the sense of being faster than currently used algorithms for matrix sizes that appear in practical computations, but at least they could reasonably be implemented and used for matrix sizes that fit into the memory of a large computer. We will use direct sums and Kronecker products of tensors in the following part. The important property is that they are compatible with the notion of restriction, so we have T_{1}\leq T_{1}^{\prime},T_{2}\leq T_{2}^{\prime}\implies T_{1}\oplus T_{2}\leq T_{1}^{\prime}\oplus T_{2}^{\prime},T_{1}\otimes T_{2}\leq T_{1}^{\prime}\otimes T_{2}^{\prime}. Readers less familiar with these concepts can view these operations as follows: The direct sum \oplus corresponds to computing two matrix multiplications independently, while the Kronecker product \otimes corresponds to the inner and outer part of a block matrix multiplication. In particular, we have that \langle n_{1},m_{1},p_{1}\rangle\otimes\langle n_{2},m_{2},p_{2}\rangle\cong\langle n_{1}n_{2},m_{1}m_{2},p_{1}p_{2}\rangle. Since we will frequently encounter direct sums and Kronecker products of matrix multiplication tensors of the same format, we use the notation k\odot\langle n,m,p\rangle=\bigoplus_{i=1}^{k}\langle n,m,p\rangle,\quad\langle n,m,p\rangle^{\otimes k}=\bigotimes_{i=1}^{k}\langle n,m,p\rangle. We will also use the well-known fact that one can permute the dimensions of matrix multiplication tensors. Specifically, we get from (\mathbf{A}\mathbf{B})^{T}=\mathbf{A}^{T}\mathbf{B}^{T} that we transform any algorithm from a restriction of \langle n,m,p\rangle into one for \langle p,m,n\rangle and from the cyclic symmetry of the matrix multiplication tensor it follows that we can transform it to \langle m,p,n\rangle as well. 3. divide less, conquer more While Schönhage’s ASI is an existence result, we present an explicit algorithm with the asymptotic complexity given by the generalized ASI. In contrast to the classical ASI we do not allow a direct sum of matrix multiplication tensors on the left side, but only on the right side. This means that we decompose a matrix multiplication tensor into a sum of smaller matrix multiplications, not just rank-one tensors. This allows to divide a matrix multiplication into larger subblocks, thereby performing more recursive steps (and hence more savings compared to the standard algorithm). The concept of achieving additional savings this way originates from Schönhage’s 1981 paper ( Schönhage 1981 ) , in which it is shown to find improvements to Pan’s use of the ASI ( Pan 1984 ) by taking tensor powers and then applying Strassen’s algorithm. We will illustrate the idea using the decomposition of \langle 6,6,6\rangle found by Moosbauer and Poole ( Moosbauer and Poole 2025 ) . They show that \langle 6,6,6\rangle can be decomposed into a sum of 153 rank-one tensors, analyzing the structure of this decomposition, we can find the restriction \langle 6,6,6\rangle\leq 137\odot\langle 1\rangle\oplus 8\odot\langle 1,1,2\rangle . Applying a cyclic permuation \sigma to this restriction gives \langle 6,6,6\rangle\leq 137\odot\langle 1\rangle\oplus 8\odot\langle 2,1,1\rangle , and \langle 6,6,6\rangle\leq 137\odot\langle 1\rangle\oplus 8\odot\langle 1,2,1\rangle . If we then consider the Kronecker product of these three restrictions we get \displaystyle\langle 6,6,6\rangle^{\otimes 3} \displaystyle\leq 137^{3}\odot\langle 1\rangle\oplus 8\cdot 137^{2}\odot(\langle 1,1,2\rangle\oplus\langle 2,1,1\rangle\oplus\langle 1,2,1\rangle) \displaystyle\kern-1.0pt\oplus 8^{2}\cdot 137\odot(\langle 1,2,2\rangle\oplus\langle 2,1,2\rangle\oplus\langle 2,2,1\rangle)\oplus 8^{3}\odot\langle 2,2,2\rangle. While we have to compute \langle 1,1,2\rangle,\langle 1,2,2\rangle and their cyclic permutations by the standard algorithm, using 2 and 4 multiplications respectively, we can compute \langle 2,2,2\rangle using Strassen’s algorithm with 7 multiplications. In the language of tensor restrictions we use \langle 1,1,2\rangle\leq\langle 2\rangle , \langle 1,2,2\rangle\leq\langle 4\rangle and \langle 2,2,2\rangle\leq\langle 7\rangle , to conclude that \langle 216,216,216\rangle\leq\langle 3581065\rangle . Applying Theorem 3 to this restriction gives an algorithm with exponent \omega_{0}=2.80751 , which is only slightly smaller than the original exponent 2.80754 . We can do even better by taking higher tensor powers. But this is not all. The key observation is that instead of using Strassen’s decomposition to save additional multiplications, we can use any fast matrix multiplication algorithm for this recursive calls, in particular we can use the same strategy recursively. In this example we would get an algorithm with exponent \omega_{0}=2.80496 . We will show that we can use this process in a recursive matrix multiplication algorithm that is very similar to the standard Strassen-like algorithms obtained from tensor decompositions that has the complexity as given by the generalized ASI while retaining a reasonable leading coefficient. In Algorithm 1 we write \mathcal{L}_{1}^{(i,j)},\mathcal{L}_{2}^{(i,j)},\mathcal{L}_{3}^{(k,l)} for the functions that compute the linear combinations of subblocks as given by the tensor restriction. Unlike in Strassen’s algorithm, some of these block matrices are recombined into larger matrices of size n_{i}\times m_{i} and m_{i}\times p_{i} respectively. Algorithm 1 Matrix Mult for a given restriction \langle n,m,p\rangle\leq\bigoplus_{i=0}^{q-1}s_{i}\odot\langle n_{i},m_{i},p_{i}\rangle 1: An N\times M matrix \mathbf{A} and an M\times P matrix \mathbf{B} , a treshold N_{0} . 2: The matrix product \mathbf{C}=\mathbf{A}\mathbf{B} 3: function MatrixMults ( \mathbf{A},\mathbf{B},N,M,P ) 4: if \min(N,M,P)\leq N_{0} then 5: return \mathbf{A}\mathbf{B} computed through standard algorithm 6: end if 7: if n\nmid N\lor m\nmid M\lor p\nmid P then 8: N\leftarrow\lceil N/n\rceil n 9: M\leftarrow\lceil M/m\rceil m 10: P\leftarrow\lceil P/p\rceil p 11: pad \mathbf{A} and \mathbf{B} with zeros to dimensions N\times M and M\times P 12: end if 13: for i\leftarrow 0 to q-1 do 14: for j\leftarrow 0 to s_{i}-1 do 15: X\leftarrow\mathcal{L}_{1}^{(i,j)}(\mathbf{A}) 16: Y\leftarrow\mathcal{L}_{2}^{(i,j)}(\mathbf{B}) 17: Z_{i,j}\leftarrow\textsc{MatrixMult}(X,Y,Nn_{i}/n,Nm_{i}/m,Pp_{i}/p) 18: end for 19: end for 20: for k\leftarrow 0 to N/n-1 do 21: for l\leftarrow 0 to P/p-1 do 22: \mathbf{C}_{k,l}\leftarrow\mathcal{L}_{3}^{(k,l)}(\mathbf{Z}) 23: end for 24: end for 25: return \mathbf{C} 26: end function Algorithm 1 correctly computes the matrix product \mathbf{C} , since it computes all the same matrix products as the standard Strassen-like algorithm obtained from the tensor decomposition. However, our algorithm computes some of them simultaneously as a larger matrix. If in Algorithm 1 some of the recursive calls are rectangular matrix multiplications (as will be the case in all our results), then for some recursive paths the number of recursions is limited to \min(\log_{\frac{n_{i}}{n}}(N),\log_{\frac{m_{i}}{m}}(M),\log_{\frac{p_{i}}{p}}(P)) , before we encounter a subproblem of shape \langle N^{\prime},M^{\prime},1\rangle , or a permutation thereof, which forces us to switch to the standard algorithm. However, we do not need to use the same restriction in each recursive call. Similar to the example discussed above we can alternate between three cyclic permutations of a restriction, to ensure that most recursive paths can continue for longer. 4. Complexity Analysis We will now analyze the complexity of Algorithm 1 , showing that it achieves the complexity promised by the generalized ASI. We start by analyzing the idealized case where all recursive calls are square matrix multiplications. Theorem 1. If N=M=P , n=m=p and n_{i}=m_{i}=p_{i} for all 0\leq ic=\frac{(2^{\omega_{0}}-1)n}{\sum_{i=0}^{q-1}s_{i}\left(\frac{n_{i}}{n}\right)^{\omega_{0}-1}-1} and we choose N_{0}=nn^{\prime}-1 . Then we have that T(N)=2N^{3}-N^{2} for all 1\leq Nc , we can ensure that the denominator is positive, so L is always well defined. We will prove by induction on N that (1) T(N)\leq LN^{\omega_{0}}-LcN^{\omega_{0}-1}-dN^{2} for all N\geq n^{\prime} . For the base case we have that T(N)=2N^{3}-N^{2}\leq LN^{\omega_{0}}-LcN^{\omega_{0}-1}-dN^{2} for all n^{\prime}\leq N