Communication complexity of the Gaussian elimination algorithm on multiprocessors
Yousef El-Mabruk Saad · Linear Algebra and its Applications · 1986
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(kbuilt-12N2)+O(kbuilt12N) for a lock step Gaussian elimination algorithm, and to O(kbuilt-12N2)+O(kbuilt12) for any pipelined Gaussian elimination algorithm, where k is the total number of processors. The practical implications of these bounds are discussed.