Smoothed aggregation multigrid solvers for high-order discontinuous Galerkin methods for elliptic problems. (English) Zbl 1252.65200

Summary: We develop a smoothed aggregation-based algebraic multigrid solver for high-order discontinuous Galerkin discretizations of the Poisson problem. The algebraic multigrid solver is a popular and effective method for solving the sparse linear systems that arise from discretizing partial differential equations. However, high-order discontinuous Galerkin discretizations have proved to be challenging for the algebraic multigrid solver. The increasing condition number of the matrix and the loss of locality in the matrix stencil as \(p\) increases, in addition to the effect of weakly enforced Dirichlet boundary conditions, all contribute to the challenging algebraic setting.
We propose a smoothed aggregation approach that addresses these difficulties. In particular, the approach effectively coarsens degrees-of-freedom centered at the same spatial location as well as degrees-of-freedom at the domain boundary. Moreover, the character of the near null-space, particularly at the domain boundary, is captured by interpolation. One classic prolongation smoothing step of weighted-Jacobi relaxation is also shown to be ineffective at high order, and a more robust energy-minimization approach is used, along with block relaxation that more directly utilizes the block diagonal structure of the discontinuous Galerkin discretization. Finally, we conclude by examining numerical results in support our method.


65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
Full Text: DOI


