Near linear time solution of elliptic PDE's using support-graph preconditioners
Steve Vavasis, Department of Computer Science, Cornell University
October 7th 2005, 3:30PM, Wean 7220

Abstract

Support-graph preconditioners were first proposed by Vaidya in 1991. They are a graph-based method for fast solution of a certain kinds of linear equations. The basic idea was extended and generalized by various groups including Gremban, Miller and Zagha; Boman and Hendrickson; Bern et al.; and most recently Spielman and Teng. A limitation of almost all of this previous work is that provable bounds on the running time of the various methods have been available only in the case that the matrix is diagonally dominant, which is a fairly restricted class of linear systems.

We show how to extend this previous work to linear systems arising from finite element analysis of elliptic boundary value problems. Our technique, in combination with the recent results of Spielman and Teng, establishes that these linear systems can be solved in nearly linear time. Other fast methods, notably multigrid, are also available for these problems. In comparison with multigrid, our method imposes more stringent restrictions on the class of differential equations but fewer restrictions on the mesh, geometry, and variation of the coefficient fields.

This talk represents joint work with Erik Boman and Bruce Hendrickson.