Combinatorics Seminar
When: Sunday, October 24, 10am
Where: Schreiber 309
Speaker: Raphy Yuster, University of Haifa
Title: Solving linear systems through nested dissection
Abstract:
The generalized nested dissection method, developed by Lipton,
Rose, and
Tarjan, is a seminal method for solving a linear system Ax=b where
A is a
symmetric positive definite matrix.
The method runs extremely fast whenever A is a well-separable
matrix (such
as matrices whose underlying support is planar or avoids a fixed
minor). In
this work we extend the nested dissection method to apply to
*any*
non-singular well-separable matrix
over *any* field. The running times we obtain essentially match
those of the
nested dissection method. The proof combines graph-theoretic and
linear-algebraic techniques.
Joint work with Noga Alon.