A general scalable implementation of fast matrix multiplication algorithms on distributed memory computers

Abstract

Fast matrix multiplication (FMM) algorithms to multiply two n × n matrices reduce the asymptotic operation count from O(n3) of the traditional algorithm to O(n2.38), thus on distributed memory computers, the association of FMM algorithms and the parallel matrix multiplication algorithms always gives remarkable results. Within this association, the application of FMM algorithms at interprocessor 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.