A Parallel Solution Method for Large Sparse Systems of Equations

This paper presents a new distributed multifrontal sparse matrix decomposition algorithm suitable for message passing parallel processors. The algorithm uses a nested dissection ordering and a multifrontal distribution of the matrix to minimize interprocessor data dependencies and overcome the communication bottleneck previously reported for sparse matrix decomposition [1]. Distributed multifrontal forward elimination and back substitution algorithms are also provided. Results of an implementation on the Intel iPSC are presented. Up to 16 processors are used to solve systems with as many as 7225 equations. With 16 processors, speedups of 10.2 are observed and the decomposition is shown to achieve 67 percent processor utilization. This work was motivated by the need to reduce the computational bottleneck in the Stanford PISCES [2] device simulator; however, it should be applicable to a wide range of scientific and engineering problems