×

Fast numerical integration on polytopic meshes with applications to discontinuous Galerkin finite element methods. (English) Zbl 1435.65044

Summary: In this paper we present efficient quadrature rules for the numerical approximation of integrals of polynomial functions over general polygonal/polyhedral elements that do not require an explicit construction of a sub-tessellation into triangular/tetrahedral elements. The method is based on successive application of Stokes’ theorem; thereby, the underlying integral may be evaluated using only the values of the integrand and its derivatives at the vertices of the polytopic domain, and hence leads to an exact cubature rule whose quadrature points are the vertices of the polytope. We demonstrate the capabilities of the proposed approach by efficiently computing the stiffness and mass matrices arising from hp-version symmetric interior penalty discontinuous Galerkin discretizations of second-order elliptic partial differential equations.

MSC:

65D30 Numerical integration
65D32 Numerical quadrature and cubature formulas
65L60 Finite element, Rayleigh-Ritz, Galerkin and collocation methods for ordinary differential equations

Software:

METIS; PolyMesher; FLOPS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antonietti, PF; Brezzi, F.; Marini, LD, Bubble stabilization of discontinuous Galerkin methods, Comput. Methods Appl. Mech. Eng., 198, 1651-1659, (2009) · Zbl 1227.65110 · doi:10.1016/j.cma.2008.12.033
[2] Antonietti, P.F., Cangiani, A., Collis, J., Dong, Z., Georgoulis, E.H., Giani, S., Houston, P.: Review of discontinuous Galerkin Finite Element Methods for partial differential equations on complicated domains, Lecture Notes in Computational Science and Engineering, vol. 114, 1st edn., chap. 8, pp. 281-310. Springer (2016) · Zbl 1357.65251
[3] Antonietti, P.F., Facciolà, C., Russo, A., Verani, M.: Discontinuous Galerkin approximation of flows in fractured porous media. Technical Report 22/2016, MOX Report (2016)
[4] Antonietti, PF; Formaggia, L.; Scotti, A.; Verani, M.; Verzott, N., Mimetic Finite Difference approximation of flows in fractured porous media, ESAIM Math. Model. Numer. Anal., 50, 809-832, (2016) · Zbl 1381.76231 · doi:10.1051/m2an/2015087
[5] Antonietti, PF; Giani, S.; Houston, P., \(hp\)-version Composite Discontinuous Galerkin methods for elliptic problems on complicated domains, SIAM J. Sci. Comput., 35, a1417-a1439, (2013) · Zbl 1284.65163 · doi:10.1137/120877246
[6] Antonietti, PF; Giani, S.; Houston, P., Domain decomposition preconditioners for discontinuous Galerkin methods for elliptic problems on complicated domains, J. Sci. Comput., 60, 203-227, (2014) · Zbl 1307.65174 · doi:10.1007/s10915-013-9792-y
[7] Antonietti, P.F., Houston, P., Pennesi, G.: Fast numerical integration on polytopic meshes with applications to discontinuous Galerkin finite element methods. MOX Report No. 03/2018 (2018)
[8] Antonietti, P.F., Manzini, G., Verani, M.: The fully nonconforming Virtual Element Method for biharmonic problems. Math. Mod. Methods Appl. Sci. (Accepted: 16 October 2017) · Zbl 1381.65090
[9] Antonietti, P.F., Pennesi, G.: V-cycle multigrid algorithms for discontinuous Galerkin methods on non-nested polytopic meshes. MOX Report No. 49/2017 (submitted 2017)
[10] Antonietti, PF; Veiga, LB; Mora, D.; Verani, M., A stream Virtual Element formulation of the Stokes problem on polygonal meshes, SIAM J. Numer. Anal., 52, 386-404, (2014) · Zbl 1427.76198 · doi:10.1137/13091141X
[11] Antonietti, PF; Veiga, LB; Scacchi, S.; Verani, M., A C1 Virtual Element Method for the Cahn-Hilliard equation with polygonal meshes, SIAM J. Numer. Anal., 54, 34-56, (2016) · Zbl 1336.65160 · doi:10.1137/15M1008117
[12] Arnold, Douglas N.; Brezzi, Franco; Cockburn, Bernardo; Marini, L. Donatella, Unified Analysis of Discontinuous Galerkin Methods for Elliptic Problems, SIAM Journal on Numerical Analysis, 39, 1749-1779, (2002) · Zbl 1008.65080 · doi:10.1137/S0036142901384162
[13] Ayuso de Dios, B.; Lipnikov, K.; Manzini, G., The nonconforming Virtual Element Method, ESAIM Math. Model. Numer. Anal., 50, 879-904, (2016) · Zbl 1343.65140 · doi:10.1051/m2an/2015090
[14] Bassi, F.; Botti, L.; Colombo, A., Agglomeration-based physical frame dG discretizations: an attempt to be mesh free, Math. Mod. Methods Appl. Sci., 24, 1495-1539, (2014) · Zbl 1291.65335 · doi:10.1142/S0218202514400028
[15] Beirão da Veiga, L.; Brezzi, F.; Cangiani, A.; Manzini, G.; Marini, LD; Russo, A., Basic principles of Virtual Element Methods, Math. Models Methods Appl. Sci., 23, 199-214, (2013) · Zbl 1416.65433 · doi:10.1142/S0218202512500492
[16] Beirão da Veiga, L.; Brezzi, F.; Marini, LD; Russo, A., Mixed Virtual Element Methods for general second order elliptic problems on polygonal meshes, ESAIM Math. Model. Numer. Anal., 50, 727-747, (2016) · Zbl 1343.65134 · doi:10.1051/m2an/2015067
[17] Beirão da Veiga, L.; Brezzi, F.; Marini, LD; Russo, A., Virtual Element Method for general second-order elliptic problems on polygonal meshes, Math. Models Methods Appl. Sci., 26, 729-750, (2016) · Zbl 1332.65162 · doi:10.1142/S0218202516500160
[18] Beirão da Veiga, L., Lipnikov, K., Manzini, G.: The Mimetic Finite Difference Method for Elliptic Problems, vol. 11. Springer, Cham (2014) · Zbl 1286.65141
[19] Brezzi, Franco; Lipnikov, Konstantin; Shashkov, Mikhail, Convergence of the Mimetic Finite Difference Method for Diffusion Problems on Polyhedral Meshes, SIAM Journal on Numerical Analysis, 43, 1872-1896, (2005) · Zbl 1108.65102 · doi:10.1137/040613950
[20] Brezzi, F.; Lipnikov, K.; Shashkov, M., Convergence of Mimetic Finite Difference method for diffusion problems on polyhedral meshes with curved faces, Math. Mod. Methods Appl. Sci., 16, 275-297, (2006) · Zbl 1094.65111 · doi:10.1142/S0218202506001157
[21] Brezzi, F.; Lipnikov, K.; Simoncini, V., A family of Mimetic Finite Difference methods on polygonal and polyhedral meshes, Math. Mod. Methods Appl. S., 15, 1533-1551, (2005) · Zbl 1083.65099 · doi:10.1142/S0218202505000832
[22] Cangiani, A.; Dong, Z.; Georgoulis, EH, \(hp\)-Version space-time discontinuous Galerkin methods for parabolic problems on prismatic meshes, SIAM J. Sci. Comput., 39, a1251-a1279, (2017) · Zbl 1371.65106 · doi:10.1137/16M1073285
[23] Cangiani, A.; Dong, Z.; Georgoulis, EH; Houston, P., \(hp\)-Version discontinuous Galerkin methods for advection-diffusion-reaction problems on polytopic meshes, ESAIM Math. Model. Numer. Anal., 50, 699-725, (2016) · Zbl 1342.65213 · doi:10.1051/m2an/2015059
[24] Cangiani, A., Dong, Z., Georgoulis, E.H., Houston, P.: \(hp\)-Version discontinuous Galerkin methods on polygonal and polyhedral meshes. Springer International Publishing, SpringerBriefs in Mathematics, Berlin (2017) · Zbl 1382.65307 · doi:10.1007/978-3-319-67673-9
[25] Cangiani, A.; Georgoulis, EH; Houston, P., \(hp\)-Version discontinuous Galerkin methods on polygonal and polyhedral meshes, Math. Models Methods Appl. Sci., 24, 2009-2041, (2014) · Zbl 1298.65167 · doi:10.1142/S0218202514500146
[26] Cangiani, A.; Manzini, G.; Sutton, OJ, Conforming and nonconforming Virtual Element Methods for elliptic problems, IMA J. Numer. Anal., 37, 1317-1354, (2017) · Zbl 1433.65282
[27] Chin, EB; Lasserre, JB; Sukumar, N., Numerical integration of homogeneous functions on convex and nonconvex polygons and polyhedra, Comput. Mech., 56, 967-981, (2015) · Zbl 1336.65020 · doi:10.1007/s00466-015-1213-7
[28] Chin, EB; Lasserre, JB; Sukumar, N., Modeling crack discontinuities without element-partitioning in the extended finite element method, Int. J. Numer. Methods Eng., 110, 1021-1048, (2017) · doi:10.1002/nme.5436
[29] Cockburn, B.; Dond, B.; Guzmán, J., A superconvergent LDG-hybridizable Galerkin method for second-order elliptic problems, Math. Comput., 77, 1887-1916, (2008) · Zbl 1198.65193 · doi:10.1090/S0025-5718-08-02123-6
[30] 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, 1319-1365, (2009) · Zbl 1205.65312 · doi:10.1137/070706616
[31] Cockburn, B.; Gopalakrishnan, J.; Sayas, FJ, A projection-based error analysis of HDG methods, Math. Comput., 79, 1351-1367, (2010) · Zbl 1197.65173 · doi:10.1090/S0025-5718-10-02334-3
[32] Cockburn, B.; Guzmán, J.; Wang, H., Superconvergent discontinuous Galerkin methods for second-order elliptic problems, Math. Comput., 78, 1-24, (2009) · Zbl 1198.65194 · doi:10.1090/S0025-5718-08-02146-7
[33] Di Pietro, DA; Ern, A., A hybrid high-order locking-free method for linear elasticity on general meshes, Comput. Methods Appl. Mech. Eng., 283, 1-21, (2015) · Zbl 1423.74876 · doi:10.1016/j.cma.2014.09.009
[34] Di Pietro, DA; Ern, A., Hybrid High-Order methods for variable-diffusion problems on general meshes, C. R. Math. Acad. Sci. Soc. R. Can., 353, 31-34, (2015) · Zbl 1308.65196
[35] Di Pietro, DA; Ern, A.; Lemaire, S., An arbitrary-order and compact-stencil discretization of diffusion on general meshes based on local reconstruction operators, Comput. Method Appl. Math., 14, 461-472, (2014) · Zbl 1304.65248 · doi:10.1515/cmam-2014-0018
[36] Droniou, J.; Eymard, R.; Herbin, R., Gradient schemes: generic tools for the numerical analysis of diffusion equations, ESAIM Math. Model. Numer. Anal., 50, 749-781, (2016) · Zbl 1346.65042 · doi:10.1051/m2an/2015079
[37] Fries, TP; Belytschko, T., The extended/generalized finite element method: an overview of the method and its applications, Int. J. Numer. Methods Eng., 84, 253-304, (2010) · Zbl 1202.74169
[38] Gerstenberger, A.; Wall, AW, An Extended Finite Element Method/Lagrange multiplier based approach for fluid-structure interaction, Comput. Methods Appl. Mech. Eng., 197, 1699-1714, (2008) · Zbl 1194.76117 · doi:10.1016/j.cma.2007.07.002
[39] Giani, S.; Houston, P., Domain decomposition preconditioners for discontinuous Galerkin discretizations of compressible fluid flows, Numer. Math. Theory Methods Appl., 7, 123-148, (2014) · Zbl 1324.76031
[40] Griffiths, D.J.: Introduction to Quantum Mechanics. Pearson Education, London (2005)
[41] Hackbusch, W., Sauter, S.A.: Composite Finite Elements for problems containing small geometric details. Part II: Implementation and numerical results. Comput. Visual Sci. 1(4), 15-25 (1997) · Zbl 1001.65127 · doi:10.1007/s007910050002
[42] Hackbusch, W.; Sauter, SA, Composite Finite Elements for the approximation of PDEs on domains with complicated micro-structures, Numer. Math., 75, 447-472, (1997) · Zbl 0874.65086 · doi:10.1007/s002110050248
[43] Holdych, DJ; Noble, DR; Secor, RB, Quadrature rules for triangular and tetrahedral elements with generalized functions, Int. J. Numer. Methods Eng., 73, 1310-1327, (2015) · Zbl 1167.74043 · doi:10.1002/nme.2123
[44] Hyman, J.; Shashkov, M.; Steinberg, S., The numerical solution of diffusion problems in strongly heterogeneous non-isotropic materials, J. Comput. Phys., 132, 130-148, (1997) · Zbl 0881.65093 · doi:10.1006/jcph.1996.5633
[45] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 359-392, (1998) · Zbl 0915.68129 · doi:10.1137/S1064827595287997
[46] Karypis, G., Kumar, V.: Metis: Unstructured graph partitioning and sparse matrix ordering system, version 4.0. http://www.cs.umn.edu/ metis (2009)
[47] Lasserre, JB, Integration on a convex polytope, Proc. Am. Math. Soc., 126, 2433-2441, (1998) · Zbl 0901.65012 · doi:10.1090/S0002-9939-98-04454-2
[48] Li, CJ; Lambertu, P.; Dagnino, C., Numerical integration over polygons using an eight-node quadrilateral spline finite element, J. Comput. Appl. Math., 233, 279-292, (2009) · Zbl 1181.65043 · doi:10.1016/j.cam.2009.07.017
[49] Lyness, JN; Monegato, G., Quadrature rules for regions having regular hexagonal symmetry, SIAM J. Numer. Anal., 14, 283-295, (1977) · Zbl 0365.65014 · doi:10.1137/0714018
[50] Ma, J.; Rokhlin, V.; Wandzura, S., Generalized Gaussian quadrature of systems of arbitrary functions, SIAM J. Numer. Anal., 33, 971-996, (1996) · Zbl 0858.65015 · doi:10.1137/0733048
[51] Moës, N.; Dolbow, J.; Belytschko, T., A finite element method for crack growth without remeshing, Int. J. Numer. Methods Eng., 46, 131-150, (1999) · Zbl 0955.74066 · doi:10.1002/(SICI)1097-0207(19990910)46:1<131::AID-NME726>3.0.CO;2-J
[52] Mousavi, SE; Sukumar, N., Numerical integration of polynomials and discontinuous functions on irregular convex polygons and polyhedrons, Comput. Mech., 47, 535-554, (2011) · Zbl 1221.65078 · doi:10.1007/s00466-010-0562-5
[53] Mousavi, SE; Xiao, H.; Sukumar, N., Generalized Gaussian quadrature rules on arbitrary polygons, Internat. J. Numer. Methods Eng., 82, 99-113, (2010) · Zbl 1183.65026
[54] Natarajan, S.; Bordas, S.; Mahapatra, DR, Numerical integration over arbitrary polygonal domains based on Schwarz-Christoffel conformal mapping, Int. J. Numer. Methods Eng., 80, 103-134, (2009) · Zbl 1176.74190 · doi:10.1002/nme.2589
[55] Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes 3rd Edition: The Art of Scientific Computing, 3rd edn. Cambridge University Press, New York (2007) · Zbl 1132.65001
[56] Qian, H.: Counting the floating point operations (flops). https://it.mathworks.com/matlabcentral/fileexchange/50608-counting-the-floating-point-operations–flops- (2015)
[57] Quarteroni, A., Sacco, R., Saleri, F.: Numerical Mathematics. Springer, Berlin (2007) · Zbl 1136.65001
[58] Simon, C.P., Blume, L.E.: Mathematics for Economists. W. W. Norton and Company, New York (1996)
[59] Sommariva, A.; Vianello, M., Product Gauss cubature over polygons based on Green’s integration formula, BIT, 47, 441-453, (2007) · Zbl 1122.65027 · doi:10.1007/s10543-007-0131-2
[60] Stroud, AH; Secrest, D., Gaussiam quadrature formulas, ZAMM Z. Angew. Math. Mech., 47, 138-139, (1967)
[61] Sudhakar, Y.; Wall, WA, Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in enriched partition of unity methods, Comput. Methods Appl. Mech. Eng., 258, 39-54, (2013) · Zbl 1286.65037 · doi:10.1016/j.cma.2013.01.007
[62] Sukumar, N.; Moës, N.; Belytschko, T., Extended Finite Element Method for three-dimensional crack modelling, Int. J. Numer. Methods Eng., 48, 1549-1570, (2000) · Zbl 0963.74067 · doi:10.1002/1097-0207(20000820)48:11<1549::AID-NME955>3.0.CO;2-A
[63] Sukumar, N.; Tabarraei, A., Conforming polygonal finite elements, Int. J. Numer. Methods Eng., 61, 2045-2066, (2004) · Zbl 1073.65563 · doi:10.1002/nme.1141
[64] Tabarraei, A.; Sukumar, N., Extended Finite Element Method on polygonal and quadtree meshes, Comput. Methods Appl. Mech. Eng., 197, 425-438, (2008) · Zbl 1169.74634 · doi:10.1016/j.cma.2007.08.013
[65] Talischi, C.; Paulino, GH; Pereira, A.; Menezes, IFM, Polymesher: a general-purpose mesh generator for polygonal elements written in matlab, Struct. Multidiscip. Optim., 45, 309-328, (2012) · Zbl 1274.74401 · doi:10.1007/s00158-011-0706-z
[66] Taylor, M.E.: Partial Differential Equations: Basic Theory. Springer, New York (1996) · doi:10.1007/978-1-4684-9320-7
[67] Ventura, G., On the elimination of quadrature subcells for discontinuous functions in the extended finite-element method, Int. J. Numer. Methods Eng., 66, 761-795, (2006) · Zbl 1110.74858 · doi:10.1002/nme.1570
[68] Ventura, G.; Benvenuti, E., Equivalent polynomials for quadrature in Heaviside function enriched elements, Int. J. Numer. Methods Eng., 102, 688-710, (2015) · Zbl 1352.65559 · doi:10.1002/nme.4679
[69] Xiao, H.; Gimbutas, Z., A numerical algorithm for the construction of efficient quadrature rules in two and higher dimensions, Comput. Math. Appl., 59, 663-676, (2010) · Zbl 1189.65047 · doi:10.1016/j.camwa.2009.10.027
[70] Yarvin, N.; Rokhlin, V., Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput., 20, 669-718, (1998) · Zbl 0932.65020 · doi:10.1137/S1064827596310779
[71] Yogitha, AM; Shivaram, KT, Numerical integration of arbitrary functions over a convex and non convex polygonal domain by eight noded linear quadrilateral finite element method, Aust. J. Basic Appl. Sci., 10, 104-110, (2016)
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.