A parallel auxiliary grid algebraic multigrid method for graphic processing units

DOI10.1137/120894452zbMATH Open1275.65021arXiv1209.5421OpenAlexW1972321715MaRDI QIDQ2847754FDOQ2847754

Authors: Lu Wang, X. Hu, Jonathan Cohen, Jinchao Xu 

Publication date: 11 September 2013

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

Abstract: In this paper, we develop a new parallel auxiliary grid algebraic multigrid (AMG) method to leverage the power of graphic processing units (GPUs). In the construction of the hierarchical coarse grid, we use a simple and fixed coarsening procedure based on a region quadtree generated from an auxiliary grid. This allows us to explicitly control the sparsity patterns and operator complexities of the AMG solver. This feature provides (nearly) optimal load balancing and predictable communication patterns, which makes our new algorithm suitable for parallel computing, especially on GPU. We also design a parallel smoother based on the special coloring of the quadtree to accelerate the convergence rate and improve the parallel performance of this solver. Based on the CUDA toolkit [40], we implemented our new parallel auxiliary grid AMG method on GPU and the numerical results of this implementation demonstrate the efficiency of our new method. The results achieve an average speedup of over 4 on quasi-uniform grids and 2 on shape regular grids when compared to the AMG implementation in CUSP.

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

Recommendations

• Parallel unsmoothed aggregation algebraic multigrid algorithms on GPUs
• Accelerating algebraic multigrid solvers on NVIDIA GPUs
• Porting an aggregation-based algebraic multigrid method to GPUs
• AmgX: a library for GPU accelerated algebraic multigrid and preconditioned iterative methods
• A GPU accelerated aggregation algebraic multigrid method

zbMATH Keywords

aggregationconvergencenumerical resultsparallel algorithmfinite elementsfinite volume methodPoisson equationGPUalgebraic multigrid methodheat transfer equationgraphic processing unitauxiliary gridnonlinear AMLI-cycle

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Finite volume methods for initial value and initial-boundary value problems involving PDEs (65M08) Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs (65M55) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30)

Cited In (9)

• Preconditioning heterogeneous \(\boldsymbol{H}(\mathrm{div})\) problems by additive Schur complement approximation and applications
• Reduced basis multiscale finite element methods for elliptic problems
• Accelerating algebraic multigrid solvers on NVIDIA GPUs
• Algebraic Multigrid Using a Stencil–CSR Hybrid Format on GPUs
• Parallel unsmoothed aggregation algebraic multigrid algorithms on GPUs
• A nearly optimal multigrid method for general unstructured grids
• Toward Cost-Effective Reservoir Simulation Solvers on GPUs
• Accelerating iterative linear solvers using multiple graphical processing units
• Preconditioned GMRES solver on multiple-GPU architecture

Uses Software

• BoomerAMG
• hypre
• CUDA
• CUSP
• ML
• MAGMA
• NaSt3DGPF
• CULA
• SAMG
• GitHub

This page was built for publication: A parallel auxiliary grid algebraic multigrid method for graphic processing units

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