PARALLEL MATRIX MULTIPLICATION ON THE CONNECTION MACHINE
Walter F. Tichy · International Journal of High Speed Computing · 1989
Matrix multiplication is a computation and communication intensive problem Six parallel algorithms for matrix multiplication on the Connection Machine are presented and compared with respect to their performance and processor usage. For n by n matrices, the algorithms have theoretical running times of O(n 2 log n), O(n log n), O(n), and O(1og n), and require n, n 22, n, and n 3 processors, respectively. With careful attention to communication patterns, the theoretically predicted runtimes can indeed be achieved in practice. The parallel algorithms illustrate the tradeoffs between performance, communication cost, and processor usage.