Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
DOI10.1145/3055399.3055463zbMath1370.60115arXiv1611.00755OpenAlexW2547436936MaRDI QIDQ4977989
Jonathan A. Kelner, Michael B. Cohen, Adrian Vladu, Aaron Sidford, Richard Peng, John Peebles, Anup B. Rao
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.00755
Markov chainspreconditioningstationary distributiondirected graphssparsificationlinear system solver
Analysis of algorithms (68W40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Preconditioners for iterative methods (65F08)
Related Items (9)
This page was built for publication: Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs