Symmetries of matrix multiplication algorithms. I

arXiv1508.01110MaRDI QIDQ6264243FDOQ6264243

Authors: Vladimir P. Burichenko 

Publication date: 5 August 2015

Abstract: In this work the algorithms of fast multiplication of matrices are considered. To any algorithm there associated a certain group of automorphisms. These automorphism groups are found for some well-known algorithms, including algorithms of Hopcroft, Laderman, and Pan. The automorphism group is isomorphic to $S_{3}imes{Z}_2$ and $S_4$ for Hopcroft anf Laderman algorithms, respectively. The studying of symmetry of algorithms may be a fruitful idea for finding fast algorithms, by an analogy with well-known optimization problems for codes, lattices, and graphs. {em Keywords}: Strassen algorithm, symmetry, fast matrix multiplication.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Representation theory of groups (20Cxx)

This page was built for publication: Symmetries of matrix multiplication algorithms. I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6264243)