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

zbMATH Keywords

Markov chainspreconditioningstationary distributiondirected graphssparsificationlinear system solver

Mathematics Subject Classification ID

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)

Efficient numerical methods to solve sparse linear equations with application to PageRank ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Spectral complexity of directed graphs and application to structural decomposition ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Unnamed Item ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ A queueing network-based distributed Laplacian solver for directed graphs ⋮ Polynomial-time algorithms for submodular Laplacian systems ⋮ Unnamed Item

This page was built for publication: Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs