Using Combinatorics to Solve Systems in M-matrices in Nearly-linear Time
Symmetric M-matrices arise in areas as diverse as Scientific Computing, Combinatorial Optimization, and Machine Learning. In this talk, we survey recently developed combinatorial algorithms for preconditioning these matrices. These algorithms enable one to solve linear equations in these matrices in asymptotically nearly-linear time. The problem of solving equations in symmetric M-matrices leads to questions in graph theory such as: What is the best approximation of a graph by a sparser graph? What about by a tree? And, what is a good decomposition of a graph? We will provide answers and explain their consequences. Finally, we will survey a randomized combinatorial algorithm for scaling a symmetric M-matrix to make it diagonally dominant.
Dan Spielman, Yale University
