\documentclass[aspectratio=149, sansserif, 9pt]{beamer}

\input{hal_prefs.tex}

\title[Low card. PI cub. on NURBS-shaped
domains.\hspace{0.25em}]{Low cardinality Positive Interior cubature on NURBS-shaped
domains}

\author{{\purples{\bf{Alvise Sommariva}}} and Marco Vianello}
\date{{\blues{\bf{Software for Approximation 2022}}} \\ February 3, 2022}

\begin{document}

\thispagestyle{empty}
\frame{\titlepage}


\begin{frame}[fragile]
\frametitle{Purpose}
We present an algorithm that computes an algebraic cubature rule 
$$\int_{\cal S} f(x,y) dx dy \approx \sum_{j=1}^{\eta} w_j f(Q_j)$$
over curvilinear polygons $\cal S$ defined by {\purples{piecewise rational functions}},
that 
\begin{itemize}
\item for $n$ fixed, is {\purples{exact}} for any $p \in {\mathbb{P}}_n$, being ${\mathbb{P}}_n$ the space of bivariate polynomials of total degree $n$ (i.e. ADE=$n$);
\item has {\purples{positive weights}} $\{w_j\}_j$ and {\purples{interior nodes}} $\{Q_j\}_j \subseteq {\cal S}$; 
\item has {\purples{low cardinality}}, i.e. $\eta \leq (n + 1)(n + 2)/2$ nodes.
\end{itemize}


\smsp

Examples are domains ${\cal S}$  such that $\partial{\cal S}$  is defined piecewise by 
\begin{itemize}
\item {\purples{NURBS}} curves,
\item by {\purples{composite Bezier}} curves,
\item parametric {\purples{splines}}.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Purpose}
{\purples{Key tools}}:
\begin{itemize}
\item overlooked theorem by Wilhelmsen (1976) on Tchakaloff sets, \\
{\blues{\scriptsize{(sufficiently dense set on $\cal S$ contains nodes of an algebraic rule of PI-type with ADE=$n$)}}},
\item a new in-domain algorithm for such curvilinear polygons, \\
{\blues{\scriptsize{(before available only on parametric spline curvilinear polygons or basic $\cal S$)}}},
\item the sparse nonnegative solution of underdetermined moment matching systems by the Lawson-Hanson NonNegative Least Squares solver, \\
{\blues{\scriptsize{(extracts nodes and determines positive weights from the dense pointset and moments of a basis of ${\mathbb P}_n$)}}}.
\end{itemize}

\smsp

{\purples{Applications}}:
\begin{itemize}
\item NEFEM with NURBS-shaped curvilinear elements,
\item VEM with NURBS-shaped curvilinear elements.
\end{itemize}

\end{frame}



\begin{frame}[fragile]
\frametitle{Examples of integration domains}
\begin{figure}[!htbp]
  \centering
   {\includegraphics[scale=0.175,clip]{ex1.eps}}
   {\includegraphics[scale=0.175,clip]{ex2.eps}}
      {\includegraphics[scale=0.175 ,clip]{ex3.eps}}
 \caption{Examples of integration domains.}
 \label{fig_2CRI}
 \end{figure}
 

\end{frame}


\begin{frame}[fragile]
\frametitle{In-domain routine for rational spline curvilinear polygons}
{\purples{Assumptions}}: \\

\smsp

the curvilinear polygon ${\cal{S}} \subset {\mathbb{R}}^2$ is a {\purples{Jordan domain}}  \\
{\blues{\scriptsize{(hence the domain has no holes and the boundary has no self-intersections)}}};
\begin{itemize}
\item whose boundary $\partial {\cal S}$ is described by {\purples{parametric equations}}
$x = \tilde{x}(t)$, $y = \tilde{y}(t)$, $t \in [a, b]$, $ \tilde{x},  \tilde{y} \in C([a, b])$, $\tilde{x}(a) = \tilde{x}(b)$ and $\tilde{y}(a) = \tilde{y}(b)$;
\\
{\blues{\scriptsize{(the boundary is described parametrically by two periodic continuous functions)}}};
\item for which there are partitions $\{I^{(k)}\}$, $k=1,...,M$ of $[a,b]$, and $\{I^{(k)}_j\}$ with $j=1,...,m_k$
of each $I^{(k)} := [t(k), t(k+1)]$, such that the restrictions of $\tilde{x}$, $\tilde{y}$ on each closed
interval $I^{(k)}$ are {\purples{rational splines}}, w.r.t. the subintervals $\{I^{(k)}_j\}$, \\
{\blues{\scriptsize{(the boundary is described parametrically by $M$ rational splines)}}}.

