An experimental investigation of distributed matrix multiplication techniques
Stephen A. Rees, James P. Black · Software Practice and Experience · 1991
Abstract This paper discusses the development and refinement of several distributed matrix multiplication algorithms. Our goal in this research has been to determine if successful distribution of this problem is possible within a loosely‐coupled environment. Our criteria for success are fast execution speed and, to a lesser extent, memory efficiency. Our results indicate that, perhaps counter‐intuitively, it is possible to use distribution to improve the performance of dense matrix multiplication. The speed increase obtained ranges up to a factor of four, depending upon the algorithm and the process configuration used. Among the factors affecting performance are computational complexity, number and size of interprocess messages, and bookkeeping overhead. We conclude that this approach to matrix multiplication has potential. Furthermore, some of the principles discussed here may be usefully employed in the distribution of other algorithms of the same O(n3) computational complexity, such as LU decomposition (linear system solvers) and Cholesky factorization.