article

Fast Numerical Integration on Polytopic Meshes with Applications to Discontinuous Galerkin Finite Element Methods

Authors:

Paola F. Antonietti,

Giorgio PennesiAuthors Info & Claims

Journal of Scientific Computing, Volume 77, Issue 3

Pages 1339 - 1370

https://doi.org/10.1007/s10915-018-0802-y

Published: 01 December 2018 Publication History

Abstract

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.

References

[1]

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)

[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)

[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, P.F., Formaggia, L., Scotti, A., Verani, M., Verzott, N.: Mimetic Finite Difference approximation of flows in fractured porous media. ESAIM Math. Model. Numer. Anal. 50(3), 809---832 (2016)

[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)

Digital Library

[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)

Digital Library

[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)

[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, P.F., da Veiga, L.B., Mora, D., Verani, M.: A stream Virtual Element formulation of the Stokes problem on polygonal meshes. SIAM J. Numer. Anal. 52(1), 386---404 (2014)

Digital Library

[11]

Antonietti, P.F., da Veiga, L.B., Scacchi, S., Verani, M.: A C1 Virtual Element Method for the Cahn---Hilliard equation with polygonal meshes. SIAM J. Numer. Anal. 54(1), 34---56 (2016)

[12]

Arnold, N.D., Brezzi, F., Cockburn, B., Marini, L.D.: Unified analysis of discontinuous Galerkin methods for elliptic problems. SIAM J. Numer. Anal. 39(5), 1749---1779 (2001/2002)

Digital Library

[13]

Ayuso de Dios, B., Lipnikov, K., Manzini, G.: The nonconforming Virtual Element Method. ESAIM Math. Model. Numer. Anal. 50(3), 879---904 (2016)

[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(8), 1495---1539 (2014)

[15]

Beirão da Veiga, L., Brezzi, F., Cangiani, A., Manzini, G., Marini, L.D., Russo, A.: Basic principles of Virtual Element Methods. Math. Models Methods Appl. Sci. 23(1), 199---214 (2013)

[16]

Beirão da Veiga, L., Brezzi, F., Marini, L.D., Russo, A.: Mixed Virtual Element Methods for general second order elliptic problems on polygonal meshes. ESAIM Math. Model. Numer. Anal. 50(3), 727---747 (2016)

[17]

Beirão da Veiga, L., Brezzi, F., Marini, L.D., Russo, A.: Virtual Element Method for general second-order elliptic problems on polygonal meshes. Math. Models Methods Appl. Sci. 26(4), 729---750 (2016)

[18]

Beirão da Veiga, L., Lipnikov, K., Manzini, G.: The Mimetic Finite Difference Method for Elliptic Problems, vol. 11. Springer, Cham (2014)

[19]

Brezzi, F., Lipnikov, K., Shashkov, M.: Convergence of the Mimetic Finite Difference method for diffusion problems on polyhedral meshes. SIAM J. Numer. Anal. 43(5), 1872---1896 (electronic) (2005)

Digital Library

[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(2), 275---297 (2006)

[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(10), 1533---1551 (2005)

[22]

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)

[23]

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, 699---725 (2016)

[24]

Cangiani, A., Dong, Z., Georgoulis, E.H., Houston, P.: $$hp$$hp-Version discontinuous Galerkin methods on polygonal and polyhedral meshes. Springer International Publishing, SpringerBriefs in Mathematics, Berlin (2017)

Digital Library

[25]

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)

[26]

Cangiani, A., Manzini, G., Sutton, O.J.: Conforming and nonconforming Virtual Element Methods for elliptic problems. IMA J. Numer. Anal. 37(3), 1317---1354 (2017)

[27]

Chin, E.B., Lasserre, J.B., Sukumar, N.: Numerical integration of homogeneous functions on convex and nonconvex polygons and polyhedra. Comput. Mech. 56(6), 967---981 (2015)

Digital Library

[28]

Chin, E.B., Lasserre, J.B., Sukumar, N.: Modeling crack discontinuities without element-partitioning in the extended finite element method. Int. J. Numer. Methods Eng. 110(11), 1021---1048 (2017)

[29]

Cockburn, B., Dond, B., Guzmán, J.: A superconvergent LDG-hybridizable Galerkin method for second-order elliptic problems. Math. Comput. 77(264), 1887---1916 (2008)

[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(2), 1319---1365 (2009)

Digital Library

[31]

Cockburn, B., Gopalakrishnan, J., Sayas, F.J.: A projection-based error analysis of HDG methods. Math. Comput. 79(271), 1351---1367 (2010)

[32]

Cockburn, B., Guzmán, J., Wang, H.: Superconvergent discontinuous Galerkin methods for second-order elliptic problems. Math. Comput. 78(265), 1---24 (2009)

[33]

Di Pietro, D.A., Ern, A.: A hybrid high-order locking-free method for linear elasticity on general meshes. Comput. Methods Appl. Mech. Eng. 283(1), 1---21 (2015)

[34]

Di Pietro, D.A., Ern, A.: Hybrid High-Order methods for variable-diffusion problems on general meshes. C. R. Math. Acad. Sci. Soc. R. Can. 353(1), 31---34 (2015)

[35]

Di Pietro, D.A., 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(4), 461---472 (2014)

[36]

Droniou, J., Eymard, R., Herbin, R.: Gradient schemes: generic tools for the numerical analysis of diffusion equations. ESAIM Math. Model. Numer. Anal. 50(3), 749---781 (2016)

[37]

Fries, T.P., Belytschko, T.: The extended/generalized finite element method: an overview of the method and its applications. Int. J. Numer. Methods Eng. 84(3), 253---304 (2010)

[38]

Gerstenberger, A., Wall, A.W.: An Extended Finite Element Method/Lagrange multiplier based approach for fluid-structure interaction. Comput. Methods Appl. Mech. Eng. 197(19---20), 1699---1714 (2008)

[39]

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)

[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)

[42]

Hackbusch, W., Sauter, S.A.: Composite Finite Elements for the approximation of PDEs on domains with complicated micro-structures. Numer. Math. 75(4), 447---472 (1997)

[43]

Holdych, D.J., Noble, D.R., Secor, R.B.: Quadrature rules for triangular and tetrahedral elements with generalized functions. Int. J. Numer. Methods Eng. 73(9), 1310---1327 (2015)

[44]

Hyman, J., Shashkov, M., Steinberg, S.: The numerical solution of diffusion problems in strongly heterogeneous non-isotropic materials. J. Comput. Phys. 132(1), 130---148 (1997)

Digital Library

[45]

Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359---392 (1998)

Digital Library

[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, J.B.: Integration on a convex polytope. Proc. Am. Math. Soc. 126(8), 2433---2441 (1998)

[48]

Li, C.J., Lambertu, P., Dagnino, C.: Numerical integration over polygons using an eight-node quadrilateral spline finite element. J. Comput. Appl. Math. 233(2), 279---292 (2009)

Digital Library

[49]

Lyness, J.N., Monegato, G.: Quadrature rules for regions having regular hexagonal symmetry. SIAM J. Numer. Anal. 14(2), 283---295 (1977)

[50]

Ma, J., Rokhlin, V., Wandzura, S.: Generalized Gaussian quadrature of systems of arbitrary functions. SIAM J. Numer. Anal. 33(3), 971---996 (1996)

Digital Library

[51]

Moës, N., Dolbow, J., Belytschko, T.: A finite element method for crack growth without remeshing. Int. J. Numer. Methods Eng. 46(1), 131---150 (1999)

[52]

Mousavi, S.E., Sukumar, N.: Numerical integration of polynomials and discontinuous functions on irregular convex polygons and polyhedrons. Comput. Mech. 47(5), 535---554 (2011)

Digital Library

[53]

Mousavi, S.E., Xiao, H., Sukumar, N.: Generalized Gaussian quadrature rules on arbitrary polygons. Internat. J. Numer. Methods Eng. 82(1), 99---113 (2010)

[54]

Natarajan, S., Bordas, S., Mahapatra, D.R.: Numerical integration over arbitrary polygonal domains based on Schwarz---Christoffel conformal mapping. Int. J. Numer. Methods Eng. 80(1), 103---134 (2009)

[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)

Digital Library

[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)

[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(2), 441---453 (2007)

[60]

Stroud, A.H., Secrest, D.: Gaussiam quadrature formulas. ZAMM Z. Angew. Math. Mech. 47(2), 138---139 (1967)

[61]

Sudhakar, Y., Wall, W.A.: Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in enriched partition of unity methods. Comput. Methods Appl. Mech. Eng. 258(1), 39---54 (2013)

[62]

Sukumar, N., Moës, N., Belytschko, T.: Extended Finite Element Method for three-dimensional crack modelling. Int. J. Numer. Methods Eng. 48(11), 1549---1570 (2000)

[63]

Sukumar, N., Tabarraei, A.: Conforming polygonal finite elements. Int. J. Numer. Methods Eng. 61(12), 2045---2066 (2004)

[64]

Tabarraei, A., Sukumar, N.: Extended Finite Element Method on polygonal and quadtree meshes. Comput. Methods Appl. Mech. Eng. 197(5), 425---438 (2008)

[65]

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)

Digital Library

[66]

Taylor, M.E.: Partial Differential Equations: Basic Theory. Springer, New York (1996)

[67]

Ventura, G.: On the elimination of quadrature subcells for discontinuous functions in the extended finite-element method. Int. J. Numer. Methods Eng. 66(5), 761---795 (2006)

[68]

Ventura, G., Benvenuti, E.: Equivalent polynomials for quadrature in Heaviside function enriched elements. Int. J. Numer. Methods Eng. 102(3---4), 688---710 (2015)

[69]

Xiao, H., Gimbutas, Z.: A numerical algorithm for the construction of efficient quadrature rules in two and higher dimensions. Comput. Math. Appl. 59(2), 663---676 (2010)

[70]

Yarvin, N., Rokhlin, V.: Generalized Gaussian quadratures and singular value decompositions of integral operators. SIAM J. Sci. Comput. 20(2), 669---718 (1998)

Digital Library

[71]

Yogitha, A.M., Shivaram, K.T.: 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(16), 104---110 (2016)

Cited By

Yemm L(2024)A New Approach to Handle Curved Meshes in the Hybrid High-Order MethodFoundations of Computational Mathematics10.1007/s10208-023-09615-w24:3(1049-1076)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10208-023-09615-w
Dassi FFumagalli AMazzieri IScotti AVacca G(2022)A Virtual Element Method for the Wave Equation on Curved Edges in Two DimensionsJournal of Scientific Computing10.1007/s10915-021-01683-w90:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10915-021-01683-w
Antolin PHirschler T(2022)Quadrature-free immersed isogeometric analysisEngineering with Computers10.1007/s00366-022-01644-338:5(4475-4499)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00366-022-01644-3
Show More Cited By

Fast Numerical Integration on Polytopic Meshes with Applications to Discontinuous Galerkin Finite Element Methods
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation

Recommendations

Numerical integration over polygons using an eight-node quadrilateral spline finite element

In this paper, a cubature formula over polygons is proposed and analysed. It is based on an eight-node quadrilateral spline finite element [C.-J. Li, R.-H. Wang, A new 8-node quadrilateral spline finite element, J. Comp. Appl. Math. 195 (2006) 54-65] ...
Weighted quadrature rules for finite element methods

We discuss the numerical integration of polynomials times non-polynomial weighting functions in two dimensions arising from multiscale finite element computations. The proposed quadrature rules are significantly more accurate than standard quadratures ...
hp-Discontinuous Galerkin Finite Element Methods with Least-Squares Stabilization

We consider a family of hp-version discontinuous Galerkin finite element methods with least-squares stabilization for symmetric systems of first-order partial differential equations. The family includes the classical discontinuous Galerkin finite ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Scientific Computing

Journal of Scientific Computing Volume 77, Issue 3

December 2018

678 pages

ISSN:0885-7474

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Plenum Press

United States

Publication History

Published: 01 December 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yemm L(2024)A New Approach to Handle Curved Meshes in the Hybrid High-Order MethodFoundations of Computational Mathematics10.1007/s10208-023-09615-w24:3(1049-1076)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10208-023-09615-w
Dassi FFumagalli AMazzieri IScotti AVacca G(2022)A Virtual Element Method for the Wave Equation on Curved Edges in Two DimensionsJournal of Scientific Computing10.1007/s10915-021-01683-w90:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10915-021-01683-w
Antolin PHirschler T(2022)Quadrature-free immersed isogeometric analysisEngineering with Computers10.1007/s00366-022-01644-338:5(4475-4499)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00366-022-01644-3
Lasserre J(2021)Simple formula for integration of polynomials on a simplexBIT10.1007/s10543-020-00828-x61:2(523-533)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10543-020-00828-x

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents