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.
In this section we present some related work. We start with presenting some results about multiplication of two square matrices. Note that a matrix multiplication algorithm can only be applied recursively if commutativity is not used. Since Strassen showed in 1969 that the product of two matrices can be computed using @math arithmetic operations @cite_10 and since it is shown that for @math matrices @math is the optimal number of multiplications @cite_13 @cite_6 , it is interesting to study @math matrices for @math , to obtain an even faster algorithm for matrix multiplication. For @math matrices @math multiplications would be needed to obtain an even faster algorithm than Strassen's since @math . In 1976 Laderman obtained a non-commutative @math algorithm using only @math multiplications @cite_7 . It is not known if there exists a non-commutative @math algorithm that uses @math or less multiplications. For @math matrices the best non-commutative result so far is @math multiplications by Sedoglavic @cite_15 which is an improvement on Makarov's algorithm for @math matrices @cite_18 .
@cite_18 @cite_7 @cite_10 @cite_6 @cite_15 @cite_13
2006785052 2035476608 2738523341 2539150916
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. 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 We present a non-commutative algorithm for multiplying 5 × 5 matrices using 99 multiplications. This algorithm is a minor modification of Makarov [4] algorithm. 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.