A Heuristic for Reducing Fill-In in Sparse Matrix Factorization.

Abstract

We present a heuristic that helps to improve the quality of the bisection returned by the Kernighan-Lin and greedy graph bisection algorithms. This in turns helps to reduce the amount of fill-in produced by separator-based algorithms that reorder a matrix before factorization. We also describe the performance of our heuristic on graphs from the Harwell-Boeing collection of sparse matrix test problems, and compare them with known results by other methods on the same graphs.