Parallel complexity of matrix multiplication (Q1404305)

Matrix multiplication is a kernel of many numerical algorithms, thus finding efficient and parallel solution to this problem is one of the most important topics in scientific computing. In this paper, the parallel complexity of multiplying two matrices (using the standard row/column method) on parallel distributed-memory computers is studied. The author considers three basic aspects of designing distributed algorithms, namely local computational tasks, the initial data layout, and the communication schedule with respect to LogP, the well known theoretical model of parallel distributed-memory computers, which allows to consider the basic characteristics of an interconnection network regardless of its physical structure. The main result describes the lower bounds on running time of distributed matrix multiplication. Then several algorithms with running times within a constant factor of the lower bounds are described and analyzed. It should be pointed out that this excellent paper provides some important facts about designing optimal distributed-memory parallel algorithms. For example it defines several classes of algorithms, data layouts and communication schedules which collectively produce the optimal running times.