Compressed cubature over polygonal domains
B.J. Bauman, A. Sommariva, M. Vianello
L. Livermore National Labs and Universit`a degli Studi di Padova
Introduction
Purpose: we intend to compute integrals over polygons Ω determining nodes and weights of algebraic formulas with a fixed degree of precision δ.
Meaning: given a polygon Ω ⊂ R2, determine nodes
{xi}i =1,...,M ⊂ R2 and weights {w i}i =1,...,M ∈ R such that Z Ω p(x )d Ω = M X i =1 wip(xi)
Examples I
Examples II
Approach I (2007)
In [3], the authors considered the case of simple polygons Ω, i.e. without self intersections, having the so called axis-property. This class:
I includes all convex polygons;
I includes many non convex polygons;
I in general does not include not simple or not simply connected polygons.
Algorithm features:
I no need of particular triangulators (polygon easily subdivided in triangles and quadrilaterals Ωi);
I algebraic formula with nodes in Ω and positive weights can be
Examples
Approach II (2009/2011)
In [1], it has been proposed a cubature algorithm that usesminimal triangulationof Ω (Chazelle 1991).
In particular, if Ω has N sides and is simple and simply connected, then Ω can be decomposed in N − 2 triangles Ω1, . . . , ΩN−2, and
in each one one can apply a rule with algebraic degree of precision ADE = δ.
Based on our naive algorithm, this class:
I includes all convex polygons;
I includes allnon convex polygons;
I in general does notinclude not simple or not simply connected polygons.
Algorithm peculiarities:
I on each triangle, one can use a Stroud Conical Product
Examples
Approach III (2018)
Recently Matlab introduced the routine polyshape as part of its environment.
This new class includes several facilities.
I It allows boolean operations, as intersection, difference, union, and symmetrical difference between polygons.
I It allows rotation, scaling and translation of the given sets.
I It allows triangulation on each polygon Ω, that can be of very general nature, even not simply connected, not simple or disconnected.
Approach III (2018)
After the definition of a polygon by the call of polyshape, the decomposition determined by triangulation:
I includes all convex polygons;
I includes allnon convex polygons;
I includes not simple (careful!) or not simply connected polygons.
Algorithm peculiarities:
I on each triangle one can use aquasi minimal rule with ADE = δ;
I as alternative, the previous ones are not available, on each triangle one can use a Stroud Conical Product cubature rule with ADE = δ positive weights and cardinality (δ + 1)2/4 for
Approach III (2018): fast and reliable algorithm?
How fast and reliable is the triangulation algorithmwhen one increases the number of sides? In this sense, we studied the following regions:
1. aregular polygonP(1)
whose n vertices are Pk= (cos(tk), sin(tk))
where tk= 2πkn , with k = 1, . . . , n;
2. apolygonal cardioidP(2)
whose n vertices are
Pk= (cos(tk0) · (1 − cos(tk)), sin(tk) · (1 − cos(tk)))
where tk= 2πkn , with k = 1, . . . , n;
3. apolygonal Bernoulli lemniscate P(3) whose n vertices are
Pk= (
√
2 cos(tk)/(1 + sin2(tk),
√
2 cos(tk) sin(tk)/(1 + sin2(tk)),
Approach III (2018): fast and reliable algorithm?
Figura:Triangulation over regions P(k), k = 1, 2, 3 (notice that P(3) is
Approach III (2018): fast and reliable algorithm?
Tabella:Cputime of triangulation of polygonal domains P(k); t P is the
cputime for the construction of the polyshape object, tT for the
Approach III (2018): cardinality almost minimal rules
Tabella:Cardinality Nδ∗ of (almost) minimal rules on triangles with ADE = δ. They are lower than (δ + 1)2/4 Stroud rules, for δ odd. Example: δ = 10, the cardinality of Stroud rules is 36, for δ = 50 is 676.
Approach III (2018): cardinality of the rules
Experiments for δ = 10 in the previous convex or non convex domain.
2007: Example 1: 660, Example 2: 870. Cputimes: ≈ 1 · 10−2 .
2009: Example 1: 144, Example 2: 252. Cputimes: ≈ 1 · 10−3 .
2018: Example 1: 96, Example 2: 168. Cputimes: ≈ 1 · 10−3 .
The dimension of polynomial space isdim = 66and we observe
Rule compression: Caratheodory-Tchakaloff subsampling
In some recent papers (see, e.g. [4]), the authors have applied a mathematical tool named CATCH (acronym of
(Caratheodory-Tchakaloff) subsampling), for the compression of discrete measures (as those obtained by the previous algorithms). In view of a discrete version of Tchakaloff theorem proved by Caratheodory theorem on finite-dimensional conic/convex combinations,starting from a rule with positive weights over a region Ω and algebraic degree of precision ADE = δ it is possible to extract a formula with at most (δ + 1)(δ + 2)/2 of those nodes, positive weights, having still ADE = δ.
Example over not simple polygons.
An advantage is the possibility of determining cubature rules on not simple polygons as thepolygonal Bernoulli lemniscate, not previously available.
Example over not simple polygons.
After compression we can reduce the number of points.
Example over polygonal obscured and vignetted pupils.
A problem arising in optical design is to determine a cubature formula of ADE = δ ≤ 25 over bivariate domains Ω that were filled circular or elliptical apertures (pupils), in order to compute root-mean-square (rms) spot size for an optical design.
Example over polygonal obscured and vignetted pupils.
I Recent studies by Bauman and Xiao, considered cases where
the pupil is obscured and vignetted. Indeed, Large Synoptic Survey Telescope (LSST) has a large central obscuration (about 62 per cent obscuration by diameter) as well as a considerable vignetting (of up to 10 per cent by area) making previous techniques developed not appropriate for the problem.
Example over polygonal obscured and vignetted pupils.
We determined cubature formulas over these regions by applying the algorithm that uses polyshape objects and finally we compressed them.
Example over polygonal obscured and vignetted pupils.
Tabella:Comparison of the moments of cubature rules obtained via triangulation (with/without compression) as well as their cardinalities NT, NTC, on two polygons Ω(M1), Ω(M2), with ADE = δ, partitioned
respectively in 220 and 1087 triangles.
Bibliografia
F. Basaglia, A new cubature method over polygons (Italian), Laurea Thesis in Mathematics, University of Padova, 2009 (advisors A. Sommariva and M. Vianello).
M. Gentile, A. Sommariva and M. Vianello, Polynomial interpolation and cubature over polygons, J. Comput. Appl. Math. 235 (2011), pp.5232–5239.
A. Sommariva and M. Vianello, Product Gauss cubature over polygons based on Green’s integration formula, BIT Numerical Mathematics 47 (2007), pp.441–453.
