Fast commutative matrix algorithms. (January 2023)

• Record Type: Journal Article
• Authors: Rosowski, Andreas
• Is Part Of: Journal of symbolic computation. Volume 114(2023)
• Page Start: 302
• Page End: 321
• Publication Date: 2023-01
• Subjects: Commutative -- Matrix multiplication -- Weakly bilinear; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.05.002
• Languages: English
• ISSNs: 0747-7171

Abstract

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) .