Abstract
Over the past two decades there has been much theoretical progress on efficient solvers for Symmetric Diagonally Dominant matrices, which are algorithmically equivalent to graph Laplacians. This in turn led to the Laplacian paradigm for designing graph algorithms, which now provide the best runtime guarantees for a wide range of well-studied problems on graphs such as bipartite matching, negative-length shortest paths, minimum cost flow, and isotonic regression.
This talk will overview recent and ongoing efforts towards implementing code packages for such solvers that are an order of magnitude faster than what’s currently available, and discuss on going efforts towards benchmarking solvers for structured linear systems. We will discuss ways of isolating the combinatorial, data structural, and numerical components, and observations made from such evaluations, including:
* The interaction between second order optimization methods and iterative solvers for sparse linear systems.
* Comparisons between dynamic / online / offline tree data structures for maintaining flows under cycle toggles.
* The theoretical and practice dependence numerical precision in the convergence rates of iterative methods with combinatorial preconditioners.
Time
2017-06-01 14:00 ~ 16:00Speaker
Richard Peng, Georgia Institute of TechnologyRoom
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics
