Arithmetic of finite fields: 4th International Workshop, Proceedings, pp.168-186, 2012. ,

Finding optimal formulae for bilinear maps, AriC Seminar, 2012. ,

DOI : 10.1007/978-3-642-31662-3_12

URL : https://hal.archives-ouvertes.fr/hal-00640165

General tensor decomposition, moment matrices and applications, International Symposium on Symbolic and Algebraic Computation, vol.52, pp.51-71, 2013. ,

DOI : 10.1016/j.jsc.2012.05.012

URL : https://hal.archives-ouvertes.fr/inria-00590965

On the complexity of the multiplication of matrices of small formats, Journal of Complexity, vol.19, issue.1, pp.7-9, 2003. ,

The Magma algebra system. I. The user language, Computational algebra and number theory, vol.24, pp.235-265, 1993. ,

On the optimal evaluation of a set of bilinear forms, Linear Algebra and its Applications, vol.19, issue.3, pp.207-235, 1978. ,

Algebraic Complexity Theory, 2010. ,

Algebraic complexities and algebraic curves over finite fields, Journal of Complexity, vol.4, issue.4, pp.285-316, 1988. ,

DOI : 10.1016/0885-064x(88)90012-x

URL : https://doi.org/10.1016/0885-064x(88)90012-x

Computational algebraic complexity editorial matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, vol.9, issue.3, pp.80013-80015, 1990. ,

DOI : 10.1016/s0747-7171(08)80013-2

URL : https://doi.org/10.1016/s0747-7171(08)80013-2

Lectures on the Complexity of Bilinear Problems, 1987. ,

Even faster integer multiplication, ArXiv, 2014. ,

DOI : 10.1016/j.jco.2016.03.001

URL : https://hal.archives-ouvertes.fr/hal-01022749

Discrete mathematics and its applications, 2005. ,

On minimizing the number of multiplications necessary for matrix multiplication, SIAM Journal on Applied Mathematics, vol.20, issue.1, pp.30-36, 1971. ,

Tensor rank is NP-complete, Journal of Algorithms, vol.11, issue.4, pp.90014-90020, 1990. ,

Optimal evaluation of pairs of bilinear forms, SIAM Journal on Computing, vol.8, issue.3, pp.443-462, 1979. ,

Multiplication of multidigit numbers on automata, Soviet Physics-Doklady, vol.7, pp.595-596, 1963. ,

A noncommutative algorithm for multiplying 3 × 3 matrices using 23 multiplications, Bull. Amer. Math. Soc, vol.82, issue.1, pp.126-128, 1976. ,

DOI : 10.1090/s0002-9904-1976-13988-2

URL : https://www.ams.org/bull/1976-82-01/S0002-9904-1976-13988-2/S0002-9904-1976-13988-2.pdf

Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pp.296-303, 2014. ,

Five, six, and seven-term Karatsuba-like formulae, IEEE Transactions on Computers, vol.54, issue.3, pp.362-369, 2005. ,

DOI : 10.1109/tc.2005.49

URL : http://www.csd.uwo.ca/%7Eeschost/Exam/Montgomery--Five_six_and_seven_terms_Karatsuba-like_formulae.pdf

Optimal Karatsuba-like formulae for certain bilinear forms in GF(2), Linear Algebra and its Applications, vol.429, issue.8-9, pp.2052-2066, 2008. ,

DOI : 10.1016/j.laa.2008.06.004

URL : https://doi.org/10.1016/j.laa.2008.06.004

Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, SFCS '78, pp.166-176, 1978. ,

Finding optimal Chudnovsky-Chudnovsky multiplication algorithms, pp.45-60, 2014. ,

Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method, Journal of Complexity, vol.28, issue.4, pp.489-517, 2012. ,

, Schnelle Multiplikation großer Zahlen. Computing, vol.7, issue.34, pp.281-292, 1971.

The bilinear complexity and practical algorithms for matrix multiplication, Computational Mathematics and Mathematical Physics, vol.53, issue.12, pp.1781-1795, 2013. ,

Gaussian elimination is not optimal, Numerische Mathematik, vol.13, issue.4, pp.354-356, 1969. ,

The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Mathematics Doklady, vol.3, pp.714-716, 1963. ,

, N of a polynomial R such that R(0) = 0, from which we deduce that M 3 = ((R(N ) ?1 ) T , R(N )) and M 3 ? Stab(T )

, Given the form of the elements of Stab(I ? ) ? Stab(N ), its cardinality is equal to the number of polynomials R of degree at most ? ? 1 such that R(0) = 0

Stabilizer of the matrix product We denote by T p,q,r the vector space given by the product of matrices p × q by q × r, which is isomorphic to M p,r ? I q (we do not use the canonical basis for this representation), For the group action M · ,

, Theorem 17. For the group action M · (X, Y ) ? X T M Y , the subgroup stabilizing the vector space T p,q,r can be described as the group given by the pairs

q ? 1}, we denote by M i,j the matrix X T · (e i,j ) · Y , where e i,j is the canonical basis of M p,r. Denoting by X i,h the q × q blocks of X and Y ?,j the q × q blocks of Y , we have M i,j = (X i,h Y j,? ) h,? for any i and j. Consequently, since X T · (e i,j ) · Y ? T p,q,r , we have ?i ,

, Let (i, h) such that X i,h is not null and j any integer in {0,. .. , q ? 1}. We have the inclusion X i

, Thus, for any (i, h) such that X i,h is not null, we have shown that X i,h is invertible. We have the same property for the blocks of Y. Combining the fact that the blocks of X and Y that are not null are invertible and Equation (A.1), we can conclude that the stabilizer of T p,q,r is generated by matrices, Y is invertible, we even have the equality

Using the Hamming weight for the matrix product We describe in this section a trick allowing one to speed-up the execution of our approach for the matrix product. However, this part is technical and can be skipped on a first read ,

,

, We define the following sets