Algebraic multigrid methods for Laplacians of graphs
algebraic multigridcoarse grid correctionconvergence analysisgraph partitioningLaplacians of graphsMoore-Penrose inversenumerical resultssingular systems
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) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Parallel numerical computation (65Y05)
The authors consider the convergence analysis (in the seminorm of the system matrix) of algebraic multigrid methods in the case of singular, symmetric semidefinite matrices with semisimple zero eigenvalue (i.e., the Jordan blocks belonging to it are trivial). For this, they prove a number of theorems replacing the classical ones (concerning the smoothing and approximation properties) along the lines of the Stüben paper in the book by \textit{U. Trottenberg, C. W. Oosterlee} and \textit{A. Schüller} [Multigrid. With guest contributions by A. Brandt, P. Oswald, K. Stüben. Orlando, FL: Academic Press (2001; Zbl 0976.65106)]. Among other things they show that not only the Moore-Penrose inverse can be used in the coarse grid correction operator. Since the motivation for this research is shape optimized load balancing for graph partitioning, they later specialize to irredubible diagonally dominant singular M-matrices (corresponding to Laplacians of graphs), showing that decisive properties are inherited by the Galerkin projection. A number of numerical results concerning timing of setup and iterative solution show that indeed a linear behaviour is maintained for their systems of several \(10^5\) unknowns.
- Algebraic Theory of Two-Grid Methods
- A note on algebraic multigrid methods for the discrete weighted Laplacian
- An algebraic multigrid method with guaranteed convergence rate
- Automatic coarsening in algebraic multigrid utilizing quality measures for matching-based aggregations
- Algebraic two-level convergence theory for singular systems
- Convergence of algebraic multigrid methods for symmetric and positive definite matrices with weak diagonal dominance
- Convergence analysis of algebraic multi-lattice procedures for M-matrices.
- Spectral AMGe (\rhoAMGe)
- A Multigrid Method Based on Incomplete Gaussian Elimination
- An algebraic multigrid method for elasticity based on an auxiliary topology with edge matrices
- An Algebraic Multigrid Preconditioner for a Class of Singular M-Matrices
- Convergence of Stationary Iterative Methods for Hermitian Semidefinite Linear Systems and Applications to Schwarz Methods
- scientific article; zbMATH DE number 3215568 (Why is no real title available?)
- Multigrid Methods for Variational Problems
- On algebraic multi-level methods for non-symmetric systems --- comparison results
- On algebraic multilevel methods for non-symmetric systems - convergence results
- On the Convergence of General Stationary Linear Iterative Methods for Singular Linear Systems
- On the Convergence of Iterative Methods for Semidefinite Linear Systems
- On the convergence of splittings for semidefinite linear systems
- Finite element algorithms for nonlocal minimal graphs
- Algebraic two-level convergence theory for singular systems
- On some properties of the Laplacian matrix revealed by the RCM algorithm.
- Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs
- Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
- An Algebraic Multigrid Preconditioner for a Class of Singular M-Matrices
- Algebraic multigrid for k‐form Laplacians
- Geometric multigrid for the tight-binding Hamiltonian of graphene
- Algebraic multigrid for directed graph Laplacian linear systems (NS-LAMG).
- A posteriori error estimates for multilevel methods for graph Laplacians
- An adaptive multigrid method based on path cover
- An efficient multigrid method for graph Laplacian systems. II: Robust aggregation
- Large-Scale Scientific Computing
- A note on algebraic multigrid methods for the discrete weighted Laplacian
- Accelerated multigrid for graph Laplacian operators
This page was built for publication: Algebraic multigrid methods for Laplacians of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431144)
