×

Improving the run time and quality of nested dissection ordering. (English) Zbl 0922.65018

When performing sparse matrix factorization, the ordering of matrix rows and columns has a dramatic impact on the factorization time. The authors describe a reordering method that, on the basis of their computational experiments, is significantly better than currently available methods. The authors make use of nested dissection and minimum degree ordering. It is pointed out that the main difference with other related work is the use of constrained minimum degree on the sub-graphs, network flow techniques for refining separators, and use of minimum degree post pass on the separators. Results of extensive computational experiments are given.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI