Constrained and Unconstrained Stable Discrete Minimizations for p-Robust Local Reconstructions in Vertex Patches in the de Rham Complex

We analyze constrained and unconstrained minimization problems on patches of tetrahedra sharing a common vertex with discontinuous piecewise polynomial data of degree p. We show that the discrete minimizers in the spaces of piecewise polynomials of degree p conforming in the \(H^1\), \({\varvec{H}}(\textbf{curl})\), or \({\varvec{H}}({\text {div}})\) spaces are as good as the minimizers in these entire (infinite-dimensional) Sobolev spaces, up to a constant that is independent of p. These results are useful in the analysis and design of finite element methods, namely for devising stable local commuting projectors and establishing local-best–global-best equivalences in a priori analysis and in the context of a posteriori error estimation. Unconstrained minimization in \(H^1\) and constrained minimization in \({\varvec{H}}({\text {div}})\) have been previously treated in the literature. Along with improvement of the results in the \(H^1\) and \({\varvec{H}}({\text {div}})\) cases, our key contribution is the treatment of the \({\varvec{H}}(\textbf{curl})\) framework. This enables us to cover the whole de Rham diagram in three space dimensions in a single setting.

1. Actually, some geometrical situations for boundary patches were excluded in [22] (at most two simplices in the patch \({\mathcal {T}}_{{\varvec{a}}}\) or the existence of an interior vertex in \(\Gamma \); these are now covered by the proof detailed in Sect. 7 below).

Authors and Affiliations

1. Laboratoire Paul Painlevé, Inria Univ. Lille, 59655, Villeneuve-d’Ascq, France

   Théophile Chaumont-Frelet

2. Inria, 48 rue Barrault, 75647, Paris, France

   Martin Vohralík

3. CERMICS, Ecole des Ponts, 77455, Marne-la-Vallée, France

   Martin Vohralík

Corresponding author

Correspondence to Théophile Chaumont-Frelet.

Communicated by Rob Stevenson.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (Grant Agreement No 647134 GATIPOR)

Appendix A: Mapping a Two-Dimensional Triangular Mesh into a Reference Triangle

In this appendix, we study two-dimensional triangular meshes that correspond to the planar meshes \(\lceil {\mathcal {T}}_{{\varvec{0}}}\rceil \) from Sect. 7. We will use some basic notions from the graph theory and use Tutte’s embedding theorem [34]. We start be recalling the following basic notion:

Definition A.1

(Triconnected graph) A graph \(({\mathscr {V}},{\mathscr {E}})\), with the vertex set \({\mathscr {V}}\) and the edge set \({\mathscr {E}}\), is triconnected if it has at least four vertices and if it remains connected if any two vertices, together with its corresponding edges, are removed from respectively \({\mathscr {V}}\) and \({\mathscr {E}}\).

Lemma A.2

(Triconnected graph) Consider a conforming planar triangular mesh \({\mathcal {T}}\) with at least two elements K, and assume that the set \(\omega \subset {\mathbb {R}}^2\) covered by the elements of \({\mathcal {T}}\) is connected with a connected Lipschitz boundary. Let us denote by \({\mathcal {V}}\) and \({\mathcal {E}}\) the sets of vertices and edges of \({\mathcal {T}}\) and by \({\mathcal {V}}^{\textrm{ext}}\) and \({\mathcal {E}}^{\textrm{ext}}\) the set of boundary vertices and edges of \({\mathcal {T}}\). If all edges \(e = [{\varvec{a}},{\varvec{b}}] \in {\mathcal {E}}\) that have two vertices \({\varvec{a}},{\varvec{b}}\in {\mathcal {V}}^{\textrm{ext}}\) are boundary edges (i.e. \(e \in {\mathcal {E}}^{\textrm{ext}}\)), then the undirected graph \(({\mathcal {V}},{\mathcal {E}})\) is triconnected.

Remark A.3

(Non-triconnected graph) A counterexample showing that, in general, a triangular mesh \({\mathcal {T}}\) does not have a triconnected graph, is presented in Fig. 12. There, the assumption that all edges with two boundary vertices are boundary edges is violated.

A non-triconnected graph

Full size image

Vertex patches: Examples of path joining vertices before and after the vertex has been removed

Full size image

Edge \([{\varvec{a}},{\varvec{b}}]\) such that both \({\varvec{a}}\), \({\varvec{b}}\) lie in \({\mathcal {V}}^{\textrm{int}}\): example of path joining two vertices before and after the edge is removed

