Combinatorial preconditioning for sparse linear systems

Abstract

A key ingredient in the solution of a large, sparse system of linear equations by an iterative method like conjugate gradients is a preconditioner, which is in a sense an approximation to the matrix of coefficients. Ideally, the iterative method converges much faster on the preconditioned system at the extra cost of one solve against the preconditioner per iteration.

We survey a little-known technique for preconditioning sparse linear systems, called support-graph preconditioning, that borrows some combinatorial tools from sparse Gaussian elimination. Support-graph preconditioning was introduced by Vaidya and extended by Gremban, Miller, and Zagha. We extend the technique further and use it to analyze existing preconditioners based on incomplete factorization and on multilevel diagonal scaling. In the end, we argue that support-graph preconditioning is a ripe field for further research.

This work is joint with Marshall Bern (Xerox PARC), Bruce Hendrickson (Sandia National Labs), Nhat Nguyen (Stanford University), and Sivan Toledo (Xerox PARC and Tel Aviv University). It was supported in part by DARPA contract number DABT63-95-C-0087 and by NSF contract number ASC-96-26298.