A Heuristic for Reducing Fill-In in Sparse Matrix Factorization.
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A heuristic is presented that helps to improve the quality of the bisection returned by the Kernighan-Lin and greedy graph bisection algorithms and helps to reduce the amount of fill-in produced by separator-based algorithms that reorder a matrix before 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.