×
Vassilevski, Panayot S.; Yang, Ulrike Meier

Reducing communication in algebraic multigrid using additive variants. (English) Zbl 1340.65304

Numer. Linear Algebra Appl. 21, No. 2, 275-296 (2014).
The authors consider in the paper an additive algebraic multigrid (AMG) variant, which exhibits identical convergence behavior to multiplicative AMG, and several new variants of this method that are less expensive but still exhibit very good convergence properties. They analyze their computational, and communication costs, as well as memory requirements. They show improved solve times for the new variants over multiplicative AMG on a parallel computer. The results also show that these new AMG variants are effective at aleviating the difficulties caused by the increased size of coarse grid stencils typical for variational AMG.
Reviewer: Constantin Popa (Constanţa)

Cited in 9 Documents

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65Y05 Parallel numerical computation

Keywords:

multiplicative multigrid; additive implementation; parallelism; reduced communication; algebraic multigrid; convergence; parallel computer

Software:

MFEM; BoomerAMG; VAMPIR; hypre
PDFBibTeX XMLCite
\textit{P. S. Vassilevski} and \textit{U. M. Yang}, Numer. Linear Algebra Appl. 21, No. 2, 275--296 (2014; Zbl 1340.65304)
Full Text: DOI Link

References:

[1] Baker, High Performance Scientific Computing: Algorithms and Applications pp 261– (2012) · doi:10.1007/978-1-4471-2437-5_13
[2] Baker A Gamblin T Schulz M Yang UM Challenges of scaling algebraic multigrid across modern multicore architectures 25th IEEE International Symposium on Parallel and Distributed Processing IPDPS 2011, Anchorage, AK, USA, 16-20 May, 2011 - Conference Proceedings 2011 275 286
[3] Baker, Lecture Notes in Computer Science 6449, in: VECPAR 2010 pp 102– (2011) · Zbl 1323.65134 · doi:10.1007/978-3-642-19328-6_12
[4] Gahvari H Baker A Schulz M Yang UM Jordan K Gropp W Modeling the performance of an algebraic multigrid cycle Proceedings of the 25th International Conference on Supercomputing 2011 172 181
[5] Bramble, Parallel multilevel preconditioners, Mathematics of Computation 55 pp 1– (1990) · Zbl 0703.65076 · doi:10.1090/S0025-5718-1990-1023042-6
[6] Greenbaum, A multigrid method for multiprocessors, Applied Mathematics and Computation 19 pp 75– (1986) · Zbl 0616.65094 · doi:10.1016/0096-3003(86)90097-4
[7] Bastian, Additive and multiplicative multi-grid - a comparison, Computing 60 pp 345– (1998) · Zbl 0908.65107 · doi:10.1007/BF02684380
[8] Chan, Multigrid Methods: Theory, Applications, and Supercomputing pp 101– (1988)
[9] Chan, Proceedings of the Fourth Copper Mountain Conference on Multigrid Methods pp 66– (1989)
[10] Tuminaro, A highly parallel multigrid-like method for the solution of the Euler equations, SIAM Journal on Scientific and Statistical Computing 13 pp 88– (1992) · Zbl 0742.76068 · doi:10.1137/0913005
[11] Matheson, Parallelism in multigrid methods: how much is too much?, International Journal of Parallel Programming 24 pp 397– (1996) · doi:10.1007/BF02583022
[12] Fournier, Multiplicative and additive parallel multigrid algorithms for the acceleration of compressible flow computations on unstructured meshes, Applied Numerical Mathematics 36 pp 401– (2001) · Zbl 1037.76033 · doi:10.1016/S0168-9274(00)00017-9
[13] Vassilevski, Multilevel Block Factorization Preconditioners: Matrix-based Analysis and Algorithms for Solving Finite Element Equations (2008) · Zbl 1170.65001
[14] Baker, Multigrid smoothers for ultraparallel computing, SIAM Journal on Scientific Computing 33 pp 2864– (2011) · Zbl 1237.65032 · doi:10.1137/100798806
[15] Kolev, Parallel auxiliary space AMG for h(curl) problems, Journal of Computational Mathematics 27 pp 604– (2009) · Zbl 1212.65128 · doi:10.4208/jcm.2009.27.5.013
[16] hypre 2.9.0b: High Performance Preconditioners http://www.llnl.gov/CASC/linear_solvers/
[17] De Sterck, Reducing complexity in parallel algebraic multigrid preconditioners, SIAM Journal on Matrix Analysis and Applications 27 pp 1019– (2006) · Zbl 1102.65034 · doi:10.1137/040615729
[18] De Sterck, Distance-two interpolation for parallel algebraic multigrid, Numerical Linear Algebra with Applications 15 pp 115– (2008) · Zbl 1212.65139 · doi:10.1002/nla.559
[19] Stüben, Multigrid (2001)
[20] Yang, On long range interpolation operators for aggressive coarsening, Numerical Linear Algebra with Applications 17 pp 453– (2010)
[21] Vampir 8.0 http://www.vampir.eu
[22] MFEM Finite Element Discretization Library v. 2.0 http://code.google.com/p/mfem/
[23] Henson, BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Applied Numerical Mathematics 41 pp 155– (2002) · Zbl 0995.65128 · doi:10.1016/S0168-9274(01)00115-5
[24] Falgout, Pursuing scalability for hypre’s conceptual interfaces, ACM Transactions on Mathematical Software 31 pp 326– (2005) · Zbl 1136.65313 · doi:10.1145/1089014.1089018
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.