APPLIED MATH SEMINAR

Speaker: Daniel Spielman, Computer Science, Yale University

Title: Progress on Combinatorial Preconditioners for Diagonally-Dominant Matrices

When/where: Tuesday, March 23rd,  4:15 PM, AKW 200

Abstract::

Combinatorial preconditioners have given us nearly-linear time algorithms for
solving linear equations in symmetric diagonally-dominant matrices such as
the Laplacian matrices of graphs.  I will survey recent progress on these techniques
that lead to solvers that run in time O(n log² n) and that suggest the existence of
solvers that run in time O(n log n).
I will focus on the connection to the problems of approximating graphs by
sparser graphs and by spanning trees.