The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Fast Matrix Multiplication Algorithms

Fast algorithms for matrix multiplication --- i.e., algorithms that compute less than O(N^3) operations--- are becoming attractive for two simple reasons:

1. Todays software libraries are reaching the core peak performance (i.e., 90% of peak performance) and thus reaching the limitats of current systems. Fast algorithms deploy new algorithmic strategies, new opportunities, thus reaching new performance and, in practice, stretching the system capabilities. 2. Fast algorithms reduce the number of operations and thus data movements. This means that for very large problems they (may) reduce off-chip communication (dominant factor in multicore systems).

  • Offical Site

    Problem Links

    Matrix Multiplication (10)

    This page last modified on 2008-07-10 .