Communication complexity of the Gaussian elimination algorithm on multiprocessors (Q1077125): Difference between revisions

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.