Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
| Autor: | Anup Rao, Jonathan A. Kelner, John Peebles, Michael B. Cohen, Adrian Vladu, Aaron Sidford, Richard Peng |
|---|---|
| Přispěvatelé: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. Department of Mathematics, Cohen, Michael B., Kelner, Jonathan Adam, Peebles, John Lee Thompson, Vladu, Adrian Valentin |
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences Stationary distribution Markov chain Spectral graph theory 010103 numerical & computational mathematics 0102 computer and information sciences Directed graph Solver 01 natural sciences Combinatorics 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms Graph (abstract data type) Data Structures and Algorithms (cs.DS) 0101 mathematics Condition number Time complexity Algorithm Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | arXiv STOC |
| Popis: | In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Using this notion of approximation, we provide a general framework for solving asymmetric linear systems that is broadly inspired by the work of [Peng-Spielman, STOC`14]. Applying this framework in conjunction with our sparsification algorithm, we obtain an almost linear time algorithm for solving directed Laplacian systems associated with Eulerian Graphs. Using this solver in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16], we obtain almost linear time algorithms for solving a directed Laplacian linear system, computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each of these problems, our algorithms improves the previous best running times of $O((nm^{3/4} + n^{2/3} m) \log^{O(1)} (n \kappa \epsilon^{-1}))$ to $O((m + n2^{O(\sqrt{\log{n}\log\log{n}})}) \log^{O(1)} (n \kappa \epsilon^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is the number of edges, $\kappa$ is a natural condition number associated with the problem, and $\epsilon$ is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|