Reducing the parallel solution time of sparse circuit matrices using reordered Gaussian elimination and relaxation

The authors examine two approaches for reducing parallel sparse matrix solution time: the first based on pivot ordering algorithms for Gaussian elimination, and the second based on relaxation algorithms. A pivot ordering algorithm is presented which increases the parallelism of Gaussian elimination compared to the commonly used Markowitz method. The minimum number of parallel steps for the solution of a tridiagonal matrix is derived, and it is shown that this optimum is nearly achieved by the ordering heuristics which attempt to maximize parallelism. Also presented is an optimality result about Gauss-Jacobi over Gauss-Seidel relaxation on parallel processors.<>