[1] Lottes, J.W.; Fischer, P.F., Hybrid multigrid/Schwarz algorithms for the spectral element method, J. sci. comput., 24, 45-78, (2005) · Zbl 1078.65570
[2] Olson, L., Algebraic multigrid preconditioning of high-order spectral elements for elliptic problems on a simplicial mesh, SIAM J. sci. comput., 29, 5, 2189-2209, (2007) · Zbl 1149.65094
[3] Heys, J.J.; Manteuffel, T.A.; McCormick, S.F.; Olson, L.N., Algebraic multigrid for higher-order finite elements, J. comput. phys., 204, 2, 520-532, (2005) · Zbl 1060.65673
[4] Castillo, P., Performance of discontinuous Galerkin methods for elliptic pdes, SIAM J. sci. comput., 24, 2, 524-547, (2002) · Zbl 1021.65054
[5] Brezzi, F.; Manzini, G.; Marini, D.; Pietra, P.; Russo, A., Discontinuous Galerkin approximations for elliptic problems, Numer. meth. partial diff. eq., 16, 365-378, (2000) · Zbl 0957.65099
[6] Arnold, D.N.; Brezzi, F.; Cockurn, B.; Marini, L.D., Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM J. numer. anal., 39, 1749-1779, (2002) · Zbl 1008.65080
[7] Cockburn, B.; Gopalakrishnan, J.; Lazarov, R., Unified hybridization of discontinuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems, SIAM J. numer. anal., 47, 2, 1319-1365, (2009) · Zbl 1205.65312
[8] Nguyen, N.C.; Peraire, J.; Cockburn, B., A hybridizable discontinuous Galerkin method for Stokes flow, Comput. methods appl. mech. eng., 199, 9-12, 582-597, (2010) · Zbl 1227.76036
[9] Jeon, Y.; Park, E.., A hybrid discontinuous Galerkin method for elliptic problems, SIAM J. numer. anal., 48, 5, 1968-1983, (2010) · Zbl 1220.65164
[10] Kanschat, G., Preconditioning methods for local discontinuous Galerkin discretizations, SIAM J. sci. comput., 25, 3, 815-831, (2003) · Zbl 1048.65110
[11] Kanschat, G., Robust smoothers for high-order discontinuous Galerkin discretizations of advection – diffusion problems, J. comput. appl. math., 218, 1, 53-60, (2008), (special Issue: Finite Element Methods in Engineering and Science (FEMTEC 2006)) · Zbl 1143.65097
[12] Atkins, H.; Helenbrook, B., Application of p-multigrid to discontinuous Galerkin formulations of the Poisson operator, Aiaa j., 44, 3, 566-575, (2005)
[13] Fidkowski, K.J.; Oliver, T.A.; Lu, J.; Darmofal, D.L., p-multigrid solution of high-order discontinuous Galerkin discretizations of the compressible navier – stokes equations, J. comput. phys., 207, 1, 92-113, (2005) · Zbl 1177.76194
[14] Dobrev, V.A.; Lazarov, R.D.; Vassilevski, P.S.; Zikatanov, L.T., Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations, Numer. linear algebra appl., 13, 9, 753-770, (2006) · Zbl 1224.65263
[15] Gopalakrishnan, J.; Kanschat, G., A multilevel discontinuous Galerkin method, Numer. math., 95, 3, 527-550, (2003) · Zbl 1044.65084
[16] Hemker, P.W.; Hoffmann, W.; Raalte, M.H. v., Two-level Fourier analysis of a multigrid approach for discontinuous Galerkin discretizations, SIAM J. sci. comput., 25, 3, 1018-1041, (2003) · Zbl 1048.65108
[17] Prill, F.; Lukáčová-Medviďová, M.; Hartmann, R., Smoothed aggregation multigrid for the discontinuous Galerkin method, SIAM J. sci. comput., 31, 5, 3503-3528, (2009) · Zbl 1200.35059
[18] Cockburn, B.; Shu, C.-W., The local discontinuous Galerkin method for time-dependent convection – diffusion systems, SIAM J. numer. anal., 35, 6, 2440-2463, (1998) · Zbl 0927.65118
[19] Douglas, J.J.; Dupont, T., Interior penalty procedures for elliptic and parabolic Galerkin methods, (), 207-216
[20] F. Brezzi, G. Manzini, D. Marini, P. Pietra, A. Russo, Discontinuous finite elements for diffusion problems, in: in Atti Convegno in onore di F. Brioschi (Milan, 1997), Instituto Lombardo, Accademia di Scienze e Lettere, Italy, 1999, pp. 197-217.
[21] Castillo, P.; Cockurn, B.; Perugia, I.; Schötzau, D., An a priori error analysis of the local discontinuous Galerkin method for elliptic problems, SIAM J. numer. anal., 38, 1676-1706, (2000) · Zbl 0987.65111
[22] Cockurn, B.; Kanschat, G.; Perugia, I.; Schötzau, D., Superconvergence of the local discontinuous Galerkin method for elliptic problems on Cartesian grids, SIAM J. numer. anal., 39, 264-285, (2001) · Zbl 1041.65080
[23] Hesthaven, J.; Warburton, T., Nodal discontinuous Galerkin methods: algorithms, analysis, and applications, () · Zbl 1134.65068
[24] McCormick, S.F.; Ruge, J.W., Multigrid methods for variational problems, SIAM J. numer. anal., 19, 5, 924-929, (1982) · Zbl 0499.65032
[25] Brezina, M.; Falgout, R.; MacLachlan, S.; Manteuffel, T.; McCormick, S.; Ruge, J., Adaptive smoothed aggregation (αSA) multigrid, SIAM rev., 47, 2, 317-346, (2005) · Zbl 1075.65042
[26] M. Brezina, T. Manteuffel, S. Mccormick, J. Ruge, G. Sanders, Towards adaptive smoothed aggregation (αSA) for nonsymmetric problems, SIAM J. Sci. Comput. · Zbl 1210.65075
[27] 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
[28] Brannick, J.; Brezina, M.; MacLachlan, S.; Manteuffel, T.; McCormick, S.; Ruge, J., An energy-based AMG coarsening strategy, Numer. linear algebra appl., 13, 2-3, 133-148, (2006) · Zbl 1174.65542
[29] Olson, L.N.; Schroder, J.B.; Tuminaro, R.S., A new perspective on strength measures in algebraic multigrid, Numer. linear algebra appl., 17, 4, 713-733, (2010) · Zbl 1240.65360
[30] L.N. Olson, J.B. Schroder, R.S. Tuminaro, A general interpolation strategy for algebraic multigrid using energy-minimization, SIAM J. Sci. Comput. Submitted. · Zbl 1233.65096
[31] Warburton, T.; Hesthaven, J.; Wilcox, L., Sledge++ users’ guide, (2006), <http://www.caam.rice.edu/timwar/TimWarburton/Sledge++.html>
[32] Vaněk, P.; Brezina, M.; Mandel, J., Convergence of algebraic multigrid based on smoothed aggregation, Numer. math., 88, 3, 559-579, (2001) · Zbl 0992.65139
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.