Solving local linear systems with boundary conditions using heat kernel pagerank

DOI10.1080/15427951.2015.1009522MaRDI QIDQ4985799zbMATH OpenOpenAlexFDO

Authors Fan 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

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

Recommendations

• Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• A local graph partitioning algorithm using heat kernel pagerank
• A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank

Cites work

• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• A sublinear time algorithm for PageRank computations
• Algorithms, graph theory, and linear equations in Laplacian matrices
• An efficient parallel solver for SDD linear systems
• Approaching optimality for solving SDD linear systems
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Lx = b
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• On the spectra of general random graphs
• Probability and Computing
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Strong converse for identification via quantum channels
• User-friendly tail bounds for sums of random matrices

Cited in

(4)

• A queueing network-based distributed Laplacian solver
• Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• On solving linear systems in sublinear time
• Sublinear Algorithms for Local Graph-Centrality Estimation

This page was built for publication: Solving local linear systems with boundary conditions using heat kernel pagerank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985799)