\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Example I: composite Bezier closed curves}
{\purples{I: composite Bezier closed curves}}: \\

\smsp
\begin{itemize}
\item for specific points $\{{\bf{P}}_{i,k}\}_{1,\dots,m_k} \subset {\mathbb{R}}^2$ choosen by the user;
\item defined the {\it{Bernstein polynomials}}
$$
b_{i,l}(t)=
\left( \begin{array}{c}  {l} \\ {i}\end{array} \right) t^i (1-t)^{l-i}, \,\,\, i=0,\ldots,l-1, \,\,\,\ t \in [0,1];
$$
\end{itemize}
the k-th curve is of the form
$$
{\cal{B}}({\tilde{t}})={\cal{B}}(\omega_k(t))=\sum_{i=0}^{m_k-1} b_{i,m_k-1}({{t}}) {\bf{P}}_{i+1,k},
$$
where 
$$
{\tilde{t}}=\frac{t^{(k+1)} + t^{(k)}}{2}+\frac{t^{(k+1)} - t^{(k)}}{2} t:=\omega_k(t), t \in [0,1], 
$$
{\blues{\scriptsize{(the boundary is described parametrically by continuous functions that are specific piecewise polynomials, often used in computer graphics)}}}.
\end{frame}



\begin{frame}[fragile]
\frametitle{Example II: NURBS}
{\purples{II: NURBS}}: \\

\smsp
{{
domains $\cal S$ in which $\partial {\cal S}$ is locally a $p$-th degree NURBS curve, i.e. defined in the  curvilinear side $V_k \frown V_{k+1}$ as

$$
{\bf{C}}(t)=\frac{\sum_{i=1}^{m_k} B_{i,p}(t) \,w_i {\bf{P}}_{i,k} }{\sum_{i=1}^{m_k} B_{i,p}(t) \,w_i}, \,\,\, t \in [t^{(k)}, t^{(k+1)}]
$$

\noindent where

\begin{itemize}
\item $\{{\bf{P}}_{i,k}\}_{i=1}^{m_k}$ are the {\reds{control points}}, $\{{\bf{w}}_{i,k}\}_{i=1}^{m_k}$ are the {\reds{weights}},
\item $\{B_{i,p}\}_{i=1}^{m_k}$ are suitable $p$-th degree {\reds{B-spline basis functions}} defined on the nonperiodic (and nonuniform) knot vector
$$
U=\{ \underbrace {t^{(k)},\ldots,t^{(k)}}_{p+1},t^{(k)}_{p+1},\ldots,t^{(k)}_{m_k-(p+1)},\underbrace {t^{(k+1)},\ldots,t^{(k+1)}}_{p+1}\}.
$$
with $t_{p+j}^{(k)} \leq t_{p+j+1}^{(k)}$, $j=1,\ldots,m_k-1$,
\end{itemize}
}}
{\blues{\scriptsize{(the boundary $\partial {\cal S}$ is described parametrically by continuous functions that are specific piecewise rational functions, often used in computer graphics)}}}.
\end{frame}




\begin{frame}[fragile]
\frametitle{In-domain algorithm: Jordan curve theorem}

{\purples{Jordan curve theorem}}: \\ a point $P$ belongs to a Jordan domain ${\cal{S}}$ if and only if, 
having taken a point $P^* \notin {\cal{S}}$ then the segment 
${\overline{P^*P}}$ crosses $\partial {\cal{S}}$ an odd number $c(P)$ of times. 

\begin{figure}[!htbp]
  \centering
   {\includegraphics[scale=0.25,clip]{FIG1.eps}}
   {\includegraphics[scale=0.25,clip]{FIG2.eps}}
 \caption{Points and boundary intersections. On the left $c(P)=1$ and the point $P$ is in the domain. On the right $c(P)=2$ and the point $P$ is outside the domain.}
 \label{fig_2CRI}
 \end{figure}
 
\end{frame}




\begin{frame}[fragile]
\frametitle{In-domain algorithm: Pathological cases}

