Algebraic multigrid techniques for discontinuous Galerkin methods with varying polynomial order. (English) Zbl 1396.65151

Summary: We present a parallel algebraic multigrid (AMG) algorithm for the implicit solution of the Darcy problem discretized by the discontinuous Galerkin (DG) method that scales optimally for regular and irregular meshes. The main idea centers on recasting the preconditioning problem so that existing AMG solvers for nodal lower order finite elements can be leveraged. This is accomplished by a transformation operator which maps the solution from a Lagrange basis representation to a Legendre basis representation. While this mapping function must be user supplied, we demonstrate how easily it can be constructed for somepopular finite element representations includingquadrilateral/hexahedral and triangular/tetrahedral DG formulations. Furthermore, we show that the mapping does not depend on the Jacobian transformation between reference and physical space and so it can be constructed with very limited mesh information. Parallel performance studies demonstrate the versatility of this approach.


65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
35Q86 PDEs in connection with geophysics
76E20 Stability and instability of geophysical and astrophysical flows
Full Text: DOI


[1] Antonietti, P; Ayuso, B, Two-level Schwarz preconditioners for super penalty discontinuous Galerkin methods, Commun. Comput. Phys., 5, 398-412, (2009) · Zbl 1364.65235
[2] Arnold, DN; Brezzi, F; Cockburn, B; Marini, LD, Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM J. Numer. Anal., 39, 1749-1779, (2002) · Zbl 1008.65080
[3] Atkins, H., Helenbrook, B.: Application of \(p\)-multigrid to discontinuous Galerkin formulations of the Poisson operator. In: AIAA Computational Fluid Dynamics Conference (2005) · Zbl 0992.65139
[4] Ayuso De Dios, B; Zikatanov, L, Uniformly convergent iterative methods for discontinuous Galerkin discretizations, J. Sci. Comput., 40, 4-36, (2009) · Zbl 1203.65242
[5] Barker, A; Brenner, S; Sung, L, Overlapping Schwarz domain decomposition preconditioners for the local discontinuous Galerkin method for elliptic problems, J. Numer. Math. Appl., 19, 165-187, (2011) · Zbl 1232.65164
[6] Bastian, P; Blatt, M; Scheichl, R, Algebraic multigrid for discontinuous Galerkin discretizations of heterogeneous elliptic problems, Numer. Linear Algebra Appl., 19, 367-388, (2012) · Zbl 1274.65313
[7] Beck, R.: Algebraic multigrid by component splitting for edge elements on simplicial triangulations. Tech. Rep. SC 99-40, Zuse Institute, Berlin (1999) · Zbl 1203.65242
[8] Blackford, L; Demmel, J; Dongarra, J; Duff, I; Hammarling, S; Henry, G; Heroux, M; Kaufman, L; Lumsdaine, A; Petitet, A; Pozo, R; Remington, K; Whaley, R, An updated set of basic linear algebra subprograms (BLAS), ACM Trans. Math. Soft., 28, 135-151, (2002) · Zbl 1070.65520
[9] Bochev, PB; Hu, JJ; Siefert, CM; Tuminaro, RS, An algebraic multigrid approach based on a compatible gauge reformulation of maxwell’s equations, SIAM J. Sci. Comput., 31, 557-583, (2008) · Zbl 1184.78007
[10] Brandt, A; McCormick, SF; Ruge, JW; Evans, DJ (ed.), Algebraic multigrid (AMG) for sparse matrix equations, 257-284, (1984), Cambridge
[11] Brenner, S; Zhao, J, Convergence of multigrid algorithms for interior penalty methods, Appl. Numer. Anal. Comput. Math., 2, 3-18, (2005) · Zbl 1073.65117
[12] Briggs, W.L., Henson, V.E., McCormick, S.: A multigrid tutorial, 2nd edn. SIAM, Philadelphia (2000) · Zbl 0958.65128
[13] Clees, T.: AMG strategies for PDE systems with applications in industrial semiconductor simulation. PhD thesis, University of Koln (2005) · Zbl 1200.35059
[14] C. Development Team: CUBIT geometry and meshing toolkit. Version 13.2 (2012)
[15] Dobrev, VA; Lazarov, RD; Vassilevski, PS; Zikatanov, LT, Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations, Numer. Linear Algebra Appl., 13, 753-770, (2006) · Zbl 1224.65263
[16] Dubiner, M, Spectral methods on triangles and other domains, J. Sci. Comput., 6, 345-390, (1991) · Zbl 0742.76059
[17] Fidkowski, KJ; Oliver, TA; Lu, J; Darmofal, DL, P-multigrid solution of high-order discontinuous Galerkin discretizations of the compressible Navier-Stokes equations, J. Comput. Phys., 207, 92-113, (2005) · Zbl 1177.76194
[18] Füllenbach, T, Stüben, K.: Algebraic multigrid for selected PDE systems. In: Proceedings of the Fourth European Conference on Elliptic and Parabolic Problems, pp. 399-410 (2002) · Zbl 1048.65110
[19] Gee, M., Hu, J., Sala, M., Siefert, C., Tuminaro, R.: ML 5.0 smoothed aggregation user’s guide. Tech. Rep. SAND2006-2649, Sandia National Laboratories (2007)
[20] Gee, M., Siefert, C., Hu, J., Tuminaro, R., Sala, M.: ML 5.0 smoothed aggregation user’s guide, Tech. Rep. SAND2006-2649, Sandia National Laboratories (2006) · Zbl 1391.65181
[21] Gerstenberger, A., Scovazzi, G., Collis, S.S.: Computing gravity-driven viscous fingering in complex subsurface geometries: a high-order discontinuos Galerkin approach, Computational Geosciences, (submitted) · Zbl 1382.86003
[22] Gopalakrishnan, J; Kanschat, G, A multilevel discontinuous Galerkin method, Numer. Math., 95, 527-550, (2003) · Zbl 1044.65084
[23] Hackbusch, W.: Multigrid Methods and Applications, Vol. 4 of Computational Mathematics. Springer, Berlin (1985) · Zbl 0577.65118
[24] Hageman, L., Young, D.: Applied Iterative Methods. Academic Press, New York (1981) · Zbl 0459.65014
[25] Hemker, PW; Hoffmann, W; Raalte, MHv, Two-level Fourier analysis of a multigrid approach for discontinuous Galerkin discretization, SIAM J. Sci. Comput., 25, 1018-1041, (2003) · Zbl 1048.65108
[26] Henson, VE; Yang, UM, Boomeramg: a parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math. Trans. IMACS, 41, 155-177, (2002) · Zbl 0995.65128
[27] Heroux, M., Bartlett, R., Hoekstra, V.H.R., Hu, J., Kolda, T., Lehoucq, R., Long, K., Pawlowski, R., Phipps, E., Salinger, A., Thornquist, H., Tuminaro, R., Willenbring, J., Williams, A.: An overview of Trilinos. Tech. Rep. SAND2003-2927, Sandia National Laboratories (2003) · Zbl 1136.65354
[28] Hiptmair, R; Xu, J, Nodal auxiliary space preconditioning in H(curl) and H(div) spaces, SIAM J. Numer. Anal., 45, 2483-2509, (2007) · Zbl 1153.78006
[29] Jones, JE; Vassilevski, PS, Amge based on element agglomeration, SIAM J. Sci. Comput., 23, 109-133, (2001) · Zbl 0992.65140
[30] Kanschat, G, Preconditioning methods for local discontinuous Galerkin discretizations, SIAM J. Sci. Comput., 25, 815-831, (2003) · Zbl 1048.65110
[31] Kanschat, G, Robust smoothers for high-order discontinuous Galerkin discretizations of advection-diffusion problems, J. Comput. Appl. Math., 218, 53-60, (2008) · Zbl 1143.65097
[32] Kolev, T., Pasciak, J., Vassilevski, P.: H(curl) auxiliary mesh preconditioning. Tech. Rep. UCRL-JRNL-224227, Lawrence Livermore National Labs (2006) · Zbl 1212.65490
[33] Kolev, T., Vassilevski, P.: Parallel H1-based auxiliary space AMG solver for H(curl) problems. Tech. Rep. UCRL-TR-222763, Lawrence Livermore National Labs (2006) · Zbl 1364.65235
[34] Kolev, T., Vassilevski, P.: Some experience with a H1-based auxiliary space AMG for H(curl) problems. Tech. Rep. UCRL-TR-21841, Lawrence Livermore National Labs (2006) · Zbl 1008.65080
[35] Nastase, C., Mavriplis, D.: A parallel hp-multigrid solver for three-dimensional discontinuous Galerkin discretizations of the Euler equations. AIAA Paper 512 (2007)
[36] L. Olson, Algebraic multigrid preconditioning of high-order spectral elements for elliptic problems on a simplicial mesh, SIAM J. Sci. Comput., 29, 2189-2209 (electronic), (2007) · Zbl 1149.65094
[37] Olson, LN; Schroder, JB, Smoothed aggregation multigrid solvers for high-order discontinuous Galerkin methods for elliptic problems, J. Comput. Phys., 230, 6959-6976, (2011) · Zbl 1252.65200
[38] Prill, F; Lukáčová-Medvidóvá, M; Hartmann, R, Smoothed aggregation multigrid for the discontinuous Galerkin method, SIAM J. Sci. Comput., 31, 3503-3528, (2009) · Zbl 1200.35059
[39] Prometheus. http://www.columbia.edu/ma2325/prometheus/ · Zbl 1177.76194
[40] Tuminaro, JXRS; Zhu, Y; Widlund, O (ed.); Keyes, DE (ed.), Auxiliary space preconditioners for mixed finite element methods, 99-109, (2009), Berlin · Zbl 1183.65151
[41] Ruge, JW; Stüben, K; McCormick, SF (ed.), Algebraic multigrid (AMG), 73-130, (1987), Philadelphia
[42] Ruge, JW; Stüben, K; McCormick, SF (ed.), Algebraic multigrid (AMG), 73-130, (1987), Philadelphia
[43] Scovazzi, G., Gerstenberger, A., Collis, S.S.: A discontinuous Galerkin method for gravity-driven viscous fingering instabilities in porous media. J. Comput. Phys. (2012) · Zbl 1286.76152
[44] Shahbazi, K; Mavriplis, DJ; Burgess, NK, Multigrid algorithms for high-order discontinuous Galerkin discretizations of the compressible Navier-Stokes equations, J. Comput. Phys., 228, 7917-7940, (2009) · Zbl 1391.65181
[45] Sherwin, S; Karniadakis, G, A new triangular and tetrahedral basis for high-order (hp) finite element methods, Int. J. Numer. Methods Eng., 38, 3775-3802, (1995) · Zbl 0837.73075
[46] Trottenberg, U., Oosterlee, C., Schüller, A.: Multigrid. Academic, London (2001)
[47] Vaněk, P; Brezina, M; Mandel, J, Convergence of algebraic multigrid based on smoothed aggregation, Numer. Math., 88, 559-579, (2001) · Zbl 0992.65139
[48] Vaněk, P; Mandel, J; Brezina, M, Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 179-196, (1996) · Zbl 0851.65087
[49] Xu, J, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56, 215-235, (1996) · Zbl 0857.65129
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.