×

A GPU accelerated aggregation algebraic multigrid method. (English) Zbl 1367.65049

Summary: We present an efficient, robust and fully GPU-accelerated aggregation-based algebraic multigrid preconditioning technique for the solution of large sparse linear systems. These linear systems arise from the discretization of elliptic PDEs. The method involves two stages, setup and solve. In the setup stage, hierarchical coarse grids are constructed through aggregation of the fine grid nodes. These aggregations are obtained using a set of maximal independent nodes from the fine grid nodes. We use a “fine-grain” parallel algorithm for finding a maximal independent set from a graph of strong negative connections. The aggregations are combined with a piece-wise constant (unsmooth) interpolation from the coarse grid solution to the fine grid solution, ensuring low setup and interpolation cost. The grid independent convergence is achieved by using recursive Krylov iterations (K-cycles) in the solve stage. An efficient combination of K-cycles and standard multigrid V-cycles is used as a preconditioner for Krylov iterative solvers such as generalized minimal residual and conjugate gradient. We compare the solver performance with other solvers based on smooth aggregation and classical algebraic multigrid methods.

MSC:

65F10 Iterative numerical methods for linear systems
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65Y10 Numerical algorithms for specific classes of architectures
65Y05 Parallel numerical computation

Software:

GAMPACK; SuperLU; CUDA; Thrust
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ruge, J.; Stüben, K., Algebraic multigrid, Multigrid Methods, 3, 73-130 (1987)
[2] Stüben, K., A review of algebraic multigrid, J. Comput. Appl. Math., 128, 1, 281-309 (2001) · Zbl 0979.65111
[3] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 3, 179-196 (1996) · Zbl 0851.65087
[4] Notay, Y., An aggregation-based algebraic multigrid method, Electron. Trans. Numer. Anal., 37, 6, 123-146 (2010) · Zbl 1206.65133
[5] Emans, M.; Liebmann, M.; Basara, B., Steps towards GPU accelerated aggregation AMG, (2012 11th International Symposium on Parallel and Distributed Computing. 2012 11th International Symposium on Parallel and Distributed Computing, (ISPDC) (2012), IEEE), 79-86
[6] K. Esler, V. Natoli, A. Samardzic, GAMPACK (GPU Accelerated Algebraic Multigrid Package), in: ECMOR XIII-13th European Conference on the Mathematics of Oil Recovery, 2012.; K. Esler, V. Natoli, A. Samardzic, GAMPACK (GPU Accelerated Algebraic Multigrid Package), in: ECMOR XIII-13th European Conference on the Mathematics of Oil Recovery, 2012.
[7] Bell, N.; Dalton, S.; Olson, L. N., Exposing fine-grained parallelism in algebraic multigrid methods, SIAM J. Sci. Comput., 34, 4, C123-C152 (2012) · Zbl 1253.65041
[8] Stüben, K., An introduction to algebraic multigrid, Multigrid, 413-532 (2001)
[9] Notay, Y., Aggregation-based algebraic multilevel preconditioning, SIAM J. Matrix Anal. Appl., 27, 4, 998-1018 (2006) · Zbl 1102.65053
[10] Bell, N.; Garland, M., Efficient Sparse Matrix-Vector Multiplication on CUDA, Tech. Rep., NVIDIA Technical Report NVR-2008-004 (2008), NVIDIA Corporation
[11] J. Hoberock, N. Bell, Thrust: A parallel template library, version 1.7.0 (2010). URL http://thrust.github.io/; J. Hoberock, N. Bell, Thrust: A parallel template library, version 1.7.0 (2010). URL http://thrust.github.io/
[12] Demmel, J. W.; Eisenstat, S. C.; Gilbert, J. R.; Li, X. S.; Liu, J. W.H., A supernodal approach to sparse partial pivoting, SIAM J. Matrix Anal. Appl., 20, 3, 720-755 (1999) · Zbl 0931.65022
[13] Christie, M.; Blunt, M., Tenth SPE comparative solution project: A comparison of upscaling techniques, SPE Reservoir Eval. Eng., 4, 4, 308-317 (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.