{\purples{Pathological cases}}: 
\begin{figure}[!htbp]
  \centering
   {\includegraphics[scale=0.178,clip]{sing_spl_side2.eps}}
   {\includegraphics[scale=0.178,clip]{sing_spl_side3.eps}}
   {\includegraphics[scale=0.178,clip]{sing_spl_side1.eps}}
 \caption{Critical situations for establishing the crossing number on curvilinear polygons.}
 \label{fig_2CRI}
 \end{figure}
\end{frame}





\begin{frame}[fragile]
\frametitle{In-domain algorithm: implementation}

{\purples{Basic idea}}: 
\begin{itemize}
\item {\reds{Cover the boundary $\partial {\cal S}$ by rectangles}}, with sides parallel to the axes, so that $x={\tilde{x}}(t)$ and $y={\tilde{y}}(t)$ are monotone (we will name them {\purples{monotone boxes}}). Thus, the boundary is the graph of a local monotone Cartesian function in $x$ and $y$.
\item For each point $P$ that is not in a pathological case, {\reds{count the $c_0(P)$ monotone boxes {\sl{strictly below}} $P$}}.
\item If a point is {\reds{inside some monotone boxes}}, count all the $c_1(P)$ times that is {\sl{over}} the part of the boundary belonging to the box. 
\item Put $c(P)=c_0(P)+c_1(P)$. If $c(P)$ is {\reds{odd then $P$}} is inside $\cal S$, otherwise it is not inside the curvilinear domain.
\item For pathological cases, use alternative techniques, see [1].
\end{itemize}
\end{frame}




\begin{frame}[fragile]
\frametitle{In-domain algorithm: examples I}
\begin{figure}[!htbp]
  \centering
   {\includegraphics[scale=0.27,clip]{FIG3.eps}}
   {\includegraphics[scale=0.27,clip]{FIG4.eps}}
 \caption{Monotone boxes and computation of the crossing number $c(P)$ when $\cal{P}$ is a disk. On the left figure, $c(P)=1$, on the right one $c(P)=2$.}
 \label{fig_3CRI}
 \end{figure}
\end{frame}



\begin{frame}[fragile]
\frametitle{In-domain algorithm: examples II}


\begin{figure}[!htbp]
  \centering
   {\includegraphics[scale=0.175,clip]{S3B.eps}}
   {\includegraphics[scale=0.175,clip]{S4B.eps}}
   {\includegraphics[scale=0.13,clip]{S5B.eps}}
 \caption{Monotone boxes and detection of the points inside the domain.}
 \label{fig_2CRI}
 \end{figure}
 
\end{frame}



\begin{frame}[fragile]
\frametitle{In-domain algorithm: main difficulties}
{{
\begin{enumerate}
\item Fast determination of the monotone boxes, from the piecewise rational splines ${\tilde{x}}$, ${\tilde{y}}$ (pre-processing);
\item analysis of the pathological points;
\item for each point $P$, fast determination of the monotone boxes necessary to the computation of $c(P)$;
\item fast determination if a point $P$ belonging to a monotone box is over or below the curve relative to the monotone box;
\item deciding when a point $P$ close to the boundary $\partial {\cal S}$ is {\it{numerically inside}} $ {\cal S}$ or not.
\item for cubature purposes, we must be able to analyse 1000 points in less than $10^{-3}$ seconds, including the pre-processing cputime.
\end{enumerate}
}}

\begin{remark}
{{The fact that the boundary is described parametrically by piecewise rational splines is fundamental in items {\purples{1}}, {\purples{4}}, {\purples{5}}.}}
\end{remark}
\end{frame}





\begin{frame}[fragile]
\frametitle{Moments computation}
Having in mind to compute a rule with algebraic degree of precision $ADE=n$ by moments equations, we 

\begin{itemize}
\item define a {\purples{suitable basis}} $\{\phi_j\}$ of the polynomial space ${\mathbb{P}}_n$ ({\it{tensorial Chebyshev}} on the bounding box ${\cal R}^*$ of $\cal{S}$), 
\item compute the {\purples{moments}} $\gamma_1,\ldots,\gamma_N$, where
$$
{\reds{
\gamma_j:=\int_{\cal S} \phi_j(x,y) dx dy.
}}
$$
\end{itemize}
\smsp

To this purpose:

