A general scalable parallelizing of strassen's algorithm for matrix multiplication on distributed memory computers

Abstract

Strassen's algorithm to multiply two n × n matrices reduces the asymptotic operation count from O(n3) of the traditional algorithm to O(n2.38), thus on distributed memory computers, the association of Strassen's algorithm and the parallel matrix multiplication algorithms always gives remarkable results. Within this association, the application of Strossen's algorithm at inter-processor level requires us to solve more difficult problems in designing but it forms the most effective algorithms. In this paper, a general model of these algorithms will be presented and we also introduce a scalable method to implement this model on distributed memory computers. © 2005 IEEE.