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
2004948173 2053839977 1986272312
A method for deriving bilinear algorithms for matrix multiplication is proposed. New estimates for the bilinear complexity of a number of problems of the exact and approximate multiplication of rectangular matrices are obtained. In particular, the estimate for the boundary rank of multiplying 3 × 3 matrices is improved and a practical algorithm for the exact multiplication of square n × n matrices is proposed. The asymptotic arithmetic complexity of this algorithm is O(n2.7743). The paper considers the complexity of bilinear forms in a noncommutative ring. The dual of a computation is defined and applied to matrix multiplication and other bilinear forms. It is shown that the dual of an optimal computation gives an optimal computation for a dual problem. An @math by @math matrix product is shown to be the dual of an @math by @math or an @math by @math matrix product, implying that each of the matrix products requires the same number of multiplications to compute. Finally, an algorithm for computing a single bilinear form over a noncommutative ring with a minimum number of multiplications is derived by considering a dual problem. 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.