Two Bilinear (3 × 3)-Matrix Multiplication Algorithms of Complexity 25

Аннотация

As is known, a bilinear algorithm for multiplying 3 × 3 matrices can be constructed by using ordered triples of 3 × 3 matrices A_ρ, B_ρ, C_ρ, \(\rho = \overline {1,r} ,\) where r is the complexity of the algorithm. Algorithms with various symmetries are being extensively studied. This paper presents two algorithms of complexity 25 possessing the following two properties (symmetries): (1) the matricesA₁,B₁, and C1 are identity, (2) if the algorithm involves a tripleA, B, C, then it also involves the triples B, C, A and C, A, B. For example, these properties are inherent in the well-known Strassen algorithm for multiplying 2 × 2 matrices. Many existing (3 × 3)-matrix multiplication algorithms have property (2). Methods for finding new algorithms are proposed. It is shown that the found algorithms are different and new.