Coarse-grid selection using simulated annealing

DOI10.1016/J.CAM.2023.115263zbMATH Open1523.65034arXiv2105.13280OpenAlexW3164380484MaRDI QIDQ6137788FDOQ6137788

Authors: Tareq Uz Zaman, Scott P. MacLachlan, Luke Olson, M. West 

Publication date: 4 September 2023

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Abstract: Multilevel techniques are efficient approaches for solving the large linear systems that arise from discretized partial differential equations and other problems. While geometric multigrid requires detailed knowledge about the underlying problem and its discretization, algebraic multigrid aims to be less intrusive, requiring less knowledge about the origin of the linear system. A key step in algebraic multigrid is the choice of the coarse/fine partitioning, aiming to balance the convergence of the iteration with its cost. In work by MacLachlan and Saad, a constrained combinatorial optimization problem is used to define the ``best coarse grid within the setting of a two-level reduction-based algebraic multigrid method and is shown to be NP-complete. Here, we develop a new coarsening algorithm based on simulated annealing to approximate solutions to this problem, which yields improved results over the greedy algorithm developed previously. We present numerical results for test problems on both structured and unstructured meshes, demonstrating the ability to exploit knowledge about the underlying grid structure if it is available.

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

Recommendations

• A Greedy Strategy for Coarse-Grid Selection
• Modifying CLJP to select grid hierarchies with lower operator complexities and better performance
• Coarse grid classification: a parallel coarsening scheme for algebraic multigrid methods
• Parallel coarse-grid selection
• General highly accurate algebraic coarsening

zbMATH Keywords

simulated annealingcombinatorial optimizationalgebraic multigridcoarse-grid selection

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)

Cites Work

• \textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
• Title not available (Why is that?)
• Least squares quantization in PCM
• Title not available (Why is that?)
• Title not available (Why is that?)
• An overview of the Trilinos project
• On AMG methods with F-smoothing based on Chebyshev polynomials and their relation to AMGr
• An algebraic multigrid method with guaranteed convergence rate
• Title not available (Why is that?)
• Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
• The Methods of Cyclic Reduction, Fourier Analysis and the FACR Algorithm for the Discrete Solution of Poisson’s Equation on a Rectangle
• Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
• Stochastic Optimization
• An energy‐based AMG coarsening strategy
• A new perspective on strength measures in algebraic multigrid
• Placement by thermodynamic simulated annealing
• Coarsening by compatible relaxation
• A note on MGR methods
• Combinatorial optimization. Theory and algorithms
• Compatible relaxation and coarsening in algebraic multigrid
• A Greedy Strategy for Coarse-Grid Selection
• Parallel coarse-grid selection
• Adaptive reduction-based AMG
• Distance-two interpolation for parallel algebraic multigrid
• Greedy Coarsening Strategies for Nonsymmetric Problems
• Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs
• An unstructured multigrid method based on geometric smoothness
• Nonsymmetric reduction-based algebraic multigrid
• Theoretical bounds for algebraic multigrid performance: review and analysis.

Cited In (5)

• A Greedy Strategy for Coarse-Grid Selection
• Coarse-Graining Large Search Landscapes Using Massive Edge Collapse
• AIR multigrid with GMRES polynomials (AIRG) and additive preconditioners for Boltzmann transport
• Coarsening invariance and bucket-sorted independent sets for algebraic multigrid
• Collocation coarse approximation in multigrid

This page was built for publication: Coarse-grid selection using simulated annealing

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