PERFORMANCE BOUNDS FOR COLUMN-BLOCK PARTITIONING OF PARALLEL GAUSSIAN-ELIMINATION AND GAUSS-JORDAN METHODS

Column-block partitioning is commonly used in the parallelization of Gaussian Elimination (GE) and Gauss-Jordan (GJ) algorithms. It is therefore of interest to know performance bounds of such partitioning on scalable distributed-memory parallel architectures. In this paper, we use a graph-theoretic approach in deriving asymptotic performance lower bounds of column-block partitioning for both GE and GJ. The new contribution is the incorporation of communication cost in the analysis which results in the derivation of sharper lower bounds. We use our scheduling system PYRROS to experimentally compare the actual run time performance with that derived by these lower bounds on the nCUBE-2 hypercube parallel machine.