1 Introduction
2 Integrating Polynomials over General Polygons/Polyhedra
-
\({\mathscr {P}} \subset \mathbb {R}^d \textit{, }d=2,3\), is a closed polytope, whose boundary \(\partial {\mathscr {P}} \) is defined by m \((d-1)\)-dimensional faces \({\mathcal {F}}_i,\ i=1,\ldots ,m\). Each face \({\mathcal {F}}_i\) lies in a hyperplane \({\mathcal {H}}_i\) identified by a vector \({\mathbf {a}}_i \in \mathbb {R}^d \) and a scalar number \(b_i\), such thatWe observe that \({\mathbf {a}}_i\), \(i=1,\ldots ,m\), can be chosen as the unit outward normal vector to \({\mathcal {F}}_i\), \(i=1,\ldots ,m\), respectively, relative to \({\mathscr {P}} \), cf. Figs. 1 and 2.$$\begin{aligned} {\mathbf {x}} \in {\mathcal {H}}_i \iff {\mathbf {a}}_i \cdot {\mathbf {x}} = b_i, \quad i=1,\ldots ,m. \end{aligned}$$(1)
-
\(g:{\mathscr {P}} \rightarrow \mathbb {R}\) is a homogeneous function of degree \(q \in \mathbb {R}\), i.e., for all \(\lambda > 0\), \(g(\lambda {\mathbf {x}}) = \lambda ^q g({\mathbf {x}})\) for all \({\mathbf {x}} \in {\mathscr {P}} \).
\(N = 3\)
|
\(N=2\)
|
\(N=1\)
|
\(N=0\)
| |
---|---|---|---|---|
\(d=3\)
|
is a polyhedron |
is a polygon |
is an edge |
is a point |
\(d=2\)
|
is a polygon |
is an edge |
is a point | |
\(d=1\)
|
is an interval |
is a point |
2.1 Integration of Bivariate Polynomials over Polygonal Domains
Vertex |
x-cordinates |
y-cordinates | |
---|---|---|---|
\({\mathscr {P}} _1\)
| 1 |
\(-\) 1.000000000000000 |
\(-\) 1.000000000000000 |
2 | 1.000000000000000 | 0.000000000000000 | |
3 |
\(-\) 1.000000000000000 | 1.000000000000000 | |
\({\mathscr {P}} _2\)
| 1 |
\(-\) 0.666666666666667 |
\(-\) 0.789473684210526 |
2 | 0.555555555555556 |
\(-\) 1.000000000000000 | |
3 | 1.000000000000000 |
\(-\) 0.052631578947368 | |
4 |
\(-\) 0.555555555555556 | 1.000000000000000 | |
5 |
\(-\) 1.000000000000000 |
\(-\) 0.157894736842105 | |
\({\mathscr {P}} _3\)
| 1 | 0.413048522141662 | 0.781696234443715 |
2 | 0.024879797655533 | 0.415324992429711 | |
3 |
\(-\) 0.082799691823524 | 0.688810136531751 | |
4 |
\(-\) 0.533191422779328 | 1.000000000000000 | |
5 |
\(-\) 0.553573605852999 | 0.580958514816226 | |
6 |
\(-\) 0.972432940212767 | 0.734117068746903 | |
7 |
\(-\) 1.000000000000000 | 0.238078507228890 | |
8 |
\(-\) 0.789986179147920 | 0.012425068086110 | |
9 |
\(-\) 0.627452906935866 |
\(-\) 0.636532897516109 | |
10 |
\(-\) 0.452662174765764 |
\(-\) 1.000000000000000 | |
11 |
\(-\) 0.069106265580153 |
\(-\) 0.289054989277619 | |
12 | 0.141448047807069 |
\(-\) 0.464417038155806 | |
13 | 1.000000000000000 |
\(-\) 0.245698820584615 | |
14 | 0.363704451489016 |
\(-\) 0.134079689960635 | |
15 | 0.627086024018283 |
\(-\) 0.110940423607648 |
\({\mathscr {P}} _1\)
|
\({\mathscr {P}} _2\)
|
\({\mathscr {P}} _3\)
| |
---|---|---|---|
0 |
\(-\,0.0020324991\)
|
\(-\,0.002589861\)
| |
0.0111339078 |
\(7.4274779926\times 10^{-5}\)
|
\(1.5738050178\times 10^{-4}\)
| |
0.0030396808 |
\(6.0738145408\times 10^{-8}\)
|
\(1.3793481020\times 10^{-6}\)
| |
\(7.9534562047 \times 10^{-4}\)
|
\(2.2238524572\times 10^{-12}\)
|
\(4.2588831784\times 10^{-10}\)
| |
0 |
\(-\,2.0911953867\times 10^{-4}\)
| 0.0014996521 | |
0 |
\(-\,1.3797380205\times 10^{-5}\)
|
\(7.0356275077\times 10^{-4}\)
| |
0 |
\(-\,7.9203571311\times 10^{-7}\)
|
\(2.5065856538\times 10^{-4}\)
| |
\(-\,0.005890191\)
|
\(8.08469022058\times 10^{-5}\)
|
\(-\,1.330384913\times 10^{-4}\)
| |
\(-\,0.001868889\)
|
\(4.37593748009\times 10^{-5}\)
|
\(-\,3.963064075\times 10^{-5}\)
|
\({\mathscr {P}} _1\)
|
\({\mathscr {P}} _2\)
|
\({\mathscr {P}} _3\)
| |||||||
---|---|---|---|---|---|---|---|---|---|
A.1
|
A.2
|
A.3
|
A.1
|
A.2
|
A.3
|
A.1
|
A.2
|
A.3
| |
\(x^5y^5\)
| 0.054 | 0.159 | 0.616 | 0.083 | 0.244 | 0.973 | 0.227 | 0.678 | 2.856 |
\(x^{10}y^{10}\)
| 0.078 | 0.221 | 1.359 | 0.123 | 0.328 | 2.321 | 0.351 | 0.939 | 7.301 |
\(x^{20}y^{20}\)
| 0.124 | 0.344 | 4.060 | 0.207 | 0.540 | 7.399 | 0.580 | 1.498 | 22.70 |
\(x^{40}y^{40}\)
| 0.208 | 0.578 | 14.79 | 0.377 | 0.934 | 27.24 | 1.073 | 2.671 | 86.63 |
\(x^{10}y^5\)
| 0.064 | 0.191 | 0.999 | 0.081 | 0.296 | 1.699 | 0.237 | 0.833 | 5.125 |
\(x^{20}y^5\)
| 0.078 | 0.240 | 1.955 | 0.089 | 0.412 | 3.690 | 0.274 | 1.093 | 10.99 |
\(x^{40}y^5\)
| 0.107 | 0.363 | 4.975 | 0.085 | 0.616 | 9.504 | 0.332 | 1.680 | 29.40 |
\(x^5y^{20}\)
| 0.052 | 0.244 | 1.971 | 0.085 | 0.412 | 3.662 | 0.243 | 1.117 | 11.07 |
\(x^5y^{40}\)
| 0.051 | 0.365 | 5.009 | 0.082 | 0.597 | 9.295 | 0.272 | 1.673 | 29.17 |
2.2 Computational Complexity of Algorithm 1
-
Set \(d=2\) and assume \(k_1 \le k_2\), so that we can choose \(x_{0,1}\ne 0\) and \(x_{0,2} = 0\) on each of the edges of \({\mathscr {P}} \). Then, according to Algorithm 1 we haveandwhere we have denoted the vertices of the edge as \({\mathbf {v}}_{i1}\) and \({\mathbf {v}}_{i2}\). Hence,In general, for \(d=2\) we deduce that(14)
-
Set \(d=3\) and assume \(k_1 = \min \{k_1,k_2,k_3\}\), so that we may select \(x_{0,1} \ne 0\) and \(x_{0,2} = x_{0,3} = 0\) on each of the faces of \({\mathscr {P}} \). Thereby, employing Algorithm 1 we deduce thatwhere, for each \(i=1,\ldots ,m\),Here, the computational complexity of depends on the choice of \({\mathbf {x}} _{0} \equiv {\mathbf {x}} _{0,ij}\) which defines the origin of the coordinate system for , \(j=1,\ldots ,m_i\), \(i=1,\ldots ,m\). According to Remark 4, two components of \({\mathbf {x}} _{0,ij}\) can possibly be different from zero, which implies that the complexity of Algorithm 1 increases exponentially when \(d=3\). However, it is possible to modify Algorithm 1 in order to avoid the double recursive calls which cause this exponential complexity. In particular, in Sect. 2.3 we propose an alternative algorithm which exploits the same idea of Algorithm 1 and allows us to overcome this issue.
gauleg
, cf. [55], for example, is included/excluded. In particular, we show results both in the case when the cost of the function evaluations is excluded, cf. Fig. 7a, as well as the total number of FLOPs required by each algorithm to exactly evaluate \(\int _{{\mathscr {P}}} x^{k} y^{k}\mathrm {d} \mathbf{x}\), cf. Fig. 7b. As expected, the computational complexity of A.3 grows as \({\mathcal O}(k^2)\) and \({\mathcal O}(k^3)\) in these two latter cases, respectively, while the cost of the quadrature free method is always \({\mathcal O}(k)\) as k increases.2.3 Integration of Families of Monomial Functions
3 Application to hp-Version DG Methods
4 Elemental Stiffness and Mass Matrices
4.1 Shape Functions for the Discrete Space \(V_h\)
4.2 Volume Integrals Over Polytopic Mesh Elements
4.3 Interface Integrals over Polytopic Mesh Elements
5 Numerical Experiments
5.1 Two-Dimensional Test Case
PolyMesher
, cf. [65]. Here, we are interested in the CPU time needed to assemble the matrices (21) and (22).