We show that the product of an nx3 matrix and a 3x3 matrix over a commutative ring can be computed using 6n+3 multiplications. For two 3x3 matrices this gives us an algorithm using 21 multiplications. This is an improvement with respect to Makarov algorithm using 22 multiplications[10]. We generalize our result for nx3 and 3x3 matrices and present an algorithm for computing the product of an lxn matrix and an nxm matrix over a commutative ring for odd n using n(lm+l+m-1) 2 multiplications if m is odd and using (n(lm+l+m-1)+l-1) 2 multiplications if m is even. Waksman algorithm for odd n needs (n-1)(lm+l+m-1) 2+lm multiplications[16], thus in both cases less multiplications are required by our algorithm.
We present some examples of non-square matrix multiplication algorithms. In @cite_1 Hopcroft and Kerr showed that the product of a @math matrix and a @math matrix can be multiplied using @math multiplications without using commutativity. In the case @math this gives an algorithm using @math multiplications. Combined with the results of @cite_16 this gives an algorithm for @math matrices using @math multiplications and an exponent of @math . Smirnov obtained an algorithm for the product of a @math matrix and a @math matrix using @math multiplications @cite_0 . By @cite_16 this gives an algorithm for @math matrices using @math multiplications and an exponent of @math .
@cite_0 @cite_16 @cite_1
2006785052 2539150916 1986272312 2035476608
Abstract A non-commutative algorithm is proposed for multiplying square 5 × 5 matrices that uses one hundred multiplications. Its application to 7 × 7, 10 × 10 and 15 × 15 matrices allows algorithms to be constructed that require 273, 700 and 2300 multiplications respectively. This paper develops techniques for establishing a lower bound on the number of arithmetic operations necessary for sets of simple expressions. The techniques are applied to matrix multiplication. A modification of Strassen's algorithm is developed for multiplying n × p matrices by p × q matrices. The techniques are used to prove that this algorithm minimizes the number of multiplications for a few special cases. In so doing we establish that matrix multiplication with elements from a commutative ring requires fewer multiplications than with elements from a non-commutative ring. This paper develops an algorithm to multiply a px2 matrix by a 2xn matrix in @math multiplications for matrix multiplication without commutativity. The algorithm minimizes the number of multiplications for matrix multiplication without commutativity for the special cases p=1 or 2, n=1,2, @math and p = 3, n = 3. It is shown that with commutativity fewer multiplications are required. t. Below we will give an algorithm which computes the coefficients of the product of two square matrices A and B of order n from the coefficients of A and B with tess than 4 . 7 n l°g7 arithmetical operations (all logarithms in this paper are for base 2, thus tog 7 2.8; the usual method requires approximately 2n 3 arithmetical operations). The algorithm induces algorithms for invert ing a matr ix of order n, solving a system of n linear equations in n unknowns, comput ing a determinant of order n etc. all requiring less than const n l°g 7 arithmetical operations. This fact should be compared with the result of KLYUYEV and KOKOVKINSHCHERBAK [1 ] tha t Gaussian elimination for solving a system of l inearequations is optimal if one restricts oneself to operations upon rows and columns as a whole. We also note tha t WlNOGRAD [21 modifies the usual algorithms for matr ix multiplication and inversion and for solving systems of linear equations, trading roughly half of the multiplications for additions and subtractions. I t is a pleasure to thank D. BRILLINGER for inspiring discussions about the present subject and ST. COOK and B. PARLETT for encouraging me to write this paper. 2. We define algorithms e , which mult iply matrices of order m2 , by induction on k: , 0 is the usual algorithm, for matr ix multiplication (requiring m a multiplications and m 2 ( m t) additions), e ,k already being known, define , +t as follows: If A, B are matrices of order m 2 k to be multiplied, write