Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank

DOI10.1007/978-3-319-03536-9_16MaRDI QIDQ2938032zbMATH OpenOpenAlexFDO

Authors Fan Chung, Olivia Simpson

Publication date 13 January 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.03157

zbMATH Keywords

boundary conditionsgraph Laplacianheat kernelPageRanksymmetric diagonally dominant linear systems

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)

Abstract: We present an efficient algorithm for solving local linear systems with a boundary condition using the Green's function of a connected induced subgraph related to the system. We introduce the method of using the Dirichlet heat kernel pagerank vector to approximate local solutions to linear systems in the graph Laplacian satisfying given boundary conditions over a particular subset of vertices. With an efficient algorithm for approximating Dirichlet heat kernel pagerank, our local linear solver algorithm computes an approximate local solution with multiplicative and additive error $epsilon$ by performing $O(epsilo{n}^{-5}{s}^{3}log(s^{3}epsilo{n}^{-1})logn)$ random walk steps, where $n$ is the number of vertices in the full graph and $s$ is the size of the local system on the induced subgraph.

Recommendations

• Solving local linear systems with boundary conditions using heat kernel pagerank
• Efficient numerical methods to solve sparse linear equations with application to PageRank
• Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations
• Reproducing kernel methods for solving linear initial-boundary-value problems
• scientific article; zbMATH DE number 5847104
• Reproducing kernel method for solving systems of linear equations
• Gradient-descent iterative algorithm for solving a class of linear matrix equations with applications to heat and Poisson equations
• Efficient solution of a nonlinear system of boundary value problems in reproducing kernel space
• A numerical method for solving matrix coefficient heat equations with interfaces
• A stable and efficient technique for linear boundary value problems by applying kernel functions

Cited in

(2)

• Sublinear column-wise actions of the matrix exponential on social networks
• Solving local linear systems with boundary conditions using heat kernel pagerank

This page was built for publication: Solving 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 Q2938032)