Geodesic
Non-existence of a short algorithm for multiplication of $3\times3$ matrices with group $S_4\times S_3$
Trudy Instituta matematiki, Tome 30 (2022) no. 1, pp. 99-116.

Voir la notice de l'article provenant de la source Math-Net.Ru

One of prospective ways to find new fast algorithms of matrix multiplication is to study algorithms admitting nontrivial symmetries. In the work possible algorithms for multiplication of $3\times3$ matrices, admitting a certain group $G$ isomorphic to $S_4\times S_3$, are investigated. It is shown that there exist no such algorithms of length $\leq23$. In the first part of the work, which is the content of the present article, we describe all orbits of length $\leq23$ of $G$ on the set of decomposable tensors in the space $M\otimes M\otimes M$, where $M=M_3({\mathbb C})$ is the space of complex $3\times3$ matrices. In the second part of the work this description will be used to prove that a short algorithm with the above-mentioned group does not exist. 
@article{TIMB_2022_30_1_a9,
     author = {V. P. Burichenko},
     title = {Non-existence of a short algorithm for multiplication of $3\times3$ matrices with group $S_4\times S_3$},
     journal = {Trudy Instituta matematiki},
     pages = {99--116},
     publisher = {mathdoc},
     volume = {30},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a9/}
}
TY  - JOUR
AU  - V. P. Burichenko
TI  - Non-existence of a short algorithm for multiplication of $3\times3$ matrices with group $S_4\times S_3$
JO  - Trudy Instituta matematiki
PY  - 2022
SP  - 99
EP  - 116
VL  - 30
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a9/
LA  - en
ID  - TIMB_2022_30_1_a9
ER  - 
%0 Journal Article
%A V. P. Burichenko
%T Non-existence of a short algorithm for multiplication of $3\times3$ matrices with group $S_4\times S_3$
%J Trudy Instituta matematiki
%D 2022
%P 99-116
%V 30
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a9/
%G en
%F TIMB_2022_30_1_a9
V. P. Burichenko. Non-existence of a short algorithm for multiplication of $3\times3$ matrices with group $S_4\times S_3$. Trudy Instituta matematiki, Tome 30 (2022) no. 1, pp. 99-116. http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a9/

[1] Aho A. V., Hopcroft J. E., Ullman J. D., The Design and Analisys of Computer Algorithms, Addison-Wesley, 1974 | MR

[2] Bürgisser P., Clausen M., Shokrollahi M. A., Algebraic Complexity Theory, Springer, 1997 | MR | Zbl

[3] Burichenko V. P., On symmetries of the Strassen algorithm, 2014, arXiv: 1408.6273 | Zbl

[4] Burichenko V. P., Symmetries of matrix multiplication algorithms. I, 2015, arXiv: 1508.01110 | Zbl

[5] Chiantini L., Ikenmeyer C., Landsberg J. M., Ottaviani G., “The geometry of rank decompositions of matrix multiplication I: $2\times2$ matrices”, Experimental Mathematics, 28:3 (2019), 322–327 | DOI | MR | Zbl

[6] Burichenko V. P., “The isotropy group of the matrix multiplication tensor”, Trudy Instituta matematiki (= Proceedings of the Institute of Mathematics), 24:2 (2016), 106–118 | MR

[7] Grochow J.A., Moore C., Matrix multiplication algorithms from group orbits, 2016, arXiv: 1612.01527v1

[8] Ballard G., Ikenmeyer C., Landsberg J. M., Ryder N., “The geometry of rank decompositions of matrix multiplication II: $3\times3$ matrices”, J. Pure Appl. Algebra, 223:8 (2018), 3205–3224 | DOI | MR

[9] Chokaev B. V., Shumkin G. N., “Dva bilineinykh algoritma umnozheniya matrits $3\times3$ slozhnosti $25$”, Vestn. Mosk. univ. Ser.15. Vychisl. matem. i kibern., 2018, no. 1, 23–31 | MR | Zbl

[10] Chokaev B. V., Shumkin G. N., “Two bilinear $(3\times3)$-matrix multiplication algorithms of complexity $25$”, Moscow University Computational Mathematics and Cybernetics, 42 (2018), 23–30 (translation of [9]) | DOI | MR | Zbl

[11] Bläser M., “On the complexity of the multiplication of matrices of small formats”, J. Complexity, 19 (2003), 43–60 | DOI | MR | Zbl

[12] Hall M., The Theory of Groups, Macmillan, 1959 | MR | Zbl