Fast commutative matrix algorithms. (January 2023) - Rosowski, Andreas
Abstract: We show that the product of an n × 3 matrix and a 3 × 3 matrix over a commutative ring can be computed using 6 n + 3 multiplications. For two 3 × 3 matrices this gives us an algorithm using 21 multiplications. This is an improvement with respect to Makarov's algorithm using 22 multiplications (Makarov, 1986 ). We generalize our result for n × 3 and 3 × 3 matrices and present an algorithm for computing the product of an l × n matrix and an n × m matrix over a commutative ring for odd n using n ( l m + l + m − 1 ) / 2 multiplications if m is odd and using ( n ( l m + l + m − 1 ) + l − 1 ) / 2 multiplications if m is even. Waksman's algorithm (Waksman, 1970 ) and its generalization to rectangular matrices by Islam (2009) for odd n needs ( n − 1 ) ( n 2 + 2 n − 1 ) / 2 + n 2 multiplications and ( n − 1 ) ( l m + l + m − 1 ) / 2 + l m multiplications respectively, thus for even and odd m less multiplications are required by our algorithm. We also give an algorithm for even n using n ( l m + l + m − 1 ) / 2 multiplications without making use of divisions. Although Waksman's algorithm (Waksman, 1970 ) and its generalization to rectangular matrices by Islam (2009) use the same number of multiplications our algorithm is an improvement over these algorithms since they make use of some divisions by 2 and we are able to avoid them. Furthermore we present a novelty for matrix multiplication: In this paper we show that some algorithms with special properties that we refer to as weakly bilinear can be used as recursive algorithms. In comparison to bilinear algorithms for small n × n matrices say n < 20 we obtain some better results. From these weakly bilinear algorithms we finally obtain approximate weakly bilinear algorithms. For instance we obtain an approximate weakly bilinear algorithm for 5 × 5 matrices that uses only 87 multiplications. If at all it is possible to compare this algorithm with a bilinear algorithm we obtain a better result with respect to the algorithm in Sedoglavic and Smirnov (2021) .