Approximately optimal elimination orderings for sparse matrices
Éva Tardos, Wee-Liang Heng · 1998
Many problems in engineering and science require the solution of a sparse system of linear equations $Ax=b,$ where A is a symmetric positive definite matrix. The system is typically solved via Gaussian elimination on A, which results in nonzero entries (known as fill-in) being introduced into the matrix. By judicious reordering of the rows and columns of A, it is often possible to reduce the amount of fill-in greatly, and consequently, the space and time taken to solve the system. Finding an ordering that minimizes fill-in is an NP-complete problem. In practice, heuristics are used to find good orderings. These heuristics, however, do not have any guarantees on the quality of the ordering produced. In contrast, by using a divide-and-conquer approach with approximately optimal balanced vertex separators, Agrawal, Klein and Ravi recently gave the first approximation algorithm for optimal elimination orderings. This thesis describes an extensive computational study of Agrawal-Klein-Ravi algorithm and its underlying subroutines, and also proposes and investigates improvements to that algorithm. We introduce a new cost measure for the separators used to decompose a problem, and also devise a novel way of forming the subproblems and combining the solutions to these subproblems. These new approaches are empirically compared to existing ones in the literature, and fare well against them. The computational bottleneck in all the divide-and-conquer approaches is the construction of approximately optimal balanced vertex separators. We demonstrate that substantial running time improvements can be obtained by aggressively optimizing the implementation of the construction.