\begin{enumerate}
\item By applying the {\purples{Gauss-Green}} theorem, each $\gamma_j$ is the sum of some line integrals, that after some computation are shown to require the {\purples{integration in $[-1,1]$ of continuous rational functions}}.
\item We compute these integrals in $[-1,1]$ by {\purples{high-order Gauss-Legendre  rule}} (other techniques may be used).
\end{enumerate}
\end{frame}





\begin{frame}[fragile]
\frametitle{Implementing Tchakaloff-like algebraic cubature rules}
We {\purples{extract the nodes and positive weights 
of a Tchakaloff-like algebraic cubature rule}} (i.e. a rule with ADE=$n$, positive weights, and cardinality at most equal to the dimension of ${\mathbb{P}}_n$, i.e. $N=(n+1)(n+2)/2$), by the following algorithm:
{{
\begin{itemize}
\item compute the {\purples{moments}} $\gamma=(\gamma_j)$ of a suitable basis of ${\mathbb{P}}_n$; \\ 
\smsp
\begin{center}
{{\red{at the k-th iteration of the algorithm}}}
\end{center}
\item  introduce a {\purples{tensorial grid}} 
${\cal{M}}_\ell$ in the rectangle ${\cal{R}}^*:=[a_1,b_1] \times [a_2,b_2]$ 
containing ${\cal{S}}$;
\item determine by the {\purples{{\it{in-domain}}}} algorithm, at the ${\ell}$-th iteration of 
the procedure, the set 
$${\cal{P}}_{\ell}={\cal{P}}_{\ell-1} \cup ({\cal{M}}_\ell \cap {\cal{S}})$$
({\blues{\scriptsize{the points of the analysed meshes, as well as of the present one, 
belong to $\cal S$}}});
\item compute the {\purples{Vandermonde matrix}} $V_{{\cal{P}}_{\ell}}=(\phi_j ({\cal{P}}^{(\ell)}_i))_{i,j}$ (relatively to the basis $\{\phi_j\}$ of ${\mathbb{P}}_n$ and the pointset ${\cal{P}}_{\ell}=\{ {\cal{P}}^{(\ell)}_i \}$);
\end{itemize}
}}
\end{frame}


\begin{frame}[fragile]
\frametitle{Implementing Tchakaloff-like algebraic cubature rules}
{{
\begin{itemize}
\item apply the {\purples{Lawson-Hanson algorithm}} to attempt to find a solution $w^* \geq 0$ to the overdetermined linear system $V_{{\cal{P}}_{\ell}}w=\gamma$ \\ 
{\blues{\scriptsize{(any solution provides an alg. rule with pos. weights, internal nodes, $ADE=n$)}}};
\item find the {\purples{nonnull components of $w^*$}}, say $\{w^{(\ell)}_i\}_{i=1,\ldots,\nu_\ell}$;
\item determine the {\purples{corresponding nodes}} $\{(x^{(\ell)}_i,y^{(\ell)}_i)\}_{i=1,\ldots,\nu_\ell}$, $\nu_\ell\leq N$ \\
{\blues{\scriptsize{(if $w_l^* >0$ then $(x^{(\ell)}_l,y^{(\ell)}_l)$ is the relative node);}}}
\item for a fixed tolerance $\varepsilon$, check if the so obtained rule is such that
$$
\gamma_j^{(\ell)}=\sum_{i=1}^{\nu_\ell} w^{(\ell)}_i 
\phi_j(x^{(\ell)}_i,y^{(\ell)}_i), {\mbox{   }}j=1,\ldots,N\;,
$$
{\purples{well approximates the set of moments}} $\gamma=\{\gamma_j\}$, i.e.
\begin{equation}\label{eqtoll}
\|\gamma^{(\ell)}-\gamma\|_{2} \leq \varepsilon
\end{equation}
{\blues{\scriptsize{(the cubature rule numerically matches the moments at $ADE=n$)}}};
\item if (\ref{eqtoll}) does not hold, iterate the procedure.
\end{itemize}
}}

\end{frame}


\begin{frame}[fragile]
\frametitle{Implementing Tchakaloff-like algebraic cubature rules}