Full size image

Edge \([{\varvec{a}},{\varvec{b}}]\) such that \({\varvec{b}}\) lies in \({\mathcal {V}}^{\textrm{int}}\) and \({\varvec{a}}\) lies in \({\mathcal {V}}^{\textrm{ext}}\): example of path joining two vertices before and after the edge is removed

Full size image

Edge \([{\varvec{a}},{\varvec{b}}]\) such that both \({\varvec{a}}\), \({\varvec{b}}\) lie in \({\mathcal {V}}^{\textrm{ext}}\): example of path joining two vertices before and after the edge is removed

Full size image

Proof

Notice first that the assumption that \({\mathcal {T}}\) contains at least two elements ensures that \({\mathcal {V}}\) contains at least four vertices, so that we fit in the context of Definition A.1. Considering a mesh \({\mathcal {T}}\) satisfying the assumptions above, we need to show that if we remove any pair of vertices \({\varvec{a}},{\varvec{b}}\in {\mathcal {V}}\), the associated graph \(({\mathcal {V}},{\mathcal {E}})\) remains connected. It means that if \({\varvec{c}},{\varvec{d}}\in {\mathcal {V}}\) are two other points, we can join \({\varvec{c}}\) to \({\varvec{d}}\) via a sequence of edges without passing through \({\varvec{a}}\) or \({\varvec{b}}\).

For the sake of clarity, we use the additional notation \({\mathcal {V}}^\textrm{int} :={\mathcal {V}}{\setminus } {\mathcal {V}}^{\textrm{ext}}\) and \({\mathcal {E}}^{\textrm{int}} :={\mathcal {E}}{\setminus } {\mathcal {E}}^{\textrm{ext}}\) in the reminder of the proof. Let us first consider the operation of removing a single vertex \({\varvec{a}}\in {\mathcal {V}}\). Then, since the set \(\omega \subset {\mathbb {R}}^2\) covered by \({\mathcal {T}}\) has a Lipschitz boundary, the patch of elements \(K \in {\mathcal {T}}\) sharing the vertex \({\varvec{a}}\) either forms an open domain around \({\varvec{a}}\) when \({\varvec{a}}\in {\mathcal {V}}^{\textrm{int}}\), or it forms an open domain with \({\varvec{a}}\) on the boundary if \({\varvec{a}}\in {\mathcal {V}}^{\textrm{ext}}\). In both cases, the boundary of the vertex patch is connected and consists of a subset of \({\mathcal {E}}\), and this property remains true after the vertex \({\varvec{a}}\) has been removed. This is illustrated in Fig. reffigurespsvertexspspatches. If there exists a path joining two vertices \({\varvec{b}},{\varvec{c}}\in {\mathcal {V}}{\setminus } \{{\varvec{a}}\}\) through \({\varvec{a}}\), then the path must go through two vertices \({\varvec{b}}',{\varvec{c}}' \in {\mathcal {V}}\) on the boundary of the vertex patch surrounding \({\varvec{a}}\). Once \({\varvec{a}}\) is removed, \({\varvec{b}}'\) and \({\varvec{c}}'\) can still be connected via remaining edges on the boundary of the patch. This shows the graph of the mesh is biconnected: it remains connected after we remove one vertex. Here, we need to show that the graph is triconnected, meaning that it remains connected after two vertices have been removed.

Let us first consider the case where the two vertices \({\varvec{a}},{\varvec{b}}\in {\mathcal {V}}\) removed from the graph do not share an edge, i.e. \([{\varvec{a}},{\varvec{b}}] \not \in {\mathcal {E}}\). Then, we can first remove, say, \({\varvec{a}}\) and apply the reasoning above to show that the graph remains connected. Because there is no edge connecting \({\varvec{a}}\) and \({\varvec{b}}\), the vertex patch around \({\varvec{b}}\) remains untouched after the deletion of \({\varvec{a}}\). As a result, the reasoning presented above still applies, and the graph remains connected.

