A posteriori error estimates for multilevel methods for graph Laplacians
From MaRDI portal
(Redirected from Publication:5161767)
Abstract: In this paper, we study a posteriori error estimators which aid multilevel iterative solvers for linear systems with graph Laplacians. In earlier works such estimates were computed by solving global optimization problems, which could be computationally expensive. We propose a novel strategy to compute these estimates by constructing a Helmholtz decomposition on the graph based on a spanning tree and the corresponding cycle space. To compute the error estimator, we solve efficiently the linear system on the spanning tree, and then we solve approximately a least-squares problem on the cycle space. As we show, such an estimator has a nearly-linear computational complexity for sparse graphs under certain assumptions. Numerical experiments are presented to demonstrate the efficacy of the proposed method.
Recommendations
- Adaptive aggregation on graphs
- Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs
- An efficient multigrid method for graph Laplacian systems
- An efficient multigrid method for graph Laplacian systems. II: Robust aggregation
- Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
Cites work
- A‐posteriori error estimates for the finite element method
- A cascadic multigrid algorithm for computing the Fiedler vector of graph Laplacians
- A multigrid method based on graph matching for convection–diffusion equations
- A Multigrid Tutorial, Second Edition
- A posteriori error analysis and adaptive processes in the finite element method: Part I—error analysis
- A Posteriori Error Estimates for Nonlinear Problems. Finite Element Discretizations of Elliptic Equations
- A posteriori error estimation in finite element analysis
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Adaptive aggregation on graphs
- Adaptive Algebraic Multigrid
- Adaptive AMG with coarsening based on compatible weighted matching
- Adaptive Hypergraph Learning and its Application in Image Classification
- Adaptive Smoothed Aggregation (\alphaSA)
- Adaptive Smoothed Aggregation (\alphaSA) Multigrid
- Algebraic multigrid methods
- Algebraic multigrid methods for Laplacians of graphs
- Algebraic multilevel iteration method for lowest order Raviart-Thomas space and applications
- Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- An adaptive multigrid method based on path cover
- An aggregation-based algebraic multigrid method
- An algebraic multigrid method with guaranteed convergence rate
- An efficient multigrid method for graph Laplacian systems
- Approximations in elasticity based on the concept of function space
- Bootstrap algebraic multigrid: status report, open problems, and outlook
- Bootstrap AMG
- Commuting projections on graphs
- Computing the diffusion state distance on graphs via algebraic multigrid and random projections.
- Convergence analysis of the fast subspace descent method for convex optimization problems
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Efficient computable error bounds for discontinuous Galerkin approximations of elliptic problems
- Efficient preconditioning of laplacian matrices for computer graphics
- Explicit error bounds in a conforming finite element method
- Global and uniform convergence of subspace correction methods for some convex optimization problems
- Guaranteed and robust error bounds for nonconforming approximations of elliptic problems
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- Introduction to algorithms.
- Iterative Methods by Space Decomposition and Subspace Correction
- Laplacian matrices of graphs: A survey
- Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
- Multimodal Graph-Based Reranking for Web Image Search
- Primer of adaptive finite element methods
- Robust and adaptive multigrid methods: comparing structured and algebraic approaches.
- The University of Florida sparse matrix collection
- Towards adaptive smoothed aggregation (\(\alpha\)SA) for nonsymmetric problems
Cited in
(3)
This page was built for publication: A posteriori error estimates for multilevel methods for graph Laplacians
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5161767)
