Implementation of Strassen's algorithm for matrix multiplication

ABSTRACT

In this paper we report on the development of an efficient and portable implementation of Strassen's matrix multiplication algorithm for matrices of arbitrary size. Our technique for defining the criterion which stops the recursions is more detailed than those generally used, thus allowing enhanced performance for a larger set of input sizes. In addition, we deal with odd matrix dimensions using a method whose usefulness had previously been in question and had not so far been demonstrated. Our memory requirements have also been reduced, in certain cases by 40 to more than 70 percent over other similar implementations. We measure performance of our code on the IBM RS/6000, CRAY YMP C90, and CRAY T3D single processor, and offer comparisons to other codes. Finally, we demonstrate the usefulness of our implementation by using it to perform the matrix multiplications in a large application code.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: David H. Bailey, Extra high speed matrix multiplication on the Cray-2, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.603-607, May 1988 [doi>10.1137/0909040]
• 3: David H. Bailey , King Lee , Horst D. Simon, Using Strassen's algorithm to accelerate the solution of linear systems, The Journal of Supercomputing, v.4 n.4, p.357-371, 1990 [doi>10.1007/BF00129836]
• 4: Richard P. Brent, Algorithms for matrix multiplication, Stanford University, Stanford, CA, 1970
• 5: J. Cohen and M. Roth. On the implementation of Strassen's fast multiplication algorithm. Acta Informatica, 6:341-355, 1976.
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 8: Craig C. Douglas , Michael Heroux , Gordon Slishman , Roger M. Smith, GEMMW: a portable level 3 BLAS Winograd variant of Strassen's matrix-matrix multiply algorithm, Journal of Computational Physics, v.110 n.1, p.1-10, Jan. 1994 [doi>10.1006/jcph.1994.1001]
• 9: Patrick C. Fischer, Further Schemes for Combining Matrix Algorithms, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.428-436, July 29-August 02, 1974
• 10: Patrick C. Fischer , Robert L. Probert, Efficient Procedures for Using Matrix Algorithms, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.413-427, July 29-August 02, 1974
• 11: Nicholas J. Higham, Exploiting fast matrix multiplication within the level 3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.352-368, Dec. 1990 [doi>10.1145/98267.98290]
• 12: James W. Demmel , Nicholas J. Higham, Stability of block algorithms with fast level-3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.18 n.3, p.274-291, Sept. 1992 [doi>10.1145/131766.131769]
• 13: J. E. Hopcroft and L. R. Kerr. Some techniques for proving certain simple programs optimal. In Proceedings, Tenth Annual Symposium on Switching and Automata Theory, pages 36-45, 1969.
• 14: S. Huss-Lederman, E. M. Jacobson, J. R. Johnson, A. Tsao, and T. Turnbull. Strassen's algorithm for matrix multiplication: Modeling, analysis, and implementation. Technical report, Center for Computing Sciences, 1996. Technical Report CCS-TR-96-147.
• 15: Steven Huss-Lederman , Anna Tsao , Thomas Turnbull, A Parallelizable Eigensolver for Real Diagonalizable Matrices with Real Eigenvalues, SIAM Journal on Scientific Computing, v.18 n.3, p.869-885, May 1997 [doi>10.1137/S1064827592228833]
• 16: IBM Engineering and Scientific Subroutine Library Guide and Reference, 1992. Order No. SC23-0526.
• 17: P. A. Knight. Fast rectangular matrix multiplication and QR decomposition. Linear Algebra Appl., 221:69-81, 1995.
• 18: R. L. Probert. On the additive complexity of matrix multiplication. SIAM Journal of Computing, 5(6):187-203, 1976.
• 19: V. Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354-356, 1969.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
matrix multiplication, Strassen's algorithm, Winograd variant, Level 3 BLAS