We therefore only need to consider cases where we remove two vertices \({\varvec{a}},{\varvec{b}}\in {\mathcal {V}}\) such that \(e = [{\varvec{a}},{\varvec{b}}] \in {\mathcal {E}}\). We then have to consider two cases, either \(e \in {\mathcal {E}}^{\textrm{int}}\) or not. If \(e \in {\mathcal {E}}^{\textrm{int}}\), due to our assumptions, then either one or two vertices are interior, and in either case, the boundary of edge patch remains connected after the edge is removed. This is depicted on Figs. reffigurespsinteriorspsedge and reffigurespsedgespsonespsvertex. In both cases, if \({\varvec{c}},{\varvec{d}}\in {\mathcal {V}}{\setminus } \{{\varvec{a}},{\varvec{b}}\}\) are two vertices connected through \({\varvec{a}}\) or \({\varvec{b}}\), we can still connect them through a path going around the boundary of the edge patch. We finally consider the case where \(e \in {\mathcal {E}}^{\textrm{ext}}\). In this case too, the boundary of the edge patch is connected, and it remains connected after the edge is removed. The process of modifying a path going through \(e = [{\varvec{a}},{\varvec{b}}] \in {\mathcal {E}}^{\textrm{ext}}\) after it is removed is shown in Fig. reffigurespsexteriorspsedge. \(\square \)

Proposition A.4

(Mapping a two-dimensional triangular mesh into a reference triangle) Consider a triangular mesh \({\mathcal {T}}\) covering a domain \(\omega \subset {\mathbb {R}}^2\) and either composed of a single element K or satisfying the assumptions of Lemma A.2. Then, there exists a bilipschitz mapping \(\Psi \) from \({\overline{\omega }}\) to the reference triangle \({\widehat{T}} :=\{(y_1,y_2) \in [0,1]^2 \; | \; y_1+y_2 \le 1\;\}\) such that \(\Psi |_K\) is affine for each \(K \in {\mathcal {T}}\). In addition, if \(\{\Gamma ^\flat ,\Gamma ^\sharp \}\) is a partition of \(\partial \omega \) into connected components consisting of entire edges, then we can always choose the mapping \(\Psi \) so that \(\Psi (\overline{\Gamma ^\flat }) = {\widehat{E}}\) or \(\Psi (\overline{\Gamma ^\sharp }) = {\widehat{E}}\), with \({\widehat{E}} = \{ (y_1,y_2) \in [0,1]^2 \; | \; y_1+y_2 = 1 \}\).

Triangular representation of a mesh

Full size image

Proof

We first note that if \({\mathcal {T}}\) consists of a single element K, then it is clear that the result is true by considering a simple affine map associating the relevant vertices of K to the ones of \({\widehat{T}}\). We therefore focus on the case where \({\mathcal {T}}\) has at least two elements hereafter.

Due to Lemma A.2, we know that the graph \(({\mathcal {V}},{\mathcal {E}})\), where \({\mathcal {V}}\) and \({\mathcal {E}}\) are the vertices and edges of \({\mathcal {T}}\), is triconnected. Then [34, (9.2)], Tutte’s embedding theorem ensures that we can place the boundary vertices \({\mathcal {V}}^{\textrm{ext}}\) so that they correspond to the vertices of an arbitrary convex polygon P, and draw the graph \(({\mathcal {V}},{\mathcal {E}})\) in the plane such that the outer face of the graph is P. In fact, we can always do so for a large family of star-shaped polygons [25, Theorem 10], and it is in particular possible to place the boundary vertices on the boundary of the reference triangle \({\widehat{T}}\). Since the original mesh covering \(\omega \) and the drawing of the graph \(({\mathcal {V}},{\mathcal {E}})\) in \({\widehat{T}}\) are two drawings of the same graph, the mapping \(\Psi \) that is piecewise affine on \({\mathcal {T}}\) and maps the vertices of \({\mathcal {T}}\) to the coordinates of the drawing in \({\widehat{T}}\) is uniquely defined and satisfies the first statement of the proposition. This process is illustrated in Fig. eff16b.

If we further partition the boundary of \(\omega \), then either \(\Gamma ^\flat \) or \(\Gamma ^\sharp \) consists of at least two edges. To fix the ideas, let us assume that \(\Gamma ^\flat \) has at least two edges. Then, we can place the vertices on the boundary of \(\widehat{T}\) so that \(\Gamma ^\flat \) is mapped on the horizontal and vertical edges of \({\widehat{T}}\) (see Fig. 17c), and \(\Gamma ^\sharp \) is then mapped onto the remaining edge. We proceed the other way around if \(\Gamma ^\flat \) consists of a single edge. \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions