1.2.3 Matrix Multiplication

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: An x x y matrix A, and an y x z matrix B.

Problem: The x x z matrix A x B.

Excerpt from The Algorithm Design Manual: Although matrix multiplication is an important problem in linear algebra, its main significance for combinatorial algorithms is its equivalence to a variety of other problems, such as transitive closure and reduction, solving linear systems, and matrix inversion. Thus a faster algorithm for matrix multiplication implies faster algorithms for all of these problems. Matrix multiplication arises in its own right in computing the results of such coordinate transformations as scaling, rotation, and translation for robotics and computer graphics.

Asymptotically faster algorithms for matrix multiplication exist, based on clever divide-and-conquer recurrences. However, these prove difficult to program and require very large matrices to beat the trivial algorithm.

The best books available for this problem are Matrix Computations by Gene H. Golub and Charles F. Van Loan, and Numerical Recipes in C , Fortran 77 , Fortran 90 , or Pascal , by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Programs from these books in C and Fortran are also available.


Implementations

  • () (rating 7)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 6)
  • Mathematica -- Assorted Routines (Mathematica) (rating 6)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 4)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 2)

    Related Problems

  • Solving Linear Equations
  • Shortest Path


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .