Scalable parallel Strassen's matrix multiply algorithm for distributed memory computers

摘要

The authors present a scalable parallel Strassen's matrix multiply algorithm for distributed memory, message passing computers. Strassen's algorithm to multiply two N x N matrices reduces the asymptotic operation count from O(N(sup 3)) of the traditional algorithm to O(N(sup 2.81)). In a sequential implementation the Strassen's algorithm offers better performance even for relatively low order matrices. However, due to its complexity, the parallel Strassen's algorithm is less than straight forward. Here a scalable parallel Strassen's algorithm is presented and compared with several other parallel algorithms. Performances of these algorithms are tested on a 128-processor Intel iPSC/860.