Experiments with Strassen's Algorithm: From Sequential to Parallel
Fengguang Song, Jack J. Dongarra, Shirley Moore · IASTED International Conference on Parallel and Distributed Computing and Systems · 2006
This paper studies Strassen’s matrix multiplication algorithm by implementing it in a variety of methods: sequential, workflow, and in parallel. All the methods show better performance than the well-known scientific libraries for medium to large size matrices. The sequential recursive program is implemented and compared with ATLAS’s DGEMM subroutine. A workflow program in the NetSolve 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 performance tools or libraries.