On the Ideal Interpolation Operator in Algebraic Multigrid Methods

DOI10.1137/17M1162779zbMATH Open1394.65027arXiv1711.08751WikidataQ129638697 ScholiaQ129638697MaRDI QIDQ4572018FDOQ4572018

Authors: Xuefeng Xu, Chensong Zhang 

Publication date: 4 July 2018

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Abstract: Various algebraic multigrid algorithms have been developed for solving problems in scientific and engineering computation over the past decades. They have been shown to be well-suited for solving discretized partial differential equations on unstructured girds in practice. One key ingredient of algebraic multigrid algorithms is a strategy for constructing an effective prolongation operator. Among many questions on constructing a prolongation, an important question is how to evaluate its quality. In this paper, we establish new characterizations (including sufficient condition, necessary condition, and equivalent condition) of the so-called ideal interpolation operator. Our result suggests that, compared with common wisdom, one has more room to construct an ideal interpolation, which can provide new insights for designing algebraic multigrid algorithms. Moreover, we derive a new expression for a class of ideal interpolation operators.

Full work available at URL: https://arxiv.org/abs/1711.08751

Recommendations

• Interpolation Operators for Algebraic Multigrid by Local Optimization
• scientific article; zbMATH DE number 2076849
• Multiple Vector Preserving Interpolation Mappings in Algebraic Multigrid
• Efficient Algebraic Multigrid Algorithms and Their Convergence
• scientific article; zbMATH DE number 1301775
• General constrained energy minimization interpolation mappings for AMG
• New interpolation formulas of using geometric assumptions in the algebraic multigrid method
• Relaxation-corrected bootstrap algebraic multigrid (\(r\)BAMG).
• On the algebraic multigrid method
• Element-free AMGe: General algorithms for computing interpolation weights in AMG

zbMATH Keywords

coarseningideal interpolationsymmetric positive definite matrixalgebraic multigridsmootherpropagation operator

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Iterative numerical methods for linear systems (65F10)

Cites Work

• Iterative Methods by Space Decomposition and Subspace Correction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Iterative solution of large sparse systems of equations
• Multilevel Block Factorization Preconditioners
• Spectral AMGe ($\rho$AMGe)
• Algebraic multigrid theory: The symmetric case
• Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
• An improved convergence analysis of smoothed aggregation algebraic multigrid.
• Convergence of algebraic multigrid based on smoothed aggregation
• Robustness and Scalability of Algebraic Multigrid
• Algebraic multigrid based on element interpolation (AMGe)
• On two‐grid convergence estimates
• Title not available (Why is that?)
• AMGe based on element agglomeration
• On Generalizing the Algebraic Multigrid Framework
• Algebraic multigrid methods
• Convergence Analysis of Perturbed Two‐Grid and Multigrid Methods
• Algebraic Theory of Two-Grid Methods
• Optimal interpolation and compatible relaxation in classical algebraic multigrid
• A two-grid SA-AMG convergence bound that improves when increasing the polynomial degree.

Cited In (10)

• Convergence analysis of inexact two-grid methods: a theoretical framework
• Interpolation Operators for Algebraic Multigrid by Local Optimization
• A supplementary strategy for coarsening in algebraic multigrid
• Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time
• Nonsymmetric algebraic multigrid based on local approximate ideal restriction (\(\ell\)AIR)
• On long-range interpolation operators for aggressive coarsening
• Parallel Energy-Minimization Prolongation for Algebraic Multigrid
• Nonsymmetric reduction-based algebraic multigrid
• A New Analytical Framework for the Convergence of Inexact Two-Grid Methods
• Convergence of VW-cycle and WV-cycle multigrid methods

This page was built for publication: On the Ideal Interpolation Operator in Algebraic Multigrid Methods

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