Seminar • Algorithms and Complexity • Treewidth and Linear Algebra

Please note: This seminar will take place in DC 1302 and online.

Luke Schaeffer, Professor
Institute for Quantum Computing
David R. Cheriton School of Computer Science

We look at the complexity of solving sparse linear systems as a function of the treewidth of the instance. That is, the sparse matrix is associated with a sparse graph, and solutions can be found faster when that graph has low treewidth. We give a parameterized algorithm in system size and treewidth achieving the conjectured optimal performance. No prior knowledge of treewidth is necessary.

This is joint work with Daniel Grier.

To attend this seminar in person, please go to DC 1302. You can also attend virtually on Zoom.