CRAMG: A Communication-Reduced Algebraic Multigrid Method

Algebraic multigrid (AMG) is widely used to accelerate large-scale sparse linear solvers. In distributed environments, neighboring communication overhead in AMG significantly impacts overall solution time. We propose Communication-Reduced Algebraic Multigrid (CRAMG) methods to minimize inter-process data exchange and message count by fusing interpolation/restriction operators with residual computations. This reduces communication frequency from four per level to as few as two. Experiments show up to 45% reduction in data exchange and 35% fewer messages. Performance evaluations on an Intel platform demonstrate significant improvements over classical multiplicative AMG and the mult-additive version in the Hypre package.

• Publication year

  2025

• Venue

  International Conference on Supercomputing

• Publication date

  2025-06-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3721145.3725764
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimizing SpMV on Heterogeneous Multi-Core DSPs through Improved Locality and Vectorization

  2024cited by this paper
• Optimizing Multi-grid Computation and Parallelization on Multi-cores

  2023cited by this paper
• Optimizing MPI Collectives on Shared Memory Multi-Cores

  2023cited by this paper
• Optimizing Irregular Communication with Neighborhood Collectives and Locality-Aware Parallelism

  2023cited by this paper
• AlphaSparse: Generating High Performance SpMV Codes Directly from Sparse Matrices

  2022cited by this paper
• Enabling and Scaling the HPCG Benchmark on the Newest Generation Sunway Supercomputer with 42 Million Heterogeneous Cores

  2021cited by this paper
• A Recursive Algebraic Coloring Technique for Hardware-efficient Symmetric Sparse Matrix-vector Multiplication

  2020cited by this paper
• Reducing communication in algebraic multigrid with multi-step node aware communication

  2019cited by this paper
• PETSc Users Manual: Revision 3.11

  2019cited by this paper
• Asynchronous Multigrid Methods

  2019cited by this paper
• Exploiting Common Neighborhoods to Optimize MPI Neighborhood Collectives

  2017cited by this paper
• Reducing Parallel Communication in Algebraic Multigrid through Sparsification

  2015cited by this paper
• Reducing communication in algebraic multigrid using additive variants

  2014influential reference
• Non-Galerkin Coarse Grids for Algebraic Multigrid

  2014cited by this paper
• s-Step Krylov Subspace Methods as Bottom Solvers for Geometric Multigrid

  2014cited by this paper
• An Effective Method for Parameter Estimation with PDE Constraints with Multiple Right-Hand Sides

  2012cited by this paper
• Multigrid Smoothers for Ultraparallel Computing

  2011cited by this paper
• Improving communication performance in dense linear algebra via topology aware collectives

  2011cited by this paper
• Scaling Hypre's Multigrid Solvers to 100, 000 Cores

  2011cited by this paper
• Challenges of Scaling Algebraic Multigrid Across Modern Multicore Architectures

  2011cited by this paper
• The university of Florida sparse matrix collection

  2011cited by this paper
• On long‐range interpolation operators for aggressive coarsening

  2009cited by this paper
• Multilevel Block Factorization Preconditioners: Matrix-based Analysis and Algorithms for Solving Finite Element Equations

  2008cited by this paper
• Distance-two interpolation for parallel algebraic multigrid

  2007cited by this paper
• Algebraic Multigrid

  2007cited by this paper
• An overview of the Trilinos project

  2005cited by this paper
• On the use of relaxation parameters in hybrid smoothers

  2004cited by this paper
• Reducing Complexity in Parallel Algebraic Multigrid Preconditioners

  2004cited by this paper
• A block LU-SGS implicit dual time-stepping algorithm for hybrid dynamic meshes

  2003cited by this paper
• Iterative methods for sparse linear systems

  2003cited by this paper
• hypre: A Library of High Performance Preconditioners

  2002cited by this paper
• Multiplicative and additive parallel multigrid algorithms for the acceleration of compressible flow computations on unstructured meshes

  2001cited by this paper
• Parallel Smoothed Aggregation Multigrid : Aggregation Strategies on Massively Parallel Machines

  2000cited by this paper
• Algebraic Multigrid (AMG) : An Introduction With Applications

  2000cited by this paper
• Convergence of algebraic multigrid based on smoothed aggregation

  1998cited by this paper
• Parmetis parallel graph partitioning and sparse matrix ordering library

  1997cited by this paper
• Parallel multilevel preconditioners

  1990cited by this paper
• A multigrid tutorial

  1987cited by this paper

• A Diagonal Block Memory-Aware Polynomial Preconditioner for Linear and Eigenvalue Solvers

  2026cites this paper