{\purples{Comment:}} 
{{
\begin{itemize}
\item The basic idea is to fill the domain $\cal S$ with points until one is able to determine the wanted ruled by Lawson-Hanson algorithm [5].
\item Important: Lawson-Hanson will find a solution with at most {\purples{$(n+1)(n+2)/2$}} positive components!
\item In {\purples{VEM}}, the algebraic degree of precision $ADE=n$ is typically low, say $n \leq 5$, and all the process must take at most $10^{-2}$ seconds (many MATLAB tricks!).
\item By construction the rules have {\purples{internal nodes and positive weights}}.
\item In exact arithmetic this procedure has 
{\purples{finite termination}} in view of a theorem by Wilhelmsen mentioned above 
[5], 
since the set ${\cal{P}}_{\ell}$ becomes sufficiently dense 
after a finite number of iterations.
\item Many {\purples{technical details}} are skipped and can be found in [1].
\end{itemize}
}}
\end{frame}








\begin{frame}[fragile]
\frametitle{Numerical examples: cubature}
We have implemented in Matlab the ideas sketched above (cf.[3]).

\smsp

In order to show the flexibility of our method, we consider the domains that are in the next figure from left to right,
\begin{enumerate}
\item a {\purples{"M" shaped domain}} ${\cal{S}}_1$, in which $\partial {\cal{S}}_1$ 
is determined by a unique order 3 NURBS curve with 16 distinct control points,
\item a {\purples{convex domain}} ${\cal{S}}_2$, where $\partial {\cal{S}}_2$ 
is obtained by joining a circular and an elliptical arc, followed by  a segment,
\item a {\purples{concave domain}} ${\cal{S}}_3$ whose boundary $\partial {\cal{S}}_3$ 
consists of a unique NURBS curve of order 3 with 9 distinct control points.
\end{enumerate}

\end{frame}



\begin{frame}[fragile]
\frametitle{Numerical examples: cubature}
 \begin{figure}[!htbp]
  \centering
   {\includegraphics[scale=0.175,clip]{domain03_06.eps}}
   {\includegraphics[scale=0.175,clip]{domain04_06.eps}}
    {\includegraphics[scale=0.175,clip]{domain05_06.eps}}
 \caption{{The curvilinear domains ${\cal{S}}_i$
with $i=1,2,3$, the grid points $P$ outside the domain or on its boundary
(in red), those inside the domain (in green) and the nodes of
a cubature formula of PI-type for $n=6$ (28 magenta dots). The control 
points of the NURBS curve are represented as cyan squares, joined 
to represent the so called {\it{control points polygon}}.}}
 \label{fig_1N2}
 \end{figure}

\end{frame}



\begin{frame}[fragile]
\frametitle{Numerical examples: cubature}

