This paper proposes a few lower bounds for communication complexity of the Gaussian elimination algorithm on multiprocessors. Three types of architectures are considered: a bus architecture, a nearest neighbor ring network, and a nearest neighbor grid network. It is shown that for the bus and the ring architectures, the minimum communication time is O(N2), independent of the number of processors, while for the grid it is reduced to O(k built-1 2N2)+O(k built1 2N) for a lock step Gaussian elimination algorithm, and to O(k built-1 2N2)+O(k built1 2) for any pipelined Gaussian elimination algorithm, where k is the total number of processors. The practical implications of these bounds are discussed.
Bibliographical noteFunding Information:
*Revised version. Original version issued as Research Report YALEU/DCS/RR-348, January 1985. This work was supported in part by ONR grant NOO014-82.Kal84 and in part by a joint study with IBM/Kingston.