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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2022},
     volume = {30},
     number = {1},
     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
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
%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