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 onesolve against the preconditioner per iteration. I will present a littleknown technique for preconditioning sparse systems of linear equations, called supportgraph preconditioning, that borrows some combinatorial tools from sparse Gaussian elimination. Supportgraph preconditioning was introduced by Vaidya and has been extended by several others. I will survey the method (not assuming any background in sparse matrix computation) and then show how to use it to analyze some preconditioners based on incomplete factorization and on multilevel diagonal scaling. I will conclude with a couple of open problems whose solutions will require both combinatorial and algebraic techniques. This is joint work with Marshall Bern, Bruce Hendrickson, Nhat Nguyen, and Sivan Toledo. Return to Applied Math Colloquium home page 