Algebraic multigrid methods
From MaRDI portal
Abstract: This paper is to give an overview of AMG methods for solving large scale systems of equations such as those from the discretization of partial differential equations. AMG is often understood as the acronym of "Algebraic Multi-Grid", but it can also be understood as "Abstract Muti-Grid". Indeed, as it demonstrates in this paper, how and why an algebraic multigrid method can be better understood in a more abstract level. In the literature, there are a variety of different algebraic multigrid methods that have been developed from different perspectives. In this paper, we try to develop a unified framework and theory that can be used to derive and analyze different algebraic multigrid methods in a coherent manner. Given a smoother for a matrix , such as Gauss-Seidel or Jacobi, we prove that the optimal coarse space of dimension is the span of the eigen-vectors corresponding to the first eigenvalues of (with ). We also prove that this optimal coarse space can be obtained by a constrained trace-minimization problem for a matrix associated with and demonstrate that coarse spaces of most of existing AMG methods can be viewed some approximate solution of this trace-minimization problem. Furthermore, we provide a general approach to the construction of a quasi-optimal coarse space and we prove that under appropriate assumptions the resulting two-level AMG method for the underlying linear system converges uniformly with respect to the size of the problem, the coefficient variation, and the anisotropy. Our theory applies to most existing multigrid methods, including the standard geometric multigrid method, the classic AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG, and spectral AMGe.
Recommendations
Cites work
- scientific article; zbMATH DE number 3831213 (Why is no real title available?)
- scientific article; zbMATH DE number 434719 (Why is no real title available?)
- scientific article; zbMATH DE number 4192967 (Why is no real title available?)
- scientific article; zbMATH DE number 3874483 (Why is no real title available?)
- scientific article; zbMATH DE number 3906496 (Why is no real title available?)
- scientific article; zbMATH DE number 3924053 (Why is no real title available?)
- scientific article; zbMATH DE number 3987790 (Why is no real title available?)
- scientific article; zbMATH DE number 4043364 (Why is no real title available?)
- scientific article; zbMATH DE number 52660 (Why is no real title available?)
- scientific article; zbMATH DE number 3576661 (Why is no real title available?)
- scientific article; zbMATH DE number 3622441 (Why is no real title available?)
- scientific article; zbMATH DE number 1218952 (Why is no real title available?)
- scientific article; zbMATH DE number 467276 (Why is no real title available?)
- scientific article; zbMATH DE number 736323 (Why is no real title available?)
- scientific article; zbMATH DE number 1064580 (Why is no real title available?)
- scientific article; zbMATH DE number 1561761 (Why is no real title available?)
- scientific article; zbMATH DE number 949303 (Why is no real title available?)
- scientific article; zbMATH DE number 3997082 (Why is no real title available?)
- scientific article; zbMATH DE number 3451986 (Why is no real title available?)
- scientific article; zbMATH DE number 2113718 (Why is no real title available?)
- scientific article; zbMATH DE number 5587346 (Why is no real title available?)
- scientific article; zbMATH DE number 5049875 (Why is no real title available?)
- scientific article; zbMATH DE number 3248523 (Why is no real title available?)
- scientific article; zbMATH DE number 3366440 (Why is no real title available?)
- scientific article; zbMATH DE number 3410718 (Why is no real title available?)
- scientific article; zbMATH DE number 3101207 (Why is no real title available?)
- A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning
- A Family of Energy Minimizing Coarse Spaces for Overlapping Schwarz Preconditioners
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A Greedy Strategy for Coarse-Grid Selection
- A Multigrid Tutorial, Second Edition
- A New Convergence Proof for the Multigrid Method Including the V-Cycle
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A general interpolation strategy for algebraic multigrid using energy minimization
- A generalized eigensolver based on smoothed aggregation (GES-SA) for initializing smoothed aggregation (SA) multigrid
- A modification of the two-level algorithm with overcorrection
- A multigrid method based on graph matching for convection–diffusion equations
- A nearly optimal multigrid method for general unstructured grids
- A sharp convergence estimate for the method of subspace corrections for singular systems of equations
- A simple preconditioner for a discontinuous Galerkin method for the Stokes problem
- AMG by element agglomeration and constrained energy minimization interpolation
- AMG for problems of elasticity
- AMGe based on element agglomeration
- Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps
- Acceleration of convergence of a two-level algebraic algorithm by aggregation in smoothing process
- Adaptive AMG with coarsening based on compatible weighted matching
- Adaptive Algebraic Multigrid
- Adaptive Smoothed Aggregation ($\alpha$SA)
- Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid
- Adaptive filtering
- Adaptive reduction-based AMG
- Adaptive reduction-based multigrid for nearly singular and highly disordered physical systems
- Adaptive strategies in the multilevel multiscale mimetic (M\(^3\)) method for two-phase flows in porous media
- Additive multilevel preconditioners based on bilinear interpolation, matrix-dependent geometric coarsening and algebraic multigrid coarsening for second-order elliptic PDEs
- Aggregation-Based Algebraic Multigrid for Convection-Diffusion Equations
- Algebraic Multigrid Based on Computational Molecules, 2: Linear Elasticity Problems
- Algebraic Multigrid for High-Order Hierarchical H(curl) Finite Elements
- Algebraic multigrid (AMG): Experiences and comparisons
- Algebraic multigrid based on computational molecules. 1: Scalar elliptic problems
- Algebraic multigrid based on element interpolation (AMGe)
- Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
- Algebraic multigrid theory: The symmetric case
- Algebraic study of multigrid methods for symmetric, definite problems
- An Algebraic Interpretation of Multigrid Methods
- An Energy-minimizing Interpolation for Robust Multigrid Methods
- An aggregation-based algebraic multigrid method
- An algebraic multigrid method with guaranteed convergence rate
- An algebraic multilevel method for anisotropic elliptic equations based on subgraph matching.
- An algebraic multilevel multigraph algorithm
- An algebraic preconditioning method for M‐matrices: linear versus non‐linear multilevel iteration
- An energy‐based AMG coarsening strategy
- Analysis of a two-level method for anisotropic diffusion equations on aligned and nonaligned grids.
- Black box multigrid
- Black box multigrid for nonsymmetric problems
- Bootstrap AMG
- Bootstrap algebraic multigrid: status report, open problems, and outlook
- Coarsening by compatible relaxation
- Comparative convergence analysis of nonlinear AMLI-cycle multigrid
- Compatible relaxation and coarsening in algebraic multigrid
- Convergence Estimates for Multigrid Algorithms without Regularity Assumptions
- Convergence Estimates for Product Iterative Methods with Applications to Domain Decomposition
- Convergence of a Nonconforming Multiscale Finite Element Method
- Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients
- Counterexamples Concerning A Weighted L 2 Projection
- Deriving the X-Z identity from auxiliary space method
- Distance-two interpolation for parallel algebraic multigrid
- Element-free AMGe: General algorithms for computing interpolation weights in AMG
- Energy optimization of algebraic multigrid bases
- Fast multilevel methods for Markov chains.
- Flexible conjugate gradients
- General highly accurate algebraic coarsening
- Generalized Finite Element Methods: Their Performance and Their Relation to Mixed Methods
- Graph theory
- Inexact Preconditioned Conjugate Gradient Method with Inner-Outer Iteration
- Iterative Aggregation--A New Approach to the Solution of Large-Scale Problems
- Iterative Methods by Space Decomposition and Subspace Correction
- Iterative solution of large sparse systems of equations. Transl. from the German
- Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
- Matrix iterative analysis
- Matrix-dependent prolongations and restrictions in a blackbox multigrid solver
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- Multigrid Methods for Variational Problems
- Multigrid Methods for Variational Problems: Further Results
- Multigrid Methods for Variational Problems: General Theory for the V-Cycle
- Multigrid with matrix-dependent transfer operators for a singular perturbation problem
- Multilevel Block Factorization Preconditioners
- Multiple Vector Preserving Interpolation Mappings in Algebraic Multigrid
- Multiscale and multiresolution methods. Theory and applications
- New Convergence Estimates for Multigrid Algorithms
- Non-Galerkin multigrid based on sparsified smoothed aggregation
- On Generalizing the Algebraic Multigrid Framework
- On an energy minimizing basis for algebraic multigrid methods
- On multiple grid and related techniques for solving discrete elliptic systems
- On the Computation of Approximate Eigenvalues and Eigenfunctions of Elliptic Operators by Means of a Multi-Grid Method
- On the abstract theory of additive and multiplicative Schwarz algorithms
- On the l 2 Convergence of an Algorithm for Solving Finite Element Equations
- On the robustness of the BPX-preconditioner with respect to jumps in the coefficients
- On two‐grid convergence estimates
- One-Dimensional Algorithm for Finding Eigenbasis of the Schrödinger Operator
- Operator-based interpolation for bootstrap algebraic multigrid.
- Optimal multilevel methods for graded bisection grids
- Parallel Multilevel Preconditioners
- Parallel frequency filtering
- Parallel iterative methods for sparse linear systems
- ROBUST SUBSPACE CORRECTION METHODS FOR NEARLY SINGULAR SYSTEMS
- Recursive Krylov-based multigrid cycles
- Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
- Robust and adaptive multigrid methods: comparing structured and algebraic approaches.
- Robust multigrid methods for nonsmooth coefficient elliptic linear systems
- Sharp Estimates for Multigrid Rates of Convergence with General Smoothing and Acceleration
- Smoothed aggregation solvers for anisotropic diffusion
- Smoothed aggregation spectral element agglomeration AMG: SA-\(\rho \)AMGe
- Some Estimates for a Weighted L 2 Projection
- Some Nonoverlapping Domain Decomposition Methods
- Spectral AMGe ($\rho$AMGe)
- Spectral element agglomerate algebraic multigrid methods for elliptic problems with high-contrast coefficients
- The Analysis of Multigrid Algorithms with Nonnested Spaces or Noninherited Quadratic Forms
- The Multi-Grid Method for the Diffusion Equation with Strongly Discontinuous Coefficients
- The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids
- The development of coarse spaces for domain decomposition algorithms
- The finite element methods for elliptic problems.
- The frequency decomposition multi-grid method. I: Application to anisotropic equations
- The method of alternating projections and the method of subspace corrections in Hilbert space
- Theoretical bounds for algebraic multigrid performance: review and analysis.
- Two-sided bounds on the convergence rate of two-level methods
- Uniformly convergent multigrid methods for convection--diffusion problems without any constraint on coarse grids
- Variable‐step multilevel preconditioning methods, I: Self‐adjoint and positive definite elliptic problems
- \textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
Cited in
(only showing first 100 items - show all)- An Algebraic Multigrid Method for a Class of Elliptic Differential Systems
- Multigrid methods of macrogrid domain decomposition
- Algebraic multigrid theory: The symmetric case
- Coarse spaces by algebraic multigrid: multigrid convergence and upscaling error estimates
- A novel algebraic multigrid approach based on adaptive smoothing and prolongation for ill-conditioned systems
- Block preconditioning for fault/fracture mechanics saddle-point problems
- A robust adaptive algebraic multigrid linear solver for structural mechanics
- Theoretical bounds for algebraic multigrid performance: review and analysis.
- Convergence analysis of two-level methods with general coarse solvers
- A graph convolutional autoencoder approach to model order reduction for parametrized PDEs
- Convergence analysis of inexact two-grid methods: a theoretical framework
- Agglomeration of polygonal grids using graph neural networks with applications to multigrid solvers
- Algebraic multigrid and discrete calculus representations of coupled-fields
- Efficient Algebraic Multigrid Methods for Multilevel Overlapping Coclustering of User-Item Relationships
- Alternative dissolution-rate controlled model and time adaptive, high resolution scheme for site-scale subsurface carbon sequestration simulation
- Eigenvalue topology optimization via efficient multilevel solution of the frequency response
- Recent advancements in preconditioning techniques for large size linear systems suited for high performance computing
- Superconvergence of high order finite difference schemes based on variational formulation for elliptic equations
- An algebraic multigrid method with guaranteed convergence rate
- Chronos: a general purpose classical AMG solver for high performance computing
- Comparison of block preconditioners for the Stokes problem with discontinuous viscosity and friction
- Algebraic multigrid block triangular preconditioning for multidimensional three-temperature radiation diffusion equations
- Nodal auxiliary space preconditioning for the surface de Rham complex
- Super-localization of spatial network models
- A simplified new multigrid algorithm of lattice Boltzmann method for steady states
- Algebraic Theory of Two-Grid Methods
- Robust discretization and solvers for elliptic optimal control problems with energy regularization
- MgNet: a unified framework of multigrid and convolutional neural network
- AMG Preconditioners for Linear Solvers towards Extreme Scale
- scientific article; zbMATH DE number 3994974 (Why is no real title available?)
- Dual-grid mapping method for the advection-diffusion-reaction equation in a heterogeneous medium
- A supplementary strategy for coarsening in algebraic multigrid
- Newton Solvers for Drift-Diffusion and Electrokinetic Equations
- Combining physics-based and data-driven models: advancing the frontiers of research with scientific machine learning
- Scalable preconditioning for the stabilized contact mechanics problem
- On Generalizing the Algebraic Multigrid Framework
- lifex-cfd: an open-source computational fluid dynamics solver for cardiovascular applications
- scientific article; zbMATH DE number 3874483 (Why is no real title available?)
- High-order extended finite element methods for solving interface problems
- Strong convergence analysis of iterative solvers for random operator equations
- A primal-dual flow for affine constrained convex optimization
- Efficient Algebraic Multigrid Preconditioners on Clusters of GPUs
- Rational approximation preconditioners for multiphysics problems
- A matrix-free high-order solver for the numerical solution of cardiac electrophysiology
- Accelerating Exponential Integrators to Efficiently Solve Semilinear Advection-Diffusion-Reaction Equations
- On AMG methods with F-smoothing based on Chebyshev polynomials and their relation to AMGr
- Finite elements for Matérn-type random fields: uncertainty in computational mechanics and design optimization
- Multiscale graph neural networks with adaptive mesh refinement for accelerating mesh-based simulations
- Review of Methods Inspired by Algebraic-Multigrid for Data and Image Analysis Applications
- Algebraic multigrid methods for constrained linear systems with applications to contact problems in solid mechanics
- Multigrid methods for convergent mixed finite difference scheme for Monge-Ampère equation
- An Interpretive Constrained Linear Model for ResNet and MgNet
- Operator-dependent prolongation and restriction for the parameter-dependent multigrid method using low-rank tensor formats
- Algebraic multigrid for the finite pointset method
- Meta-mgnet: meta multigrid networks for solving parameterized partial differential equations
- Agglomeration-based geometric multigrid solvers for compact discontinuous Galerkin discretizations on unstructured meshes
- Preconditioning strategies for vectorial finite element linear systems arising from phase-field models for fracture mechanics
- Emergence of non-trivial solutions from trivial solutions in reaction-diffusion equations for pattern formation
- Parallel Energy-Minimization Prolongation for Algebraic Multigrid
- Learning-based local weighted least squares for algebraic multigrid method
- Iterative method for large-scale Timoshenko beam models assessed on commercial-grade paperboard
- A stable loosely-coupled scheme for cardiac electro-fluid-structure interaction
- Learning Optimal Multigrid Smoothers via Neural Networks
- Dilated convolution neural operator for multiscale partial differential equations
- A highly parallelized multiscale preconditioner for Darcy flow in high-contrast media
- An energy‐based AMG coarsening strategy
- HAZniCS -- software components for multiphysics problems
- SlabLU: a two-level sparse direct solver for elliptic PDEs
- Preconditioned nonsymmetric/symmetric discontinuous Galerkin method for elliptic problem with reconstructed discontinuous approximation
- \(\mathrm{AutoAMG}(\theta)\): an auto-tuned AMG method based on deep learning for strong threshold
- A comparative study of scalable multilevel preconditioners for cardiac mechanics
- Re-parameterisation technique in algebraic numerical grid generation via subdivision schemes
- A posteriori error estimates of finite element methods by preconditioning
- An inexact Uzawa algorithmic framework for nonlinear saddle point problems with applications to elliptic optimal control problem
- Large-Scale Scientific Computing
- A multigrid method for nonlocal problems: non-diagonally dominant or Toeplitz-plus-tridiagonal systems
- Multigrid incomplete factorization methods in Krylov subspaces
- Fast linear solvers for incompressible CFD simulations with compatible discrete operator schemes
- Algebraic Multigrid for High-Order Hierarchical H(curl) Finite Elements
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- A root-node-based algebraic multigrid method
- Preprocessed GMRES for fast solution of linear equations
- Spectral coarse spaces for the substructured parallel Schwarz method
- An efficient algebraic multigrid method for solving optimality systems
- Modifying AMG coarse spaces with weak approximation property to exhibit approximation in energy Norm
- Three Anderson accelerated iterative methods for solving large scale linear equations
- A hierarchical approach for multicontinuum homogenization in high contrast media
- Coarsening in algebraic multigrid using Gaussian processes
- AIR multigrid with GMRES polynomials (AIRG) and additive preconditioners for Boltzmann transport
- An algebraic multigrid method based on local relaxation and coarsening strategy
- A reduced conjugate gradient basis method for fractional diffusion
- Algebraic multigrid methods for metric-perturbed coupled problems
- An aggregation-based two-grid method for multilevel block Toeplitz linear systems
- Iterative solution of spatial network models by subspace decomposition
- Fast algebraic multigrid for block-structured dense systems arising from nonlocal diffusion problems
- Jet: multilevel graph partitioning on graphics processing units
- On the asymptotic optimality of spectral coarse spaces
- Preconditioners for Krylov subspace methods: An overview
- A hybrid iterative method based on MIONet for PDEs: theory and numerical examples
- Algebraic multigrid methods with F-smoothing
This page was built for publication: Algebraic multigrid methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4594246)
