Reducing parallel communication in algebraic multigrid through sparsification
From MaRDI portal
Abstract: Algebraic multigrid (AMG) is an solution process for many large sparse linear systems. A hierarchy of progressively coarser grids is constructed that utilize complementary relaxation and interpolation operators. High-energy error is reduced by relaxation, while low-energy error is mapped to coarse-grids and reduced there. However, large parallel communication costs often limit parallel scalability. As the multigrid hierarchy is formed, each coarse matrix is formed through a triple matrix product. The resulting coarse-grids often have significantly more nonzeros per row than the original fine-grid operator, thereby generating high parallel communication costs on coarse-levels. In this paper, we introduce a method that systematically removes entries in coarse-grid matrices after the hierarchy is formed, leading to an improved communication costs. We sparsify by removing weakly connected or unimportant entries in the matrix, leading to improved solve time. The main trade-off is that if the heuristic identifying unimportant entries is used too aggressively, then AMG convergence can suffer. To counteract this, the original hierarchy is retained, allowing entries to be reintroduced into the solver hierarchy if convergence is too slow. This enables a balance between communication cost and convergence, as necessary. In this paper we present new algorithms for reducing communication and present a number of computational experiments in support.
Recommendations
- Reducing communication costs for sparse matrix multiplication within algebraic multigrid
- Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
- Non-Galerkin multigrid based on sparsified smoothed aggregation
- Reducing communication in algebraic multigrid using additive variants.
- A new grid-coarsening algorithm for parallel algebraic multigrid method
Cites work
- \textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
- A general framework for graph sparsification
- A new perspective on strength measures in algebraic multigrid
- Black box multigrid
- Black box multigrid for nonsymmetric problems
- Collocation coarse approximation in multigrid
- Distance-two interpolation for parallel algebraic multigrid
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 3874483 (Why is no real title available?)
- scientific article; zbMATH DE number 4078693 (Why is no real title available?)
- Improved spectral sparsification and numerical algorithms for SDD matrices
- Multigrid Methods for Variational Problems
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Non-Galerkin coarse grids for algebraic multigrid
- Non-Galerkin multigrid based on sparsified smoothed aggregation
- On long-range interpolation operators for aggressive coarsening
- On the Performance of an Algebraic Multigrid Solver on Multicore Clusters
- Parallel coarse-grid selection
- Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
- Sparse matrix approximations for multigrid methods
Cited in
(25)- A filter in constructing the preconditioner for solving linear equation systems of radiation diffusion problems
- A two-scale approach for efficient on-the-fly operator assembly in massively parallel high performance multigrid codes
- A supplementary strategy for coarsening in algebraic multigrid
- Reducing communication costs for sparse matrix multiplication within algebraic multigrid
- Non-Galerkin coarse grids for algebraic multigrid
- Sparse matrix-vector multiply algorithm based on overlapping computation and communication and application in AMG
- scientific article; zbMATH DE number 2089164 (Why is no real title available?)
- Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution
- Non-Galerkin multigrid based on sparsified smoothed aggregation
- Nonsymmetric algebraic multigrid based on local approximate ideal restriction (AIR)
- Preparing sparse solvers for exascale computing
- Parallel performance of algebraic multigrid domain decomposition
- A New Analytical Framework for the Convergence of Inexact Two-Grid Methods
- Chronos: a general purpose classical AMG solver for high performance computing
- A Comparison of Classical and Aggregation-Based Algebraic Multigrid Preconditioners for High-Fidelity Simulation of Wind Turbine Incompressible Flows
- Nonsymmetric reduction-based algebraic multigrid
- Reducing communication in algebraic multigrid using additive variants.
- A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations
- Parallelisation of selective algebraic multigrid for block-pressure-velocity system in OpenFOAM
- Parallel Energy-Minimization Prolongation for Algebraic Multigrid
- Automated tuning for the parameters of linear solvers
- On the Recursive Structure of Multigrid Cycles
- Recent advancements in preconditioning techniques for large size linear systems suited for high performance computing
- Reducing operator complexity of Galerkin coarse-grid operators with machine learning
- A nonoverlapping spectral additive Schwarz method for interior penalty discontinuous Galerkin discretizations of Anisotropic Elliptic Problems
This page was built for publication: Reducing parallel communication in algebraic multigrid through sparsification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830618)
