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
2539150916 1990568697 2006785052 2043670592
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. Strassen's matrix multiplication (MM) has benefits with respect to any (highly tuned) implementations of MM because Strassen's reduces the total number of operations. Strassen achieved this operation reduction by replacing computationally expensive MMs with matrix additions (MAs). For architectures with simple memory hierarchies, having fewer operations directly translates into an efficient utilization of the CPU and, thus, faster execution. However, for modern architectures with complex memory hierarchies, the operations introduced by the MAs have a limited in-cache data reuse and thus poor memory-hierarchy utilization, thereby overshadowing the (improved) CPU utilization, and making Strassen's algorithm (largely) useless on its own. In this paper, we investigate the interaction between Strassen's effective performance and the memory-hierarchy organization. We show how to exploit Strassen's full potential across different architectures. We present an easy-to-use adaptive algorithm that combines a novel implementation of Strassen's idea with the MM from automatically tuned linear algebra software (ATLAS) or GotoBLAS. An additional advantage of our algorithm is that it applies to any size and shape matrices and works equally well with row or column major layout. Our implementation consists of introducing a final step in the ATLAS GotoBLAS-installation process that estimates whether or not we can achieve any additional speedup using our Strassen's adaptation algorithm. Then we install our codes, validate our estimates, and determine the specific performance. We show that, by the right combination of Strassen's with ATLAS GotoBLAS, our approach achieves up to 30 22 speed-up versus ATLAS GotoBLAS alone on modern high-performance single processors. We consider and present the complexity and the numerical analysis of our algorithm, and, finally, we show performance for 17 (uniprocessor) systems. 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. Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O(m0.7n1.2+n2+o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over R. The naive matrix multiplication algorithm, on the other hand, may need to perform o(mn) operations to accomplish the same task. For m≤n1.14, the new algorithm performs an almost optimal number of only n2+o(1) operations. For m≤n1.68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n2.38) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.