×

BoomerAMG: A parallel algebraic multigrid solver and preconditioner. (English) Zbl 0995.65128

Summary: Driven by the need to solve linear systems arising from problems posed on extremely large, unstructured grids, there has been a recent resurgence of interest in algebraic multigrid (AMG). AMG is attractive in that it holds out the possibility of multigrid-like performance on unstructured grids. The sheer size of many modern physics and simulation problems has led to the development of massively parallel computers, and has sparked much research into developing algorithms for them. Parallelizing AMG is a difficult task, however. While much of the AMG method parallelizes readily, the process of coarse-grid selection, in particular, is fundamentally sequential in nature.
We have previously introduced a parallel algorithm [cf. A. J. Cleary, R. D. Falgout, V. E. Henson and J. E. Jones, Coarse grid selection for parallel algebraic multigrid, in: A. Ferriera, J. Rollin, H. Simon, S.-H. Teng (eds.), Proceedings of the Fifth International Symposium on Solving Irregularly Structured Problems in Parallel, Lecture Notes in Computer Science, Vol. 1457, Springer, New York (1998)] for the selection of coarse-grid points, based on modifications of certain parallel independent set algorithms and the application of heuristic designed to insure the quality of the coarse grids, and shown results from a prototype serial version of the algorithm.
In this paper we describe an implementation of a parallel AMG code, using the algorithm of A. J. Cleary, R. D. Falgout and V. E. Henson [loc. cit.] as well as other approaches to parallelizing the coarse-grid selection. We consider three basic coarsening schemes and certain modifications to the basic schemes, designed to address specific performance issues. We present numerical results for a broad range of problem sizes and descriptions, and draw conclusion regarding the efficacy of the method. Finally, we indicate the current directions of the research.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N06 Finite difference methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J25 Boundary value problems for second-order elliptic equations
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65Y05 Parallel numerical computation

Software:

BoomerAMG; AMG2013
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] A. Brandt, Algebraic multigrid theory: The symmetric case, in: Preliminary Proceedings for the International Multigrid Conference, Copper Mountain, CO, April 1983 · Zbl 0616.65037
[2] Brandt, A., Algebraic multigrid theory: the symmetric case, Appl. math. comput., 19, 23-56, (1986) · Zbl 0616.65037
[3] A. Brandt, S.F. McCormick, J.W. Ruge, Algebraic multigrid (AMG) for automatic multigrid solutions with application to geodetic computations, Report, Inst. for Computational Studies, Fort Collins, CO, October 1982
[4] Brandt, A.; McCormick, S.F.; Ruge, J.W., Algebraic multigrid (AMG) for sparse matrix equations, () · Zbl 0548.65014
[5] Brezina, M.; Cleary, A.J.; Falgout, R.D.; Henson, V.E.; Jones, J.E.; Manteuffel, T.A.; McCormick, S.F.; Ruge, J.W., Algebraic multigrid based on element interpolation (amge), SIAM J. sci. comput., 22, 1570-1592, (2000) · Zbl 0991.65133
[6] Briggs, W.L.; Henson, V.E.; McCormick, S.F., A multigrid tutorial, (2000), SIAM Philadelphia, PA · Zbl 0958.65128
[7] Cleary, A.J.; Falgout, R.D.; Henson, V.E.; Jones, J.E., Coarse grid selection for parallel algebraic multigrid, () · Zbl 0991.65133
[8] Cleary, A.J.; Falgout, R.D.; Henson, V.E.; Jones, J.E.; Manteuffel, T.A.; McCormick, S.F.; Miranda, G.N.; Ruge, J.W., Robustness and scalability of algebraic multigrid, SIAM J. sci. comput., 21, 1886-1908, (2000) · Zbl 0959.65049
[9] Golubovici, G.; Popa, C., Interpolation and related coarsening techniques for the algebraic multigrid method, (), 201-213 · Zbl 0809.65116
[10] Jones, J.E.; McCormick, S.F., Parallel multigrid methods, () · Zbl 0865.65088
[11] Jones, M.T.; Plassman, P.E., A parallel graph coloring heuristic, SIAM J. sci. comput., 14, 654-669, (1993) · Zbl 0772.68046
[12] Krechel, A.; Stüben, K., Parallel algebraic multigrid based on subdomain blocking, Parallel comput., 27, 1009-1031, (2001), also: GMD Report 71, GMD, Sankt Augustin, Germany · Zbl 0971.68215
[13] Luby, M., A simple parallel algorithm for the maximal independent set problem, SIAM J. comput., 15, 1036-1053, (1986) · Zbl 0619.68058
[14] Ruge, J.W.; Stüben, K., Efficient solution of finite difference and finite element equations by algebraic multigrid (AMG), (), 169-212
[15] Ruge, J.W.; Stüben, K., Algebraic multigrid (AMG), (), 73-130
[16] Stüben, K., Algebraic multigrid (AMG): experiences and comparisons, Appl. math. comput., 13, 419-452, (1983) · Zbl 0533.65064
[17] Stüben, K., Algebraic multigrid (AMG): an introduction with applications, () · Zbl 0979.65111
[18] Stüben, K.; Trottenberg, U.; Witsch, K., Software development based on multigrid techniques, ()
[19] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid based on smoothed aggregation for second and fourth order problems, Computing, 56, 179-196, (1996) · Zbl 0851.65087
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.