{{
\begin{table}[ht]
\begin{center}\small
{\renewcommand{\arraystretch}{1.1}
\begin{tabular}{| c | c | c | c | c | c | c |  }
\hline
& {\mbox{n}} & $\#$ & {\mbox{\#}} trial pts & {\mbox{cond}} & {\mbox{moment res}} & {\mbox{cpu}}  \\
\hline
 	${\cal{S}}_1$ &  $ 2 $  & $6$    & $28$ ($121$) & $1$ &  5$e-$16 
&  1.3$e-$2 \\
 	   	             & $4 $   & $15$ & $108$ ($377$) & $1$ 
&   1$e-$15 &  1.8$e-$2\\
 	   	             & $6 $    & $28$& $225$ ($637$) & $1$ 
&   1$e-$15 &  2.2$e-$2\\
 	   	             & $8 $   & $45$ & $693$ ($1573$) & $1$ 
&   3$e-$15 &  3.4$e-$2\\
 	   	             & $10 $   & $66$& $1304$ ($3077$) & $1$ 
&   5$e-$15 &  8.5$e-$2\\		 
\hline
\hline
 	${\cal{S}}_2$ & $ 2 $  & $6$     & $65$ ($121$) & $1$ &  8$e-$16 
&  4.8$e-$3 \\
 	   	             & $4 $   & $15$ & $65$ ($121$) & $1$ 
&  2$e-$15 &  4.8$e-$3\\
 	   	             & $6 $    & $28$& $109$ ($196$) & $1$ 
&   2$e-$15 &  6.6$e-$3\\
 	   	             & $8 $   & $45$ & $274$ ($484$) & $1$ 
&   2$e-$15 &  9.0$e-$3\\
 	   	             & $10 $   & $66$& $609$ ($961$) & $1$ 
&   3$e-$15 &  1.5$e-$2\\		 
\hline
\hline
 	${\cal{S}}_3$ & $ 2 $  & $6$ & $50$ ($121$) & $1$ &  5$e-$16 
&  5.3$e-$3 \\
 	   	             & $4 $   & $15$ & $50$ ($121$) & $1$ 
&   7$e-$16 &  6.1$e-$3\\
 	   	             & $6 $    & $28$ & $89$ ($196$) & $1$ 
&   1$e-$15 &  7.6$e-$3\\
 	   	             & $8 $   & $45$ & $239$ ($484$) & $1$ 
&   2$e-$15 &  1.1$e-$2\\
 	   	             & $10 $   & $66$ & $491$ ($961$) & $1$ 
&   4$e-$15 &  1.6$e-$2\\		 
\hline
\end{tabular}
        }
\caption{{Degree of precision $n=2,4,6,8,10$ of the rule, cardinality $\#$ 
of the extracted nodes, 
cubature conditioning and moment residual of the rule 
on domains ${\cal{S}}_i$, $i=1,2,3$, number of trial points used 
in the extraction, cubature condition number {\tt{cond}}, moment residual 
of the rule 
and median of the cputime over 50 tests.}}
\label{tab01}
\end{center}
\end{table}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Numerical examples: cubature}
{{
As a further illustration, we report in the next Table
the relative errors made by the Tchakaloff-like rules when  
approximating $\int_{{\cal{S}}_i} f_k(x,y) \, dx \, dy$, where
\begin{eqnarray}
f_1(x,y) &=& \exp(-(x^2+y^2)), \nonumber \\
f_2(x,y) &=& ((x-x_0)^2+(y-y_0)^2)^{11/2}\;, {\mbox{   }} 
(x_0,y_0)=(0,0.4),\nonumber  \\
f_3 (x,y) &=& ((x-x_0)^2+(y-y_0)^2)^{1/2}\;, {\mbox{   }}  
(x_0,y_0)=(0,0.4), \nonumber 
\end{eqnarray} 

\begin{itemize}
\item The functions $f_k$, $k=1,2,3$ are examples of functions with different degree of regularity 
on each domain 
${{\cal{S}}_i}$, $i=1,2,3$. 
\item The reference values of these integrals are those 
obtained by the same routines with $ADE=20$.
\item As expected, in both the domains the quality of the 
approximation worsens for less regular integrands (indeed $f_1\in 
C^\infty(\mathcal{S}_i)$, whereas $(0,0.4)\in 
\mathcal{S}_i$ is a singular point for the first derivatives of $f_3$ 
and for $6$-th derivatives of $f_2$). 
\end{itemize}
}}
\end{frame}


\begin{frame}[fragile]
\frametitle{Numerical examples: cubature}

\begin{table}[!htbp]
\begin{center}\small
\begin{tabular}{| c | c  | c  | c | c  | c  | c |  c  | c  | c |}
\hline
\multicolumn{1}{| c |}{} & \multicolumn{3}{| c |}{${\cal{S}}_3$}  & \multicolumn{3}{| c |}{${\cal{S}}_4$}  
& \multicolumn{3}{| c |}{${\cal{S}}_5$} \\
\hline
{\mbox{ADE}} & $f_1$ & $f_2$ &  $f_3$ & $f_1$ & $f_2$ &  $f_3$ & $f_1$ 
& $f_2$ &  $f_3$ \\
  \hline 
2&2$e-$02& 4$e-$01& 4$e-$02& 4$e-$03& 9$e-$01 &6$e-$02 &6$e-$03 &2$e-$01& 1$e-$02\\
4&3$e-$03& 2$e-$01& 9$e-$02& 3$e-$04& 2$e-$02 &4$e-$02 &9$e-$04 &2$e-$01& 1$e-$02\\
6&3$e-$04& 4$e-$02& 6$e-$03& 4$e-$05& 3$e-$02& 2$e-$02& 4$e-$05& 1$e-$02 &4$e-$03\\
8& 3$e-$05&3$e-$03 &2$e-$03 &1$e-$06& 8$e-$04 &1$e-$03& 2$e-$06&2$e-$03& 3$e-$03\\
10&1$e-$06 &8$e-$05 &1$e-$03 &8$e-$09& 4$e-$05 &2$e-$04 &8$e-$08& 3$e-$05 &2$e-$04\\
\hline
\end{tabular}
\caption{{Relative errors of the new rules on the domains 
$\mathcal{S}_{i}$, $i=1,2,3$ with 
$ADE=2,4,6,8,10$. }}
\label{tab02a}
\end{center}
\end{table}

\end{frame}




\begin{frame}[fragile]
\frametitle{Numerical examples: indomain} 

\begin{table}[!htbp]
\begin{center}\small
\begin{tabular}{|c | c| c | c | c |}
\hline
$\#$ & algorithm   & ${\cal S}_1$ & ${\cal S}_2$
& ${\cal S}_3$ \\
\hline
& $inRS1$  & 4.3$e-$03$s$  & 1.9$e-$03$s$ &  2.1$e-$03$s$\\
$10^3$ & $inRS2$ & 2.8$e-$03$s$  & 1.3$e-$03$s$  & 1.3$e-$03$s$\\
& speed-up & 1.5  & 1.5 & 1.6\\
\hline
\hline
& $inRS1$  & 1.8$e-$02$s$  & 8.8$e-$03$s$ & 9.5$e-$03$s$\\
$10^4$ & $inRS2$ & 4.4$e-$03$s$  & 3.2$e-$03$s$ & 3.2$e-$03$s$\\
& speed-up & 4.1  & 2.8 & 3.0\\
\hline
\hline
& $inRS1$  & 1.6$e-$01$s$  & 7.3$e-$02$s$ &  8.0$e-$02$s$\\
$10^ 5$ & $inRS2$ & 1.7$e-$02$s$  & 2.1$e-$02$s$ & 2.0$e-$02$s$\\
& speed-up & 9.4 & 3.5 & 4.0\\
\hline
\end{tabular}
\caption{{The indomain algorithm named {\tt{inRS1}} proposed in [1] has been improved in [2] by {\tt{inRS2}}. In this table we list the CPU time of
these routines on the three 
NURBS-shaped domains ${\cal S}_i$, $i=1,2,3$, with $\#$ Halton points 
of the corresponding bounding box.}}
\label{tab01}
\end{center}
\end{table}

\end{frame}




\begin{frame}[fragile]
\frametitle{MATLAB Software}

\begin{itemize}
\item All the MATLAB routines and demos are collected in the toolbox {\purples{\tt{CUB\_RS}}} and can be downloaded at [3]. 
\item We are not aware of 
the existence of an official built-in {\purples{NURBS toolbox}} (though it can be 
retrieved by third-parties and MATLAB has a specific environment for 
rational splines). Thus we have implemented a set of routines to describe $\partial {\cal S} \subset {\mathbb{R}}^2$ by 
piecewise rational  splines, including parametric splines or 
composite Bezier curves or NURBS.
\item Finally we provide the routines
\begin{itemize}
\item {\purples{\tt{inRS}}} that implement the faster in-domain algorithm introduced in [2] (of interest also in {\purples{meshless methods}}),
\item {\purples{\tt{cubRS}}} that computes a PI-type Tchakaloff-like algebraic 
cubature rule of degree $n$,
\end{itemize}
for the designed domain $\cal S$.
\end{itemize}

\end{frame}





\begin{frame}[fragile]
\frametitle{Future research}

\begin{itemize}
\item Fast filling of the domain;
\item generalisation to domains that are not simply connected;
\item application to PDE problems with VEM and NEFEM;
\item application to meshless methods;
\item 3D instances (very difficult task!).
\end{itemize}

\end{frame}



\begin{frame}[fragile]
\frametitle{Bibliography}

{{

\begin{enumerate}
\item A. Sommariva and M. Vianello, Low cardinality Positive Interior cubature on NURBS-shaped domains (submitted). \\
{\blues{\scriptsize{(Cubature and first indomain routine)}}}


\item A. Sommariva and M. Vianello, inRS: implementing the indicator function for NURBS-shaped planar domains (submitted).\\
{\blues{\scriptsize{(Faster indomain routine)}}}

\item {\purples{Matlab software:}} A. Sommariva homepage, {\url{https://www.math.unipd.it/~alvise/software.html}}.

\item A. Sommariva, M. Vianello, 
  Compression of multivariate discrete measures and applications, 
  {\em Numer. Funct. Anal. Optim.}, 36 (2015), 1198--1223. \\
{\blues{\scriptsize{(Details on cubature compression)}}}

\item D. R. Wilhelmsen,
  A Nearest Point Algorithm for Convex Polyhedral
Cones and Applications to Positive Linear approximation,
  {\em Math. Comp.}, 30 (1976), 48-57.
\end{enumerate}

}}


\end{frame}

\end{document}


