Abstract

Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination O(polylog(n)) time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely-used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approximate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees.

While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greedily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating the interleaved queries and updates to this randomized data structure may be of independent interest.

Joint work with Matthew Fahrbach, Gary L. Miller, Saurabh Sawlani, Junxing Wang, and Shen Chen Xu. Manuscript available at:
https://arxiv.org/abs/1804.04239.

Time

7月30日（周一）14:00-15:00

Speaker

Richard Peng is an assistant professor in the School of ComputerScience at the Georgia Institute of Technology. His main research interests are in the design, analysis, and implementation of efficient algorithms. Over the past decade these interests revolved around problems induced by practice that arise at the intersection of discrete, numerical, and randomized algorithms. Results involving him give the current best runtime bounds for: solving linear systems corresponding to random walks on undirected/directed graphs, maintaining approximate max-matchings in fully dynamic graphs,reducing the sizes of matrices while preserving L_1-norm structures, and approximating max-flows on undirected graphs.

Richard received his BMath from the University of Waterloo in 2009, Ph.D. in Computer Science from CMU in 2013, and worked for two years as a postdoc/instructor in Applied Math at MIT. He was a Microsoft Research PhD Fellow, and his thesis received the CMU SCS Distinguished Dissertation Award. Richard also has extensive involvements in outreach activities related to algorithmic problem solving, including serving on the scientific committee for the International Olympiad in Informatics in 2015 - 2018.

Venue

信息管理与工程学院  602室

上海财经大学

上海市杨浦区武东路100号