Exploiting fast matrix multiplication within the level 3 BLAS

ABSTRACT

The Level 3 BLAS (BLAS3) are a set of specifications of FORTRAN 77 subprograms for carrying out matrix multiplications and the solution of triangular systems with multiple right-hand sides. They are intended to provide efficient and portable building blocks for linear algebra algorithms on high-performance computers. We describe algorithms for the BLAS3 operations that are asymptotically faster than the conventional ones. These algorithms are based on Strassen's method for fast matrix multiplication, which is now recognized to be a practically useful technique once matrix dimensions exceed about 100. We pay particular attention to the numerical stability of these “fast BLAS3.” Error bounds are given and their significance is explained and illustrated with the aid of numerical experiments. Our conclusion is that the fast BLAS3, although not as strongly stable as conventional implementations, are stable enough to merit careful consideration in many applications.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 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: BINI, D., AND LOTTI, D. Stability of fast algorithms for matrix multiplication. Numer. Math. 36 (1980), 63-72.
• 4: Gilles Brassard , Paul Bratley, Algorithmics: theory & practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 5: Richard P. Brent, Algorithms for matrix multiplication, Stanford University, Stanford, CA, 1970
• 6: BRENT, R.P. Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity. Numer. Math. 16 (1970), 145-156.
• 7: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 8: DAYD~, M0' J', AND DUFF, I.S. Use of level 3 BLAS in LU factorization on the Cray-2, the ETA-10P, and the IBM 3090-200/VF. Tech. Rep. CSS 229, Computer Science and Systems Div., Harwell Lab., 1988.
• 9: DEMMEL, J. W., DONGARRA, J. J., Du CROZ, J. J., GREENBAUM, A., HAMMARLING, S. J., AND SORENSEN, D. C. Prospectus for the development of a linear algebra library for highperformance computers. Tech. Memor. 97. Mathematics and Computer Science Div., Argonne National Lab., Argonne, Ill., 1987.
• 10: 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]
• 11: J. J. Dongarra , Jermey Du Cruz , Sven Hammerling , I. S. Duff, Algorithm 679; a set of level 3 basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.18-28, March 1990 [doi>10.1145/77626.77627]
• 12: Kyle Gallivam , William Jalby , Ulrike Meier, The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1079-1084, November 1, 1987 [doi>10.1137/0908086]
• 13: GALLIVAN, K., JALBY, W., MEIER, U., AND SAMEH, A. I-I. Impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomput. Appl. 2 (1988), 12-48.
• 14: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 15: Daniel P. Heyman, Further comparisons of direct methods for computing stationary distributions of Markov chains, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.226-232, April 1, 1987 [doi>10.1137/0608020]
• 16: N. J. Higham, The accuracy of solutions to triangular systems, SIAM Journal on Numerical Analysis, v.26 n.5, p.1252-1265, Oct. 1989 [doi>10.1137/0726070]
• 17: Nicholas J. Higham , Robert S. Schreiber, Fast polar decomposition of an arbitrary matrix, SIAM Journal on Scientific and Statistical Computing, v.11 n.4, p.648-655, July 1990 [doi>10.1137/0911038]
• 18: IBM. Engineering and Scientific Subroutine Library, Guide and Reference, Release 3. 4th ed., Program 5668-863, 1988.
• 19: MILLER, W. Computational complexity and numerical stability. SIAM J. Comput. 4 (1975), 97-107.
• 20: MOLER, C. B., LITTLE, J. N., AND BANGERT, S. Pro-Matlab User's Guide. The MathWorks, Inc., South Natick, Mass., 1987.
• 21: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 22: SCHREIBER, R.S. Block algorithms for parallel machines. In Numerical Algorithms for Modern Parallel Computer Architectures, M. H. Schultz, Ed., IMA Volumes In Mathematics and Its Applications 13, Springer-Verlag, Berlin, 1988, 197-207.
• 23: R. Sedgewick, Algorithms (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 24: STRASSEN, V. Gaussian elimination is not optimal. Numer. Math. I3 (1969), 354-356.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

General Terms:
Algorithms