Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning

DOI10.1137/15M1050872MaRDI QIDQ5348222zbMATH OpenOpenAlexFDO

Authors Colin Ponce, Panayot S. Vassilevski

Publication date 14 August 2017

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/15m1050872

zbMATH Keywords

condition numberdirect methodgraph Laplaciannumerical experimentrecursive bisectionsupport graph preconditionerstwo-grid methods

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05) Preconditioners for iterative methods (65F08)

Recommendations

• An efficient multigrid method for graph Laplacian systems
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• An empirical comparison of graph Laplacian solvers
• An efficient multigrid method for graph Laplacian systems. II: Robust aggregation
• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians

Cites work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A Nearly-m log n Time Solver for SDD Linear Systems
• A survey of preconditioned iterative methods for linear systems of algebraic equations
• Collective dynamics of `small-world' networks
• Emergence of Scaling in Random Networks
• Generalized Nested Dissection
• scientific article; zbMATH DE number 3874483 (Why is no real title available?)
• Multilevel Block Factorization Preconditioners
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Nested Dissection of a Regular Finite Element Mesh
• On two‐grid convergence estimates

Cited in

(5)

• Iterative preconditioned methods in Krylov spaces: trends of the 21st century
• Support-Graph Preconditioners
• A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations
• Solving Graph Laplacians via Multilevel Sparsifiers
• Accelerated multigrid for graph Laplacian operators

Describes a project that uses

Uses Software

• SNAP
• PT-Scotch

This page was built for publication: Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning

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