Communication complexity of the Gaussian elimination algorithm on multiprocessors (Q1077125)

The author analyses the effects of data movement delays in parallel Gaussian elimination algorithms on multiprocessors. Three types of architectures are considered: a bus architecture, a nearest neighbour 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(N^ 2)\), independent of processors, while for the grid it is reduced to \(O(K^{-1/2}N^ 2)+O(K^{1/2})\) for a lock step Gaussian elimination algorithm, and to \(O(K^{1/2}N^ 2)+O(K^{1/2})\) for any pipelined Gaussian elimination algorithm, where K is the total number of processors. The practical implications of these bounds are discussed.