×

\(V\)-cycle multigrid algorithms for discontinuous Galerkin methods on non-nested polytopic meshes. (English) Zbl 1410.65092

Summary: In this paper we analyze the convergence properties of \(V\)-cycle multigrid algorithms for the numerical solution of the linear system of equations stemming from discontinuous Galerkin discretization of second-order elliptic partial differential equations on polytopic meshes. Here, the sequence of spaces that stands at the basis of the multigrid scheme is possibly non-nested and is obtained based on employing agglomeration algorithms with possible edge/face coarsening. We prove that the method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree \(p\), provided that the minimum number of smoothing steps, which depends on \(p\), is chosen sufficiently large.

MSC:

65F10 Iterative numerical methods for linear systems
65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Antonietti, P.F., Ayuso de Dios, B.: Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case. Math. Model. Numer. Anal. 41(1), 21-54 (2007) · Zbl 1129.65080
[2] Antonietti, P.F., Ayuso de Dios, B.: Multiplicative Schwarz methods for discontinuous Galerkin approximations of elliptic problems. Math. Model. Numer. Anal. 42(3), 443-469 (2008) · Zbl 1146.65081
[3] Antonietti, P.F., Brezzi, F., Marini, L.D.: Bubble stabilization of discontinuous Galerkin methods. Comput. Methods Appl. Mech. Eng. 198(21-26), 1651-1659 (2009) · Zbl 1227.65110
[4] Antonietti, P.F., Facciolà, C., Russo, A., Verani, M.: Discontinuous Galerkin approximation of flows in fractured porous media. MOX report 55/2016 (2016, Submitted) · Zbl 1407.65255
[5] Antonietti, P.F., Giani, S., Houston, \[P.: hp\] hp-version composite discontinuous Galerkin methods for elliptic problems on complicated domains. SIAM J. Sci. Comput. 35(3), A1417-A1439 (2013) · Zbl 1284.65163
[6] Antonietti, P.F., Giani, S., Houston, P.: Domain decomposition preconditioners for discontinuous Galerkin methods for elliptic problems on complicated domains. J. Sci. Comput. 60(1), 203-227 (2014) · Zbl 1307.65174
[7] Antonietti, P.F., Houston, P.: A class of domain decomposition preconditioners for \[hp\] hp-discontinuous Galerkin finite element methods. J. Sci. Comput. 46(1), 124-149 (2011) · Zbl 1230.65123
[8] Antonietti, P.F., Houston, P., Hu, X., Sarti, M., Verani, M.: Multigrid algorithms for \[hp\] hp-version interior penaty discontinuous Galerkin methods on polygonal and polyhedral meshes. Calcolo 54(4), 1169-1198 (2017) · Zbl 1421.65029
[9] Antonietti, P.F., Houston, P., Smears, I.: A note on optimal spectral bounds for nonoverlapping domain decomposition preconditioners for \[hp\] hp-version discontinuous Galerkin methods. Int. J. Numer. Methods Eng. 13(4), 513-524 (2016) · Zbl 1350.65134
[10] Antonietti, P.F., Mazzieri, I.: DG methods for the elastodynamics equations on polygonal/polyhedral grids. MOX report 06/2018 (2018, Submitted )
[11] Antonietti, P.F., Sarti, M., Verani, M.: Multigrid algorithms for \[hp\] hp-discontinuous Galerkin discretizations of elliptic problems. SIAM J. Numer. Anal. 53(1), 598-618 (2015) · Zbl 1312.65181
[12] Arnold, D.N.: An interior penalty finite element method with discontinuous elements. SIAM J. Numer. Anal. 19(4), 742-760 (1982) · Zbl 0482.65060
[13] Arnold, D.N., Brezzi, F., Cockburn, B., Marini, L.D.: Unified analysis of discontinuous Galerkin methods for elliptic problems. SIAM J. Numer. Anal. 39(5), 1749-1779 (2002) · Zbl 1008.65080
[14] Ayuso de Dios, B., Zikatanov, L.: Uniformly convergent iterative methods for discontinuous Galerkin discretizations. J. Sci. Comput. 40(1-3), 4-36 (2009) · Zbl 1203.65242
[15] Baker, G.A.: Finite element methods for elliptic equations using nonconforming elements. Math. Comput. 31(137), 45-59 (1977) · Zbl 0364.65085
[16] Bank, R.E., Dupont, T.: An optimal order process for solving finite element equations. Math. Comput. 36(153), 35-51 (1981) · Zbl 0466.65059
[17] Bassi, F., Botti, L., Colombo, A., Brezzi, F., Manzini, G.: Agglomeration-based physical frame dG discretizations: an attempt to be mesh free. Math. Models Methods Appl. Sci. 24(8), 1495-1539 (2014) · Zbl 1291.65335
[18] Bassi, F., Botti, L., Colombo, A., Di Pietro, D.A., Tesini, P.: On the flexibility of agglomeration based physical space discontinuous Galerkin discretizations. J. Comput. Phys. 231(1), 45-65 (2012) · Zbl 1457.65178
[19] Bassi, F., Botti, L., Colombo, A., Rebay, S.: Agglomeration based discontinuous Galerkin discretization of the Euler and Navier-Stokes equations. Comput. Fluids 61, 77-85 (2012) · Zbl 1365.76109
[20] Braess, D., Verfürth, R.: Multigrid methods for nonconforming finite element methods. SIAM J. Numer. Anal. 22(4), 979-986 (1990) · Zbl 0703.65067
[21] Bramble, J.H.: Multigrid Methods (Pitman Research Notes in Mathematics Series). Longman Scientific and Technical, New York (1993)
[22] Bramble, J.H., Kwak, D.Y., Pasciak, J.E.: Uniform convergence of multigrid \[VV\]-cycle iterations for indefinite and nonsymmetric problems. SIAM J. Numer. Anal. 31(6), 1746-1763 (1994) · Zbl 0813.65130
[23] Bramble, J.H., Pasciak, J.E.: The analysis of smoothers for multigrid algorithms. Math. Comput. 58(198), 467-488 (1992) · Zbl 0771.65082
[24] Bramble, J.H., Pasciak, J.E.: New estimates for multilevel algorithms including the \[VV\]-cycle. Math. Comput. 60(202), 447-471 (1993) · Zbl 0783.65081
[25] Bramble, J.H., Pasciak, J.E.: Uniform convergence estimates for multigrid \[VV\]-cycle algorithms with less than full elliptic regularity. SIAM J. Numer. Anal. 31(6), 1746-1763 (1994) · Zbl 0797.65085
[26] Bramble, J.H., Pasciak, J.E., Xu, J.: The analysis of multigrid algorithms with nonnested space or noninherited quadratic forms. Math. Comput. 56(193), 1-34 (1991) · Zbl 0718.65081
[27] Bramble, J.H., Zhang, X.: Uniform convergence of the multigrid \[VV\]-cycle for an anisotropic problem. Math. Comput. 70(234), 453-470 (2001) · Zbl 0967.65104
[28] Brenner, S.C., Cui, J., Gudi, T., Sung, L.-Y.: Multigrid algorithms for symmetric discontinuous Galerkin methods on graded meshes. Numer. Math. 119(1), 21-47 (2011) · Zbl 1229.65224
[29] Brenner, S.C., Cui, J., Sung, L.-Y.: Multigrid methods for the symmetric interior penalty method on graded meshes. Numer. Linear Algebra Appl. 16(6), 481-501 (2009) · Zbl 1224.65288
[30] Brenner, S.C., Owens, L.: A \[WW\]-cycle algorithm for a weakly over-penalized interior penalty method. Comput. Methods Appl. Mech. Eng. 196(37-40), 3823-3832 (2007) · Zbl 1173.65368
[31] Brenner, S.C., Park, E.-H., Sung, L.-Y.: A balancing domain decomposition by constraints preconditioner for a weakly over-penalized symmetric interior penalty method. Numer. Linear Algebra Appl. 20(3), 472-491 (2013) · Zbl 1313.65049
[32] Cangiani, A., Dong, Z., Georgoulis, E.\[H.: hp\] hp-version space-time discontinuous Galerkin methods for parabolic problems on prismatic meshes. SIAM J. Sci. Comput. 39(4), A1251-A1279 (2017) · Zbl 1371.65106
[33] Cangiani, A., Dong, Z., Georgoulis, E.H., Houston, \[P.: hp\] hp-version discontinuous Galerkin methods for advection-diffusion-reaction problems on polytopic meshes. ESAIM Math. Model. Numer. Anal. 50(3), 699-725 (2016) · Zbl 1342.65213
[34] Cangiani, A., Georgoulis, E.H., Houston, \[P.: hp\] hp-version discontinuous Galerkin methods on polygonal and polyhedral meshes. Math. Models Methods Appl. Sci. 24(10), 2009-2041 (2014) · Zbl 1298.65167
[35] Chan, T.F., Xu, J., Zikatanov, L.: An agglomeration multigrid method for unstructured grids. Contemp. Math. 218, 67-81 (1998) · Zbl 0909.65102
[36] Cockburn, B., Karniadakis, G.E., Shu, C.-W.: Discontinuous Galerkin Methods. Theory, Computation and Applications. Springer, Berlin (2000) · Zbl 0935.00043
[37] Di Pietro, D.A., Ern, A.: Mathematical Aspects of Discontinuous Galerkin Methods. Springer, Berlin (2011) · Zbl 1231.65209
[38] Dobrev, V.A., Lazarov, R.D., Vassilevski, P.S., Zikatanov, L.: Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations. Numer. Linear Algebra Appl. 13(9), 753-770 (2006) · Zbl 1224.65263
[39] Dryja, M.: On discontinuous Galerkin methods for elliptic problems with discontinuous coefficients. Comput. Methods Appl. Mat. 3(1), 76-85 (2003) · Zbl 1039.65079
[40] Dryja, M., Galvis, J., Sarkis, M.: BDDC methods for discontinuous Galerkin discretization of elliptic problems. J. Complex. 23, 715-739 (2007) · Zbl 1133.65097
[41] Dryja, M., Krzyżanowski, P., Sarkis, M.: Additive Schwarz method for dG discretization of anisotropic elliptic problems. Lect. Notes Comput. Sci. Eng. 98, 407-415 (2014) · Zbl 1382.65388
[42] Dryja, M., Sarkis, M.: Additive average Schwarz methods for discretization of elliptic problems with highly discontinuous coefficients. Comput. Methods Appl. Math. 10(2), 164-176 (2010) · Zbl 1283.65019
[43] Duan, H.Y., Gao, S.Q., Tan, R.C.E., Zhang, S.: A generalized BPX multigrid framework covering nonnested \[VV\]-cycle methods. Math. Comput. 76(257), 137-152 (2007) · Zbl 1121.65126
[44] Feng, X., Karakashian, O.A.: Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems. SIAM J. Numer. Anal. 39(4), 1343-1365 (2001). (electronic) · Zbl 1007.65104
[45] Feng, X., Karakashian, O.A.: Analysis of two-level overlapping additive Schwarz preconditioners for a discontinuous Galerkin method. In: Domain Decomposition Methods in Science and Engineering (Lyon, 2000), Theory Eng. Appl. Comput. Methods, pp. 237-245. Internat. Center Numer. Methods Eng. (CIMNE), Barcelona (2002) · Zbl 1026.65121
[46] Feng, X., Karakashian, O.A.: Two-level non-overlapping Schwarz preconditioners for a discontinuous Galerkin approximation of the biharmonic equation. J. Sci. Comput. 22(23), 289-314 (2005) · Zbl 1072.65161
[47] Georgoulis, E.H., Suli, E.: Optimal error estimates for the \[hp\] hp-version interior penalty discontinuous Galerkin finite element method. IMA J. Numer. Anal. 25(1), 205-220 (2005) · Zbl 1069.65118
[48] Giani, S., Houston, P.: Domain decomposition preconditioners for discontinuous Galerkin discretizations of compressible fluid flows. Numer. Math. Theory Methods Appl. 7(2), 123-148 (2014) · Zbl 1324.76031
[49] Giani, S., Houston, \[P.: hp\] hp-adaptive composite discontinuous Galerkin methods for elliptic problems on complicated domains. Numer. Methods Part. Differ. Equ. 30(4), 1342-1367 (2014) · Zbl 1298.65173
[50] Gopalakrishnan, J., Kanschat, G.: A multilevel discontinuous Galerkin method. Numer. Math. 95(3), 527-550 (2003) · Zbl 1044.65084
[51] Gopalakrishnan, J., Pasciak, J.E.: Multigrid for the Mortar finite element method. SIAM J. Numer. Anal. 37(3), 1029-1052 (2000) · Zbl 0951.65134
[52] Hesthaven, J.S., Warburton, T.: Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications, 1st edn. Springer, Berlin (2008) · Zbl 1134.65068
[53] Holz, S.: Polygon clipper. https://it.mathworks.com/matlabcentral/fileexchange/8818-polygon-clipper
[54] Karakashian, O.A., Collins, C.: Two-level additive Schwarz methods for discontinuous Galerkin approximations of second-order elliptic problems. IMA J. Numer. Anal. 37(4), 1800-1830 (2017) · Zbl 1433.65301
[55] Karypis, G., Kumar, V.: Metis: Unstructured graph partitioning and sparse matrix ordering system, version 4.0. http://www.cs.umn.edu/ metis (2009)
[56] Ladson, C.L., Jr., C.W.: Brooks. Development of a computer program to obtain ordinates for NACA 6- and 6A-series airfoils. NASA Technical Memorandum X-3069 (1974)
[57] Lipnikov, K., Vassilev, D., Yotov, I.: Discontinuous Galerkin and mimetic finite difference methods for coupled Stokes-Darcy flows on polygonal and polyhedral grids. Numer. Math. 126(2), 321-360 (2014) · Zbl 1282.76139
[58] Persson, P.O., Strang, G.: A simple mesh generator in MATLAB. SIAM Rev. 46(2), 329-345 (2004) · Zbl 1061.65134
[59] Reed, W.H., Hill, T.R.: Triangular mesh methods for the neutron transport equation. Technical Report LA-UR-73-479, Los Alamos Scientific Laboratory (1973)
[60] Rivière, B.: Discontinuous Galerkin Methods for Solving Elliptic and Parabolic Equations. SIAM, Philadelphia (2008) · Zbl 1153.65112
[61] Scott, L.R., Zhang, S.: Higher-dimensional nonnested multigrid methods. Math. Comput. 58(198), 457-466 (1992) · Zbl 0772.65077
[62] Stein, E.M.: Singular Integrals and Differentiability Properties of Functions. Princeton University Press, Princeton (1970) · Zbl 0207.13501
[63] Talischi, C., Paulino, G.H., Pereira, A., Menezes, I.F.M.: Polymesher: a general-purpose mesh generator for polygonal elements written in MATLAB. Struct. Multidiscip. Optim. 45(3), 309-328 (2012) · Zbl 1274.74401
[64] Toselli, A., Widlund, O.B.: Domain Decomposition Methods—Algorithms and Theory. Springer Series in Computational Mathematics, vol. 34. Springer, Berlin (2004) · Zbl 1069.65138
[65] Wheeler, M.F.: An elliptic collocation finite element method with interior penalties. SIAM J. Numer. Anal. 15(1), 152-161 (1978) · Zbl 0384.65058
[66] Wiresaet, D., Kubatko, E.J., Michoski, C.E., Tanaka, S., Westerink, J.J., Dawson, C.: Discontinuous Galerkin methods with nodal and hybrid modal/nodal triangular, quadrilateral, and polygonal elements for nonlinear shallow water flow. Comput. Methods Appl. Mech. Eng. 270, 113-149 (2014) · Zbl 1296.76089
[67] Xu, X., Chen, J.: Multigrid for the mortar element method for \[P1\] P1 nonconforming element. Numer. Math. 88(2), 381-389 (2001) · Zbl 0989.65141
[68] Xu, X., Li, L., Chen, W.: A multigrid method for the Mortar-type Morley element approximation of a plate bending problem. SIAM J. Numer. Anal. 39(5), 1712-1731 (2002) · Zbl 1049.74056
[69] Zhang, S.: Optimal-order nonnested multigrid methods for solving finite element equations I: on quasi-uniform meshes. Math. Comput. 55(191), 23-36 (1990) · Zbl 0703.65068
[70] Zhang, S., Zhang, Z.: Treatments of discontinuity and bubble functions in the multigrid method. Math. Comput. 66(219), 1055-1072 (1997) · Zbl 0870.65111
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.