FAST MATRIX MULTIPLICATION ALGORITHMS ON MIMD ARCHITECTURES

Abstract

We present in this paper the parallelization of fast matrix multiplication algorithms of Strassen and Wino-grad on MIMD distributed architectures whose interconnection networks are ring and torus. Complexity and efficiency are analyzed and good asymptotic behaviour is proved. These new parallel algorithms are compared with standard algorithms on a 128-processor parallel computer; experiments confirm the theoretical results.