John R. Gilbert

Massachusetts Institute of Technology and
University of California, Santa Barbara

November 4, 4:15pm


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 little-known technique for preconditioning sparse systems
of linear equations, called support-graph preconditioning, that borrows
some combinatorial tools from sparse Gaussian elimination.  Support-graph
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