Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication

TitleCommunication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
Publication TypeConference Paper
Year of Publication2012
AuthorsBallard, G., Demmel J., Holtz O., Lipshitz B., & Schwartz O.
Conference Name24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012)
Conference LocationPittsburgh, PA

Parallel matrix multiplication is one of the most studied fundamental
problems in distributed and high performance computing.
We obtain a new parallel algorithm that is based on
Strassen's fast matrix multiplication and minimizes communication.
The algorithm outperforms all known parallel matrix
multiplication algorithms, classical and Strassen-based, both
asymptotically and in practice.
A critical bottleneck in parallelizing Strassen's algorithm
is the communication between the processors. Ballard, Demmel,
Holtz, and Schwartz (SPAA'11) prove lower bounds on
these communication costs, using expansion properties of the
underlying computation graph. Our algorithm matches these
lower bounds, and so is communication-optimal. It exhibits
perfect strong scaling within the maximum possible range.

Communitation Optimal Parallel Algorithms for Strassens Matrix Multiplication.pdf575.19 KB