Parallel Energy-Minimization Prolongation for Algebraic Multigrid

DOI10.1137/22M1513794arXiv2208.02995OpenAlexW4387060712MaRDI QIDQ6074545FDOQ6074545

Authors: C. Janna, Andrea Franceschini, Jacob B. Schroder, Luke Olson 

Publication date: 12 October 2023

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: Algebraic multigrid (AMG) is one of the most widely used solution techniques for linear systems of equations arising from discretized partial differential equations. The popularity of AMG stems from its potential to solve linear systems in almost linear time, that is with an O(n) complexity, where n is the problem size. This capability is crucial at the present, where the increasing availability of massive HPC platforms pushes for the solution of very large problems. The key for a rapidly converging AMG method is a good interplay between the smoother and the coarse-grid correction, which in turn requires the use of an effective prolongation. From a theoretical viewpoint, the prolongation must accurately represent near kernel components and, at the same time, be bounded in the energy norm. For challenging problems, however, ensuring both these requirements is not easy and is exactly the goal of this work. We propose a constrained minimization procedure aimed at reducing prolongation energy while preserving the near kernel components in the span of interpolation. The proposed algorithm is based on previous energy minimization approaches utilizing a preconditioned restricted conjugate gradients method, but has new features and a specific focus on parallel performance and implementation. It is shown that the resulting solver, when used for large real-world problems from various application fields, exhibits excellent convergence rates and scalability and outperforms at least some more traditional AMG approaches.

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

Recommendations

• A general interpolation strategy for algebraic multigrid using energy minimization
• Parallel performance of algebraic multigrid domain decomposition
• Parallel algebraic multigrid methods: state-of-the art and challenges for extreme-scale applications
• scientific article; zbMATH DE number 5049875
• Reducing parallel communication in algebraic multigrid through sparsification

zbMATH Keywords

preconditioningenergy minimizationAMGprolongationalgebraic multigrid

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Parallel algorithms in computer science (68W10) PDE constrained optimization (numerical aspects) (49M41)

Cites Work

• Chronos: a general purpose classical AMG solver for high performance computing
• How to find a good submatrix
• Numerical solution of saddle point problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Multigrid Tutorial, Second Edition
• Multilevel Block Factorization Preconditioners
• An Energy-minimizing Interpolation for Robust Multigrid Methods
• Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
• Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
• Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid
• Bootstrap AMG
• A New Petrov–Galerkin Smoothed Aggregation Preconditioner for Nonsymmetric Linear Systems
• Semi-optimal bases for linear dependencies
• Energy optimization of algebraic multigrid bases
• A new perspective on strength measures in algebraic multigrid
• A general interpolation strategy for algebraic multigrid using energy minimization
• Non-Galerkin coarse grids for algebraic multigrid
• On Generalizing the Algebraic Multigrid Framework
• Algebraic multigrid methods
• Compatible relaxation and coarsening in algebraic multigrid
• Algebraic distance for anisotropic diffusion problems: multilevel results
• Adaptive reduction-based AMG
• Improving algebraic multigrid interpolation operators for linear elasticity problems
• A novel algebraic multigrid approach based on adaptive smoothing and prolongation for ill-conditioned systems
• Nonsymmetric reduction-based algebraic multigrid
• Optimal interpolation and compatible relaxation in classical algebraic multigrid
• Nonsymmetric algebraic multigrid based on local approximate ideal restriction (\(\ell\)AIR)
• On the Ideal Interpolation Operator in Algebraic Multigrid Methods
• A root-node-based algebraic multigrid method

Cited In (4)

• A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints
• Learning-based local weighted least squares for algebraic multigrid method
• A multigrid reduction framework for domains with symmetries
• Energy optimization of algebraic multigrid bases

This page was built for publication: Parallel Energy-Minimization Prolongation for Algebraic Multigrid

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