Communication-optimal parallel algorithm for strassen’s matrix multiplication

Parallel matrix multiplication is one of the most studied fun-damental problems in distributed and high performance com-puting. We obtain a new parallel algorithm that is based on Strassen’s fast matrix multiplication and minimizes communi-cation. 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, Dem-mel, 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. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ∗Research supported by Microsoft (Award #024263) and Intel (Award #024894) funding and by matching funding b