A General Scalable Implementation of Fast Matrix Multiplication Algorithms on Distributed Memory Computers
Duc Kien Nguyen, Ivan Lavallée, Marc Bui, Quoc Trung Ha · 2005
Fast matrix multiplication (FMM) algorithms to multiply two n /spl times/ n matrices reduce the asymptotic operation count from O(n/sup 3/) of the traditional algorithm to O(n/sup 2.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 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 is presented and we also introduce a scalable method to implement this model on distributed memory computers.