Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank

DOI10.1080/15427951.2015.1009522zbMath1461.68025OpenAlexW3104617709MaRDI QIDQ4985799

Fan R. K. Chung, Olivia Simpson

Publication date: 26 April 2021

Published in: Internet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/15427951.2015.1009522

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Internet topics (68M11) Flows in graphs (05C21)

Related Items

Computing heat kernel PageRank and a local clustering algorithm, Sublinear Algorithms for Local Graph-Centrality Estimation, A queueing network-based distributed Laplacian solver, Unnamed Item

Cites Work

• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• On the spectra of general random graphs
• User-friendly tail bounds for sums of random matrices
• Computing heat kernel PageRank and a local clustering algorithm
• A Sublinear Time Algorithm for PageRank Computations
• Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Strong converse for identification via quantum channels
• An efficient parallel solver for SDD linear systems
• Solving SDD linear systems in nearly m log ^1/2 n time
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Lx = b
• Approaching Optimality for Solving SDD Linear Systems
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• Probability and Computing
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Unnamed Item
• Unnamed Item
• Unnamed Item