Performance of a fully parallel sparse solver

The performance of a fully parallel direct solver for large sparse-symmetric positive definite systems of linear equations is demonstrated. The solver is designed for distributed-memory, message-passing parallel computer systems. All phases of the computation, including symbolic processing as well as numeric factorization and triangular solution, are performed in parallel. A parallel Cartesian-nested dissection algorithm is used to compute a fill-reducing ordering for the matrix and an appropriate partitioning of the problem across the processors. The separator tree resulting from nested dissection is used to identity and exploit large-grain parallelism in the remaining steps of the computation. The parallel performance of the solver is reported for a series of test problems on the Thinking Machines CM-5 and the Intel Touchstone Delta. The parallel efficiency, scalability, and absolute performance of the solver, as well as the relative importance of the various phases of the computation, are investigated empirically.