Experiments with Strassen's Algorithm: From Sequential to Parallel

F. Song, J. Dongarra, and S. Moore (USA)


Strassen’s Algorithm, Matrix Multiplication, Parallel Com puting.


This paper studies Strassen’s matrix multiplication algo rithm by implementing it in a variety of methods: sequen tial, workflow, and in parallel. All the methods show bet ter performance than the well-known scientific libraries for medium to large size matrices. The sequential recur sive program is implemented and compared with ATLAS’s DGEMM subroutine. A workflow program in the Net Solve system and two parallel programs based on MPI and ScaLAPACK are also implemented. By analyzing the time complexity and memory requirement of each method, we provide insight into how to utilize Strassen’s Algorithm to speedup matrix multiplication based on existing high per formance tools or libraries.

Important Links:

Go Back