Algebraic multigrid methods for Laplacians of graphs

DOI10.1016/j.laa.2010.11.008zbMath1217.65063OpenAlexW2050711087MaRDI QIDQ2431144

Matthias Bolten, Karsten Kahl, Matthias Heming, Stephanie Friedhoff, Andreas Frommer

Publication date: 11 April 2011

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2010.11.008

zbMATH Keywords

convergence analysisnumerical resultsalgebraic multigridsingular systemsgraph partitioningMoore-Penrose inversecoarse grid correctionLaplacians of graphs

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Iterative numerical methods for linear systems (65F10) Parallel numerical computation (65Y05)

Related Items

An Efficient Multigrid Method for Graph Laplacian Systems II: Robust Aggregation, A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians, Algebraic Two-Level Convergence Theory for Singular Systems, On some properties of the Laplacian matrix revealed by the RCM algorithm

Uses Software

• METIS
• JOSTLE
• DibaP

Cites Work

• Unnamed Item
• On algebraic multilevel methods for non-symmetric systems - convergence results
• On the convergence of splittings for semidefinite linear systems
• On algebraic multi-level methods for non-symmetric systems --- comparison results
• An Algebraic Multigrid Preconditioner for a Class of Singular M-Matrices
• On the Convergence of General Stationary Linear Iterative Methods for Singular Linear Systems
• Convergence of Stationary Iterative Methods for Hermitian Semidefinite Linear Systems and Applications to Schwarz Methods
• Multigrid Methods for Variational Problems
• On the Convergence of Iterative Methods for Semidefinite Linear Systems