CS Colloquium

Stephen Vavasis, Cornell University

DATE: Wednesday, October 26, 2005
TIME: 10:00 A.M.
PLACE: 2405 Siebel Center
201 North Goodwin Ave., Urbana, IL

TITLE: Near Linear Time Solution of Elliptic Differential Equations Using Support-Graph Preconditioners

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.

BIOGRAPHY

Stephen Vavasis is a professor of Computer Science at Cornell University. He joined the Cornell faculty in 1989 after receiving his PhD in computer science from Stanford. Prior to that, he received his A.B. from Princeton and a Certificate of Advanced Study from Cambridge, both in mathematics. Vavasis has held visiting positions at several research labs including Argonne, Sandia, Xerox PARC and Bell Labs. His research area is scientific computing, and he specializes in numerical linear algebra, optimization, and computational geometry. He has been a Presidential Young Investigator and a Guggenheim Fellow.