Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods (Q1344340)

This paper gives asymptotic lower bounds for the performance of Gaussian elimination and the Gauss-Jordan algorithm on scalable distributed-memory parallel architectures. Asymptotic refers to the large size of the linear system being solved. Such bounds are given when the matrix is partitioned in square blocks or when it is column-partitioned. The bounds for the optimal schedule time are expressed in terms of the time needed to perform the actual flops, the start up time for processor communication, the transmission speed, the number of processors and of course, the size of the problem. Numerical experiments are discussed, which show that the bounds are close to the actual execution time on the nCUBE-2 machine.