A nearly optimal multigrid method for general unstructured grids

DOI10.1007/S00211-015-0785-7zbMATH Open1356.65241arXiv1410.2153OpenAlexW2257046020MaRDI QIDQ728458FDOQ728458

Authors: L. Grasedyck, Lu Wang, Jinchao Xu 

Publication date: 20 December 2016

Published in: Numerische Mathematik (Search for Journal in Brave)

Abstract: In this paper, we develop a multigrid method on unstructured shape-regular grids. For a general shape-regular unstructured grid of $calO(N)$ elements, we present a construction of an auxiliary coarse grid hierarchy on which a geometric multigrid method can be applied together with a smoothing on the original grid by using the auxiliary space preconditioning technique. Such a construction is realized by a cluster tree which can be obtained in $calO(NlogN)$ operations for a grid of $N$ elements. This tree structure in turn is used for the definition of the grid hierarchy from coarse to fine. For the constructed grid hierarchy we prove that the convergence rate of the multigrid preconditioned CG for an elliptic PDE is $1-calO(1/logN)$. Numerical experiments confirm the theoretical bounds and show that the total complexity is in $calO(NlogN)$.

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

Recommendations

• The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids
• A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner
• scientific article; zbMATH DE number 1047479
• scientific article; zbMATH DE number 1218952
• scientific article; zbMATH DE number 736328

zbMATH Keywords

clusteringconvergencepreconditioningfinite elementsnumerical experimentconjugate gradient methodmultigridauxiliary spaceunstructured shape-regular grids

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Boundary value problems for second-order elliptic equations (35J25) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50)

Cites Work

• \textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite Element Interpolation of Nonsmooth Functions Satisfying Boundary Conditions
• Quad trees: A data structure for retrieval by composite keys
• Iterative Methods by Space Decomposition and Subspace Correction
• The method of alternating projections and the method of subspace corrections in Hilbert space
• On the multi-level splitting of finite element spaces
• A review of algebraic multigrid
• A coarsening algorithm on adaptive grids by newest vertex bisection and its applications
• Title not available (Why is that?)
• Optimal multilevel methods for graded bisection grids
• Parallel Multilevel Preconditioners
• New Convergence Estimates for Multigrid Algorithms
• An Optimal Order Process for Solving Finite Element Equations
• Adaptive geometrically balanced clustering of \({\mathcal H}\)-matrices
• Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
• Convergence Estimates for Multigrid Algorithms without Regularity Assumptions
• Algebraic multigrid (AMG): Experiences and comparisons
• The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids
• An improved convergence analysis of smoothed aggregation algebraic multigrid.
• Convergence of algebraic multigrid based on smoothed aggregation
• Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid
• Acceleration of convergence of a two-level algorithm by smoothing transfer operators
• Coarse grid spaces for domains with a complicated boundary
• On two‐grid convergence estimates
• Title not available (Why is that?)
• Title not available (Why is that?)
• Application of auxiliary space preconditioning in field-scale reservoir simulation
• Combined Preconditioning with Applications in Reservoir Simulation
• Fast multigrid solver
• The Analysis of Multigrid Algorithms with Nonnested Spaces or Noninherited Quadratic Forms
• A parallel auxiliary grid algebraic multigrid method for graphic processing units
• Parallel unsmoothed aggregation algebraic multigrid algorithms on GPUs
• Optimal multilevel methods for \(H\)(grad), \(H\)(curl), and \(H\)(div) systems on graded and unstructured grids
• Title not available (Why is that?)
• A New Convergence Proof for the Multigrid Method Including the V-Cycle
• Title not available (Why is that?)
• Towards algebraic multigrid for elliptic problems of second order
• AMGe based on element agglomeration
• Bridging the gap between geometric and algebraic multi-grid methods
• Multi-level iterative technique and aggregation concept with semi-analytical preconditioning for solving boundary-value problems
• On some versions of the element agglomeration AMGe method
• Title not available (Why is that?)
• On Generalizing the Algebraic Multigrid Framework

Cited In (22)

• Title not available (Why is that?)
• Unstructured geometric multigrid in two and three dimensions on complex and graded meshes
• Title not available (Why is that?)
• An unstructured multigrid method for elliptic problems
• A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints
• Title not available (Why is that?)
• Optimal-Order Nonnested Multigrid Methods for Solving Finite Element Equations I: On Quasi-Uniform Meshes
• Optimal multigrid algorithms for variable-coupling isotropic Gaussian models
• Quasi-matrix-free hybrid multigrid on dynamically adaptive Cartesian grids
• Hierarchical hybrid grids: data structures and core algorithms for multigrid
• Algebraic multigrid methods
• The image-based multiscale multigrid solver, preconditioner, and reduced order model
• Auxiliary space preconditioners for a \(C^0\) finite element approximation of Hamilton-Jacobi-Bellman equations with cordes coefficients
• An aspect ratio agglomeration multigrid for unstructured grids
• Unified Matching Grids for Multidomain Multiphysics Simulations
• An optimal piecewise cubic nonconforming finite element scheme for the planar biharmonic equation on general triangulations
• Title not available (Why is that?)
• A generic balanced-force algorithm for finite volume method on polyhedral unstructured grids with non-orthogonality
• Generalized multiresolution analysis on unstructured grids
• A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner
• An unstructured multigrid method based on geometric smoothness
• Black-box learning of multigrid parameters

Uses Software

• BoomerAMG
• SAMG

This page was built for publication: A nearly optimal multigrid method for general unstructured grids

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