Reordering sparse matrices for parallel elimination (Q1123535)

This paper describes a new reordering algorithm for a sparse symmetric positive-definite matrix A which produces a matrix suitable for parallel Gaussian elimination. It is assumed that a good fill-reducing ordering P of A has already been obtained. The reordering scheme proposed by \textit{J. A. G. Jess} and \textit{H. G. M. Kees} [IEEE Trans. Comput. C-31, 231-239 (1982; Zbl 0479.68034)] finds a final reordering \(\tilde P\) which has the same fill reduction as P. Firstly, the current author shows that the process generates an elimination tree with minimum height amongst all such trees from the class of equivalent orderings. In the second part of the paper the author considers a new reordering strategy which forms the elimination tree of the matrix \(PAP^ T\) and reduces its height without the introduction of additional fill. Numerical examples with standard sparse systems of order between 1000 and 6400 demonstrate that ordering times may be reduced by a factor of two or better over a basic minimum degree ordering previously described by the author [ACM Trans. Math. Software 11, 141-153 (1985; Zbl 0568.65015)].