Introduction
Geometric multigrid (GMG) methods are among the most efficient solvers for the large, sparse linear systems arising from the discretisation of partial differential equations (PDEs) [7 , 24 ] . By exploiting a hierarchy of discretisations defined on progressively coarser meshes, they achieve optimal computational complexity, solving the system in a number of operations that scales linearly with the number of unknowns.
For classical finite element methods (FEMs), this efficiency comes at the price of a rigid geometric requirement. Classical GMG hierarchies consist of nested simplicial or cuboidal meshes, every level being a conforming mesh of the same element type. Such a hierarchy cannot in general be obtained by coarsening a given fine mesh; the union of a few simplices or cuboids is not a simplex or a cuboid. It has to be generated the other way round, by successive refinement of a coarse mesh. The fine mesh then inherits the geometry of its coarsest ancestor, and the domain boundary is resolved only to the accuracy of the coarsest mesh, which is impractical for general domains. Lifting this restriction requires non-nested hierarchies, which are not automatic either, since they involve unstructured mesh generation at every level, and which in turn demand the construction of intricate inter-level transfer operators [8 ] . Since the coarse and fine spaces are no longer nested, the transfer operators are L 2 L^2 L 2 -projections between spaces defined on unrelated meshes. Evaluating them requires locating the fine cells overlapped by each coarse cell and integrating over their intersections, which amounts to building an auxiliary supermesh, a delicate and expensive task, especially in parallel.
Polytopal methods, that is methods supporting meshes whose cells are general polytopes with an arbitrary number of faces, do not have this difficulty. Since most agglomerations of a fine mesh yield an admissible coarser one, the hierarchy can be built from a single fine mesh by successive agglomeration. Multilevel solvers of this kind have been developed for Discontinuous Galerkin (DG) methods [3 , 4 ] , Virtual Element Method (VEM) [1 ] and Hybrid High-Order (HHO) methods [5 ] . Polytopal methods are, however, more expensive than their simplicial counterparts, whether because of a larger number of degrees of freedom (DOFs), as in DG methods, or because of a more involved formulation and assembly, as in VEM and HHO methods.
In this work we introduce a family of multilevel preconditioners. At the first level, a standard conforming Lagrangian finite element (FE) discretisation on the fine mesh is preconditioned by a non-conforming polytopal discretisation posed on an arbitrarily agglomerated coarse mesh. At the subsequent levels, the coarse problem is solved by an agglomeration-based GMG method for that polytopal discretisation, for DG the one of [3 , 4 ] and for HHO the one of [5 ] , so that the whole hierarchy is generated from the fine mesh by agglomeration alone. The convergence of these GMG solvers has already been analysed in the cited works, so only the first level needs to be analysed here. This is where the difficulty of transferring between a conforming and a non-conforming space lies. We analyse the two-level method for an arbitrary coarse solver, whose accuracy enters through two constants, and the bounds of the cited works then supply these constants for the GMG coarse solver. The fine mesh can thus be produced by a standard mesher, such as Gmsh [23 ] , and discretised with a conforming method, which is the cheapest option on the finest and most expensive level, while the coarse mesh can be generated by any agglomeration strategy. The analysis uses the auxiliary space preconditioning theory [36 , 37 ] , and covers two polytopal coarse discretisations, a symmetric interior penalty Galerkin (SIPG) DG method and a statically condensed HHO method. The HHO results extend directly to the closely related Hybridizable Discontinuous Galerkin (HDG) [16 ] method, and vice versa. In all cases we prove that the preconditioned system has a condition number bounded independently of the mesh size for a fixed coarsening ratio H / h H/h H / h , and we corroborate the theory with numerical experiments spanning a range of meshes and agglomeration levels.
Auxiliary space methods have classically been used in the opposite direction to the one proposed here, i.e. a non-conforming fine discretisation is preconditioned by a conforming auxiliary space defined on the same mesh. This is the setting of the seminal works on two-level additive Schwarz preconditioners for non-conforming FEMs [9 , 30 ] , later extended to C 0 C^0 C 0 interior penalty discretisations [11 ] . In these works, the transfer between the non-conforming and conforming spaces is provided by nodal averaging operators. Most solvers for non-conforming hybridised discretisations follow the same direction. Early multigrid methods for HDG problems recast the skeleton unknowns into bulk functions, so that a standard conforming piecewise-linear multigrid solver could be used [17 ] . The more recent homogeneous multigrid methods keep the hybrid discretisation at every level [18 ] , but conformity is still needed. Their analysis rests on a compatibility condition between the hybrid discretisation and the space of continuous piecewise linear functions, which restricts the method to nested, geometrically conforming simplicial meshes and leaves the agglomerated case open. Such solvers give up the freedom in meshing that motivates hybridised and polytopal methods, and the same holds for the DG solvers built on conforming auxiliary spaces mentioned above. Here the fine problem is conforming, and it is the non-conformity of the auxiliary space that allows arbitrary agglomeration.
The closest relatives of our approach are the auxiliary space preconditioners of Kalchev and Vassilevski [26 , 27 ] , in which a conforming FE problem is preconditioned via non-conforming reformulations. Our construction differs in that the auxiliary problem is a standard polytopal discretisation, either SIPG or statically condensed HHO, equipped, in the HHO case, with high-order face spaces supported on non-planar agglomerate interfaces [38 ] , and in that we prove condition number bounds that explicitly track the coarsening ratio H / h H/h H / h . Our method can also be read as a geometric, high-order analogue of smoothed aggregation algebraic multigrid (SA-AMG) [12 , 35 ] , where the tentative prolongator and the algebraic prolongator-smoothing step are replaced by an exact polytopal reconstruction on geometric agglomerates followed by Oswald averaging.
The paper is organised as follows. Sect. 2 fixes the model problem and the conforming discretisation. Sect. 3 recalls the auxiliary space framework and reduces the condition number of the two-level preconditioner to three assumptions. Sect. 4 collects the analysis tools on polytopal elements and Sect. 5 the additive Schwarz smoothers. Sect. 6 and Sect. 7 verify the three assumptions for the DG and HHO coarse spaces, which gives the bound O ( ( H / h ) 3 ) O((H/h)^3) O (( H / h ) 3 ) , and O ( ( H / h ) 2 ) O((H/h)^2) O (( H / h ) 2 ) for DG with penalty proportional to H / h H/h H / h . Sect. 8 discusses the remaining ingredient, the coarse solver itself, for which agglomeration-based GMG methods are available in the literature. Sect. 9 reports the numerical experiments and Sect. 10 concludes.
Let Ω ⊂ R d \Omega\subset\mathbb{R}^{d} Ω ⊂ R d , d ∈ { 2 , 3 } d \in\{2,3\} d ∈ { 2 , 3 } , be a bounded Lipschitz polytopal domain with boundary ∂ Ω \partial\Omega ∂ Ω . Without loss of generality, we assume diam ( Ω ) = 1 \operatorname{diam}(\Omega)=1 diam ( Ω ) = 1 . All hidden constants below are stated under this normalisation. We consider the Poisson problem with homogeneous Dirichlet boundary conditions:
− Δ u = f in Ω , u = 0 on ∂ Ω , -\Delta u = f \quad\text{in }\Omega,\qquad u=0 \quad\text{on }\partial\Omega, − Δ u = f in Ω , u = 0 on ∂ Ω ,
where f ∈ L 2 ( Ω ) f \in L^{2}(\Omega) f ∈ L 2 ( Ω ) is a given source term.1 The weak formulation reads: find u ∈ H 0 1 ( Ω ) u \in H_{0}^{1}(\Omega) u ∈ H 0 1 ( Ω ) such that
a ( u , v ) : = ( ∇ u , ∇ v ) Ω , ℓ ( v ) : = ( f , v ) Ω , a ( u , v ) = ℓ ( v ) ∀ v ∈ H 0 1 ( Ω ) . (1) a(u,v) := (\nabla u,\nabla v)_{\Omega},\qquad\ell(v) := (f,v)_{\Omega},\qquad a(u,v)=\ell(v)\quad\forall v \in H_{0}^{1}(\Omega). \tag*{(1)} a ( u , v ) := ( ∇ u , ∇ v ) Ω , ℓ ( v ) := ( f , v ) Ω , a ( u , v ) = ℓ ( v ) ∀ v ∈ H 0 1 ( Ω ) . (1)
By the Lax-Milgram lemma, problem (1) admits a unique solution. Let T h \mathcal{T}_{h} T h be a conforming simplicial mesh of Ω \Omega Ω , consisting of a set of disjoint open simplices t t t with diameters h t = diam ( t ) h_{t}=\operatorname{diam}(t) h t = diam ( t ) , and let h = max t ∈ T h h t h=\max_{t\in\mathcal{T}_{h}}h_{t} h = max t ∈ T h h t denote the mesh size of the mesh T h \mathcal{T}_{h} T h . We assume that T h \mathcal{T}_{h} T h is shape-regular and quasi-uniform in the usual sense. We restrict the presentation to simplicial meshes and Lagrangian elements for simplicity. All results below extend to tensor-product (quadrilateral/hexahedral) meshes equipped with Q p \mathbb{Q}^{p} Q p Lagrange elements, for which the nodal and trace arguments used in the analysis hold verbatim.
We denote by F h \mathcal{F}_{h} F h the set of faces of the mesh T h \mathcal{T}_{h} T h , and by F h ( t ) \mathcal{F}_{h}(t) F h ( t ) the set of faces of an element t ∈ T h t\in\mathcal{T}_{h} t ∈ T h . We also introduce the sets of interior and boundary faces as F h i = { f ∈ F h : f ⊂ ⊂ Ω } \mathcal{F}_{h}^{\mathrm{i}}=\{f\in\mathcal{F}_{h}: f\subset\subset\Omega\} F h i = { f ∈ F h : f ⊂⊂ Ω } and F h b d = { f ∈ F h : f ⊂ ∂ Ω } \mathcal{F}_{h}^{\mathrm{bd}}=\{f\in\mathcal{F}_{h}: f\subset\partial\Omega\} F h bd = { f ∈ F h : f ⊂ ∂ Ω } , respectively.
Given a geometric entity X X X , e.g. t t t or a planar face f f f , let P k ( X ) \mathbb{P}^{k}(X) P k ( X ) denote the space of polynomials of total degree at most k k k on X X X . Similarly, given X h \mathcal{X}_{h} X h a collection of geometrical entities, e.g. T h \mathcal{T}_{h} T h , F h \mathcal{F}_{h} F h , we define P k ( X h ) = × X ∈ X h P k ( X ) \mathbb{P}^{k}(\mathcal{X}_{h})=\times_{X\in\mathcal{X}_{h}}\mathbb{P}^{k}(X) P k ( X h ) = × X ∈ X h P k ( X ) the broken polynomial space on each entity. For any measurable set X X X , ( ⋅ , ⋅ ) X (\cdot,\cdot)_{X} ( ⋅ , ⋅ ) X represents the L 2 ( X ) L^{2}(X) L 2 ( X ) inner product and ∥ ⋅ ∥ X \|\cdot\|_{X} ∥ ⋅ ∥ X the associated norm. For a collection X h \mathcal{X}_{h} X h , these are extended element-wise, ( u , v ) X h = ∑ X ∈ X h ( u , v ) X (u,v)_{\mathcal{X}_{h}}=\sum_{X\in\mathcal{X}_{h}}(u,v)_{X} ( u , v ) X h = ∑ X ∈ X h ( u , v ) X . Given r ≥ 0 r\geq0 r ≥ 0 and a partition X h \mathcal{X}_{h} X h of Ω \Omega Ω (in this work, T h \mathcal{T}_{h} T h or T H \mathcal{T}_{H} T H ), we use the broken norms and seminorms
∥ v ∥ H r ( X h ) 2 : = ∑ X ∈ X h ∥ v ∥ H r ( X ) 2 , ∣ v ∣ H r ( X h ) 2 : = ∑ X ∈ X h ∣ v ∣ H r ( X ) 2 , \|v\|_{H^{r}(\mathcal{X}_{h})}^{2}:=\sum_{X\in\mathcal{X}_{h}}\|v\|_{H^{r}(X)}^{2},\qquad|v|_{H^{r}(\mathcal{X}_{h})}^{2}:=\sum_{X\in\mathcal{X}_{h}}|v|_{H^{r}(X)}^{2}, ∥ v ∥ H r ( X h ) 2 := X ∈ X h ∑ ∥ v ∥ H r ( X ) 2 , ∣ v ∣ H r ( X h ) 2 := X ∈ X h ∑ ∣ v ∣ H r ( X ) 2 ,
defined for functions that are only piecewise H r H^{r} H r -regular over X h \mathcal{X}_{h} X h , with the convention ∣ v ∣ H 0 ( X ) = ∥ v ∥ L 2 ( X ) |v|_{H^{0}(X)}=\|v\|_{L^{2}(X)} ∣ v ∣ H 0 ( X ) = ∥ v ∥ L 2 ( X ) . We abbreviate ∣ u ∣ 1 , X : = ∣ u ∣ H 1 ( X ) |u|_{1,X}:=|u|_{H^{1}(X)} ∣ u ∣ 1 , X := ∣ u ∣ H 1 ( X ) and ∣ u ∣ 1 , X h : = ∣ u ∣ H 1 ( X h ) |u|_{1,\mathcal{X}_{h}}:=|u|_{H^{1}(\mathcal{X}_{h})} ∣ u ∣ 1 , X h := ∣ u ∣ H 1 ( X h ) .
Given a polynomial degree p ≥ 1 p\geq1 p ≥ 1 , we consider the standard Lagrangian conforming space V h V_{h} V h , that is
V h = { v h ∈ H 0 1 ( Ω ) : v h ∣ t ∈ P p ( t ) for all t ∈ T h } . V_{h}=\{v_{h}\in H_{0}^{1}(\Omega):v_{h}|_{t}\in\mathbb{P}^{p}(t)\text{ for all }t\in\mathcal{T}_{h}\}. V h = { v h ∈ H 0 1 ( Ω ) : v h ∣ t ∈ P p ( t ) for all t ∈ T h } .
The conforming finite element discretisation of (1) reads: find u h ∈ V h u_{h}\in V_{h} u h ∈ V h such that
a ( u h , v h ) = ℓ ( v h ) ∀ v h ∈ V h . a(u_{h},v_{h})=\ell(v_{h})\quad\forall v_{h}\in V_{h}. a ( u h , v h ) = ℓ ( v h ) ∀ v h ∈ V h .
We denote by A h : V h → V h A_{h}:V_{h}\to V_{h} A h : V h → V h the associated operator, characterised by a ( u h , v h ) = ( A h u h , v h ) Ω a(u_{h},v_{h})=(A_{h}u_{h},v_{h})_{\Omega} a ( u h , v h ) = ( A h u h , v h ) Ω for all u h , v h ∈ V h u_{h},v_{h}\in V_{h} u h , v h ∈ V h .
Auxiliary space preconditioners: abstract framework
For a given mesh T h \mathcal{T}_{h} T h , we define a coarse partition T H \mathcal{T}_{H} T H , given by non-overlapping agglomeration of elements of T h \mathcal{T}_{h} T h . That is, T H = { T } \mathcal{T}_{H}=\{T\} T H = { T } is such that each T ∈ T H T\in\mathcal{T}_{H} T ∈ T H is a union of elements from T h \mathcal{T}_{h} T h . Here H T = diam ( T ) H_{T}=\operatorname{diam}(T) H T = diam ( T ) denotes the diameter of each agglomerated element and H = max T ∈ T H H T H=\max_{T\in\mathcal{T}_{H}}H_{T} H = max T ∈ T H H T the mesh size of the partition.
Throughout this work, we make the following regularity assumptions on the coarse partition.
Assumption 3.1 (Coarse mesh regularity). There exists a constant c R > 0 c_{R}>0 c R > 0 , independent of h h h and H H H , such that the coarse partition T H \mathcal{T}_{H} T H satisfies:
(i) Quasi-uniformity: c R H ≤ H T ≤ H c_{R}H\leq H_{T}\leq H c R H ≤ H T ≤ H for all T ∈ T H T\in\mathcal{T}_{H} T ∈ T H ;
(ii) Star-shapedness: every T ∈ T H T\in\mathcal{T}_{H} T ∈ T H is star-shaped with respect to a ball of radius ρ T ≥ c R H T \rho_{T}\geq c_{R}H_{T} ρ T ≥ c R H T ;
(iii) Simplicial covering: *there exists a covering T H # = { K # } \mathcal{T}_{H}^{\#}=\{K^{\#}\} T H # = { K # } of T H \mathcal{T}_{H} T H by shape-regular d d d -simplices such that, for every T ∈ T H T\in\mathcal{T}_{H} T ∈ T H , there is K # ∈ T H # K^{\#}\in\mathcal{T}_{H}^{\#} K # ∈ T H # with T ⊂ K # T\subset K^{\#} T ⊂ K # and diam ( K # ) ≤ c R − 1 H T \operatorname{diam}(K^{\#})\leq c_{R}^{-1}H_{T} diam ( K # ) ≤ c R − 1 H T .
Conditions (ii)–(iii) are the standard shape-regularity requirements for polytopal meshes [14 ] . Condition (ii) guarantees that the trace and Poincaré inequalities of Sect. 4 hold on the agglomerated elements with constants depending only on c R c_R c R , and that each agglomerate is connected. Conditions (ii) and (iii) together yield the inverse inequalities for polynomials on polytopal elements required by the coarse bilinear forms introduced in Sect. 6 and Sect. 7. The inverse inequality holds on the shape-regular simplex K ♯ K^{\sharp} K ♯ supplied by condition (iii) and is transferred to T T T using T ⊂ K ♯ T \subset K^{\sharp} T ⊂ K ♯ , while condition (ii) is what allows the resulting L 2 ( K ♯ ) L^2(K^{\sharp}) L 2 ( K ♯ ) norm to be brought back to T T T .
We denote by F H = F H i n ∪ F H b d \mathcal{F}_H = \mathcal{F}_H^{\mathrm{in}} \cup\mathcal{F}_H^{\mathrm{bd}} F H = F H in ∪ F H bd the set of interfaces of the coarse partition T H \mathcal{T}_H T H . An interior interface F ∈ F H i n F \in\mathcal{F}_H^{\mathrm{in}} F ∈ F H in is the union of the fine faces contained in T ‾ 1 ∩ T ‾ 2 \overline{T}_1 \cap\overline{T}_2 T 1 ∩ T 2 , for two distinct elements T 1 , T 2 ∈ T H T_1,T_2 \in\mathcal{T}_H T 1 , T 2 ∈ T H , whenever that union has positive ( d − 1 ) (d-1) ( d − 1 ) -dimensional measure, and a boundary interface F ∈ F H b d F \in\mathcal{F}_H^{\mathrm{bd}} F ∈ F H bd is the union of the fine faces contained in T ‾ ∩ ∂ Ω \overline{T} \cap\partial\Omega T ∩ ∂ Ω for some T ∈ T H T \in\mathcal{T}_H T ∈ T H . Interfaces are piecewise-linear curves for d = 2 d=2 d = 2 and polygonal surfaces for d = 3 d=3 d = 3 . We will still refer to these interfaces as faces for brevity. For each cell T T T , we use ∂ T \partial T ∂ T to denote its boundary, and let F H ( T ) = { F ∈ F H : F ⊂ ∂ T } \mathcal{F}_H(T)=\{F\in\mathcal{F}_H:F\subset\partial T\} F H ( T ) = { F ∈ F H : F ⊂ ∂ T } denote the set of faces of T T T . For each face F ∈ F H F\in\mathcal{F}_H F ∈ F H , we define H F H_F H F as the mean of the diameters of the (at most two) coarse elements sharing F F F :
H F ≔ 1 ∣ T H ( F ) ∣ ∑ T ∈ T H ( F ) H T , T H ( F ) ≔ { T ∈ T H : F ⊂ ∂ T } . H_F \coloneqq\frac{1}{|\mathcal{T}_H(F)|}\sum_{T\in\mathcal{T}_H(F)}H_T,\qquad\mathcal{T}_H(F)\coloneqq\{T\in\mathcal{T}_H:F\subset\partial T\}. H F : = ∣ T H ( F ) ∣ 1 T ∈ T H ( F ) ∑ H T , T H ( F ) : = { T ∈ T H : F ⊂ ∂ T } .
In particular, H F ≃ H H_F\simeq H H F ≃ H for all F ∈ F H F\in\mathcal{F}_H F ∈ F H .
Let V H V_H V H be an auxiliary finite-dimensional space defined on the coarse partition T H \mathcal{T}_H T H and a H : V H × V H → R a_H:V_H\times V_H\to\mathbb{R} a H : V H × V H → R a symmetric positive definite bilinear form defined on V H V_H V H . Let I H h : V H → V h I_{Hh}:V_H\to V_h I H h : V H → V h be a prolongation operator from the auxiliary space V H V_H V H to the original space V h V_h V h . We also introduce a symmetric positive definite smoother D h : V h → V h D_h:V_h\to V_h D h : V h → V h and a symmetric positive definite operator B H : V H → V H B_H:V_H\to V_H B H : V H → V H , which plays the role of an approximate inverse of A H A_H A H , that is, of a solver for the coarse problem. We denote by A H : V H → V H A_H:V_H\to V_H A H : V H → V H the operator associated with a H a_H a H , characterised by ( A H u H , v H ) = a H ( u H , v H ) (A_Hu_H,v_H)=a_H(u_H,v_H) ( A H u H , v H ) = a H ( u H , v H ) for all u H , v H ∈ V H u_H,v_H\in V_H u H , v H ∈ V H , and by I H h ∗ : V h → V H I_{Hh}^{*}:V_h\to V_H I H h ∗ : V h → V H the adjoint of the prolongation operator, characterised by ( I H h v H , v h ) Ω = ( v H , I H h ∗ v h ) (I_{Hh}v_H,v_h)_{\Omega}=(v_H,I_{Hh}^{*}v_h) ( I H h v H , v h ) Ω = ( v H , I H h ∗ v h ) for all v H ∈ V H v_H\in V_H v H ∈ V H and v h ∈ V h v_h\in V_h v h ∈ V h . Here ( ⋅ , ⋅ ) (\cdot,\cdot) ( ⋅ , ⋅ ) denotes an inner product on V H V_H V H . The coarse correction I H h A H − 1 I H h ∗ I_{Hh}A_H^{-1}I_{Hh}^{*} I H h A H − 1 I H h ∗ , and hence the preconditioner itself, is the same for every choice of this inner product, so the choice affects neither the method nor its implementation. Given a symmetric positive definite bilinear form b b b (resp. operator B B B ) on a space V V V , we denote the associated energy norm by ∥ v ∥ b = b ( v , v ) 1 / 2 \|v\|_b=b(v,v)^{1/2} ∥ v ∥ b = b ( v , v ) 1/2 (resp. ∥ v ∥ B = ( B v , v ) 1 / 2 \|v\|_B=(Bv,v)^{1/2} ∥ v ∥ B = ( B v , v ) 1/2 ) for v ∈ V v\in V v ∈ V . We will use the energy norms ∥ ⋅ ∥ a H \|\cdot\|_{a_H} ∥ ⋅ ∥ a H and ∥ ⋅ ∥ D h \|\cdot\|_{D_h} ∥ ⋅ ∥ D h below. Our auxiliary space preconditioner is then defined as
P a d d − 1 ≔ I H h B H I H h ∗ + D h − 1 . (2) P_{\mathrm{add}}^{-1}\coloneqq I_{Hh}B_HI_{Hh}^{*}+D_h^{-1}. \tag*{(2)} P add − 1 : = I H h B H I H h ∗ + D h − 1 . (2)
Assumption 3.4 (Stability of the prolongation). There exists a constant c I c_I c I such that for all v H ∈ V H v_H\in V_H v H ∈ V H it holds that
∥ I H h v H ∥ a 2 ≤ c I 2 ∥ v H ∥ a H 2 . \|I_{Hh}v_H\|_a^2\leq c_I^2\|v_H\|_{a_H}^2. ∥ I H h v H ∥ a 2 ≤ c I 2 ∥ v H ∥ a H 2 .
Assumption 3.5 (Smoother stability). There exists a constant c D c_D c D such that for all v h ∈ V h v_h\in V_h v h ∈ V h it holds that
∥ v h ∥ a 2 ≤ c D 2 ∥ v h ∥ D h 2 . \|v_h\|_a^2\leq c_D^2\|v_h\|_{D_h}^2. ∥ v h ∥ a 2 ≤ c D 2 ∥ v h ∥ D h 2 .
Assumption 3.6 (Stable decomposition). There exist constants c 0 , H c_{0,H} c 0 , H and c 0 , D c_{0,D} c 0 , D such that for all v h ∈ V h v_h\in V_h v h ∈ V h there exists v H ∈ V H v_H\in V_H v H ∈ V H with
∥ v H ∥ a H 2 ≤ c 0 , H 2 ∥ v h ∥ a 2 and ∥ v h − I H h v H ∥ D h 2 ≤ c 0 , D 2 ∥ v h ∥ a 2 . \|v_H\|_{a_H}^2\leq c_{0,H}^2\|v_h\|_a^2
\qquad\text{and}\qquad
\|v_h-I_{Hh}v_H\|_{D_h}^2\leq c_{0,D}^2\|v_h\|_a^2. ∥ v H ∥ a H 2 ≤ c 0 , H 2 ∥ v h ∥ a 2 and ∥ v h − I H h v H ∥ D h 2 ≤ c 0 , D 2 ∥ v h ∥ a 2 .
Assumption 3.7 (Accuracy of the coarse solver). There exist constants 0 < λ 0 ≤ λ 1 0 < \lambda_0 \le\lambda_1 0 < λ 0 ≤ λ 1 such that for all μ H ∈ V H \mu_H \in V_H μ H ∈ V H it holds that
λ 0 ( A H − 1 μ H , μ H ) ≤ ( B H μ H , μ H ) ≤ λ 1 ( A H − 1 μ H , μ H ) . \lambda_0(A_H^{-1}\mu_H,\mu_H) \le(B_H\mu_H,\mu_H) \le\lambda_1(A_H^{-1}\mu_H,\mu_H). λ 0 ( A H − 1 μ H , μ H ) ≤ ( B H μ H , μ H ) ≤ λ 1 ( A H − 1 μ H , μ H ) . that is, λ 0 \lambda_0 λ 0 and λ 1 \lambda_1 λ 1 bound the extreme eigenvalues of B H A H B_HA_H B H A H from below and above, so that λ 1 / λ 0 \lambda_1/\lambda_0 λ 1 / λ 0 bounds the condition number κ ( B H A H ) \kappa(B_HA_H) κ ( B H A H ) of the preconditioned coarse problem. An exact coarse solve, B H = A H − 1 B_H=A_H^{-1} B H = A H − 1 , corresponds to λ 0 = λ 1 = 1 \lambda_0=\lambda_1=1 λ 0 = λ 1 = 1 .
In the following, given symmetric operators X X X and Y Y Y , we use the compact notation X ≤ Y X\le Y X ≤ Y (equivalently, Y ≥ X Y\ge X Y ≥ X ) to indicate that Y − X Y-X Y − X is positive semi-definite. In this notation, Assumption 3.7 reads λ 0 A H − 1 ≤ B H ≤ λ 1 A H − 1 \lambda_0A_H^{-1}\le B_H\le\lambda_1A_H^{-1} λ 0 A H − 1 ≤ B H ≤ λ 1 A H − 1 . We recall that inversion reverses this order on symmetric positive definite operators.
Then the condition number of the preconditioned system P a d d − 1 A h P_{\mathrm{add}}^{-1}A_h P add − 1 A h can be bounded as follows:
Lemma 3.8. Assume that Assumptions 3.4, 3.5, 3.7 and 3.6 hold. Then
κ ( P a d d − 1 A h ) ≤ ( c D 2 + λ 1 c I 2 ) ( c 0 , D 2 + c 0 , H 2 λ 0 ) . \kappa(P_{\mathrm{add}}^{-1}A_h) \le(c_D^2+\lambda_1c_I^2)\left(c_{0,D}^2+\frac{c_{0,H}^2}{\lambda_0}\right). κ ( P add − 1 A h ) ≤ ( c D 2 + λ 1 c I 2 ) ( c 0 , D 2 + λ 0 c 0 , H 2 ) .
This result is a variant of [37 Theorem 2.1] . It differs from it in the assumptions on the smoother and on the decomposition. The analysis in [37 ] requires a two-sided Richardson-type equivalence for the smoother and measures the stable decomposition in a scaled L 2 L^2 L 2 norm, whereas Assumption 3.5 is one-sided for a general symmetric positive definite D h D_h D h and Assumption 3.6 is stated in the D h D_h D h -norm. Since our assumptions are weaker, the result does not follow from the cited theorem, and we must prove it.
Proof. Note first that P a d d − 1 P_{\mathrm{add}}^{-1} P add − 1 is symmetric with respect to ( ⋅ , ⋅ ) (\cdot,\cdot) ( ⋅ , ⋅ ) , so P a d d − 1 A h P_{\mathrm{add}}^{-1}A_h P add − 1 A h is self-adjoint with respect to a ( ⋅ , ⋅ ) a(\cdot,\cdot) a ( ⋅ , ⋅ ) , and it is positive definite, since a ( P a d d − 1 A h v h , v h ) ≥ ( D h − 1 A h v h , A h v h ) > 0 a(P_{\mathrm{add}}^{-1}A_hv_h,v_h)\ge(D_h^{-1}A_hv_h,A_hv_h)>0 a ( P add − 1 A h v h , v h ) ≥ ( D h − 1 A h v h , A h v h ) > 0 for v h ≠ 0 v_h\ne0 v h = 0 . Its extreme eigenvalues are therefore characterised by the Rayleigh quotients below. Write g v ≔ I H h ∗ A h v h g_v\coloneqq I_{Hh}^*A_hv_h g v : = I H h ∗ A h v h , so that
a ( P a d d − 1 A h v h , v h ) = ( B H g v , g v ) + ( D h − 1 A h v h , A h v h ) . a(P_{\mathrm{add}}^{-1}A_hv_h,v_h)=(B_Hg_v,g_v)+(D_h^{-1}A_hv_h,A_hv_h). a ( P add − 1 A h v h , v h ) = ( B H g v , g v ) + ( D h − 1 A h v h , A h v h ) .
For the upper bound, the dual-norm characterisation of the D h − 1 D_h^{-1} D h − 1 -norm as the dual of the D h D_h D h -norm followed by Assumption 3.5, gives
( D h − 1 A h v h , A h v h ) = sup w h ≠ 0 ( A h v h , w h ) 2 ( D h w h , w h ) = sup w h ≠ 0 a ( v h , w h ) 2 ∥ w h ∥ D h 2 ≤ c D 2 ∥ v h ∥ a 2 , (D_h^{-1}A_hv_h,A_hv_h)=\sup_{w_h\ne0}\frac{(A_hv_h,w_h)^2}{(D_hw_h,w_h)}=\sup_{w_h\ne0}\frac{a(v_h,w_h)^2}{\lVert w_h\rVert_{D_h}^2}\le c_D^2\lVert v_h\rVert_a^2, ( D h − 1 A h v h , A h v h ) = w h = 0 sup ( D h w h , w h ) ( A h v h , w h ) 2 = w h = 0 sup ∥ w h ∥ D h 2 a ( v h , w h ) 2 ≤ c D 2 ∥ v h ∥ a 2 ,
while Assumptions 3.7 and 3.4 give
( B H g v , g v ) ≤ λ 1 ( A H − 1 g v , g v ) = λ 1 sup μ H ≠ 0 ( g v , μ H ) 2 ∥ μ H ∥ a H 2 = λ 1 sup μ H ≠ 0 a ( v h , I H h μ H ) 2 ∥ μ H ∥ a H 2 ≤ λ 1 c I 2 ∥ v h ∥ a 2 , (B_Hg_v,g_v)\le\lambda_1(A_H^{-1}g_v,g_v)=\lambda_1\sup_{\mu_H\ne0}\frac{(g_v,\mu_H)^2}{\lVert\mu_H\rVert_{a_H}^2}=\lambda_1\sup_{\mu_H\ne0}\frac{a(v_h,I_{Hh}\mu_H)^2}{\lVert\mu_H\rVert_{a_H}^2}\le\lambda_1c_I^2\lVert v_h\rVert_a^2, ( B H g v , g v ) ≤ λ 1 ( A H − 1 g v , g v ) = λ 1 μ H = 0 sup ∥ μ H ∥ a H 2 ( g v , μ H ) 2 = λ 1 μ H = 0 sup ∥ μ H ∥ a H 2 a ( v h , I H h μ H ) 2 ≤ λ 1 c I 2 ∥ v h ∥ a 2 ,
so that λ max ( P a d d − 1 A h ) ≤ c D 2 + λ 1 c I 2 \lambda_{\max}(P_{\mathrm{add}}^{-1}A_h)\le c_D^2+\lambda_1c_I^2 λ m a x ( P add − 1 A h ) ≤ c D 2 + λ 1 c I 2 . For the lower bound, let v h = I H h v H + w h v_h=I_{Hh}v_H+w_h v h = I H h v H + w h be the decomposition of Assumption 3.6, with ∥ v H ∥ a H 2 ≤ c 0 , H 2 ∥ v h ∥ a 2 \lVert v_H\rVert_{a_H}^2\le c_{0,H}^2\lVert v_h\rVert_a^2 ∥ v H ∥ a H 2 ≤ c 0 , H 2 ∥ v h ∥ a 2 and ∥ w h ∥ D h 2 ≤ c 0 , D 2 ∥ v h ∥ a 2 \lVert w_h\rVert_{D_h}^2\le c_{0,D}^2\lVert v_h\rVert_a^2 ∥ w h ∥ D h 2 ≤ c 0 , D 2 ∥ v h ∥ a 2 . Then
∥ v h ∥ a 2 = a ( v h , I H h v H ) + a ( v h , w h ) = ( g v , v H ) + ( A h v h , w h ) , \lVert v_h\rVert_a^2=a(v_h,I_{Hh}v_H)+a(v_h,w_h)=(g_v,v_H)+(A_hv_h,w_h), ∥ v h ∥ a 2 = a ( v h , I H h v H ) + a ( v h , w h ) = ( g v , v H ) + ( A h v h , w h ) ,
and the Cauchy–Schwarz inequality, first in the B H B_H B H - and D h D_h D h -inner products and then in R 2 \mathbb{R}^2 R 2 , yields
∥ v h ∥ a 2 ≤ [ ( B H g v , g v ) + ( D h − 1 A h v h , A h v h ) ] 1 / 2 [ ( B H − 1 v H , v H ) + ( D h w h , w h ) ] 1 / 2 . \lVert v_h\rVert_a^2\le\left[(B_Hg_v,g_v)+(D_h^{-1}A_hv_h,A_hv_h)\right]^{1/2}\left[(B_H^{-1}v_H,v_H)+(D_hw_h,w_h)\right]^{1/2}. ∥ v h ∥ a 2 ≤ [ ( B H g v , g v ) + ( D h − 1 A h v h , A h v h ) ] 1/2 [ ( B H − 1 v H , v H ) + ( D h w h , w h ) ] 1/2 .
The first bracket is a ( P a d d − 1 A h v h , v h ) a(P_{\mathrm{add}}^{-1}A_hv_h,v_h) a ( P add − 1 A h v h , v h ) . For the second, Assumption 3.7 gives B H ≥ λ 0 A H − 1 B_H\ge\lambda_0A_H^{-1} B H ≥ λ 0 A H − 1 , hence B H − 1 ≤ λ 0 − 1 A H B_H^{-1}\le\lambda_0^{-1}A_H B H − 1 ≤ λ 0 − 1 A H by order reversal under inversion, and ( B H − 1 v H , v H ) ≤ λ 0 − 1 ∥ v H ∥ a H 2 ≤ λ 0 − 1 c 0 , H 2 ∥ v h ∥ a 2 (B_H^{-1}v_H,v_H)\le\lambda_0^{-1}\lVert v_H\rVert_{a_H}^2\le\lambda_0^{-1}c_{0,H}^2\lVert v_h\rVert_a^2 ( B H − 1 v H , v H ) ≤ λ 0 − 1 ∥ v H ∥ a H 2 ≤ λ 0 − 1 c 0 , H 2 ∥ v h ∥ a 2 , so that
∥ v h ∥ a 4 ≤ a ( P a d d − 1 A h v h , v h ) ( c 0 , H 2 λ 0 + c 0 , D 2 ) ∥ v h ∥ a 2 , \lVert v_h\rVert_a^4\le a(P_{\mathrm{add}}^{-1}A_hv_h,v_h)\left(\frac{c_{0,H}^2}{\lambda_0}+c_{0,D}^2\right)\lVert v_h\rVert_a^2, ∥ v h ∥ a 4 ≤ a ( P add − 1 A h v h , v h ) ( λ 0 c 0 , H 2 + c 0 , D 2 ) ∥ v h ∥ a 2 ,
i.e. λ min ( P a d d − 1 A h ) ≥ ( c 0 , D 2 + c 0 , H 2 / λ 0 ) − 1 \lambda_{\min}(P_{\mathrm{add}}^{-1}A_h)\ge(c_{0,D}^2+c_{0,H}^2/\lambda_0)^{-1} λ m i n ( P add − 1 A h ) ≥ ( c 0 , D 2 + c 0 , H 2 / λ 0 ) − 1 . Since P a d d − 1 A h P_{\mathrm{add}}^{-1}A_h P add − 1 A h is self-adjoint and positive definite with respect to a ( ⋅ , ⋅ ) a(\cdot,\cdot) a ( ⋅ , ⋅ ) , the two bounds give the claim. □ \square □
We now provide a more concrete version of the previous lemma, which will be used in the analysis of the preconditioners proposed in this work.
Lemma 3.9. Assume that Assumption 3.7 holds, and that there exist constants c D > 0 c_D>0 c D > 0 and c D , 0 , c D , 1 ≥ 0 c_{D,0},c_{D,1}\ge0 c D , 0 , c D , 1 ≥ 0 such that the following properties hold:
:::`
Then the condition number of the preconditioned system satisfies
κ ( P a d d − 1 A h ) ≲ ( c D 2 + λ 1 H h ) ( c D , 1 H h + c D , 0 H 2 + 1 λ 0 ) . \kappa(P_{\mathrm{add}}^{-1}A_h)\lesssim\left(c_D^2+\lambda_1\frac{H}{h}\right)\left(c_{D,1}\frac{H}{h}+c_{D,0}H^2+\frac{1}{\lambda_0}\right). κ ( P add − 1 A h ) ≲ ( c D 2 + λ 1 h H ) ( c D , 1 h H + c D , 0 H 2 + λ 0 1 ) .
Proof. (4) gives Assumption 3.4 with c I 2 = H h c_I^2=\frac{H}{h} c I 2 = h H . (3) 2 _2 2 is Assumption 3.5 with the constant c D c_D c D . Finally, we combine (3.2)1 _1 1 and (3.4). For all v h ∈ V h v_h\in V_h v h ∈ V h , take v H ∈ V H v_H\in V_H v H ∈ V H as in (3.4) and set w h = v h − I H h v H w_h=v_h-I_{Hh}v_H w h = v h − I H h v H . Then (3.4)1 _1 1 bounds the first term of Assumption 3.6, while (3.4)2 , 3 _{2,3} 2 , 3 together with (3.2)1 _1 1 give, for the second term,
∥ w h ∥ D h 2 = ( D h w h , w h ) Ω ≲ (3.2) 1 c D , 1 ∥ w h ∥ H 1 ( Ω ) 2 + c D , 0 ∥ w h ∥ L 2 ( Ω ) 2 ≲ (3.4) 2 , 3 ( c D , 1 H h + c D , 0 H 2 ) ∥ v h ∥ a 2 . \lVert w_h\rVert_{D_h}^2=(D_hw_h,w_h)_\Omega\underset{\text{(3.2)}_1}{\lesssim} c_{D,1}\lVert w_h\rVert_{H^1(\Omega)}^2+c_{D,0}\lVert w_h\rVert_{L^2(\Omega)}^2 \underset{\text{(3.4)}_{2,3}}{\lesssim} \left(c_{D,1}\frac{H}{h}+c_{D,0}H^2\right)\lVert v_h\rVert_a^2. ∥ w h ∥ D h 2 = ( D h w h , w h ) Ω (3.2) 1 ≲ c D , 1 ∥ w h ∥ H 1 ( Ω ) 2 + c D , 0 ∥ w h ∥ L 2 ( Ω ) 2 (3.4) 2 , 3 ≲ ( c D , 1 h H + c D , 0 H 2 ) ∥ v h ∥ a 2 .
This gives Assumption 3.6 with c 0 , H 2 = 1 c_{0,H}^2=1 c 0 , H 2 = 1 and c 0 , D 2 = c D , 1 H h + c D , 0 H 2 c_{0,D}^2=c_{D,1}\frac{H}{h}+c_{D,0}H^2 c 0 , D 2 = c D , 1 h H + c D , 0 H 2 . Applying Lemma 3.8 concludes the proof. □
Analysis tools
We recall a series of well-known results that will be used throughout the paper. Let K K K be a polytopal element of diameter h K h_K h K that is star-shaped with respect to a ball of radius ρ K ≥ c R h K \rho_K\ge c_Rh_K ρ K ≥ c R h K , as in Assumption 3.1(ii). In our setting, K K K is either a cell of T h \mathcal{T}_h T h or an agglomerated element of T H \mathcal{T}_H T H . These results are classical. We refer to [10 ] for the standard simplicial setting, and to [14 , 32 ] for their polytopal counterparts, where the hidden constants depend only on the space dimension d d d , the polynomial degree, and the shape regularity of K K K , that is the parameter c R c_R c R of Assumption 3.1 when K ∈ T H K\in\mathcal{T}_H K ∈ T H and the shape regularity of T h \mathcal{T}_h T h assumed in Sect. 2 when K ∈ T h K\in\mathcal{T}_h K ∈ T h . The trace, Poincaré and Poincaré–Friedrichs inequalities, and the estimates for the elliptic projector with m ≤ 1 m\le1 m ≤ 1 , rely on star-shapedness alone. The remaining projector estimates go through an inverse inequality on K K K , which for K ∈ T H K\in\mathcal{T}_H K ∈ T H uses in addition the simplicial covering of Assumption 3.1(iii).
Similarly, denote by π K 1 , k : H 1 ( K ) → P k ( K ) \pi_K^{1,k}:H^1(K)\to\mathbb{P}^k(K) π K 1 , k : H 1 ( K ) → P k ( K ) the elliptic projector defined by
( ∇ π K 1 , k v , ∇ w ) K = ( ∇ v , ∇ w ) K ∀ w ∈ P k ( K ) , (10) (\nabla\pi_K^{1,k}v,\nabla w)_K=(\nabla v,\nabla w)_K\qquad\forall w\in\mathbb{P}^k(K), \tag*{(10)} ( ∇ π K 1 , k v , ∇ w ) K = ( ∇ v , ∇ w ) K ∀ w ∈ P k ( K ) , (10)
( π K 1 , k v , 1 ) K = ( v , 1 ) K . (\pi_K^{1,k}v,1)_K=(v,1)_K. ( π K 1 , k v , 1 ) K = ( v , 1 ) K .
For all v ∈ H s ( K ) v \in H^s(K) v ∈ H s ( K ) with 1 ≤ s ≤ k + 1 1 \le s \le k+1 1 ≤ s ≤ k + 1 , we have
∣ v − π K 1 , k v ∣ H m ( K ) ≲ h K s − m ∣ v ∣ H s ( K ) , 0 ≤ m ≤ s , (11) \left|v-\pi_K^{1,k}v\right|_{H^m(K)} \lesssim h_K^{s-m}|v|_{H^s(K)}, \qquad0 \le m \le s, \tag*{(11)} v − π K 1 , k v H m ( K ) ≲ h K s − m ∣ v ∣ H s ( K ) , 0 ≤ m ≤ s , (11)
∥ v − π K 1 , k v ∥ ∂ K ≲ h K s − 1 / 2 ∣ v ∣ H s ( K ) . (12) \left\|v-\pi_K^{1,k}v\right\|_{\partial K} \lesssim h_K^{s-1/2}|v|_{H^s(K)}. \tag*{(12)} v − π K 1 , k v ∂ K ≲ h K s − 1/2 ∣ v ∣ H s ( K ) . (12)
Given a collection of polytopal elements K h \mathcal{K}_h K h (e.g. T h \mathcal{T}_h T h or T H \mathcal{T}_H T H ), we denote by π K h k \pi_{\mathcal{K}_h}^k π K h k and π K h 1 , k \pi_{\mathcal{K}_h}^{1,k} π K h 1 , k the broken projectors acting element-wise, that is π K h k v ∣ K = π K k ( v ∣ K ) \pi_{\mathcal{K}_h}^k v|_K=\pi_K^k(v|_K) π K h k v ∣ K = π K k ( v ∣ K ) and π K h 1 , k v ∣ K = π K 1 , k ( v ∣ K ) \pi_{\mathcal{K}_h}^{1,k}v|_K=\pi_K^{1,k}(v|_K) π K h 1 , k v ∣ K = π K 1 , k ( v ∣ K ) for all K ∈ K h K\in\mathcal{K}_h K ∈ K h . The previous approximation properties hold element-wise, and thus also for the broken projectors.
Additive Schwarz smoothers
Additive Schwarz smoothers have been widely studied in the literature in the context of Domain Decomposition (DD) and GMG solvers for conforming discretisations of elliptic problems. Classical examples include the point-Jacobi smoother and overlapping block smoothers such as the vertex-star patch smoother, in which each subdomain is the union of the cells sharing a mesh vertex. These are the two smoothers used in our experiments. We provide here a brief definition of these smoothers, and recall some of their properties that are relevant for the analysis of the GMG method.
Abstract setting
Additive Schwarz smoothers are built from a decomposition of V h V_h V h into a family of subspaces. The family is indexed by a set D \mathcal{D} D of geometrical entities of the mesh, such as nodes, vertices or patches of cells, the choice of D \mathcal{D} D being what distinguishes one smoother from another. Let { W r } r ∈ D \{W_r\}_{r\in\mathcal{D}} { W r } r ∈ D be subspaces of V h V_h V h such that V h = ∑ r ∈ D W r V_h=\sum_{r\in\mathcal{D}}W_r V h = ∑ r ∈ D W r , and assume that the functions of W r W_r W r are supported in the closure of an open set ω r ⊂ Ω \omega_r\subset\Omega ω r ⊂ Ω .
We denote by R r : V h → W r R_r:V_h\to W_r R r : V h → W r the L 2 L^2 L 2 -orthogonal projection onto W r W_r W r , and by R r ∗ : W r → V h R_r^*:W_r\to V_h R r ∗ : W r → V h its adjoint, which is the natural injection of W r W_r W r into V h V_h V h . We define the local bilinear forms as the restrictions of a a a to the subspaces W r W_r W r , that is
a r ( u r , v r ) ≔ a ( R r ∗ u r , R r ∗ v r ) ∀ u r , v r ∈ W r , a_r(u_r,v_r) \coloneqq a(R_r^*u_r,R_r^*v_r)\qquad\forall u_r,v_r\in W_r, a r ( u r , v r ) : = a ( R r ∗ u r , R r ∗ v r ) ∀ u r , v r ∈ W r ,
with associated operators A r : W r → W r A_r:W_r\to W_r A r : W r → W r . The additive Schwarz smoother associated with the decomposition { W r } \{W_r\} { W r } is then defined through its inverse as
D h − 1 ≔ ∑ r ∈ D R r ∗ A r − 1 R r . (13) D_h^{-1}\coloneqq\sum_{r\in\mathcal{D}}R_r^*A_r^{-1}R_r. \tag*{(13)} D h − 1 : = r ∈ D ∑ R r ∗ A r − 1 R r . (13)
The operator D h D_h D h is symmetric positive definite, and its quadratic form admits the classical characterisation (see [34 Lemma 2.5] )
( D h v h , v h ) Ω = min { ∑ r ∈ D a r ( v r , v r ) : v r ∈ W r , v h = ∑ r ∈ D R r ∗ v r } . (14) (D_hv_h,v_h)_\Omega=\min\left\{\sum_{r\in\mathcal{D}}a_r(v_r,v_r):v_r\in W_r,\ v_h=\sum_{r\in\mathcal{D}}R_r^*v_r\right\}. \tag*{(14)} ( D h v h , v h ) Ω = min { r ∈ D ∑ a r ( v r , v r ) : v r ∈ W r , v h = r ∈ D ∑ R r ∗ v r } . (14)
We will refer to any set { v r } \{v_r\} { v r } , v r ∈ W r v_r\in W_r v r ∈ W r , such that v h = ∑ r ∈ D R r ∗ v r v_h=\sum_{r\in\mathcal{D}}R_r^*v_r v h = ∑ r ∈ D R r ∗ v r as an admissible decomposition of v h v_h v h . Any such decomposition provides an upper bound for ( D h v h , v h ) Ω (D_hv_h,v_h)_\Omega ( D h v h , v h ) Ω , which is how the first inequality in (3.2) is established in each of the cases below. The second inequality holds whenever the decomposition has finite overlap, in the following sense.
Assumption 5.1. (see [34 Assumption 3.2] ) The sets { ω r } \{\omega_r\} { ω r } can be coloured using at most N O N_O N O colours, in such a way that subregions with the same colour are disjoint. Since sets sharing a common point have different colours, every x ∈ Ω x\in\Omega x ∈ Ω belongs to at most N O N_O N O of them.
Lemma 5.2 (Smoother stability). Let Assumption 5.1 hold. Then Assumption 3.5 holds with c D 2 = N O c_D^2=N_O c D 2 = N O , that is for all $v_h\in V_h,
a ( v h , v h ) ≤ N O ( D h v h , v h ) Ω . a(v_h,v_h)\le N_O(D_hv_h,v_h)_\Omega. a ( v h , v h ) ≤ N O ( D h v h , v h ) Ω .
Proof. Let v h ∈ V h v_h\in V_h v h ∈ V h and let v h = ∑ r ∈ D R r ∗ v r v_h=\sum_{r\in\mathcal{D}}R_r^*v_r v h = ∑ r ∈ D R r ∗ v r , v r ∈ W r v_r\in W_r v r ∈ W r , be an arbitrary admissible decomposition. Grouping the subspaces by colour according to Assumption 5.1, we can write v h = ∑ c = 1 N O w c v_h=\sum_{c=1}^{N_O}w_c v h = ∑ c = 1 N O w c with w c ≔ ∑ r ∈ C c R r ∗ v r w_c\coloneqq\sum_{r\in\mathcal{C}_c}R_r^*v_r w c : = ∑ r ∈ C c R r ∗ v r , where C c \mathcal{C}_c C c collects the entities of colour c c c . By the triangle and Cauchy–Schwarz inequalities,
a ( v h , v h ) = ∥ ∑ c w c ∥ a 2 ≤ ( ∑ c ∥ w c ∥ a ) 2 ≤ N O ∑ c ∥ w c ∥ a 2 , a(v_h,v_h)=\left\|\sum_c w_c\right\|_a^2\le\left(\sum_c\|w_c\|_a\right)^2\le N_O\sum_c\|w_c\|_a^2, a ( v h , v h ) = c ∑ w c a 2 ≤ ( c ∑ ∥ w c ∥ a ) 2 ≤ N O c ∑ ∥ w c ∥ a 2 ,
where the last step is the Cauchy–Schwarz inequality in R N O \mathbb{R}^{N_O} R N O . Since the sets ω r \omega_r ω r of the same colour are disjoint, the supports of { R r ∗ v r } r ∈ C c \{R_r^*v_r\}_{r\in\mathcal{C}_c} { R r ∗ v r } r ∈ C c meet only on sets of zero measure, and thus
∥ w c ∥ a 2 = ∑ r ∈ C c a ( R r ∗ v r , R r ∗ v r ) = ∑ r ∈ C c a r ( v r , v r ) . \lVert w_c\rVert_a^2=\sum_{r\in\mathcal{C}_c}a(R_r^*v_r,R_r^*v_r)=\sum_{r\in\mathcal{C}_c}a_r(v_r,v_r). ∥ w c ∥ a 2 = r ∈ C c ∑ a ( R r ∗ v r , R r ∗ v r ) = r ∈ C c ∑ a r ( v r , v r ) .
Combining both bounds gives a ( v h , v h ) ≤ N O ∑ r ∈ D a r ( v r , v r ) a(v_h,v_h)\leq N_O\sum_{r\in D}a_r(v_r,v_r) a ( v h , v h ) ≤ N O ∑ r ∈ D a r ( v r , v r ) . Taking the minimum over all admissible decompositions and using the characterisation (5.2) concludes the proof. □
For every decomposition considered below, N O N_O N O is a fixed constant determined by the shape regularity of T h \mathcal{T}_h T h and by the polynomial degree. We therefore stop tracking it explicitly from here on, and absorb it into the hidden constants.
Nodal decompositions
The two smoothers used in our experiments correspond to two natural choices of the index set D D D , and are covered by an elementary argument. Let N h i n t \mathcal{N}_h^{\mathrm{int}} N h int denote the set of interior Lagrangian nodes of T h \mathcal{T}_h T h , that is those not lying on ∂ Ω \partial\Omega ∂ Ω , and for ν ∈ N h i n t \nu\in\mathcal{N}_h^{\mathrm{int}} ν ∈ N h int let φ ν \varphi_\nu φ ν be the associated basis function. Since V h ⊂ H 0 1 ( Ω ) V_h\subset H_0^1(\Omega) V h ⊂ H 0 1 ( Ω ) , the family { φ ν } ν ∈ N h i n t \{\varphi_\nu\}_{\nu\in\mathcal{N}_h^{\mathrm{int}}} { φ ν } ν ∈ N h int is a basis of V h V_h V h and
v h = ∑ ν ∈ N h i n t v h ( ν ) φ ν . (15) v_h=\sum_{\nu\in\mathcal{N}_h^{\mathrm{int}}}v_h(\nu)\varphi_\nu. \tag*{(15)} v h = ν ∈ N h int ∑ v h ( ν ) φ ν . (15)
We will use the standard scaling ∣ φ ν ∣ 1 , Ω 2 ≃ h d − 2 \lvert\varphi_\nu\rvert_{1,\Omega}^2\simeq h^{d-2} ∣ φ ν ∣ 1 , Ω 2 ≃ h d − 2 of the basis functions, together with the norm equivalence h d ∑ ν ∈ N h i n t ∣ v h ( ν ) ∣ 2 ≃ ∥ v h ∥ L 2 ( Ω ) 2 h^d\sum_{\nu\in\mathcal{N}_h^{\mathrm{int}}}\lvert v_h(\nu)\rvert^2\simeq\lVert v_h\rVert_{L^2(\Omega)}^2 h d ∑ ν ∈ N h int ∣ v h ( ν ) ∣ 2 ≃ ∥ v h ∥ L 2 ( Ω ) 2 on V h V_h V h .
Corollary 5.3 (Point-Jacobi smoother). Let D = N h i n t D=\mathcal{N}_h^{\mathrm{int}} D = N h int and let D h D_h D h be given by (5.1) with W ν = span { φ ν } W_\nu=\operatorname{span}\{\varphi_\nu\} W ν = span { φ ν } . Then (3.2) holds with c D , 0 ≃ h − 2 c_{D,0}\simeq h^{-2} c D , 0 ≃ h − 2 , c D , 1 = 0 c_{D,1}=0 c D , 1 = 0 and c D 2 ≃ 1 c_D^2\simeq1 c D 2 ≃ 1 .
Proof. Since { φ ν } ν ∈ N h i n t \{\varphi_\nu\}_{\nu\in\mathcal{N}_h^{\mathrm{int}}} { φ ν } ν ∈ N h int is a basis of V h V_h V h , the decomposition (5.3) is the only admissible one, and the minimum in (5.2) is therefore attained at it. Hence
( D h v h , v h ) Ω = ∑ ν ∈ N h i n t ∣ v h ( ν ) ∣ 2 ∣ φ ν ∣ 1 , Ω 2 ≃ h d − 2 ∑ ν ∈ N h i n t ∣ v h ( ν ) ∣ 2 ≃ h − 2 ∥ v h ∥ L 2 ( Ω ) 2 , (D_hv_h,v_h)_\Omega=\sum_{\nu\in\mathcal{N}_h^{\mathrm{int}}}\lvert v_h(\nu)\rvert^2\lvert\varphi_\nu\rvert_{1,\Omega}^2\simeq h^{d-2}\sum_{\nu\in\mathcal{N}_h^{\mathrm{int}}}\lvert v_h(\nu)\rvert^2\simeq h^{-2}\lVert v_h\rVert_{L^2(\Omega)}^2, ( D h v h , v h ) Ω = ν ∈ N h int ∑ ∣ v h ( ν ) ∣ 2 ∣ φ ν ∣ 1 , Ω 2 ≃ h d − 2 ν ∈ N h int ∑ ∣ v h ( ν ) ∣ 2 ≃ h − 2 ∥ v h ∥ L 2 ( Ω ) 2 ,
which is (3.2)1 _1 1 with c D , 0 ≃ h − 2 c_{D,0}\simeq h^{-2} c D , 0 ≃ h − 2 and c D , 1 = 0 c_{D,1}=0 c D , 1 = 0 . Equation (3.2)2 _2 2 follows from Lemma 5.2, since the supports of the φ ν \varphi_\nu φ ν can be coloured with a number of colours bounded in terms of the shape regularity of T h \mathcal{T}_h T h and of p p p . □
Corollary 5.4 (Vertex-star patch smoother). Let D = V h D=\mathcal{V}_h D = V h be the set of vertices of T h \mathcal{T}_h T h and, for z ∈ V h z\in\mathcal{V}_h z ∈ V h , let S z S_z S z be its star, that is the union of the cells sharing z z z . Let D h D_h D h be given by (5.1) with W z = { v h ∈ V h : supp ( v h ) ⊂ S z ‾ } W_z=\{v_h\in V_h:\operatorname{supp}(v_h)\subset\overline{S_z}\} W z = { v h ∈ V h : supp ( v h ) ⊂ S z } . Then (3.2) holds with c D , 0 ≃ h − 2 c_{D,0}\simeq h^{-2} c D , 0 ≃ h − 2 , c D , 1 = 0 c_{D,1}=0 c D , 1 = 0 and c D 2 ≃ 1 c_D^2\simeq1 c D 2 ≃ 1 .
Proof. For each ν ∈ N h i n t \nu\in\mathcal{N}_h^{\mathrm{int}} ν ∈ N h int , let e ( ν ) e(\nu) e ( ν ) be the lowest-dimensional mesh entity containing ν \nu ν , and fix one vertex z ( ν ) z(\nu) z ( ν ) of e ( ν ) e(\nu) e ( ν ) . The basis function φ ν \varphi_\nu φ ν is supported in the cells whose closure contains ν \nu ν , which are exactly those containing e ( ν ) e(\nu) e ( ν ) , and each of them contains the vertex z ( ν ) z(\nu) z ( ν ) of e ( ν ) e(\nu) e ( ν ) . Hence supp ( φ ν ) ⊂ S z ( ν ) ‾ \operatorname{supp}(\varphi_\nu)\subset\overline{S_{z(\nu)}} supp ( φ ν ) ⊂ S z ( ν ) . Taking e ( ν ) e(\nu) e ( ν ) of lowest dimension is essential here, since a vertex of a larger entity containing ν \nu ν need not belong to every cell containing ν \nu ν . The map ν ↦ z ( ν ) \nu\mapsto z(\nu) ν ↦ z ( ν ) partitions N h i n t \mathcal{N}_h^{\mathrm{int}} N h int , so
v z : = ∑ ν : z ( ν ) = z v h ( ν ) φ ν ∈ W z v_z:=\sum_{\nu:z(\nu)=z}v_h(\nu)\varphi_\nu\in W_z v z := ν : z ( ν ) = z ∑ v h ( ν ) φ ν ∈ W z
regroups (5.3) into an admissible decomposition, since ∑ z ∈ V h R z ∗ v z = ∑ ν ∈ N h i n t v h ( ν ) φ ν = v h \sum_{z\in\mathcal{V}_h}R_z^*v_z=\sum_{\nu\in\mathcal{N}_h^{\mathrm{int}}}v_h(\nu)\varphi_\nu=v_h ∑ z ∈ V h R z ∗ v z = ∑ ν ∈ N h int v h ( ν ) φ ν = v h . The subspaces W z W_z W z do overlap, but that plays no role here, because each node contributes to exactly one v z v_z v z .
The number of nodes assigned to a given vertex is bounded in terms of the shape regularity of T h \mathcal{T}_h T h and of p p p , so the triangle and Cauchy–Schwarz inequalities give ∣ v z ∣ 1 , S z 2 ≲ ∑ ν : z ( ν ) = z ∣ v h ( ν ) ∣ 2 ∣ φ ν ∣ 1 , Ω 2 \lvert v_z\rvert_{1,S_z}^2\lesssim\sum_{\nu:z(\nu)=z}\lvert v_h(\nu)\rvert^2\lvert\varphi_\nu\rvert_{1,\Omega}^2 ∣ v z ∣ 1 , S z 2 ≲ ∑ ν : z ( ν ) = z ∣ v h ( ν ) ∣ 2 ∣ φ ν ∣ 1 , Ω 2 . Summing over z ∈ V h z\in\mathcal{V}_h z ∈ V h , and using (5.2) together with the fact that the map ν ↦ z ( ν ) \nu\mapsto z(\nu) ν ↦ z ( ν ) is a partition,
( D h v h , v h ) Ω ≤ ∑ z ∈ V h ∣ v z ∣ 1 , S z 2 ≲ ∑ ν ∈ N h i n t ∣ v h ( ν ) ∣ 2 ∣ φ ν ∣ 1 , Ω 2 ≃ h − 2 ∥ v h ∥ L 2 ( Ω ) 2 . (D_hv_h,v_h)_\Omega\leq\sum_{z\in\mathcal{V}_h}\lvert v_z\rvert_{1,S_z}^2\lesssim\sum_{\nu\in\mathcal{N}_h^{\mathrm{int}}}\lvert v_h(\nu)\rvert^2\lvert\varphi_\nu\rvert_{1,\Omega}^2\simeq h^{-2}\lVert v_h\rVert_{L^2(\Omega)}^2. ( D h v h , v h ) Ω ≤ z ∈ V h ∑ ∣ v z ∣ 1 , S z 2 ≲ ν ∈ N h int ∑ ∣ v h ( ν ) ∣ 2 ∣ φ ν ∣ 1 , Ω 2 ≃ h − 2 ∥ v h ∥ L 2 ( Ω ) 2 .
(3) 2 _2 2 follows again from Lemma 5.2. Here the overlap of the stars does matter, and it is controlled by Assumption 5.1. Two stars intersect only if their vertices belong to a common cell, so the vertices can be coloured with a number of colours bounded by the shape regularity of T h \mathcal{T}_h T h in such a way that stars of the same colour are disjoint. □
DG auxiliary space preconditioner
We now instantiate the abstract framework of Sect. 3. The coarse auxiliary space V H V_H V H is a broken polynomial space on the agglomerated mesh T H \mathcal{T}_H T H , the coarse bilinear form a H a_H a H is a Symmetric Interior Penalty Galerkin (SIPG) discretisation and the prolongation I H h = I H h d g I_{Hh}=I_{Hh}^{\mathrm{dg}} I H h = I H h dg is built from an Oswald-type averaging operator on the fine mesh. We prove that the resulting preconditioned system has condition number bounded by O ( H 3 / h 3 ) O(H^3/h^3) O ( H 3 / h 3 ) at fixed penalty, and by O ( H 2 / h 2 ) O(H^2/h^2) O ( H 2 / h 2 ) for σ ≃ H / h \sigma\simeq H/h σ ≃ H / h , for the point-Jacobi and vertex-star patch smoothers of Sect. 5.
Coarse DG space and bilinear form
Given a coarse polynomial degree q ≥ 1 q \ge1 q ≥ 1 , in general independent of the fine degree p p p , we define the coarse auxiliary space as the broken polynomial space of degree q q q on the agglomerated mesh:
V H ≔ P q ( T H ) = { v H ∈ L 2 ( Ω ) : v H ∣ T ∈ P q ( T ) ∀ T ∈ T H } . V_H \coloneqq\mathbb{P}^q(\mathcal{T}_H)=\left\{v_H\in L^2(\Omega):v_H|_T\in\mathbb{P}^q(T)\ \forall T\in\mathcal{T}_H\right\}. V H : = P q ( T H ) = { v H ∈ L 2 ( Ω ) : v H ∣ T ∈ P q ( T ) ∀ T ∈ T H } .
For an interior face F ∈ F H i n F\in\mathcal{F}_H^{\mathrm{in}} F ∈ F H in shared by two coarse elements T 1 , T 2 ∈ T H T_1,T_2\in\mathcal{T}_H T 1 , T 2 ∈ T H , let n T i \boldsymbol{n}_{T_i} n T i denote the unit normal to F F F pointing outwards from T i T_i T i , and define the jump and the average as
⟦ v H ⟧ ∣ F ≔ v H ∣ T 1 n T 1 + v H ∣ T 2 n T 2 , { { ∇ v H } } ∣ F ≔ 1 2 ( ∇ v H ∣ T 1 + ∇ v H ∣ T 2 ) . \llbracket v_H\rrbracket\big|_F \coloneqq v_H|_{T_1}\boldsymbol{n}_{T_1}+v_H|_{T_2}\boldsymbol{n}_{T_2},\qquad\{\!\{\nabla v_H\}\!\}\big|_F\coloneqq\frac{1}{2}\left(\nabla v_H|_{T_1}+\nabla v_H|_{T_2}\right). [ [ v H ] ] F : = v H ∣ T 1 n T 1 + v H ∣ T 2 n T 2 , { { ∇ v H } } F : = 2 1 ( ∇ v H ∣ T 1 + ∇ v H ∣ T 2 ) .
where the restrictions denote traces taken from within each element. For a boundary face F ∈ F H b d F\in\mathcal{F}_H^{\mathrm{bd}} F ∈ F H bd with outward unit normal n F \boldsymbol{n}_F n F we set ⟦ v H ⟧ ∣ F ≔ v H ∣ F n F \llbracket v_H\rrbracket|_F\coloneqq v_H|_F\boldsymbol{n}_F [ [ v H ] ] ∣ F : = v H ∣ F n F and { { ∇ v H } } ∣ F ≔ ∇ v H ∣ F \{\!\{\nabla v_H\}\!\}|_F\coloneqq\nabla v_H|_F { { ∇ v H } } ∣ F : = ∇ v H ∣ F , so that both notations extend uniformly to all F ∈ F H F\in\mathcal{F}_H F ∈ F H . In either case ∥ ⟦ v H ⟧ ∥ \|\llbracket v_H\rrbracket\| ∥ [ [ v H ] ] ∥ is the modulus of the difference of the two traces, respectively of the trace itself, so that ∥ ⟦ v H ⟧ ∥ F \|\llbracket v_H\rrbracket\|_F ∥ [ [ v H ] ] ∥ F is the quantity appearing in all the estimates below. The same conventions are used on the fine mesh, on every f ∈ F h f\in\mathcal{F}_h f ∈ F h . The face size H F H_F H F is as defined in Sect. 3, namely the mean diameter of the coarse elements sharing F F F rather than the diameter of F F F itself.
The coarse bilinear form a H : V H × V H → R a_H:V_H\times V_H\to\mathbb{R} a H : V H × V H → R is taken as the SIPG formulation: for u H , v H ∈ V H u_H,v_H\in V_H u H , v H ∈ V H ,
a H ( u H , v H ) ≔ ∑ T ∈ T H ( ∇ u H , ∇ v H ) T − ∑ F ∈ F H [ ( { { ∇ u H } } , ⟦ v H ⟧ ) F + ( { { ∇ v H } } , ⟦ u H ⟧ ) F ] + ∑ F ∈ F H σ H F ( ⟦ u H ⟧ , ⟦ v H ⟧ ) F . (16) a_H(u_H,v_H)\coloneqq\sum_{T\in\mathcal{T}_H}(\nabla u_H,\nabla v_H)_T-\sum_{F\in\mathcal{F}_H}\left[\left(\{\!\{\nabla u_H\}\!\},\llbracket v_H\rrbracket\right)_F+\left(\{\!\{\nabla v_H\}\!\},\llbracket u_H\rrbracket\right)_F\right]+\sum_{F\in\mathcal{F}_H}\frac{\sigma}{H_F}\left(\llbracket u_H\rrbracket,\llbracket v_H\rrbracket\right)_F. \tag*{(16)} a H ( u H , v H ) : = T ∈ T H ∑ ( ∇ u H , ∇ v H ) T − F ∈ F H ∑ [ ( { { ∇ u H } } , [ [ v H ] ] ) F + ( { { ∇ v H } } , [ [ u H ] ] ) F ] + F ∈ F H ∑ H F σ ( [ [ u H ] ] , [ [ v H ] ] ) F . (16)
where σ > 0 \sigma>0 σ > 0 is the interior penalty parameter. The boundary face terms weakly enforce the homogeneous Dirichlet condition. The associated energy norm is
∥ v H ∥ d g , H 2 ≔ ∣ v H ∣ 1 , T H 2 + ∑ F ∈ F H σ H F ∥ ⟦ v H ⟧ ∥ F 2 . (17) \|v_H\|_{\mathrm{dg},H}^2\coloneqq|v_H|_{1,\mathcal{T}_H}^2+\sum_{F\in\mathcal{F}_H}\frac{\sigma}{H_F}\|\llbracket v_H\rrbracket\|_F^2. \tag*{(17)} ∥ v H ∥ dg , H 2 : = ∣ v H ∣ 1 , T H 2 + F ∈ F H ∑ H F σ ∥ [ [ v H ] ] ∥ F 2 . (17)
The continuity and coercivity of the bilinear form (16) with respect to ∥ ⋅ ∥ d g , H \|\cdot\|_{\mathrm{dg},H} ∥ ⋅ ∥ dg , H are well established in the literature, see, e.g. [14 , 20 ] , and are given by the following lemma.
Lemma 6.1. If T H \mathcal{T}_H T H satisfies Assumption 3.1, then there is σ 0 ≥ 1 \sigma_0\ge1 σ 0 ≥ 1 , depending only on q q q and the constants of Assumption 3.1, such that for all σ ≥ σ 0 \sigma\ge\sigma_0 σ ≥ σ 0
a H ( u H , v H ) ≲ ∥ u H ∥ d g , H ∥ v H ∥ d g , H , ∀ u H , v H ∈ V H . a_H(u_H,v_H)\lesssim\|u_H\|_{\mathrm{dg},H}\|v_H\|_{\mathrm{dg},H},\qquad\forall u_H,v_H\in V_H. a H ( u H , v H ) ≲ ∥ u H ∥ dg , H ∥ v H ∥ dg , H , ∀ u H , v H ∈ V H . a H ( v H , v H ) ≳ ∥ v H ∥ d g , H 2 , ∀ v H ∈ V H , a_H(v_H,v_H)\gtrsim\|v_H\|_{\mathrm{dg},H}^2,\qquad\forall v_H\in V_H, a H ( v H , v H ) ≳ ∥ v H ∥ dg , H 2 , ∀ v H ∈ V H , with hidden constants independent of σ \sigma σ .
The σ \sigma σ -uniformity of the constants follows from Young’s inequality together with the trace and inverse inequalities on T H \mathcal{T}_H T H . We assume σ ≥ σ 0 \sigma\ge\sigma_0 σ ≥ σ 0 throughout, and track the dependence on σ \sigma σ of all estimates below.
Prolongation operator
We define the prolongation I H h d g : P k ( T H ) → V h I_{Hh}^{\mathrm{dg}}:\mathbb{P}^k(\mathcal{T}_H)\to V_h I H h dg : P k ( T H ) → V h by composing an element-wise interpolant with an Oswald-type nodal averaging operator, both defined on the fine mesh. Here k ≥ 1 k\ge1 k ≥ 1 is a generic degree for the argument of I H h d g I_{Hh}^{\mathrm{dg}} I H h dg , distinct from the fine degree p p p and the coarse degree q q q . In this section I H h d g I_{Hh}^{\mathrm{dg}} I H h dg acts on the coarse DG space and k = q k=q k = q , while in Sect. 7 it acts on the potential reconstruction of the coarse HHO function and k = q + 1 k=q+1 k = q + 1 . Since q q q is independent of p p p , the argument of I H h d g I_{Hh}^{\mathrm{dg}} I H h dg may have a higher degree than the fine space can represent. With the choice q = p q=p q = p used in our experiments, k = p k=p k = p here and k = p + 1 > p k=p+1>p k = p + 1 > p in Sect. 7. The estimates below assume no relation between k k k and p p p .
Let I h \mathcal{I}_h I h denote the element-wise Lagrange interpolant of degree p p p onto P p ( T h ) \mathbb{P}^p(\mathcal{T}_h) P p ( T h ) , i.e. ( I h w ) ∣ t (\mathcal{I}_h w)|_t ( I h w ) ∣ t interpolates w ∣ t w|_t w ∣ t at the Lagrangian nodes of t t t for all t ∈ T h t \in\mathcal{T}_h t ∈ T h . It is defined for any w w w that is piecewise continuous in T h \mathcal{T}_h T h , in particular on P k ( T H ) \mathbb{P}^k(\mathcal{T}_H) P k ( T H ) for any k ≥ 1 k \ge1 k ≥ 1 , and it is the identity on P p ( T h ) \mathbb{P}^p(\mathcal{T}_h) P p ( T h ) . For each interior node ν ∈ N h i n t \nu\in\mathcal{N}_h^{\mathrm{int}} ν ∈ N h int , let N h ( ν ) ⊂ T h \mathcal{N}_h(\nu) \subset\mathcal{T}_h N h ( ν ) ⊂ T h be the set of fine cells whose closure contains ν \nu ν , and let { α t ( ν ) } t ∈ N h ( ν ) \{\alpha_t(\nu)\}_{t \in\mathcal{N}_h(\nu)} { α t ( ν ) } t ∈ N h ( ν ) be weights with α t ( ν ) ≥ 0 \alpha_t(\nu) \ge0 α t ( ν ) ≥ 0 and ∑ t ∈ N h ( ν ) α t ( ν ) = 1 \sum_{t \in\mathcal{N}_h(\nu)} \alpha_t(\nu) = 1 ∑ t ∈ N h ( ν ) α t ( ν ) = 1 . The averaging operator W h : P p ( T h ) → V h \mathcal{W}_h : \mathbb{P}^p(\mathcal{T}_h) \to V_h W h : P p ( T h ) → V h combines the (possibly multi-valued) values of its argument at each interior node with these weights and vanishes at boundary nodes:
( W h w h ) ( ν ) : = ∑ t ∈ N h ( ν ) α t ( ν ) ( w h ∣ t ) ( ν ) for ν ∉ ∂ Ω , ( W h w h ) ( ν ) : = 0 for ν ∈ ∂ Ω . (18) (\mathcal{W}_h w_h)(\nu) := \sum_{t \in\mathcal{N}_h(\nu)} \alpha_t(\nu)(w_h|_t)(\nu) \quad\text{for } \nu\notin\partial\Omega,\qquad(\mathcal{W}_h w_h)(\nu) := 0 \quad\text{for } \nu\in\partial\Omega. \tag*{(18)} ( W h w h ) ( ν ) := t ∈ N h ( ν ) ∑ α t ( ν ) ( w h ∣ t ) ( ν ) for ν ∈ / ∂ Ω , ( W h w h ) ( ν ) := 0 for ν ∈ ∂ Ω. (18)
With uniform weights α t ( ν ) = ∣ N h ( ν ) ∣ − 1 \alpha_t(\nu)=|\mathcal{N}_h(\nu)|^{-1} α t ( ν ) = ∣ N h ( ν ) ∣ − 1 , W h \mathcal{W}_h W h is the classical Oswald interpolation operator [13 , 28 ] . The prolongation is the composition
I H h d g : = W h I h : P k ( T H ) → V h . (19) I_{Hh}^{\mathrm{dg}} := \mathcal{W}_h\mathcal{I}_h : \mathbb{P}^k(\mathcal{T}_H) \to V_h. \tag*{(19)} I H h dg := W h I h : P k ( T H ) → V h . (19)
Since ( I h v H ∣ t ) ( ν ) = ( v H ∣ T ) ( ν ) (\mathcal{I}_h v_H|_t)(\nu)=(v_H|_T)(\nu) ( I h v H ∣ t ) ( ν ) = ( v H ∣ T ) ( ν ) for every fine cell t ∈ T t \in\mathcal{T} t ∈ T and every node ν \nu ν of t t t , the sum in (18) can be grouped by agglomerates, and I H h d g I_{Hh}^{\mathrm{dg}} I H h dg reduces to a nodal averaging of the coarse one-sided values,
( I H h d g v H ) ( ν ) = ∑ T ∈ N H ( ν ) β T ( ν ) ( v H ∣ T ) ( ν ) for ν ∉ ∂ Ω , β T ( ν ) : = ∑ t ∈ N h ( ν ) , t ⊂ T α t ( ν ) , (20) (I_{Hh}^{\mathrm{dg}}v_H)(\nu)=\sum_{T\in\mathcal{N}_H(\nu)}\beta_T(\nu)(v_H|_T)(\nu)\quad\text{for }\nu\notin\partial\Omega,\qquad\beta_T(\nu):=\sum_{\substack{t\in\mathcal{N}_h(\nu),\,t\subset T}}\alpha_t(\nu), \tag*{(20)} ( I H h dg v H ) ( ν ) = T ∈ N H ( ν ) ∑ β T ( ν ) ( v H ∣ T ) ( ν ) for ν ∈ / ∂ Ω , β T ( ν ) := t ∈ N h ( ν ) , t ⊂ T ∑ α t ( ν ) , (20)
where N H ( ν ) ⊂ T H \mathcal{N}_H(\nu)\subset\mathcal{T}_H N H ( ν ) ⊂ T H is the set of coarse elements whose closure contains ν \nu ν . The induced weights β T ( ν ) \beta_T(\nu) β T ( ν ) are non-negative and sum to one. The resulting function is piecewise polynomial on T h \mathcal{T}_h T h , globally continuous and vanishes on ∂ Ω \partial\Omega ∂ Ω , so I H h d g v H ∈ V h I_{Hh}^{\mathrm{dg}}v_H\in V_h I H h dg v H ∈ V h .
Remark 6.2 (Choice of the weights). All the estimates below hold for any admissible choice of the weights α t ( ν ) \alpha_t(\nu) α t ( ν ) , with hidden constants independent of this choice. Two natural options are the uniform weights α t ( ν ) = ∣ N h ( ν ) ∣ − 1 \alpha_t(\nu)=|\mathcal{N}_h(\nu)|^{-1} α t ( ν ) = ∣ N h ( ν ) ∣ − 1 , for which β T ( ν ) \beta_T(\nu) β T ( ν ) is proportional to the number of fine cells of T T T at ν \nu ν , and the agglomerate-aware weights α t ( ν ) = ( ∣ N H ( ν ) ∣ n T ( ν ) ) − 1 \alpha_t(\nu)=(|\mathcal{N}_H(\nu)|\,n_T(\nu))^{-1} α t ( ν ) = ( ∣ N H ( ν ) ∣ n T ( ν ) ) − 1 for t ⊂ T t\subset T t ⊂ T , with n T ( ν ) n_T(\nu) n T ( ν ) the number of fine cells of T T T whose closure contains ν \nu ν , for which (6.5) is the plain average β T ( ν ) = ∣ N H ( ν ) ∣ − 1 \beta_T(\nu)=|\mathcal{N}_H(\nu)|^{-1} β T ( ν ) = ∣ N H ( ν ) ∣ − 1 of the coarse one-sided values.
The estimate we need for I H h d g I_{Hh}^{\mathrm{dg}} I H h dg rests on the following bound for the averaging operator W h \mathcal{W}_h W h . Classical versions of it, for the fine-mesh Oswald operator, are given in [28 Th. 2.2] for r = 1 r=1 r = 1 and [13 Lem. 3.2] for r = 0 r=0 r = 0 . Neither is stated for general weights, and the L 2 L^2 L 2 bound is not stated for simplicial Lagrange elements with the boundary treatment used here, so we give the (elementary) proof.
Lemma 6.3 (Nodal averaging on the fine mesh). For r = 0 , 1 r=0,1 r = 0 , 1 and all w h ∈ P p ( T h ) w_h\in\mathbb{P}^p(\mathcal{T}_h) w h ∈ P p ( T h ) , the averaging operator W h \mathcal{W}_h W h defined in (6.3) with any weights that are non-negative and sum to one satisfies
∥ w h − W h w h ∥ H r ( T h ) 2 ≲ ∑ f ∈ F h h f 1 − 2 r ∥ [ w h ] ∥ f 2 , (21) \|w_h-\mathcal{W}_h w_h\|_{H^r(\mathcal{T}_h)}^2\lesssim\sum_{f\in\mathcal{F}_h}h_f^{1-2r}\|[w_h]\|_f^2, \tag*{(21)} ∥ w h − W h w h ∥ H r ( T h ) 2 ≲ f ∈ F h ∑ h f 1 − 2 r ∥ [ w h ] ∥ f 2 , (21)
with a hidden constant depending only on p p p and the shape regularity and quasi-uniformity of T h \mathcal{T}_h T h , and in particular independent of the weights α t \alpha_t α t .
Proof. Set δ h : = w h − W h w h ∈ P p ( T h ) \delta_h:=w_h-\mathcal{W}_h w_h\in\mathbb{P}^p(\mathcal{T}_h) δ h := w h − W h w h ∈ P p ( T h ) and fix t ∈ T h t\in\mathcal{T}_h t ∈ T h and a node ν \nu ν of t t t .
If ν ∉ ∂ Ω \nu\notin\partial\Omega ν ∈ / ∂ Ω , then, since the weights sum to one,
( δ h ∣ t ) ( ν ) = ∑ t ′ ∈ N h ( ν ) α t ′ ( ν ) [ ( w h ∣ t ) ( ν ) − ( w h ∣ t ′ ) ( ν ) ] . (\delta_h|_t)(\nu)=\sum_{t'\in\mathcal{N}_h(\nu)}\alpha_{t'}(\nu)\left[(w_h|_t)(\nu)-(w_h|_{t'})(\nu)\right]. ( δ h ∣ t ) ( ν ) = t ′ ∈ N h ( ν ) ∑ α t ′ ( ν ) [ ( w h ∣ t ) ( ν ) − ( w h ∣ t ′ ) ( ν ) ] .
Because T h \mathcal{T}_h T h is conforming and simplicial and Ω \Omega Ω is Lipschitz, the cells of N h ( ν ) \mathcal{N}_h(\nu) N h ( ν ) tile a neighbourhood of ν \nu ν in Ω ‾ \overline{\Omega} Ω , so any two of them are connected by a chain
t = t 0 , t 1 , … , t M = t ′ , t i ∈ N h ( ν ) , M ≤ ∣ N h ( ν ) ∣ , t=t_0,t_1,\ldots,t_M=t',\qquad t_i\in\mathcal{N}_h(\nu),\qquad M\leq|\mathcal{N}_h(\nu)|, t = t 0 , t 1 , … , t M = t ′ , t i ∈ N h ( ν ) , M ≤ ∣ N h ( ν ) ∣ ,
in which t i − 1 t_{i-1} t i − 1 and t i t_i t i share a face f i ∈ F h ( ν ) f_i\in\mathcal{F}_h(\nu) f i ∈ F h ( ν ) , where F h ( ν ) \mathcal{F}_h(\nu) F h ( ν ) denotes the set of fine faces containing ν \nu ν . Writing n i n_i n i for the unit normal to f i f_i f i pointing outwards from t i − 1 t_{i-1} t i − 1 , the definition of the jump gives ( w h ∣ t i − 1 ) ( ν ) − ( w h ∣ t i ) ( ν ) = [ [ w h ] ] ∣ f i ( ν ) ⋅ n i (w_h|_{t_{i-1}})(\nu)-(w_h|_{t_i})(\nu)=[[w_h]]|_{f_i}(\nu)\cdot n_i ( w h ∣ t i − 1 ) ( ν ) − ( w h ∣ t i ) ( ν ) = [[ w h ]] ∣ f i ( ν ) ⋅ n i , so that each bracket telescopes as
( w h ∣ t ) ( ν ) − ( w h ∣ t ′ ) ( ν ) = ∑ i = 1 M [ [ w h ] ] ∣ f i ( ν ) ⋅ n i . (22) (w_h|_t)(\nu)-(w_h|_{t'})(\nu)=\sum_{i=1}^{M}[[w_h]]|_{f_i}(\nu)\cdot n_i. \tag*{(22)} ( w h ∣ t ) ( ν ) − ( w h ∣ t ′ ) ( ν ) = i = 1 ∑ M [[ w h ]] ∣ f i ( ν ) ⋅ n i . (22)
Since ∣ N h ( ν ) ∣ \lvert\mathcal{N}_h(\nu)\rvert ∣ N h ( ν )∣ is bounded by shape regularity and α t ( ν ) ≤ 1 \alpha_t(\nu)\le1 α t ( ν ) ≤ 1 ,
∣ ( δ h ∣ t ) ( ν ) ∣ ≲ max f ∈ N h ( ν ) ∥ w h ∥ f ∣ f ( ν ) ∣ . (23) \lvert(\delta_h\lvert_t)(\nu)\rvert\lesssim\max_{f\in\mathcal{N}_h(\nu)}\lVert w_h\rVert_f\lvert f(\nu)\rvert. \tag*{(23)} ∣( δ h ∣ t ) ( ν )∣ ≲ f ∈ N h ( ν ) max ∥ w h ∥ f ∣ f ( ν )∣ . (23)
If ν ∈ ∂ Ω \nu\in\partial\Omega ν ∈ ∂ Ω , then ( δ h ∣ t ) ( ν ) = ( w h ∣ t ) ( ν ) (\delta_h\lvert_t)(\nu)=(w_h\lvert_t)(\nu) ( δ h ∣ t ) ( ν ) = ( w h ∣ t ) ( ν ) . Since ∂ Ω \partial\Omega ∂ Ω is a union of fine boundary faces, there is f ∗ ∈ F h b d f^*\in\mathcal{F}_h^{\mathrm{bd}} f ∗ ∈ F h bd with ν ∈ f ∗ \nu\in f^* ν ∈ f ∗ . Let t ∗ ∈ N h ( ν ) t^*\in\mathcal{N}_h(\nu) t ∗ ∈ N h ( ν ) be the cell of f ∗ f^* f ∗ . Chaining t t t to t ∗ t^* t ∗ as above, and using ⟦ w h ⟧ f ∗ = w h ∣ f ∗ ∩ n f ∗ \llbracket w_h\rrbracket_{f^*}=w_h\lvert_{f^*}\cap n_{f^*} [ [ w h ] ] f ∗ = w h ∣ f ∗ ∩ n f ∗ on F h b d \mathcal{F}_h^{\mathrm{bd}} F h bd ,
( w h ∣ t ) ( ν ) = ( w h ∣ t ∗ ) ( ν ) + ∑ i ⟦ w h ⟧ f i ( ν ) ⋅ n i = ⟦ w h ⟧ f ∗ ( ν ) ⋅ n f ∗ + ∑ i ⟦ w h ⟧ f i ( ν ) ⋅ n i , (w_h\lvert_t)(\nu)=(w_h\lvert_{t^*})(\nu)+\sum_i\llbracket w_h\rrbracket_{f_i}(\nu)\cdot n_i=\llbracket w_h\rrbracket_{f^*}(\nu)\cdot n_{f^*}+\sum_i\llbracket w_h\rrbracket_{f_i}(\nu)\cdot n_i, ( w h ∣ t ) ( ν ) = ( w h ∣ t ∗ ) ( ν ) + i ∑ [ [ w h ] ] f i ( ν ) ⋅ n i = [ [ w h ] ] f ∗ ( ν ) ⋅ n f ∗ + i ∑ [ [ w h ] ] f i ( ν ) ⋅ n i ,
so (6.7) holds in this case as well. If ν \nu ν is interior to t t t , then N h ( ν ) = { t } \mathcal{N}_h(\nu)=\{t\} N h ( ν ) = { t } , α t ( ν ) = 1 \alpha_t(\nu)=1 α t ( ν ) = 1 and ( δ h ∣ t ) ( ν ) = 0 (\delta_h\lvert_t)(\nu)=0 ( δ h ∣ t ) ( ν ) = 0 , so such nodes contribute nothing.
Norm equivalence on the finite-dimensional space P p ( t ) \mathbb{P}^p(t) P p ( t ) , together with scaling, gives ∥ δ h ∥ L 2 ( t ) 2 ∼ h t d ∑ ν ∣ ( δ h ∣ t ) ( ν ) ∣ 2 \lVert\delta_h\lVert_{L^2(t)}^2\sim h_t^d\sum_\nu\lvert(\delta_h\lvert_t)(\nu)\rvert^2 ∥ δ h ∥ L 2 ( t ) 2 ∼ h t d ∑ ν ∣( δ h ∣ t ) ( ν ) ∣ 2 , the sum running over the nodes of t t t . The same equivalence on a face, applied to ⟦ w h ⟧ ∣ f ∈ P p ( f ) \llbracket w_h\rrbracket\lvert_f\in\mathbb{P}^p(f) [ [ w h ] ] ∣ f ∈ P p ( f ) , gives ∥ ⟦ w h ⟧ ∥ f 2 ∼ h f d − 1 ∑ ν ∣ ⟦ w h ⟧ f ( ν ) ∣ 2 \lVert\llbracket w_h\rrbracket\lVert_f^2\sim h_f^{d-1}\sum_\nu\lvert\llbracket w_h\rrbracket_f(\nu)\rvert^2 ∥ [ [ w h ] ] ∥ f 2 ∼ h f d − 1 ∑ ν ∣ [ [ w h ] ] f ( ν ) ∣ 2 . Combining these with (6.7), summing over t ∈ T h t\in\mathcal{T}_h t ∈ T h , and using that each face is counted a bounded number of times together with the quasi-uniformity h t ∼ h f ∼ h h_t\sim h_f\sim h h t ∼ h f ∼ h ,
∥ δ h ∥ L 2 ( T h ) 2 ≲ h d ∑ f ∈ F h ∑ ν ∈ f ∣ ⟦ w h ⟧ f ( ν ) ∣ 2 ∼ h d ∑ f ∈ F h h f − ( d − 1 ) ∥ ⟦ w h ⟧ ∥ f 2 ∼ ∑ f ∈ F h h f ∥ ⟦ w h ⟧ ∥ f 2 , \lVert\delta_h\lVert_{L^2(\mathcal{T}_h)}^2\lesssim h^d\sum_{f\in\mathcal{F}_h}\sum_{\nu\in f}\lvert\llbracket w_h\rrbracket_f(\nu)\rvert^2\sim h^d\sum_{f\in\mathcal{F}_h}h_f^{-(d-1)}\lVert\llbracket w_h\rrbracket\lVert_f^2\sim\sum_{f\in\mathcal{F}_h}h_f\lVert\llbracket w_h\rrbracket\lVert_f^2, ∥ δ h ∥ L 2 ( T h ) 2 ≲ h d f ∈ F h ∑ ν ∈ f ∑ ∣ [ [ w h ] ] f ( ν ) ∣ 2 ∼ h d f ∈ F h ∑ h f − ( d − 1 ) ∥ [ [ w h ] ] ∥ f 2 ∼ f ∈ F h ∑ h f ∥ [ [ w h ] ] ∥ f 2 ,
which is (6.6) for r = 0 r=0 r = 0 . The case r = 1 r=1 r = 1 follows from the case r = 0 r=0 r = 0 and the inverse inequality ∥ δ h ∣ 1 , t ∥ ≲ h t − 1 ∥ δ h ∣ L 2 ( t ) \lVert\delta_h\lvert_{1,t}\rVert\lesssim h_t^{-1}\lVert\delta_h\lvert_{L^2(t)} ∥ δ h ∣ 1 , t ∥ ≲ h t − 1 ∥ δ h ∣ L 2 ( t ) on each fine cell, using h t ∼ h f ∼ h h_t\sim h_f\sim h h t ∼ h f ∼ h and h f ≲ diam ( Ω ) h_f\lesssim\operatorname{diam}(\Omega) h f ≲ diam ( Ω ) for the L 2 L^2 L 2 part. □ \square □
Lemma 6.4 (Bounds for W h I h \mathcal{W}_h\mathcal{I}_h W h I h on the coarse broken space). Let k ≥ 1 k\ge1 k ≥ 1 and v H ∈ P k ( T H ) v_H\in\mathbb{P}^k(\mathcal{T}_H) v H ∈ P k ( T H ) . The operator I H h d g = W h I h \mathcal{I}_{Hh}^{\mathrm{dg}}=\mathcal{W}_h\mathcal{I}_h I H h dg = W h I h satisfies, for r = 0 , 1 r=0,1 r = 0 , 1 ,
∥ v H − I H h d g v H ∥ H r ( T H ) 2 ≲ ∑ F ∈ F H h 1 − 2 r ∥ ⟦ v H ⟧ ∥ F 2 + ∑ T ∈ T H ( h H T ) 2 ( p + 1 − r ) H T 2 ( 1 − r ) ∣ v H ∣ 1 , T 2 . \lVert v_H-\mathcal{I}_{Hh}^{\mathrm{dg}}v_H\rVert_{H^r(\mathcal{T}_H)}^2\lesssim\sum_{F\in\mathcal{F}_H}h^{1-2r}\lVert\llbracket v_H\rrbracket\lVert_F^2+\sum_{T\in\mathcal{T}_H}\left(\frac{h}{H_T}\right)^{2(p+1-r)}H_T^{2(1-r)}\lvert v_H\rvert_{1,T}^2. ∥ v H − I H h dg v H ∥ H r ( T H ) 2 ≲ F ∈ F H ∑ h 1 − 2 r ∥ [ [ v H ] ] ∥ F 2 + T ∈ T H ∑ ( H T h ) 2 ( p + 1 − r ) H T 2 ( 1 − r ) ∣ v H ∣ 1 , T 2 . The hidden constant depends only on k k k , p p p , the shape regularity and quasi-uniformity of T h \mathcal{T}_h T h and Assumption 3.1, and is independent of the weights of W h \mathcal{W}_h W h .
Proof. Set w h : = I h v H ∈ P p ( T h ) w_h:=\mathcal{I}_hv_H\in\mathbb{P}^p(\mathcal{T}_h) w h := I h v H ∈ P p ( T h ) , so that I H h d g v H = W h w h \mathcal{I}_{Hh}^{\mathrm{dg}}v_H=\mathcal{W}_hw_h I H h dg v H = W h w h . Since v H − I H h d g v H v_H-\mathcal{I}_{Hh}^{\mathrm{dg}}v_H v H − I H h dg v H belongs to H r ( T ) H^r(T) H r ( T ) on every T ∈ T H T\in\mathcal{T}_H T ∈ T H (both v H ∣ T v_H\lvert_T v H ∣ T and the globally continuous I H h d g v H \mathcal{I}_{Hh}^{\mathrm{dg}}v_H I H h dg v H do), its T H \mathcal{T}_H T H - and T h \mathcal{T}_h T h -broken norms coincide, and we may work with the latter. Since w h w_h w h is a priori only piecewise smooth on T h \mathcal{T}_h T h , the intermediate terms below are T h \mathcal{T}_h T h -broken norms. We can thus split
∥ v H − I H h d g v H ∥ H r ( T H ) 2 = ∥ v H − I H h d g v H ∥ H r ( T h ) 2 ≲ ∥ v H − w h ∥ H r ( T h ) 2 + ∥ w h − W h w h ∥ H r ( T h ) 2 = : J 1 + J 2 . \lVert v_H-\mathcal{I}_{Hh}^{\mathrm{dg}}v_H\rVert_{H^r(\mathcal{T}_H)}^2=\lVert v_H-\mathcal{I}_{Hh}^{\mathrm{dg}}v_H\rVert_{H^r(\mathcal{T}_h)}^2\lesssim\lVert v_H-w_h\rVert_{H^r(\mathcal{T}_h)}^2+\lVert w_h-\mathcal{W}_hw_h\rVert_{H^r(\mathcal{T}_h)}^2=:\mathcal{J}_1+\mathcal{J}_2. ∥ v H − I H h dg v H ∥ H r ( T H ) 2 = ∥ v H − I H h dg v H ∥ H r ( T h ) 2 ≲ ∥ v H − w h ∥ H r ( T h ) 2 + ∥ w h − W h w h ∥ H r ( T h ) 2 =: J 1 + J 2 .
For J 1 \mathcal{J}_1 J 1 , standard interpolation estimates on each fine cell t ⊂ T t\subset T t ⊂ T give
J 1 = ∑ T ∈ T H ∑ t ⊂ T ∥ v H − I h v H ∥ H r ( t ) 2 ≲ ∑ T ∈ T H h 2 ( p + 1 − r ) ∣ v H ∣ H p + 1 ( T ) 2 ≲ ∑ T ∈ T H ( h H T ) 2 ( p + 1 − r ) H T 2 ( 1 − r ) ∣ v H ∣ 1 , T 2 , \mathcal{J}_1=\sum_{T\in\mathcal{T}_H}\sum_{t\subset T}\lVert v_H-\mathcal{I}_hv_H\rVert_{H^r(t)}^2\lesssim\sum_{T\in\mathcal{T}_H}h^{2(p+1-r)}\lvert v_H\rvert_{H^{p+1}(T)}^2\lesssim\sum_{T\in\mathcal{T}_H}\left(\frac{h}{H_T}\right)^{2(p+1-r)}H_T^{2(1-r)}\lvert v_H\rvert_{1,T}^2, J 1 = T ∈ T H ∑ t ⊂ T ∑ ∥ v H − I h v H ∥ H r ( t ) 2 ≲ T ∈ T H ∑ h 2 ( p + 1 − r ) ∣ v H ∣ H p + 1 ( T ) 2 ≲ T ∈ T H ∑ ( H T h ) 2 ( p + 1 − r ) H T 2 ( 1 − r ) ∣ v H ∣ 1 , T 2 ,
where the last step uses the inverse inequality ∣ v H ∣ H p + 1 ( T ) ≲ H T − p ∣ v H ∣ 1 , T \lvert v_H\rvert_{H^{p+1}(T)}\lesssim H_T^{-p}\lvert v_H\rvert_{1,T} ∣ v H ∣ H p + 1 ( T ) ≲ H T − p ∣ v H ∣ 1 , T , valid for polynomials of fixed degree k k k on elements satisfying Assumption 3.1 [14 ] . If k ≤ p k\le p k ≤ p , then I h v H = v H \mathcal{I}_hv_H=v_H I h v H = v H and J 1 = 0 \mathcal{J}_1=0 J 1 = 0 .
We now bound J 2 \mathcal{J}_2 J 2 . Lemma 6.3 gives
J 2 ≲ ∑ f ∈ F h h f 1 − 2 r ∥ ⟦ w h ⟧ ∥ f 2 . \mathcal{J}_2\lesssim\sum_{f\in\mathcal{F}_h}h_f^{1-2r}\lVert\llbracket w_h\rrbracket\lVert_f^2. J 2 ≲ f ∈ F h ∑ h f 1 − 2 r ∥ [ [ w h ] ] ∥ f 2 .
For simplicial Lagrange elements, the trace of ( I h w ) ∣ t (\mathcal{I}_hw)\lvert_t ( I h w ) ∣ t on a face f ∈ F h ( t ) f\in\mathcal{F}_h(t) f ∈ F h ( t ) is determined by the values of w ∣ t w\lvert_t w ∣ t at the Lagrangian nodes lying on f f f . As a consequence, for a fine face f f f shared by two cells t 1 , t 2 t_1,t_2 t 1 , t 2 contained in the same agglomerate T T T , the traces of w h w_h w h from both sides interpolate the same polynomial v H ∣ T v_H\lvert_T v H ∣ T at the same nodes, and thus ⟦ w h ⟧ ∣ f = 0 \llbracket w_h\rrbracket\lvert_f=0 [ [ w h ] ] ∣ f = 0 . For a fine face f ⊂ F ∈ F H f\subset F\in\mathcal{F}_H f ⊂ F ∈ F H , the same argument shows that ⟦ w h ⟧ ∣ f = I h f ( [ [ v H ] ] ∣ f ) \llbracket w_h\rrbracket\lvert_f=\mathcal{I}_h^f([\![v_H]\!]\lvert_f) [ [ w h ] ] ∣ f = I h f ([ [ v H ] ] ∣ f ) , where I h f \mathcal{I}_h^f I h f denotes the Lagrange interpolant of degree p p p on f f f . By the L 2 ( f ) L^2(f) L 2 ( f ) -stability of I h f \mathcal{I}_h^f I h f on the finite-dimensional space P k ( f ) \mathbb{P}^k(f) P k ( f ) , we conclude that ∥ ⟦ w h ⟧ ∥ f ≲ ∥ ⟦ v H ⟧ ∥ f \lVert\llbracket w_h\rrbracket\lVert_f\lesssim\lVert\llbracket v_H\rrbracket\lVert_f ∥ [ [ w h ] ] ∥ f ≲ ∥ [ [ v H ] ] ∥ f , and thus
J 2 ≲ ∑ F ∈ F H ∑ f ⊂ F h f 1 − 2 r ∥ ⟦ v H ⟧ ∥ f 2 ≲ ∑ F ∈ F H h 1 − 2 r ∥ ⟦ v H ⟧ ∥ F 2 , (24) \mathcal{J}_2\lesssim\sum_{F\in\mathcal{F}_H}\sum_{f\subset F}h_f^{1-2r}\lVert\llbracket v_H\rrbracket\lVert_f^2\lesssim\sum_{F\in\mathcal{F}_H}h^{1-2r}\lVert\llbracket v_H\rrbracket\lVert_F^2, \tag*{(24)} J 2 ≲ F ∈ F H ∑ f ⊂ F ∑ h f 1 − 2 r ∥ [ [ v H ] ] ∥ f 2 ≲ F ∈ F H ∑ h 1 − 2 r ∥ [ [ v H ] ] ∥ F 2 , (24)
where the last step uses that the fine faces f ∈ F f \in F f ∈ F tile F F F and that h f ≃ h h_f \simeq h h f ≃ h for every f ∈ F h f \in\mathcal{F}_h f ∈ F h , by the quasi-uniformity of T h \mathcal{T}_h T h assumed in Sect. 2, with a constant independent of h h h and H H H . Combining the bounds for I 1 \mathcal{I}_1 I 1 and I 2 \mathcal{I}_2 I 2 concludes the proof. □
Lemma 6.5. For any k ≥ 1 k \ge1 k ≥ 1 and v H ∈ P k ( T H ) v_H \in\mathbb{P}^k(\mathcal{T}_H) v H ∈ P k ( T H ) , the operator I H h d g = W h I h I^{\mathrm{dg}}_{Hh} = W_h I_h I H h dg = W h I h satisfies
∥ I H h d g v H ∥ H 1 ( Ω ) 2 ≲ ( 1 + H σ h ) ∥ v H ∥ d g , H 2 . \left\|I^{\mathrm{dg}}_{Hh}v_H\right\|_{H^1(\Omega)}^2 \lesssim\left(1+\frac{H}{\sigma h}\right)\|v_H\|_{\mathrm{dg},H}^2. I H h dg v H H 1 ( Ω ) 2 ≲ ( 1 + σ h H ) ∥ v H ∥ dg , H 2 . In particular, since σ ≥ σ 0 ≥ 1 \sigma\ge\sigma_0 \ge1 σ ≥ σ 0 ≥ 1 and h ≤ H h \le H h ≤ H , the coarser bound ∥ I H h d g v H ∥ H 1 ( Ω ) 2 ≲ H h ∥ v H ∥ d g , H 2 \left\|I^{\mathrm{dg}}_{Hh}v_H\right\|_{H^1(\Omega)}^2 \lesssim\frac{H}{h}\|v_H\|_{\mathrm{dg},H}^2 I H h dg v H H 1 ( Ω ) 2 ≲ h H ∥ v H ∥ dg , H 2 also holds.
Proof. Since I H h d g v H ∈ H 0 1 ( Ω ) I^{\mathrm{dg}}_{Hh}v_H \in H^1_0(\Omega) I H h dg v H ∈ H 0 1 ( Ω ) , a Poincaré inequality gives ∥ I H h d g v H ∥ H 1 ( Ω ) ≲ ∣ I H h d g v H ∣ 1 , Ω \left\|I^{\mathrm{dg}}_{Hh}v_H\right\|_{H^1(\Omega)} \lesssim\left|I^{\mathrm{dg}}_{Hh}v_H\right|_{1,\Omega} I H h dg v H H 1 ( Ω ) ≲ I H h dg v H 1 , Ω . By the triangle inequality,
∣ I H h d g v H ∣ 1 , Ω ≤ ∣ v H − I H h d g v H ∣ 1 , T H + ∣ v H ∣ 1 , T H . \left|I^{\mathrm{dg}}_{Hh}v_H\right|_{1,\Omega} \le\left|v_H-I^{\mathrm{dg}}_{Hh}v_H\right|_{1,\mathcal{T}_H}+\left|v_H\right|_{1,\mathcal{T}_H}. I H h dg v H 1 , Ω ≤ v H − I H h dg v H 1 , T H + ∣ v H ∣ 1 , T H .
By Lemma 6.4 with r = 1 r=1 r = 1 and h ≤ H T h \le H_T h ≤ H T ,
∣ v H − I H h d g v H ∣ 1 , T H 2 ≲ ∑ F ∈ F H h − 1 ∥ ⟦ v H ⟧ ∥ F 2 + ∣ v H ∣ 1 , T H 2 . \left|v_H-I^{\mathrm{dg}}_{Hh}v_H\right|_{1,\mathcal{T}_H}^2 \lesssim\sum_{F\in\mathcal{F}_H}h^{-1}\left\|\llbracket v_H\rrbracket\right\|_F^2+\left|v_H\right|_{1,\mathcal{T}_H}^2. v H − I H h dg v H 1 , T H 2 ≲ F ∈ F H ∑ h − 1 ∥ [ [ v H ] ] ∥ F 2 + ∣ v H ∣ 1 , T H 2 .
Using the fact that H F ≃ H H_F \simeq H H F ≃ H , the jump term can be bounded as
∑ F ∈ F H h − 1 ∥ ⟦ v H ⟧ ∥ F 2 ≲ σ − 1 H h ∑ F ∈ F H σ H F ∥ ⟦ v H ⟧ ∥ F 2 ≤ σ − 1 H h ∥ v H ∥ d g , H 2 . \sum_{F\in\mathcal{F}_H}h^{-1}\left\|\llbracket v_H\rrbracket\right\|_F^2 \lesssim\sigma^{-1}\frac{H}{h}\sum_{F\in\mathcal{F}_H}\frac{\sigma}{H_F}\left\|\llbracket v_H\rrbracket\right\|_F^2 \le\sigma^{-1}\frac{H}{h}\|v_H\|_{\mathrm{dg},H}^2. F ∈ F H ∑ h − 1 ∥ [ [ v H ] ] ∥ F 2 ≲ σ − 1 h H F ∈ F H ∑ H F σ ∥ [ [ v H ] ] ∥ F 2 ≤ σ − 1 h H ∥ v H ∥ dg , H 2 .
Since ∣ v H ∣ 1 , T H 2 ≤ ∥ v H ∥ d g , H 2 \left|v_H\right|_{1,\mathcal{T}_H}^2 \le\|v_H\|_{\mathrm{dg},H}^2 ∣ v H ∣ 1 , T H 2 ≤ ∥ v H ∥ dg , H 2 , combining the two bounds concludes the proof. □
Lemma 6.6. Assume that, given v h ∈ V h v_h \in V_h v h ∈ V h , there exists v H ∈ P k ( T H ) v_H \in\mathbb{P}^k(\mathcal{T}_H) v H ∈ P k ( T H ) , k ≥ 1 k \ge1 k ≥ 1 , such that for r = 0 , 1 r=0,1 r = 0 , 1 it holds that
∥ v h − v H ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω . (25) \|v_h-v_H\|_{H^r(\mathcal{T}_H)} \lesssim H^{1-r}|v_h|_{1,\Omega}. \tag*{(25)} ∥ v h − v H ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω . (25) Then the operator I H h d g = W h I h I^{\mathrm{dg}}_{Hh}=W_hI_h I H h dg = W h I h satisfies
∥ v h − I H h d g v H ∥ L 2 ( Ω ) 2 ≲ H 2 ∣ v h ∣ 1 , Ω 2 and ∥ v h − I H h d g v H ∥ H 1 ( Ω ) 2 ≲ H h ∣ v h ∣ 1 , Ω 2 , (26) \|v_h-I^{\mathrm{dg}}_{Hh}v_H\|_{L^2(\Omega)}^2 \lesssim H^2|v_h|_{1,\Omega}^2
\quad\text{and}\quad
\|v_h-I^{\mathrm{dg}}_{Hh}v_H\|_{H^1(\Omega)}^2 \lesssim\frac{H}{h}|v_h|_{1,\Omega}^2, \tag*{(26)} ∥ v h − I H h dg v H ∥ L 2 ( Ω ) 2 ≲ H 2 ∣ v h ∣ 1 , Ω 2 and ∥ v h − I H h dg v H ∥ H 1 ( Ω ) 2 ≲ h H ∣ v h ∣ 1 , Ω 2 , (26) and, if v H ∈ V H v_H \in V_H v H ∈ V H ,
∥ v H ∥ d g , H ≲ ( 1 + σ ) 1 / 2 ∣ v h ∣ 1 , Ω . (27) \|v_H\|_{\mathrm{dg},H} \lesssim(1+\sigma)^{1/2}|v_h|_{1,\Omega}. \tag*{(27)} ∥ v H ∥ dg , H ≲ ( 1 + σ ) 1/2 ∣ v h ∣ 1 , Ω . (27)
Proof. We first show the auxiliary bounds
∣ v H ∣ 1 , T H 2 ≲ ∣ v h ∣ 1 , Ω 2 and ∑ F ∈ F H H F − 1 ∥ ⟦ v H ⟧ ∥ F 2 ≲ ∣ v h ∣ 1 , Ω 2 . (28) |v_H|_{1,\mathcal{T}_H}^2 \lesssim|v_h|_{1,\Omega}^2
\quad\text{and}\quad
\sum_{F\in\mathcal{F}_H}H_F^{-1}\left\|\llbracket v_H\rrbracket\right\|_F^2 \lesssim|v_h|_{1,\Omega}^2. \tag*{(28)} ∣ v H ∣ 1 , T H 2 ≲ ∣ v h ∣ 1 , Ω 2 and F ∈ F H ∑ H F − 1 ∥ [ [ v H ] ] ∥ F 2 ≲ ∣ v h ∣ 1 , Ω 2 . (28)
Using the triangle inequality, together with (6.8), we can bound
∣ v H ∣ 1 , T H 2 ≲ ∣ v h ∣ 1 , T H 2 + ∣ v h − v H ∣ 1 , T H 2 ≲ ∣ v h ∣ 1 , Ω 2 . |v_H|_{1,\mathcal{T}_H}^2 \lesssim|v_h|_{1,\mathcal{T}_H}^2+|v_h-v_H|_{1,\mathcal{T}_H}^2 \lesssim|v_h|_{1,\Omega}^2. ∣ v H ∣ 1 , T H 2 ≲ ∣ v h ∣ 1 , T H 2 + ∣ v h − v H ∣ 1 , T H 2 ≲ ∣ v h ∣ 1 , Ω 2 .
For the jump term, we can use the fact that v h v_h v h is continuous across interior F H \mathcal{F}_H F H faces and vanishes on the boundary ones to write
∑ F ∈ F H H F − 1 ∥ ⟦ v H ⟧ ∥ F 2 = ∑ F ∈ F H H F − 1 ∥ ⟦ v h − v H ⟧ ∥ F 2 . \sum_{F\in\mathcal{F}_H}H_F^{-1}\left\|\llbracket v_H\rrbracket\right\|_F^2
=
\sum_{F\in\mathcal{F}_H}H_F^{-1}\left\|\llbracket v_h-v_H\rrbracket\right\|_F^2. F ∈ F H ∑ H F − 1 ∥ [ [ v H ] ] ∥ F 2 = F ∈ F H ∑ H F − 1 ∥ [ [ v h − v H ] ] ∥ F 2 .
Then noting that H F ≃ H H_F\simeq H H F ≃ H , rearranging the face terms into element terms and using the scaled trace inequality (4.1) on each subdomain T T T , we have
∑ F ∈ F H H F − 1 ∥ ⟦ v H ⟧ ∥ F 2 ≲ ∑ T ∈ T H H − 1 ∥ v h − v H ∥ ∂ T 2 ≲ ∑ T ∈ T H H − 1 ( H T − 1 ∥ v h − v H ∥ L 2 ( T ) 2 + H T ∥ v h − v H ∥ H 1 ( T ) 2 ) . \sum_{F\in\mathcal{F}_H}H_F^{-1}\left\|\llbracket v_H\rrbracket\right\|_F^2
\lesssim
\sum_{T\in\mathcal{T}_H}H^{-1}\left\|v_h-v_H\right\|_{\partial T}^2
\lesssim
\sum_{T\in\mathcal{T}_H}H^{-1}\left(H_T^{-1}\left\|v_h-v_H\right\|_{L^2(T)}^2+H_T\left\|v_h-v_H\right\|_{H^1(T)}^2\right). F ∈ F H ∑ H F − 1 ∥ [ [ v H ] ] ∥ F 2 ≲ T ∈ T H ∑ H − 1 ∥ v h − v H ∥ ∂ T 2 ≲ T ∈ T H ∑ H − 1 ( H T − 1 ∥ v h − v H ∥ L 2 ( T ) 2 + H T ∥ v h − v H ∥ H 1 ( T ) 2 ) .
Using the fact that H T ≃ H H_T\simeq H H T ≃ H for all T ∈ T H T\in\mathcal{T}_H T ∈ T H , summing over T ∈ T H T\in\mathcal{T}_H T ∈ T H and using (6.8), we obtain
∑ F ∈ F H H F − 1 ∥ ⟦ v H ⟧ ∥ F 2 ≲ H − 1 ( H − 1 ∥ v h − v H ∥ L 2 ( Ω ) 2 + H ∥ v h − v H ∥ H 1 ( T H ) 2 ) ≲ ∣ v h ∣ 1 , Ω 2 , \sum_{F\in\mathcal{F}_H}H_F^{-1}\left\|\llbracket v_H\rrbracket\right\|_F^2
\lesssim H^{-1}\left(H^{-1}\left\|v_h-v_H\right\|_{L^2(\Omega)}^2+H\left\|v_h-v_H\right\|_{H^1(\mathcal{T}_H)}^2\right)
\lesssim|v_h|_{1,\Omega}^2, F ∈ F H ∑ H F − 1 ∥ [ [ v H ] ] ∥ F 2 ≲ H − 1 ( H − 1 ∥ v h − v H ∥ L 2 ( Ω ) 2 + H ∥ v h − v H ∥ H 1 ( T H ) 2 ) ≲ ∣ v h ∣ 1 , Ω 2 ,
which proves (6.11).
We now prove (6.9). For r = 0 , 1 r=0,1 r = 0 , 1 , a triangle inequality gives
∥ v h − I H h d g v H ∥ H r ( Ω ) 2 ≲ ∥ v h − v H ∥ H r ( T H ) 2 + ∥ v H − I H h d g v H ∥ H r ( T H ) 2 = : T 1 + T 2 . \left\|v_h-I^{\mathrm{dg}}_{Hh}v_H\right\|_{H^r(\Omega)}^2
\lesssim\left\|v_h-v_H\right\|_{H^r(\mathcal{T}_H)}^2+\left\|v_H-I^{\mathrm{dg}}_{Hh}v_H\right\|_{H^r(\mathcal{T}_H)}^2 =: \mathcal{T}_1+\mathcal{T}_2. v h − I H h dg v H H r ( Ω ) 2 ≲ ∥ v h − v H ∥ H r ( T H ) 2 + v H − I H h dg v H H r ( T H ) 2 =: T 1 + T 2 .
By (6.8), T 1 ≲ H 2 ( 1 − r ) ∣ v h ∣ 1 , Ω 2 \mathcal{T}_1 \lesssim H^{2(1-r)}|v_h|_{1,\Omega}^2 T 1 ≲ H 2 ( 1 − r ) ∣ v h ∣ 1 , Ω 2 . For T 2 \mathcal{T}_2 T 2 , we can use Lemma 6.4 and h ≤ H T h \le H_T h ≤ H T , together with H F ≃ H H_F \simeq H H F ≃ H and (6.11), to write
T 2 ≲ ∑ F ∈ F H h 1 − 2 r ∥ [ [ v H ] ] ∥ F 2 + H 2 ( 1 − r ) ∣ v H ∣ 1 , T H 2 ≲ H h 1 − 2 r ∑ F ∈ F H H F − 1 ∥ [ [ v H ] ] ∥ F 2 + H 2 ( 1 − r ) ∣ v h ∣ 1 , Ω 2 \mathcal{T}_2 \lesssim\sum_{F\in\mathcal{F}_H} h^{1-2r}\left\lVert[\![v_H]\!] \right\rVert_F^2 + H^{2(1-r)}|v_H|_{1,\mathcal{T}_H}^2 \lesssim Hh^{1-2r}\sum_{F\in\mathcal{F}_H} H_F^{-1}\left\lVert[\![v_H]\!] \right\rVert_F^2 + H^{2(1-r)}|v_h|_{1,\Omega}^2 T 2 ≲ F ∈ F H ∑ h 1 − 2 r ∥ [ [ v H ] ] ∥ F 2 + H 2 ( 1 − r ) ∣ v H ∣ 1 , T H 2 ≲ H h 1 − 2 r F ∈ F H ∑ H F − 1 ∥ [ [ v H ] ] ∥ F 2 + H 2 ( 1 − r ) ∣ v h ∣ 1 , Ω 2
≲ ( H h 1 − 2 r + H 2 ( 1 − r ) ) ∣ v h ∣ 1 , Ω 2 . \lesssim\left(Hh^{1-2r}+H^{2(1-r)}\right)|v_h|_{1,\Omega}^2. ≲ ( H h 1 − 2 r + H 2 ( 1 − r ) ) ∣ v h ∣ 1 , Ω 2 .
Since h ≤ H h \le H h ≤ H , the factor in brackets is bounded by H 2 H^2 H 2 for r = 0 r=0 r = 0 and by H / h H/h H / h for r = 1 r=1 r = 1 , which gives (6.9).
Finally, if v H ∈ V H v_H\in V_H v H ∈ V H , the definition (6.2) of the DG norm and (6.11) give
∥ v H ∥ d g , H 2 = ∣ v H ∣ 1 , T H 2 + σ ∑ F ∈ F H H F − 1 ∥ [ [ v H ] ] ∥ F 2 ≲ ( 1 + σ ) ∣ v h ∣ 1 , Ω 2 , \left\lVert v_H\right\rVert_{\mathrm{dg},H}^2=|v_H|_{1,\mathcal{T}_H}^2+\sigma\sum_{F\in\mathcal{F}_H}H_F^{-1}\left\lVert[\![v_H]\!] \right\rVert_F^2\lesssim(1+\sigma)|v_h|_{1,\Omega}^2, ∥ v H ∥ dg , H 2 = ∣ v H ∣ 1 , T H 2 + σ F ∈ F H ∑ H F − 1 ∥ [ [ v H ] ] ∥ F 2 ≲ ( 1 + σ ) ∣ v h ∣ 1 , Ω 2 ,
which is (6.10).
Main result
Theorem 6.7. The DG discretisation, with the smoother described in Section 5 and the prolongation I H h = I H h d g I_{Hh}=I_{Hh}^{\mathrm{dg}} I H h = I H h dg of (6.4), fulfils the assumptions in Lemma 3.9. More precisely, the prolongation stability holds with c I 2 ≲ max ( 1 , H / ( σ h ) ) c_I^2\lesssim\max(1,H/(\sigma h)) c I 2 ≲ max ( 1 , H / ( σ h )) and the first bound of the stable decomposition with c 0 , H 2 ≲ 1 + σ c_{0,H}^2\lesssim1+\sigma c 0 , H 2 ≲ 1 + σ . All remaining hidden constants are independent of σ \sigma σ .
Proof. That the smoother satisfies (3) is given by Corollary 5.3 or 5.4, depending on the smoother at hand.
Let v H ∈ V H v_H\in V_H v H ∈ V H . Using Lemma 6.1 together with Lemma 6.5, we obtain
∥ I H h d g v H ∥ a 2 = ∣ I H h d g v H ∣ 1 , Ω 2 ≲ ( 1 + H σ h ) ∥ v H ∥ d g , H 2 ≲ ( 1 + H σ h ) ∥ v H ∥ a H 2 ≲ H h ∥ v H ∥ a H 2 \left\lVert I_{Hh}^{\mathrm{dg}}v_H\right\rVert_a^2=|I_{Hh}^{\mathrm{dg}}v_H|_{1,\Omega}^2\lesssim\left(1+\frac{H}{\sigma h}\right)\left\lVert v_H\right\rVert_{\mathrm{dg},H}^2\lesssim\left(1+\frac{H}{\sigma h}\right)\left\lVert v_H\right\rVert_{a_H}^2\lesssim\frac{H}{h}\left\lVert v_H\right\rVert_{a_H}^2 I H h dg v H a 2 = ∣ I H h dg v H ∣ 1 , Ω 2 ≲ ( 1 + σ h H ) ∥ v H ∥ dg , H 2 ≲ ( 1 + σ h H ) ∥ v H ∥ a H 2 ≲ h H ∥ v H ∥ a H 2
which proves (4) .
We now turn to (5) . Given v h ∈ V h v_h\in V_h v h ∈ V h , we choose as coarse approximant v H : = π T H q v h ∈ V H v_H:=\pi_{T_H}^qv_h\in V_H v H := π T H q v h ∈ V H . From standard approximation properties of π T H q \pi_{T_H}^q π T H q (4.3), applied with s = 1 s=1 s = 1 and m = 0 , 1 m=0,1 m = 0 , 1 , we have that for r = 0 , 1 r=0,1 r = 0 , 1
∥ v h − v H ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω , \left\lVert v_h-v_H\right\rVert_{H^r(\mathcal{T}_H)}\lesssim H^{1-r}|v_h|_{1,\Omega}, ∥ v h − v H ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω ,
and thus our coarse approximant v H v_H v H fulfils the assumption (6.8) of Lemma 6.6.
Using (6.9), together with ∣ v h ∣ 1 , Ω = ∥ v h ∥ a |v_h|_{1,\Omega}=\left\lVert v_h\right\rVert_a ∣ v h ∣ 1 , Ω = ∥ v h ∥ a , we obtain
∥ v h − I H h d g v H ∥ L 2 ( Ω ) 2 ≲ H 2 ∥ v h ∥ a 2 and ∥ v h − I H h d g v H ∥ H 1 ( Ω ) 2 ≲ H h ∥ v h ∥ a 2 \left\lVert v_h-I_{Hh}^{\mathrm{dg}}v_H\right\rVert_{L^2(\Omega)}^2\lesssim H^2\left\lVert v_h\right\rVert_a^2
\qquad\text{and}\qquad
\left\lVert v_h-I_{Hh}^{\mathrm{dg}}v_H\right\rVert_{H^1(\Omega)}^2\lesssim\frac{H}{h}\left\lVert v_h\right\rVert_a^2 v h − I H h dg v H L 2 ( Ω ) 2 ≲ H 2 ∥ v h ∥ a 2 and v h − I H h dg v H H 1 ( Ω ) 2 ≲ h H ∥ v h ∥ a 2
Similarly, using (6.10) together with Lemma 6.1, we can write
∥ v H ∥ a H ≲ ∥ v H ∥ d g , H ≲ ( 1 + σ ) 1 / 2 ∣ v h ∣ 1 , Ω = ( 1 + σ ) 1 / 2 ∥ v h ∥ a \left\lVert v_H\right\rVert_{a_H}\lesssim\left\lVert v_H\right\rVert_{\mathrm{dg},H}\lesssim(1+\sigma)^{1/2}|v_h|_{1,\Omega}=(1+\sigma)^{1/2}\left\lVert v_h\right\rVert_a ∥ v H ∥ a H ≲ ∥ v H ∥ dg , H ≲ ( 1 + σ ) 1/2 ∣ v h ∣ 1 , Ω = ( 1 + σ ) 1/2 ∥ v h ∥ a
which proves (3.4)2 , 3 _{2,3} 2 , 3 and (3.4)1 _1 1 , respectively. □
Remark 6.8. Theorem 6.7 supplies c I 2 ≲ max ( 1 , H / ( σ h ) ) c_I^2\lesssim\max(1,H/(\sigma h)) c I 2 ≲ max ( 1 , H / ( σ h )) , c 0 , H 2 ≲ 1 + σ c_{0,H}^2\lesssim1+\sigma c 0 , H 2 ≲ 1 + σ and c 0 , D 2 ≲ c D , 1 H h + c D , 0 H 2 c_{0,D}^2\lesssim c_{D,1}\frac{H}{h}+c_{D,0}H^2 c 0 , D 2 ≲ c D , 1 h H + c D , 0 H 2 , and inserting these into Lemma 3.8 gives the final bound
κ ( P a d d , D G − 1 A h ) ≲ ( c D 2 + λ 1 max ( 1 , H σ h ) ) ( H 2 h 2 + 1 + σ λ 0 ) . \kappa(P_{\mathrm{add,DG}}^{-1}A_h)\lesssim\left(c_D^2+\lambda_1\max\left(1,\frac{H}{\sigma h}\right)\right)\left(\frac{H^2}{h^2}+\frac{1+\sigma}{\lambda_0}\right). κ ( P add , DG − 1 A h ) ≲ ( c D 2 + λ 1 max ( 1 , σ h H ) ) ( h 2 H 2 + λ 0 1 + σ ) . where we have used that Corollaries 5.3 and 5.4 give c D , 0 ≃ h − 2 c_{D,0}\simeq h^{-2} c D , 0 ≃ h − 2 and c D , 1 = 0 c_{D,1}=0 c D , 1 = 0 for both smoothers considered, and that c D 2 ≃ 1 c_D^2\simeq1 c D 2 ≃ 1 . The coarse solvers of Sect. 8 contribute the factors λ 0 \lambda_0 λ 0 and λ 1 \lambda_1 λ 1 . For an exact coarse solve, λ 0 = λ 1 = 1 \lambda_0=\lambda_1=1 λ 0 = λ 1 = 1 , and two regimes of the penalty are of interest. For fixed σ = O ( 1 ) \sigma=O(1) σ = O ( 1 ) the bound is O ( H 3 / h 3 ) O(H^3/h^3) O ( H 3 / h 3 ) , in agreement with similar bounds found for traditional FE methods. Choosing instead the penalty proportional to the coarsening ratio, σ ≃ H / h \sigma\simeq H/h σ ≃ H / h , makes the first factor O ( 1 ) O(1) O ( 1 ) while the second remains O ( H 2 / h 2 ) O(H^2/h^2) O ( H 2 / h 2 ) , so that
κ ( P a d d , D G − 1 A h ) ≲ H 2 h 2 , \kappa(P_{\mathrm{add,DG}}^{-1}A_h)\lesssim\frac{H^2}{h^2}, κ ( P add , DG − 1 A h ) ≲ h 2 H 2 , one power of H / h H/h H / h better. Sect. 8 shows how this bound composes when the coarse polytopal problem is itself solved approximately. See [15 ] or the introduction to [21 ] for a discussion on the dependence of non-overlapping additive Schwarz subdomain sizes on the final bounds.
HHO auxiliary space preconditioner
We now instantiate the abstract framework of Sect. 3 with a coarse space built from a Hybrid High-Order (HHO) discretisation on T H T_H T H . Specifically, the coarse auxiliary space will be the skeleton space obtained after elimination of the cell unknowns via static condensation. The HHO bilinear form on the skeleton controls the broken H 1 H^1 H 1 seminorm and the interface jumps of the associated potential reconstruction, which reduces the analysis to the tools of Sect. 6.
HHO discretisation on the coarse mesh
We introduce an HHO discretisation on the coarse mesh T H T_H T H , using a mixed-order approach that employs polynomials of degree q + 1 q+1 q + 1 for the cell unknowns and polynomials of degree q q q for the face unknowns. This choice admits a simpler stabilisation term than the original HHO method [32 ] , not involving the potential reconstruction, while still providing optimal approximation properties. After static condensation, the size of the global skeleton system is the same as for the equal-order method.
Face polynomial spaces. Given a face F ∈ F H F \in\mathcal{F}_H F ∈ F H , we denote our skeleton space on F F F by P q ( F ) \mathbb{P}^q(F) P q ( F ) . Recall that F F F may be non-planar, but rather a collection of planar faces from F h \mathcal{F}_h F h . The original HHO method [32 ] uses the Cartesian product of polynomial spaces on each planar face f ∈ F h f \in\mathcal{F}_h f ∈ F h to define the face unknowns, that is P q ( F ) = ∏ f ∈ F h ( F ) P q ( f ) \mathbb{P}^q(F) = \prod_{f \in\mathcal{F}_h(F)} \mathbb{P}^q(f) P q ( F ) = ∏ f ∈ F h ( F ) P q ( f ) , where, extending the notation of Sect. 2, F h ( F ) ≔ { f ∈ F h : f ⊂ F } \mathcal{F}_h(F) \coloneqq\{f \in\mathcal{F}_h : f \subset F\} F h ( F ) : = { f ∈ F h : f ⊂ F } denotes the set of fine faces composing F F F . However, this choice leads to a large number of degrees of freedom on non-planar faces. Instead, we consider the face polynomial space introduced in [38 ] :
P q ( F ) ≔ P 0 ( Ω ) ∣ F + ∇ P q + 1 ( Ω ) ∣ F ⋅ n F , (29) \mathbb{P}^q(F) \coloneqq\mathbb{P}^0(\Omega)|_F + \nabla\mathbb{P}^{q+1}(\Omega)|_F \cdot\boldsymbol{n}_F, \tag*{(29)} P q ( F ) : = P 0 ( Ω ) ∣ F + ∇ P q + 1 ( Ω ) ∣ F ⋅ n F , (29)
where n F \boldsymbol{n}_F n F is a (piecewise-constant) unit normal to F F F , either of the two on an interior face, the space being unchanged by the choice. For planar faces P q ( F ) \mathbb{P}^q(F) P q ( F ) reduces to the standard choice P q ( F ) \mathbb{P}^q(F) P q ( F ) , but for non-planar agglomerated interfaces this choice provides optimal approximation properties with fewer degrees of freedom. These spaces have been shown to be effective in the context of agglomeration-based methods in [5 ] . We denote by P q ( F H ) = { ( λ F ) F : λ F ∈ P q ( F ) , F ∈ F H } \mathbb{P}^q(\mathcal{F}_H) = \{(\lambda_F)_F : \lambda_F \in\mathbb{P}^q(F),\ F \in\mathcal{F}_H\} P q ( F H ) = {( λ F ) F : λ F ∈ P q ( F ) , F ∈ F H } its corresponding broken skeleton space. We define π F q \pi_F^q π F q as the L 2 L^2 L 2 -orthogonal projector onto P q ( F ) \mathbb{P}^q(F) P q ( F ) , and π ∂ T q \pi_{\partial T}^q π ∂ T q as the broken projector acting face-wise on ∂ T \partial T ∂ T , that is π ∂ T q v ∣ F = π F q ( v ∣ F ) \pi_{\partial T}^q v|_F = \pi_F^q(v|_F) π ∂ T q v ∣ F = π F q ( v ∣ F ) for all F ∈ F H ( T ) F \in\mathcal{F}_H(T) F ∈ F H ( T ) . Similarly, we define π F H q \pi_{\mathcal{F}_H}^q π F H q as the broken projector acting face-wise on F H \mathcal{F}_H F H . Throughout this section, projectors carrying a face subscript (F F F , ∂ T \partial T ∂ T or F H \mathcal{F}_H F H ) always denote the L 2 L^2 L 2 -orthogonal projections onto the interface spaces P q ( ⋅ ) \mathbb{P}^q(\cdot) P q ( ⋅ ) just defined, while projectors carrying a cell or fine-mesh subscript denote the projections onto full polynomial spaces of Section 4. Both conventions coexist in the formulas below. Hybrid formulation. The local HHO space of degree q q q on T T T is
V H ( T ) ≔ P q + 1 ( T ) × M ∂ T , M ∂ T ≔ ∏ F ∈ F H ( T ) P q ( F ) , V_H(T) \coloneqq\mathbb{P}^{q+1}(T) \times M_{\partial T}, \qquad M_{\partial T} \coloneqq\prod_{F \in\mathcal{F}_H(T)} \mathbb{P}^q(F), V H ( T ) : = P q + 1 ( T ) × M ∂ T , M ∂ T : = F ∈ F H ( T ) ∏ P q ( F ) ,
with hybrid unknowns v T = ( v T , v ∂ T ) v_T = (v_T, v_{\partial T}) v T = ( v T , v ∂ T ) , where v T ∈ P q + 1 ( T ) v_T \in\mathbb{P}^{q+1}(T) v T ∈ P q + 1 ( T ) is the cell unknown and v ∂ T = ( v F ) F ∈ F H ( T ) v_{\partial T} = (v_F)_{F \in\mathcal{F}_H(T)} v ∂ T = ( v F ) F ∈ F H ( T ) collects the face unknowns. The global HHO space is
V H ≔ U H × M H ≔ P q + 1 ( T H ) × P 0 q ( F H ) , P 0 q ( F H ) ≔ { λ H ∈ P q ( F H ) : λ F = 0 ∀ F ∈ F H b d } , V_H \coloneqq U_H \times M_H \coloneqq\mathbb{P}^{q+1}(\mathcal{T}_H) \times\mathbb{P}_0^q(\mathcal{F}_H), \qquad\mathbb{P}_0^q(\mathcal{F}_H) \coloneqq\{\lambda_H \in\mathbb{P}^q(\mathcal{F}_H) : \lambda_F = 0\ \ \forall F \in\mathcal{F}_H^{\mathrm{bd}}\}, V H : = U H × M H : = P q + 1 ( T H ) × P 0 q ( F H ) , P 0 q ( F H ) : = { λ H ∈ P q ( F H ) : λ F = 0 ∀ F ∈ F H bd } ,
with global hybrid unknowns v H = ( v T H , v F H ) v_H = (v_{T_H},v_{F_H}) v H = ( v T H , v F H ) and v H ∣ T = v T v_H|_T = v_T v H ∣ T = v T . The constraint on boundary faces strongly enforces the homogeneous Dirichlet boundary condition on the skeleton. Together with the norm equivalence of Lemma 7.2, it ensures that the condensed bilinear form a H a_H a H introduced below is positive definite on M H M_H M H , see Lemma 7.3 (without the boundary constraint, the constant skeleton function would belong to its kernel). On the hybrid space V H V_H V H we define the usual hybrid seminorms (the local one has the one-dimensional kernel { ( c , c ∣ ∂ T ) } \{(c,c|_{\partial T})\} {( c , c ∣ ∂ T )} , since constants belong to the face spaces, while the global one is a norm on V H V_H V H by the positive-definiteness argument below)
∥ v H ∥ h h o , H 2 ≔ ∑ T ∈ T H ∣ v T ∣ h h o , T 2 , ∣ v T ∣ h h o , T 2 ≔ ∣ v T ∣ 1 , T 2 + H T − 1 ∣ v T − v ∂ T ∣ ∂ T 2 . \lVert v_H \rVert_{\mathrm{hho},H}^2 \coloneqq\sum_{T \in\mathcal{T}_H} |v_T|_{\mathrm{hho},T}^2, \qquad|v_T|_{\mathrm{hho},T}^2 \coloneqq|v_T|_{1,T}^2 + H_T^{-1} |v_T-v_{\partial T}|_{\partial T}^2. ∥ v H ∥ hho , H 2 : = T ∈ T H ∑ ∣ v T ∣ hho , T 2 , ∣ v T ∣ hho , T 2 : = ∣ v T ∣ 1 , T 2 + H T − 1 ∣ v T − v ∂ T ∣ ∂ T 2 .
The local potential reconstruction R T : V H ( T ) → P q + 1 ( T ) \mathcal{R}_T : V_H(T) \to\mathbb{P}^{q+1}(T) R T : V H ( T ) → P q + 1 ( T ) is the unique polynomial satisfying, for all w ∈ P q + 1 ( T ) w \in\mathbb{P}^{q+1}(T) w ∈ P q + 1 ( T ) ,
( ∇ R T v T , ∇ w ) T = ( ∇ v T , ∇ w ) T + ( v ∂ T − v T , n ∂ T ⋅ ∇ w ) ∂ T , (\nabla\mathcal{R}_T v_T,\nabla w)_T = (\nabla v_T,\nabla w)_T + (v_{\partial T}-v_T,\boldsymbol{n}_{\partial T}\cdot\nabla w)_{\partial T}, ( ∇ R T v T , ∇ w ) T = ( ∇ v T , ∇ w ) T + ( v ∂ T − v T , n ∂ T ⋅ ∇ w ) ∂ T ,
( R T v T , 1 ) T = ( v T , 1 ) T , (30) (\mathcal{R}_T v_T,1)_T = (v_T,1)_T, \tag*{(30)} ( R T v T , 1 ) T = ( v T , 1 ) T , (30)
where n ∂ T \boldsymbol{n}_{\partial T} n ∂ T is the unit outward normal to T T T . The global reconstruction R H : V H → P q + 1 ( T H ) \mathcal{R}_H : V_H \to\mathbb{P}^{q+1}(\mathcal{T}_H) R H : V H → P q + 1 ( T H ) applies R T \mathcal{R}_T R T element-wise.
The local hybrid bilinear form on T T T reads
a T ( u T , v T ) ≔ ( ∇ R T u T , ∇ R T v T ) T + s T ( u T , v T ) , (31) a_T(u_T,v_T) \coloneqq(\nabla R_Tu_T,\nabla R_Tv_T)_T+s_T(u_T,v_T), \tag*{(31)} a T ( u T , v T ) : = ( ∇ R T u T , ∇ R T v T ) T + s T ( u T , v T ) , (31)
with stabilisation
s T ( u T , v T ) ≔ H T − 1 ( π ∂ T q u T − u ∂ T , π ∂ T q v T − v ∂ T ) ∂ T . (32) s_T(u_T,v_T) \coloneqq H_T^{-1}(\pi_{\partial T}^q u_T-u_{\partial T},\pi_{\partial T}^q v_T-v_{\partial T})_{\partial T}. \tag*{(32)} s T ( u T , v T ) : = H T − 1 ( π ∂ T q u T − u ∂ T , π ∂ T q v T − v ∂ T ) ∂ T . (32)
The global hybrid bilinear form is then a H ( u H , v H ) = ∑ T ∈ T H a T ( u T , v T ) a_H(u_H,v_H)=\sum_{T\in\mathcal{T}_H}a_T(u_T,v_T) a H ( u H , v H ) = ∑ T ∈ T H a T ( u T , v T ) . Unlike the SIPG method of § 6 , whose penalty parameter must be taken large enough for coercivity and is later exploited at σ ≈ H / h \sigma\approx H/h σ ≈ H / h , the stabilisation (32) carries no penalty coefficient. With the unit weight, the local bilinear form is already equivalent to the hybrid seminorm (Lemma 7.2) with constants of order one, and no super-penalisation is used in this section.
Condensed formulation. The cell unknowns can be locally eliminated by exploiting the block structure of the hybrid bilinear form. For each T ∈ T H T\in\mathcal{T}_H T ∈ T H , we define the inverse static condensation operator U T : M ∂ T → P q + 1 ( T ) \mathcal{U}_T:M_{\partial T}\to\mathbb{P}^{q+1}(T) U T : M ∂ T → P q + 1 ( T ) as the unique solution of
a T ( ( U T λ H , 0 ) , ( w T , 0 ) ) = − a T ( ( 0 , λ H ) , ( w T , 0 ) ) ∀ w T ∈ P q + 1 ( T ) . (33) a_T((\mathcal{U}_T\lambda_H,0),(w_T,0))=-a_T((0,\lambda_H),(w_T,0))\qquad\forall w_T\in\mathbb{P}^{q+1}(T). \tag*{(33)} a T (( U T λ H , 0 ) , ( w T , 0 )) = − a T (( 0 , λ H ) , ( w T , 0 )) ∀ w T ∈ P q + 1 ( T ) . (33)
That is, U T λ H \mathcal{U}_T\lambda_H U T λ H recovers the cell unknown from the skeleton data λ H ∣ ∂ T \lambda_H|_{\partial T} λ H ∣ ∂ T by solving the local cell equation. The local problem (33) is well-posed, since a T a_T a T is positive definite on cell bubbles ( w T , 0 ) (w_T,0) ( w T , 0 ) . For the face spaces (29) , this follows from the inclusion ∇ P q + 1 ( T ) ⋅ n F ∣ F ⊂ P q ( F ) \nabla\mathbb{P}^{q+1}(T)\cdot n_F|_F\subset\mathbb{P}^q(F) ∇ P q + 1 ( T ) ⋅ n F ∣ F ⊂ P q ( F ) together with P 0 ( Ω ) ∣ F ⊂ P q ( F ) \mathbb{P}^0(\Omega)|_F\subset\mathbb{P}^q(F) P 0 ( Ω ) ∣ F ⊂ P q ( F ) , which is what rules out the constants and is why (29) carries the P 0 \mathbb{P}^0 P 0 term on non-planar faces, see [5 , 38 ] . The global broken operator U H : M H → P q + 1 ( T H ) \mathcal{U}_H:M_H\to\mathbb{P}^{q+1}(\mathcal{T}_H) U H : M H → P q + 1 ( T H ) acts element-wise: ( U H λ H ) ∣ T ≔ U T ( λ H ∣ ∂ T ) (\mathcal{U}_H\lambda_H)|_T\coloneqq\mathcal{U}_T(\lambda_H|_{\partial T}) ( U H λ H ) ∣ T : = U T ( λ H ∣ ∂ T ) for all T ∈ T H T\in\mathcal{T}_H T ∈ T H . We also define the hybrid extension U ‾ H : M H → V H \underline{\mathcal{U}}_H:M_H\to V_H U H : M H → V H by
U ‾ H λ H ≔ ( U H λ H , λ H ) . \underline{\mathcal{U}}_H\lambda_H\coloneqq(\mathcal{U}_H\lambda_H,\lambda_H). U H λ H : = ( U H λ H , λ H ) .
Substituting the inverse static condensation into the hybrid bilinear form yields the local and global skeleton bilinear forms:
a T ( λ H , μ H ) ≔ a T ( ( U T λ H , λ H ) , ( U T μ H , μ H ) ) , a_T(\lambda_H,\mu_H)\coloneqq a_T((\mathcal{U}_T\lambda_H,\lambda_H),(\mathcal{U}_T\mu_H,\mu_H)), a T ( λ H , μ H ) : = a T (( U T λ H , λ H ) , ( U T μ H , μ H )) ,
a H ( λ H , μ H ) ≔ ∑ T ∈ T H a T ( λ H , μ H ) . a_H(\lambda_H,\mu_H)\coloneqq\sum_{T\in\mathcal{T}_H}a_T(\lambda_H,\mu_H). a H ( λ H , μ H ) : = T ∈ T H ∑ a T ( λ H , μ H ) .
We identify the coarse auxiliary space as V H = M H V_H=M_H V H = M H equipped with the skeleton bilinear form a H a_H a H , and denote by A H : M H → M H A_H:M_H\to M_H A H : M H → M H the associated operator, characterised by ( A H λ H , μ H ) = a H ( λ H , μ H ) (A_H\lambda_H,\mu_H)=a_H(\lambda_H,\mu_H) ( A H λ H , μ H ) = a H ( λ H , μ H ) , where ( ⋅ , ⋅ ) (\cdot,\cdot) ( ⋅ , ⋅ ) is the L 2 ( F H ) L^2(\mathcal{F}_H) L 2 ( F H ) inner product.
Since U ‾ H λ H \underline{\mathcal{U}}_H\lambda_H U H λ H minimises the local hybrid energy over all cell unknowns with the same skeleton data λ H \lambda_H λ H , the skeleton bilinear form satisfies the energy minimisation property: for any λ H ∈ M H \lambda_H\in M_H λ H ∈ M H and any v H = ( v H , λ H ) ∈ V H v_H=(v_H,\lambda_H)\in V_H v H = ( v H , λ H ) ∈ V H with skeleton values λ H \lambda_H λ H ,
a H ( λ H , λ H ) ≤ a H ( v H , v H ) . (34) a_H(\lambda_H,\lambda_H)\le a_H(v_H,v_H). \tag*{(34)} a H ( λ H , λ H ) ≤ a H ( v H , v H ) . (34)
HHO analysis tools
We start by recalling the following bound, whose proof can be found in [38 Lemma 7] : for all v ∈ H 1 ( T ) v\in H^1(T) v ∈ H 1 ( T ) ,
∥ π T q v ∥ 1 , T 2 + H T − 1 ∥ π ∂ T q v − π T q v ∥ ∂ T 2 ≲ ∣ v ∣ 1 , T 2 . (35) \lVert\pi_T^qv\rVert_{1,T}^2+H_T^{-1}\lVert\pi_{\partial T}^qv-\pi_T^qv\rVert_{\partial T}^2\lesssim|v|_{1,T}^2. \tag*{(35)} ∥ π T q v ∥ 1 , T 2 + H T − 1 ∥ π ∂ T q v − π T q v ∥ ∂ T 2 ≲ ∣ v ∣ 1 , T 2 . (35)
We note that the proof of (35) relies on the inclusion P 0 ( Ω ) ∣ F ⊂ P q ( F ) \mathbb{P}^0(\Omega)|_F\subset\mathbb{P}^q(F) P 0 ( Ω ) ∣ F ⊂ P q ( F ) , which holds by construction of (29) . From (35) we can further deduce the following result
H T − 1 ∥ π ∂ T q v − v ∥ ∂ T 2 ≲ ∣ v ∣ 1 , T 2 , (36) H_T^{-1}\lVert\pi_{\partial T}^qv-v\rVert_{\partial T}^2\lesssim|v|_{1,T}^2, \tag*{(36)} H T − 1 ∥ π ∂ T q v − v ∥ ∂ T 2 ≲ ∣ v ∣ 1 , T 2 , (36)
where it suffices to add and subtract π T q v \pi_T^qv π T q v in the face term and use the triangle inequality followed by (35) and (9) .
We now prove the following two bounds.
Lemma 7.1. For all T ∈ T H T\in\mathcal{T}_H T ∈ T H and v ‾ T ∈ V H ( T ) \underline{v}_T\in V_H(T) v T ∈ V H ( T ) ,
∣ v T ∣ 1 , T 2 + H T − 1 ∥ v ∂ T − π ∂ T q v T ∥ ∂ T 2 ≲ ∥ v ‾ T ∥ a T 2 . (37) |v_T|_{1,T}^2+H_T^{-1}\lVert v_{\partial T}-\pi_{\partial T}^qv_T\rVert_{\partial T}^2\lesssim\lVert\underline{v}_T\rVert_{a_T}^2. \tag*{(37)} ∣ v T ∣ 1 , T 2 + H T − 1 ∥ v ∂ T − π ∂ T q v T ∥ ∂ T 2 ≲ ∥ v T ∥ a T 2 . (37)
∣ R T v T − v T ∣ 1 , T ≲ H T − 1 / 2 ∥ v ∂ T − π ∂ T q v T ∥ ∂ T = s T ( v ‾ T , v ‾ T ) 1 / 2 . (38) \lvert R_Tv_T-v_T\rvert_{1,T}\lesssim H_T^{-1/2}\lVert v_{\partial T}-\pi_{\partial T}^qv_T\rVert_{\partial T}=s_T(\underline{v}_T,\underline{v}_T)^{1/2}. \tag*{(38)} ∣ R T v T − v T ∣ 1 , T ≲ H T − 1/2 ∥ v ∂ T − π ∂ T q v T ∥ ∂ T = s T ( v T , v T ) 1/2 . (38)
Proof. The proof for (37) can be found in [5 Lemma 3, (3.1a)] . For (38) , we take w = R T v T − v T ∈ P q + 1 ( T ) w = R_Tv_T-v_T \in\mathbb{P}^{q+1}(T) w = R T v T − v T ∈ P q + 1 ( T ) in (30) , then insert π ∂ T q \pi_{\partial T}^{q} π ∂ T q in the face term, which is allowed since n F ⋅ ∇ w ∣ F ∈ P q ( F ) n_F \cdot\nabla w|_F \in\mathbb{P}^{q}(F) n F ⋅ ∇ w ∣ F ∈ P q ( F ) by (29) , to obtain
∣ w ∣ 1 , T 2 = ( v ∂ T − π ∂ T q v T , n ∂ T ⋅ ∇ w ) ∂ T . |w|_{1,T}^{2} = (v_{\partial T}-\pi_{\partial T}^{q}v_T,n_{\partial T}\cdot\nabla w)_{\partial T}. ∣ w ∣ 1 , T 2 = ( v ∂ T − π ∂ T q v T , n ∂ T ⋅ ∇ w ) ∂ T .
A Cauchy–Schwarz inequality, the trace inequality (6) and an inverse inequality applied to ∇ w \nabla w ∇ w then yield (38) . □
We also state the following norm equivalence result. Its proof in the case of same-order HHO is standard and can be found, e.g. in [32 ] . For the mixed-order method with the face spaces (29) and the stabilisation (32) , it can be found in [5 Lemma 3] .
Lemma 7.2 (HHO seminorm equivalence). If T H \mathcal{T}_H T H satisfies Assumption 3.1, then, for all v T ∈ V H ( T ) v_T \in V_H(T) v T ∈ V H ( T ) ,
∣ v T ∣ h h o , T 2 ≲ ∣ v T ∣ a T 2 ≲ ∣ v T ∣ h h o , T 2 . |v_T|_{\mathrm{hho},T}^{2} \lesssim|v_T|_{a_T}^{2} \lesssim|v_T|_{\mathrm{hho},T}^{2}. ∣ v T ∣ hho , T 2 ≲ ∣ v T ∣ a T 2 ≲ ∣ v T ∣ hho , T 2 .
Summing over T ∈ T H T \in\mathcal{T}_H T ∈ T H , and using the definition of the global norms, Lemma 7.2 immediately gives the global equivalence ∥ v H ∥ h h o , H ≃ ∥ v H ∥ a H \lVert v_H\rVert_{\mathrm{hho},H} \simeq\lVert v_H\rVert_{a_H} ∥ v H ∥ hho , H ≃ ∥ v H ∥ a H for all v H ∈ V H v_H \in V_H v H ∈ V H , which is the form used in the remainder of this section.
Lemma 7.3 (Positive definiteness). If T H \mathcal{T}_H T H satisfies Assumption 3.1, then the bilinear form a H a_H a H is positive definite on V H V_H V H , and the condensed bilinear form a ‾ H \overline{a}_H a H is positive definite on M H M_H M H .
Proof. The statement for a H a_H a H is [5 Lemma 4] . For a ‾ H \overline{a}_H a H , if a ‾ H ( v H , v H ) = 0 \overline{a}_H(v_H,v_H)=0 a H ( v H , v H ) = 0 then, by Lemma 7.2, v T v_T v T is constant and equal to v ∂ T v_{\partial T} v ∂ T on every T ∈ T H T \in\mathcal{T}_H T ∈ T H , and the argument of [5 Lemma 4] applies. Cells sharing a face carry the same constant, the constant vanishes on cells with a boundary face, and every cell is joined to one such by a chain of faces since Ω \Omega Ω is connected. Hence v H = 0 v_H=0 v H = 0 . □
We now define the HHO interpolation operator J T : H 1 ( T ) → V H ( T ) J_T:H^1(T)\to V_H(T) J T : H 1 ( T ) → V H ( T ) as follows:
J T v ≔ ( π T q + 1 v , π ∂ T q v ) . J_Tv \coloneqq\left(\pi_T^{q+1}v,\ \pi_{\partial T}^{q}v\right). J T v : = ( π T q + 1 v , π ∂ T q v ) .
Its global counterpart J H : H 0 1 ( Ω ) → V H J_H:H_0^1(\Omega)\to V_H J H : H 0 1 ( Ω ) → V H is defined by applying J T J_T J T element-wise. This is well defined since the trace of v ∈ H 0 1 ( Ω ) v\in H_0^1(\Omega) v ∈ H 0 1 ( Ω ) on an interior face is single-valued. Note that, for v ∈ H 0 1 ( Ω ) v\in H_0^1(\Omega) v ∈ H 0 1 ( Ω ) , we have π F q v = 0 \pi_F^qv=0 π F q v = 0 on every boundary face F ∈ F H b d F\in\mathcal{F}_H^{\mathrm{bd}} F ∈ F H bd , so that indeed J H v ∈ V H J_Hv\in V_H J H v ∈ V H . We denote by γ H \gamma_H γ H the trace operator returning the skeleton component of a hybrid function, i.e. γ H v H = v F H \gamma_Hv_H=v_{F_H} γ H v H = v F H and, locally, γ H v T = v ∂ T \gamma_Hv_T=v_{\partial T} γ H v T = v ∂ T .
As a consequence of (36) , (9) and (8) , the HHO interpolation is bounded (see [5 Lemma 8, (3.6a)] ): for any v ∈ H 1 ( T ) v\in H^1(T) v ∈ H 1 ( T ) ,
∣ J T v ∣ h h o , T ≲ ∣ v ∣ 1 , T . (39) |J_Tv|_{\mathrm{hho},T}\lesssim|v|_{1,T}. \tag*{(39)} ∣ J T v ∣ hho , T ≲ ∣ v ∣ 1 , T . (39)
A fundamental property of the HHO reconstruction is that it commutes with the elliptic projector. For all v ∈ H 1 ( T ) v\in H^1(T) v ∈ H 1 ( T ) we have R T ( J T v ) = π T 1 , q + 1 v R_T(J_Tv)=\pi_T^{1,q+1}v R T ( J T v ) = π T 1 , q + 1 v , where π T 1 , q + 1 : H 1 ( T ) → P q + 1 ( T ) \pi_T^{1,q+1}:H^1(T)\to\mathbb{P}^{q+1}(T) π T 1 , q + 1 : H 1 ( T ) → P q + 1 ( T ) is the elliptic projector defined in (10) . For the face spaces (29) , the proof for the same-order HHO formulation can be found in [38 Lemma 2] and extends verbatim to the mixed-order method used here [5 ] . As observed in [38 Remark 4] , the proof relies on the fact that ∇ P q + 1 ( T ) ⋅ n F ∣ F ⊂ P q ( F ) \nabla\mathbb{P}^{q+1}(T)\cdot n_F|_F\subset\mathbb{P}^{q}(F) ∇ P q + 1 ( T ) ⋅ n F ∣ F ⊂ P q ( F ) .
As a consequence, the approximation properties of R T ∘ J T R_T\circ J_T R T ∘ J T reduce to standard estimates for the elliptic projector on shape-regular polytopes, given by (11) and (12) .
HHO prolongation
As our prolongation I H h = I H h h h o : M H → V h I_{Hh}=I_{Hh}^{\mathrm{hho}}:M_H\to V_h I H h = I H h hho : M H → V h , we consider an operator inspired by the ones used in [5 ] . It first maps the skeleton variable to a DG function on the coarse mesh, then applies the fine interpolant and the averaging operator W h \mathcal{W}_h W h of Section 6 to enforce conformity. Since there is more than one choice for the coarse reconstruction, we will formulate a general framework for the analysis of I H h h h o I_{Hh}^{\mathrm{hho}} I H h hho like the one in [5 ] .
Definition 7.4. Let Θ H : M H → P q + 1 ( T H ) \Theta_H:M_H\to\mathbb{P}^{q+1}(\mathcal{T}_H) Θ H : M H → P q + 1 ( T H ) be a coarse reconstruction operator mapping skeleton functions to discontinuous coarse bulk polynomials, and let I H h d g = W h I h I_{Hh}^{\mathrm{dg}}=\mathcal{W}_h\mathcal{I}_h I H h dg = W h I h be the DG prolongation (19) , which is defined on P k ( T H ) \mathbb{P}^{k}(\mathcal{T}_H) P k ( T H ) for any k ≥ 1 k\geq1 k ≥ 1 . We define the HHO prolongation as
I H h h h o ≔ I H h d g Θ H = W h I h Θ H . I_{Hh}^{\mathrm{hho}}\coloneqq I_{Hh}^{\mathrm{dg}}\Theta_H=\mathcal{W}_h\mathcal{I}_h\Theta_H. I H h hho : = I H h dg Θ H = W h I h Θ H . In particular, we will consider the choices Θ H = U H \Theta_H=\mathcal{U}_H Θ H = U H and Θ H = R H ∘ U H \Theta_H=\mathcal{R}_H\circ\mathcal{U}_H Θ H = R H ∘ U H .
We first collect the properties of the two reconstructions Θ H \Theta_H Θ H that the analysis needs, starting with two results from [5 ] on the energy of bubble functions.
Lemma 7.5. Let δ H = ( δ H , 0 ) ∈ V H \delta_H=(\delta_H,0)\in V_H δ H = ( δ H , 0 ) ∈ V H be a bubble function on V H V_H V H . Then, we have the following bound:
∥ δ H ∥ L 2 ( Ω ) ≲ H ∥ δ H ∥ a H . \|\delta_H\|_{L^2(\Omega)}\lesssim H\|\delta_H\|_{a_H}. ∥ δ H ∥ L 2 ( Ω ) ≲ H ∥ δ H ∥ a H .
Proof. The proof can be found in [5 Lemma 10, (3.10a)] . □ \square □
The next result is the H 1 H^1 H 1 counterpart of [5 Lemma 10, (3.10b)] , which assumes z ∈ H 2 ( Ω ) z\in H^2(\Omega) z ∈ H 2 ( Ω ) and gains a factor H H H . The orthogonality argument of the proof is the same, but the consistency term is bounded through the elliptic projector rather than through the consistency error.
Lemma 7.6. Let z ∈ H 0 1 ( Ω ) z\in H^1_0(\Omega) z ∈ H 0 1 ( Ω ) . Define two hybrid functions:
u H ≔ J H z = ( π H q + 1 z , π F H q z ) , v H ≔ U H γ H J H z = ( U H π F H q z , π F H q z ) . u_H\coloneqq J_Hz=(\pi_H^{q+1}z,\pi_{\mathcal{F}_H}^{q}z),\qquad v_H\coloneqq U_H\gamma_HJ_Hz=(U_H\pi_{\mathcal{F}_H}^{q}z,\pi_{\mathcal{F}_H}^{q}z). u H : = J H z = ( π H q + 1 z , π F H q z ) , v H : = U H γ H J H z = ( U H π F H q z , π F H q z ) .
Then, we have the following bound:
∥ u H − v H ∥ a H ≲ ∣ z ∣ 1 , Ω . \|u_H-v_H\|_{a_H}\lesssim|z|_{1,\Omega}. ∥ u H − v H ∥ a H ≲ ∣ z ∣ 1 , Ω .
Proof. We define the bubble function δ H = u H − v H = ( δ H , 0 ) \delta_H=u_H-v_H=(\delta_H,0) δ H = u H − v H = ( δ H , 0 ) . Then, by a a a -orthogonality of U H U_H U H with bubble functions, we have
∥ δ H ∥ a H 2 = a H ( δ H , δ H ) = a H ( u H , δ H ) = [ ∑ T ∈ T H ( ∇ R T u H , ∇ R T δ H ) T ] + ∑ T ∈ T H s T ( u H , δ H ) . \|\delta_H\|_{a_H}^2=a_H(\delta_H,\delta_H)=a_H(u_H,\delta_H)=\left[\sum_{T\in\mathcal{T}_H}(\nabla\mathcal{R}_T u_H,\nabla\mathcal{R}_T\delta_H)_T\right]+\sum_{T\in\mathcal{T}_H}s_T(u_H,\delta_H). ∥ δ H ∥ a H 2 = a H ( δ H , δ H ) = a H ( u H , δ H ) = [ T ∈ T H ∑ ( ∇ R T u H , ∇ R T δ H ) T ] + T ∈ T H ∑ s T ( u H , δ H ) .
The consistency term can be bounded by remembering that R T u H = R T J H z = π T 1 , q + 1 z \mathcal{R}_T u_H=\mathcal{R}_T J_Hz=\pi_T^{1,q+1}z R T u H = R T J H z = π T 1 , q + 1 z and thus
∑ T ∈ T H ( ∇ R T u H , ∇ R T δ H ) T = ∑ T ∈ T H ( ∇ π T 1 , q + 1 z , ∇ R T δ H ) T = ∑ T ∈ T H ( ∇ z , ∇ R T δ H ) T ≤ ∣ z ∣ 1 , Ω ∣ R H δ H ∣ 1 , T H ≤ ∣ z ∣ 1 , Ω ∥ δ H ∥ a H \begin{aligned}
\sum_{T\in\mathcal{T}_H}(\nabla\mathcal{R}_T u_H,\nabla\mathcal{R}_T\delta_H)_T
=\sum_{T\in\mathcal{T}_H}(\nabla\pi_T^{1,q+1}z,\nabla\mathcal{R}_T\delta_H)_T
=\sum_{T\in\mathcal{T}_H}(\nabla z,\nabla\mathcal{R}_T\delta_H)_T \\
&\le|z|_{1,\Omega}|\mathcal{R}_H\delta_H|_{1,\mathcal{T}_H}
\le|z|_{1,\Omega}\|\delta_H\|_{a_H}
\end{aligned} T ∈ T H ∑ ( ∇ R T u H , ∇ R T δ H ) T = T ∈ T H ∑ ( ∇ π T 1 , q + 1 z , ∇ R T δ H ) T = T ∈ T H ∑ ( ∇ z , ∇ R T δ H ) T ≤ ∣ z ∣ 1 , Ω ∣ R H δ H ∣ 1 , T H ≤ ∣ z ∣ 1 , Ω ∥ δ H ∥ a H
where we have used that ( ∇ π T 1 , q + 1 z , ∇ w ) T = ( ∇ z , ∇ w ) T (\nabla\pi_T^{1,q+1}z,\nabla w)_T=(\nabla z,\nabla w)_T ( ∇ π T 1 , q + 1 z , ∇ w ) T = ( ∇ z , ∇ w ) T for all w ∈ P q + 1 ( T ) w\in\mathbb{P}^{q+1}(T) w ∈ P q + 1 ( T ) , then a Cauchy-Schwarz inequality. The stabilisation term can be bounded as follows:
∑ T ∈ T H s T ( u H , δ H ) ≤ ( ∑ T ∈ T H s T ( J H z , J H z ) ) 1 / 2 ( ∑ T ∈ T H s T ( δ H , δ H ) ) 1 / 2 ≲ ∣ z ∣ 1 , Ω ∥ δ H ∥ a H \sum_{T\in\mathcal{T}_H}s_T(u_H,\delta_H)\le\left(\sum_{T\in\mathcal{T}_H}s_T(J_Hz,J_Hz)\right)^{1/2}\left(\sum_{T\in\mathcal{T}_H}s_T(\delta_H,\delta_H)\right)^{1/2}\lesssim|z|_{1,\Omega}\|\delta_H\|_{a_H} T ∈ T H ∑ s T ( u H , δ H ) ≤ ( T ∈ T H ∑ s T ( J H z , J H z ) ) 1/2 ( T ∈ T H ∑ s T ( δ H , δ H ) ) 1/2 ≲ ∣ z ∣ 1 , Ω ∥ δ H ∥ a H
where we have first used a Cauchy-Schwarz inequality, and then s T ( J T z , J T z ) = H T − 1 ∥ π ∂ T q ( π T q + 1 z − z ) ∥ ∂ T 2 ≲ H T − 1 ∥ z − π T q + 1 z ∥ ∂ T 2 ≲ ∣ z ∣ 1 , T 2 s_T(J_Tz,J_Tz)=H_T^{-1}\|\pi_{\partial T}^{q}(\pi_T^{q+1}z-z)\|_{\partial T}^2\lesssim H_T^{-1}\|z-\pi_T^{q+1}z\|_{\partial T}^2\lesssim|z|_{1,T}^2 s T ( J T z , J T z ) = H T − 1 ∥ π ∂ T q ( π T q + 1 z − z ) ∥ ∂ T 2 ≲ H T − 1 ∥ z − π T q + 1 z ∥ ∂ T 2 ≲ ∣ z ∣ 1 , T 2 , by L 2 L^2 L 2 -stability of π ∂ T q \pi_{\partial T}^{q} π ∂ T q and (4.4) with s = 1 s=1 s = 1 . Putting everything together and dividing by ∥ δ H ∥ a H \|\delta_H\|_{a_H} ∥ δ H ∥ a H (the case δ H = 0 \delta_H=0 δ H = 0 being trivial) concludes the proof. □ \square □
The following approximation result is the H 1 H^1 H 1 counterpart of [5 Lemmas 15 and 17] , which are stated one order higher for H 2 H^2 H 2 functions.
Lemma 7.7. Given v h ∈ V h v_h\in V_h v h ∈ V h , let λ H ≔ π F H q v h ∈ M H \lambda_H\coloneqq\pi_{\mathcal{F}_H}^{q}v_h\in M_H λ H : = π F H q v h ∈ M H . Then, for r = 0 , 1 r=0,1 r = 0 , 1 and both choices Θ H = U H \Theta_H=U_H Θ H = U H and Θ H = R H ∘ U H \Theta_H=\mathcal{R}_H\circ U_H Θ H = R H ∘ U H ,
∥ v h − Θ H λ H ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω . \|v_h-\Theta_H\lambda_H\|_{H^r(\mathcal{T}_H)}\lesssim H^{1-r}|v_h|_{1,\Omega}. ∥ v h − Θ H λ H ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω .
Proof. Using a triangle inequality, we can write, for r = 0 , 1 r=0,1 r = 0 , 1 ,
∥ v h − Θ H λ H ∥ H r ( T H ) ≤ ∥ v h − π T H q + 1 v h ∥ H r ( T H ) + ∥ π T H q + 1 v h − Θ H λ H ∥ H r ( T H ) . \|v_h-\Theta_H\lambda_H\|_{H^r(\mathcal{T}_H)}
\le\|v_h-\pi_{\mathcal{T}_H}^{q+1}v_h\|_{H^r(\mathcal{T}_H)}
+\|\pi_{\mathcal{T}_H}^{q+1}v_h-\Theta_H\lambda_H\|_{H^r(\mathcal{T}_H)}. ∥ v h − Θ H λ H ∥ H r ( T H ) ≤ ∥ v h − π T H q + 1 v h ∥ H r ( T H ) + ∥ π T H q + 1 v h − Θ H λ H ∥ H r ( T H ) .
By the approximation properties of the L 2 L^2 L 2 -orthogonal projector in Equation (8) , applied element-wise on T H \mathcal{T}_H T H with s = 1 s=1 s = 1 and m = r m=r m = r , we have that
∥ v h − π T H q + 1 v h ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω . \|v_h-\pi_{\mathcal{T}_H}^{q+1}v_h\|_{H^r(\mathcal{T}_H)}\lesssim H^{1-r}|v_h|_{1,\Omega}. ∥ v h − π T H q + 1 v h ∥ H r ( T H ) ≲ H 1 − r ∣ v h ∣ 1 , Ω .
We now tackle the second term. First consider the case Θ H = U H \Theta_H=U_H Θ H = U H , and define the two hybrid functions of Lemma 7.6 with z = v h ∈ H 0 1 ( Ω ) z=v_h\in H^1_0(\Omega) z = v h ∈ H 0 1 ( Ω ) as u H = J H v h u_H=J_Hv_h u H = J H v h and v H = U H γ H J H v h v_H=U_H\gamma_HJ_Hv_h v H = U H γ H J H v h . The bubble function δ H = u H − v H \delta_H=u_H-v_H δ H = u H − v H satisfies that δ H = π T H q + 1 v h − U H π F H q v h = π T H q + 1 v h − U H λ H \delta_H=\pi_{\mathcal{T}_H}^{q+1}v_h-U_H\pi_{\mathcal{F}_H}^{q}v_h=\pi_{\mathcal{T}_H}^{q+1}v_h-U_H\lambda_H δ H = π T H q + 1 v h − U H π F H q v h = π T H q + 1 v h − U H λ H . Then, using Lemmas 7.5 and 7.6, we have that
∥ δ H ∥ L 2 ( Ω ) ≲ H ∥ δ H ∥ a H ≲ H ∣ v h ∣ 1 , Ω . \|\delta_H\|_{L^2(\Omega)}\lesssim H\|\delta_H\|_{a_H}\lesssim H|v_h|_{1,\Omega}. ∥ δ H ∥ L 2 ( Ω ) ≲ H ∥ δ H ∥ a H ≲ H ∣ v h ∣ 1 , Ω .
Moreover, by Lemma 7.2 for the seminorm part and the previous bound with H ≤ 1 H\le1 H ≤ 1 for the L 2 L^2 L 2 part, together with Lemma 7.6,
∥ δ H ∥ H 1 ( T H ) ≲ ∥ δ H ∥ a H ≲ ∣ v h ∣ 1 , Ω . \|\delta_H\|_{H^1(\mathcal{T}_H)}\lesssim\|\delta_H\|_{a_H}\lesssim|v_h|_{1,\Omega}. ∥ δ H ∥ H 1 ( T H ) ≲ ∥ δ H ∥ a H ≲ ∣ v h ∣ 1 , Ω .
This concludes the proof for the case Θ H = U H \Theta_H = \mathcal{U}_H Θ H = U H . For the case Θ H = R H ∘ U H \Theta_H = \mathcal{R}_H \circ\mathcal{U}_H Θ H = R H ∘ U H , we start by using a triangle inequality to write
∥ v h − R H ∘ U H λ H ∥ H r ( T H ) ≤ ∥ v h − U H λ H ∥ H r ( T H ) + ∥ U H λ H − R H ∘ U H λ H ∥ H r ( T H ) . \lVert v_h-\mathcal{R}_H\circ\mathcal{U}_H\lambda_H\rVert_{H^r(\mathcal{T}_H)}
\le\lVert v_h-\mathcal{U}_H\lambda_H\rVert_{H^r(\mathcal{T}_H)}+\lVert\mathcal{U}_H\lambda_H-\mathcal{R}_H\circ\mathcal{U}_H\lambda_H\rVert_{H^r(\mathcal{T}_H)}. ∥ v h − R H ∘ U H λ H ∥ H r ( T H ) ≤ ∥ v h − U H λ H ∥ H r ( T H ) + ∥ U H λ H − R H ∘ U H λ H ∥ H r ( T H ) .
We can bound the first term using the previous case. For the second term, we apply (7.10) to v H = U H λ H v_H=\mathcal{U}_H\lambda_H v H = U H λ H , for which v T = U T λ H v_T=\mathcal{U}_T\lambda_H v T = U T λ H and v ∂ T = λ H ∣ ∂ T v_{\partial T}=\lambda_H|_{\partial T} v ∂ T = λ H ∣ ∂ T . Recalling the definition (7.4) of the stabilisation, and summing over T ∈ T H T\in\mathcal{T}_H T ∈ T H , this gives
∣ U H λ H − R H ∘ U H λ H ∣ 1 , T H 2 ≲ ∑ T ∈ T H s T ( U H λ H , U H λ H ) ≲ ∥ U H λ H ∥ a H 2 . \lvert\mathcal{U}_H\lambda_H-\mathcal{R}_H\circ\mathcal{U}_H\lambda_H\rvert_{1,\mathcal{T}_H}^2
\lesssim\sum_{T\in\mathcal{T}_H}s_T(\mathcal{U}_H\lambda_H,\mathcal{U}_H\lambda_H)
\lesssim\lVert\mathcal{U}_H\lambda_H\rVert_{a_H}^2. ∣ U H λ H − R H ∘ U H λ H ∣ 1 , T H 2 ≲ T ∈ T H ∑ s T ( U H λ H , U H λ H ) ≲ ∥ U H λ H ∥ a H 2 .
Then, with the same u H u_H u H , v H v_H v H and δ H \delta_H δ H defined above, we have U H λ H = v H = u H − δ H \mathcal{U}_H\lambda_H=v_H=u_H-\delta_H U H λ H = v H = u H − δ H , so that a triangle inequality gives
∥ U H λ H ∥ a H ≤ ∥ δ H ∥ a H + ∥ u H ∥ a H ≲ ∣ v h ∣ 1 , Ω , \lVert\mathcal{U}_H\lambda_H\rVert_{a_H}\le\lVert\delta_H\rVert_{a_H}+\lVert u_H\rVert_{a_H}\lesssim\lvert v_h\rvert_{1,\Omega}, ∥ U H λ H ∥ a H ≤ ∥ δ H ∥ a H + ∥ u H ∥ a H ≲ ∣ v h ∣ 1 , Ω ,
where the bubble term is bounded by Lemma 7.6, and the term u H = J H v h u_H=\mathcal{J}_Hv_h u H = J H v h by the continuity of a H a_H a H given by Lemma 7.2 together with the boundedness (7.11). Finally, we note that, by definition of R H \mathcal{R}_H R H , ( U H λ H − R H ∘ U H λ H , 1 ) T = 0 (\mathcal{U}_H\lambda_H-\mathcal{R}_H\circ\mathcal{U}_H\lambda_H,1)_T=0 ( U H λ H − R H ∘ U H λ H , 1 ) T = 0 for all T ∈ T H T\in\mathcal{T}_H T ∈ T H , and thus we can apply a Poincaré inequality (4.2) to obtain
∥ U H λ H − R H ∘ U H λ H ∥ L 2 ( Ω ) ≲ H ∣ U H λ H − R H ∘ U H λ H ∣ 1 , T H . \lVert\mathcal{U}_H\lambda_H-\mathcal{R}_H\circ\mathcal{U}_H\lambda_H\rVert_{L^2(\Omega)}
\lesssim H\lvert\mathcal{U}_H\lambda_H-\mathcal{R}_H\circ\mathcal{U}_H\lambda_H\rvert_{1,\mathcal{T}_H}. ∥ U H λ H − R H ∘ U H λ H ∥ L 2 ( Ω ) ≲ H ∣ U H λ H − R H ∘ U H λ H ∣ 1 , T H .
Indeed, for r = 1 r=1 r = 1 the full H 1 ( T H ) H^1(\mathcal{T}_H) H 1 ( T H ) norm is controlled by the seminorm bound together with the L 2 L^2 L 2 bound and H ≤ 1 H\le1 H ≤ 1 , while for r = 0 r=0 r = 0 the L 2 L^2 L 2 bound alone gives the claim. □
Lemma 7.8 (Control of the jumps). For all v H = ( v T H , v F H ) ∈ V H v_H=(v_{\mathcal{T}_H},v_{\mathcal{F}_H})\in V_H v H = ( v T H , v F H ) ∈ V H ,
∑ F ∈ F H H F − 1 ∥ ⟦ v T H ⟧ ∥ F 2 + ∑ F ∈ F H H F − 1 ∥ ⟦ R H v H ⟧ F 2 ≲ ∥ v H ∥ h h o , H 2 . \sum_{F\in\mathcal{F}_H}H_F^{-1}\lVert\llbracket v_{\mathcal{T}_H}\rrbracket\rVert_F^2+\sum_{F\in\mathcal{F}_H}H_F^{-1}\lVert\llbracket\mathcal{R}_Hv_H\rrbracket_F^2\lesssim\lVert v_H\rVert_{\mathrm{hho},H}^2. F ∈ F H ∑ H F − 1 ∥ [ [ v T H ] ] ∥ F 2 + F ∈ F H ∑ H F − 1 ∥ [ [ R H v H ] ] F 2 ≲ ∥ v H ∥ hho , H 2 .
Proof. The proof can be found in [5 Lemma 14] , where the bound is stated with the uniform coarse mesh size H H H in place of H F H_F H F . The two are equivalent by Assumption 3.1(i). □
Lemma 7.9. For both choices of Θ H : M H → P q + 1 ( T H ) \Theta_H:M_H\to\mathbb{P}^{q+1}(\mathcal{T}_H) Θ H : M H → P q + 1 ( T H ) in Definition 7.4, namely Θ H = U H \Theta_H=\mathcal{U}_H Θ H = U H and Θ H = R H ∘ U H \Theta_H=\mathcal{R}_H\circ\mathcal{U}_H Θ H = R H ∘ U H , we have that, for all λ H ∈ M H \lambda_H\in M_H λ H ∈ M H , the following bounds hold:
∣ Θ H λ H ∣ 1 , T H 2 ≲ ∥ λ H ∥ a H 2 , (40) \lvert\Theta_H\lambda_H\rvert_{1,\mathcal{T}_H}^2\lesssim\lVert\lambda_H\rVert_{a_H}^2, \tag*{(40)} ∣ Θ H λ H ∣ 1 , T H 2 ≲ ∥ λ H ∥ a H 2 , (40) ∑ F ∈ F H H F − 1 ∥ ⟦ Θ H λ H ⟧ ∥ F 2 ≲ ∥ λ H ∥ a H 2 . (41) \sum_{F\in\mathcal{F}_H}H_F^{-1}\lVert\llbracket\Theta_H\lambda_H\rrbracket\rVert_F^2\lesssim\lVert\lambda_H\rVert_{a_H}^2. \tag*{(41)} F ∈ F H ∑ H F − 1 ∥ [ [ Θ H λ H ] ] ∥ F 2 ≲ ∥ λ H ∥ a H 2 . (41)
Proof. We first prove (7.12). For Θ H = R H ∘ U H \Theta_H=\mathcal{R}_H\circ\mathcal{U}_H Θ H = R H ∘ U H , the gradient of the reconstruction is the first term of the local bilinear form (7.3), so that ∣ R T U T λ H ∣ 1 , T 2 ≤ a T ( λ H , λ H ) \lvert\mathcal{R}_T\mathcal{U}_T\lambda_H\rvert_{1,T}^2\le a_T(\lambda_H,\lambda_H) ∣ R T U T λ H ∣ 1 , T 2 ≤ a T ( λ H , λ H ) , and summing over T ∈ T H T\in\mathcal{T}_H T ∈ T H gives the bound. For Θ H = U H \Theta_H=\mathcal{U}_H Θ H = U H , the bound follows from (7.9) applied to U H λ H \mathcal{U}_H\lambda_H U H λ H and summed over T ∈ T H T\in\mathcal{T}_H T ∈ T H . Then Lemma 7.8 applied to v H = U H λ H v_H=\mathcal{U}_H\lambda_H v H = U H λ H , together with the norm equivalence of Lemma 7.2, gives (7.13) for both choices of Θ H \Theta_H Θ H . □
The following three lemmas are the counterparts of Lemmas 6.5 and 6.6. The reconstruction degree q + 1 q+1 q + 1 may exceed the fine polynomial degree p p p , and does so whenever q ≥ p q\ge p q ≥ p , which includes the choice q = p q=p q = p made in our experiments. This case is covered by the bounds of Lemmas 6.4–6.6, which hold for an arbitrary coarse polynomial degree k k k .
Lemma 7.10. For both choices of Θ H \Theta_H Θ H in Definition 7.4 and all λ H ∈ M H \lambda_H\in M_H λ H ∈ M H , the prolongation operator I H h h h o I_{Hh}^{\mathrm{hho}} I H h hho satisfies
∥ I H h h h o λ H ∥ H 1 ( Ω ) 2 ≲ H h ∥ λ H ∥ a H 2 . \lVert I_{Hh}^{\mathrm{hho}}\lambda_H\rVert_{H^1(\Omega)}^2\lesssim\frac{H}{h}\lVert\lambda_H\rVert_{a_H}^2. ∥ I H h hho λ H ∥ H 1 ( Ω ) 2 ≲ h H ∥ λ H ∥ a H 2 . Proof. Set v H = Θ H λ H ∈ P q + 1 ( T H ) v_H=\Theta_H\lambda_H\in\mathbb{P}^{q+1}(\mathcal{T}_H) v H = Θ H λ H ∈ P q + 1 ( T H ) , so that I H h h h o λ H = I H h d g v H I_{Hh}^{\mathrm{hho}}\lambda_H=I_{Hh}^{\mathrm{dg}}v_H I H h hho λ H = I H h dg v H . Since I H h d g v H ∈ H 0 1 ( Ω ) I_{Hh}^{\mathrm{dg}}v_H\in H_0^1(\Omega) I H h dg v H ∈ H 0 1 ( Ω ) , a Poincaré inequality and the triangle inequality give
∥ I H h h h o λ H ∥ H 1 ( Ω ) ≲ ∣ I H h d g v H ∣ 1 , Ω ≤ ∣ v H − I H h d g v H ∣ 1 , T H + ∣ v H ∣ 1 , T H . \lVert I_{Hh}^{\mathrm{hho}}\lambda_H\rVert_{H^1(\Omega)}
\lesssim\lvert I_{Hh}^{\mathrm{dg}}v_H\rvert_{1,\Omega}
\le\lvert v_H-I_{Hh}^{\mathrm{dg}}v_H\rvert_{1,\mathcal{T}_H}+\lvert v_H\rvert_{1,\mathcal{T}_H}. ∥ I H h hho λ H ∥ H 1 ( Ω ) ≲ ∣ I H h dg v H ∣ 1 , Ω ≤ ∣ v H − I H h dg v H ∣ 1 , T H + ∣ v H ∣ 1 , T H . By Lemma 6.4 with r = 1 r=1 r = 1 and k = q + 1 k=q+1 k = q + 1 , together with h ≤ H T h\le H_T h ≤ H T ,
∥ I H h h h o λ H ∥ H 1 ( Ω ) 2 ≲ ∑ F ∈ F H h − 1 ∥ ⟦ Θ H λ H ⟧ ∥ F 2 + ∣ Θ H λ H ∣ 1 , T H 2 . \lVert I_{Hh}^{\mathrm{hho}}\lambda_H\rVert_{H^1(\Omega)}^2
\lesssim\sum_{F\in\mathcal{F}_H}h^{-1}\lVert\llbracket\Theta_H\lambda_H\rrbracket\rVert_F^2+\lvert\Theta_H\lambda_H\rvert_{1,\mathcal{T}_H}^2. ∥ I H h hho λ H ∥ H 1 ( Ω ) 2 ≲ F ∈ F H ∑ h − 1 ∥ [ [ Θ H λ H ] ] ∥ F 2 + ∣ Θ H λ H ∣ 1 , T H 2 .
Since H F ≃ H H_F \simeq H H F ≃ H , the jump term satisfies
∑ F ∈ F H h − 1 ∥ ⟦ Θ H λ H ⟧ ∥ F 2 = ∑ F ∈ F H H F h H F − 1 ∥ ⟦ Θ H λ H ⟧ ∥ F 2 ≲ H h ∑ F ∈ F H H F − 1 ∥ ⟦ Θ H λ H ⟧ ∥ F 2 ≲ H h ∥ λ H ∥ a H 2 , \sum_{F\in\mathcal{F}_H} h^{-1}\lVert\llbracket\Theta_H\lambda_H\rrbracket\rVert_F^2
= \sum_{F\in\mathcal{F}_H} \frac{H_F}{h}H_F^{-1}\lVert\llbracket\Theta_H\lambda_H\rrbracket\rVert_F^2
\lesssim\frac{H}{h}\sum_{F\in\mathcal{F}_H}H_F^{-1}\lVert\llbracket\Theta_H\lambda_H\rrbracket\rVert_F^2
\lesssim\frac{H}{h}\lVert\lambda_H\rVert_{a_H}^2, F ∈ F H ∑ h − 1 ∥ [ [ Θ H λ H ] ] ∥ F 2 = F ∈ F H ∑ h H F H F − 1 ∥ [ [ Θ H λ H ] ] ∥ F 2 ≲ h H F ∈ F H ∑ H F − 1 ∥ [ [ Θ H λ H ] ] ∥ F 2 ≲ h H ∥ λ H ∥ a H 2 ,
by (7.13), and the volume term is bounded by (7.12).
Lemma 7.11. Given v h ∈ V h v_h\in V_h v h ∈ V h , let λ H : = π F H q v h ∈ M H \lambda_H:=\pi_{F_H}^qv_h\in M_H λ H := π F H q v h ∈ M H . Then, for both choices of Θ H \Theta_H Θ H in Definition 7.4, the prolongation operator I H h r h o I_{Hh}^{\mathrm{rho}} I H h rho satisfies
∥ v h − I H h r h o λ H ∥ L 2 ( Ω ) 2 ≲ H 2 ∣ v h ∣ 1 , Ω 2 and ∥ v h − I H h r h o λ H ∥ H 1 ( Ω ) 2 ≲ H h ∣ v h ∣ 1 , Ω 2 . \lVert v_h-I_{Hh}^{\mathrm{rho}}\lambda_H\rVert_{L^2(\Omega)}^2\lesssim H^2|v_h|_{1,\Omega}^2
\quad\text{and}\quad
\lVert v_h-I_{Hh}^{\mathrm{rho}}\lambda_H\rVert_{H^1(\Omega)}^2\lesssim\frac{H}{h}|v_h|_{1,\Omega}^2. ∥ v h − I H h rho λ H ∥ L 2 ( Ω ) 2 ≲ H 2 ∣ v h ∣ 1 , Ω 2 and ∥ v h − I H h rho λ H ∥ H 1 ( Ω ) 2 ≲ h H ∣ v h ∣ 1 , Ω 2 . Proof. Since I H h r h o λ H = I H h d g ( Θ H λ H ) I_{Hh}^{\mathrm{rho}}\lambda_H=I_{Hh}^{\mathrm{dg}}(\Theta_H\lambda_H) I H h rho λ H = I H h dg ( Θ H λ H ) , this is Lemma 6.6 applied to v H = Θ H λ H v_H=\Theta_H\lambda_H v H = Θ H λ H , whose hypothesis (6.8) is Lemma 7.7. □
Lemma 7.12. Given v h ∈ V h v_h\in V_h v h ∈ V h , let λ H = π F H q v h ∈ M H \lambda_H=\pi_{F_H}^qv_h\in M_H λ H = π F H q v h ∈ M H . Then we have that
∥ λ H ∥ a H ≲ ∣ v h ∣ 1 , Ω . \lVert\lambda_H\rVert_{a_H}\lesssim|v_h|_{1,\Omega}. ∥ λ H ∥ a H ≲ ∣ v h ∣ 1 , Ω . Proof. Consider the hybrid function J H v h = ( π T H q + 1 v h , π F H q v h ) ∈ V H J_Hv_h=(\pi_{T_H}^{q+1}v_h,\pi_{F_H}^qv_h)\in V_H J H v h = ( π T H q + 1 v h , π F H q v h ) ∈ V H , whose skeleton component is precisely λ H \lambda_H λ H . By the energy minimisation property (7.6), the continuity of a H a_H a H given by Lemma 7.2 and the boundedness (7.11) of the HHO interpolator, we obtain
∥ λ H ∥ a H 2 = a H ( λ H , λ H ) ≤ a H ( J H v h , J H v h ) ≲ ∥ J H v h ∥ h h o , H 2 ≲ ∣ v h ∣ 1 , Ω 2 , \lVert\lambda_H\rVert_{a_H}^2=a_H(\lambda_H,\lambda_H)\leq a_H(J_Hv_h,J_Hv_h)\lesssim\lVert J_Hv_h\rVert_{hho,H}^2\lesssim|v_h|_{1,\Omega}^2, ∥ λ H ∥ a H 2 = a H ( λ H , λ H ) ≤ a H ( J H v h , J H v h ) ≲ ∥ J H v h ∥ hh o , H 2 ≲ ∣ v h ∣ 1 , Ω 2 , which concludes the proof. □
Main result
Theorem 7.13. The HHO discretisation, with the smoother described in Section 5 and the prolongation I H h = I H h r h o I_{Hh}=I_{Hh}^{\mathrm{rho}} I H h = I H h rho of Definition 7.4, fulfils the assumptions in Lemma 3.9.
Proof. That the smoother satisfies (3.2) is given by Corollary 5.3 or 5.4, depending on the smoother at hand.
Let λ H ∈ M H \lambda_H\in M_H λ H ∈ M H . By Lemma 7.10,
∥ I H h r h o λ H ∥ a 2 = ∣ I H h r h o λ H ∣ 1 , Ω 2 ≲ H h ∥ λ H ∥ a H 2 , \lVert I_{Hh}^{\mathrm{rho}}\lambda_H\rVert_a^2=|I_{Hh}^{\mathrm{rho}}\lambda_H|_{1,\Omega}^2\lesssim\frac{H}{h}\lVert\lambda_H\rVert_{a_H}^2, ∥ I H h rho λ H ∥ a 2 = ∣ I H h rho λ H ∣ 1 , Ω 2 ≲ h H ∥ λ H ∥ a H 2 , which proves (3.3).
We now turn to (3.4). Given v h ∈ V h v_h\in V_h v h ∈ V h , we choose as coarse approximant λ H = π F H q v h ∈ M H \lambda_H=\pi_{F_H}^qv_h\in M_H λ H = π F H q v h ∈ M H . Lemma 7.11, together with ∣ v h ∣ 1 , Ω = ∥ v h ∥ a |v_h|_{1,\Omega}=\lVert v_h\rVert_a ∣ v h ∣ 1 , Ω = ∥ v h ∥ a , gives
∥ v h − I H h r h o λ H ∥ L 2 ( Ω ) 2 ≲ H 2 ∥ v h ∥ a 2 and ∥ v h − I H h r h o λ H ∥ H 1 ( Ω ) 2 ≲ H h ∥ v h ∥ a 2 . \lVert v_h-I_{Hh}^{\mathrm{rho}}\lambda_H\rVert_{L^2(\Omega)}^2\lesssim H^2\lVert v_h\rVert_a^2
\quad\text{and}\quad
\lVert v_h-I_{Hh}^{\mathrm{rho}}\lambda_H\rVert_{H^1(\Omega)}^2\lesssim\frac{H}{h}\lVert v_h\rVert_a^2. ∥ v h − I H h rho λ H ∥ L 2 ( Ω ) 2 ≲ H 2 ∥ v h ∥ a 2 and ∥ v h − I H h rho λ H ∥ H 1 ( Ω ) 2 ≲ h H ∥ v h ∥ a 2 . Finally, Lemma 7.12 gives ∥ λ H ∥ a H ≲ ∣ v h ∣ 1 , Ω = ∥ v h ∥ a \lVert\lambda_H\rVert_{a_H}\lesssim|v_h|_{1,\Omega}=\lVert v_h\rVert_a ∥ λ H ∥ a H ≲ ∣ v h ∣ 1 , Ω = ∥ v h ∥ a , which proves (3.4)2 , 3 _{2,3} 2 , 3 and (3.4)1 _1 1 , respectively. □
Remark 7.14. Analogously to the DG case, Theorem 7.13 together with Lemma 3.9 yields the final bound
κ ( P a d d , H H O − 1 A h ) ≲ ( 1 + λ 1 H h ) ( H 2 h 2 + 1 λ 0 ) , \kappa(P_{\mathrm{add,HHO}}^{-1}A_h)\lesssim\left(1+\lambda_1\frac{H}{h}\right)\left(\frac{H^2}{h^2}+\frac{1}{\lambda_0}\right), κ ( P add , HHO − 1 A h ) ≲ ( 1 + λ 1 h H ) ( h 2 H 2 + λ 0 1 ) ,
for the point-Jacobi and vertex-star patch smoothers considered in this work, for which c D , 0 ≃ h − 2 c_{D,0}\simeq h^{-2} c D , 0 ≃ h − 2 , c D , 1 = 0 c_{D,1}=0 c D , 1 = 0 and c D 2 ≃ 1 c_D^2\simeq1 c D 2 ≃ 1 , and again O ( H 3 / h 3 ) O(H^3/h^3) O ( H 3 / h 3 ) for an exact coarse solve.
Coarse solvers and geometric multigrid
Sections 5 to 7 supply all ingredients of Lemma 3.9 except the ones related to the accuracy of the coarse solver, that is { λ 0 , λ 1 } \{\lambda_0,\lambda_1\} { λ 0 , λ 1 } in Assumption 3.7.
A first approach is to solve the coarse problem exactly, which gives B H = A H − 1 B_H=A_H^{-1} B H = A H − 1 and thus λ 0 = λ 1 = 1 \lambda_0=\lambda_1=1 λ 0 = λ 1 = 1 . This requires the exact solution of a problem that is smaller than the original one by a factor ( H / h ) d (H/h)^d ( H / h ) d .
In real applications, this is often too costly, motivating the use of iterative solvers for the coarse problem. Therefore, scalable iterative solvers for polytopal methods on agglomerated meshes are required to efficiently solve the coarse problem.
In this work, we will employ GMG solvers for this purpose. GMG is a family of multilevel solvers defined on hierarchies of nested meshes, where each level corresponds to a different resolution of the computational domain. Recent advances have demonstrated the effectiveness of GMG on agglomeration-based hierarchies for both HHO [5 ] and DG [3 ] methods. These works prove bounds for the spectrum of B H A H B_HA_H B H A H when B H B_H B H is the multigrid V-cycle with appropriate prolongation operators and smoothers. These bounds are independent of the number of levels of the hierarchy and the size H H H of the finest problem (here our coarse problem A H A_H A H ). Instead, these bounds mostly depend on the coarsening ratio, which can be kept constant throughout the hierarchy.
Geometric multigrid coarse solver
We now briefly discuss the multigrid algorithm, including the choice of prolongation operators and smoothers for the GMG coarse solver that will be used in the numerical experiments. We refer to [3 , 5 ] for details.
The mesh T H \mathcal{T}_H T H , which is the coarse mesh of the two-level method, is the finest mesh seen by the coarse solver. Starting from it, we construct by further agglomeration a hierarchy of nested meshes { T ℓ } ℓ = 1 L \{\mathcal{T}_\ell\}_{\ell=1}^{L} { T ℓ } ℓ = 1 L , with T 1 = T H \mathcal{T}_1=\mathcal{T}_H T 1 = T H at the finest level ℓ = 1 \ell=1 ℓ = 1 and T L \mathcal{T}_L T L at the coarsest level ℓ = L \ell=L ℓ = L . For either DG or HHO, we construct on each level ℓ \ell ℓ a discrete space V ℓ \mathcal{V}_\ell V ℓ and its associated operator A ℓ A_\ell A ℓ , analogously to the constructions in § 6 and § 7 , respectively.
For ℓ < L \ell<L ℓ < L , let I ℓ : V ℓ + 1 → V ℓ I_\ell:\mathcal{V}_{\ell+1}\to\mathcal{V}_\ell I ℓ : V ℓ + 1 → V ℓ denote the prolongation operator from level ℓ + 1 \ell+1 ℓ + 1 to level ℓ \ell ℓ , and I ℓ ∗ I_\ell^* I ℓ ∗ its adjoint. For DG, we follow [3 ] and take I ℓ I_\ell I ℓ to be the injection operator, since we have V ℓ + 1 ⊂ V ℓ \mathcal{V}_{\ell+1}\subset\mathcal{V}_\ell V ℓ + 1 ⊂ V ℓ . For HHO, more complicated prolongation operators are required due to the hybrid nature of the method. In our experiments, we consider I ℓ I_\ell I ℓ as described in [5 Section 4.2] , which given a hybrid coarse function μ \mu μ , constructs its fine-level prolongation by averaging the cell values of its inverse static condensation U μ U\mu U μ over fine faces. The construction is analogous to the one in Definition 7.4 , with the averaging operator W h W_h W h replaced by an L 2 L^2 L 2 face-averaging operator. Operators of this kind are common in the multilevel literature for hybrid methods, and can be found in, e.g. [18 , 19 , 29 ] .
We turn to the choice of smoothers. In [3 ] , a standard point-Jacobi smoother is used. In this work, we will instead employ the block-Jacobi smoothers described in [5 Section 4.3] for both the HHO and DG implementations. These are defined as follows: on a level ℓ < L \ell<L ℓ < L , let D ℓ D_\ell D ℓ be defined as in (5.1), associated with the set D ℓ \mathcal{D}_\ell D ℓ of macro-vertices of the coarse mesh, that is, vertices shared by multiple agglomerated cells (or interfaces in the sense of Section 3). The subdomains then correspond to the vertex stars around each macro-vertex. From D ℓ \mathcal{D}_\ell D ℓ we can define its associated damped Richardson smoother on level ℓ \ell ℓ , namely
S ℓ , n s , ω ≔ ( 1 − ω D ℓ − 1 A ℓ ) n s , (42) S_{\ell,n_s,\omega} \coloneqq\left(1-\omega D_\ell^{-1}A_\ell\right)^{n_s}, \tag*{(42)} S ℓ , n s , ω : = ( 1 − ω D ℓ − 1 A ℓ ) n s , (42)
where 1 \mathbb{1} 1 is the identity on V ℓ \mathcal{V}_\ell V ℓ , ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) is the damping parameter, and n s n_s n s is the number of smoothing steps.
With these two ingredients, we can define the GMG V-cycle through its error propagation operator. Let B L = A L − 1 B_L=A_L^{-1} B L = A L − 1 be the exact solver on the coarsest level. Then for the levels ℓ = L − 1 , … , 1 \ell=L-1,\ldots,1 ℓ = L − 1 , … , 1 , we have
1 − B ℓ A ℓ ≔ S ℓ , n s , ω ( 1 − I ℓ B ℓ + 1 I ℓ ∗ A ℓ ) S ℓ , n s , ω . (43) \mathbb{1}-B_\ell A_\ell\coloneqq S_{\ell,n_s,\omega}\left(\mathbb{1}-I_\ell B_{\ell+1}I_\ell^*A_\ell\right)S_{\ell,n_s,\omega}. \tag*{(43)} 1 − B ℓ A ℓ : = S ℓ , n s , ω ( 1 − I ℓ B ℓ + 1 I ℓ ∗ A ℓ ) S ℓ , n s , ω . (43)
We can then set B H = B 1 B_H=B_1 B H = B 1 . To describe the two multilevel algorithms below in a single notation, we add the conforming problem of Sect. 2 as level ℓ = 0 \ell=0 ℓ = 0 of the hierarchy, setting T 0 = T h \mathcal{T}_0=\mathcal{T}_h T 0 = T h , V 0 = V h \mathcal{V}_0=V_h V 0 = V h , A 0 = A h A_0=A_h A 0 = A h , D 0 = D h D_0=D_h D 0 = D h and I 0 = I H h I_0=I_{Hh} I 0 = I H h , so that the full hierarchy is { T ℓ } ℓ = 0 L \{\mathcal{T}_\ell\}_{\ell=0}^{L} { T ℓ } ℓ = 0 L and the GMG coarse solver acts on levels 1 1 1 to L L L . This is the numbering used in Sect. 9.
The additive algorithm
With the GMG V-cycle as coarse solver, the additive preconditioner (3.1) reads
P a d d − 1 = I 0 B 1 I 0 ∗ + D 0 − 1 , P_{\mathrm{add}}^{-1}=I_0B_1I_0^*+D_0^{-1}, P add − 1 = I 0 B 1 I 0 ∗ + D 0 − 1 ,
an ( L + 1 ) (L+1) ( L + 1 ) -level algorithm in which level 0 is treated additively and levels 1 to L L L multiplicatively, by the V-cycle. Its condition number follows from Lemma 3.9 and the contraction factor of the V-cycle. For a convergent symmetric multigrid iteration, if its error propagation operator is a H a_H a H -self-adjoint and positive semi-definite with contraction factor ρ < 1 \rho<1 ρ < 1 , then
( 1 − ρ ) ( A H − 1 μ H , μ H ) ≤ ( B H μ H , μ H ) ≤ ( A H − 1 μ H , μ H ) ∀ μ H ∈ V H , (1-\rho)(A_H^{-1}\mu_H,\mu_H)\leq(B_H\mu_H,\mu_H)\leq(A_H^{-1}\mu_H,\mu_H)\quad\forall\mu_H\in V_H, ( 1 − ρ ) ( A H − 1 μ H , μ H ) ≤ ( B H μ H , μ H ) ≤ ( A H − 1 μ H , μ H ) ∀ μ H ∈ V H ,
that is, λ 1 ≤ 1 \lambda_1\leq1 λ 1 ≤ 1 and λ 0 = 1 − ρ \lambda_0=1-\rho λ 0 = 1 − ρ , so that
κ ( P a d d − 1 A h ) ≲ ( c D 2 + H h ) ( H 2 h 2 + 1 1 − ρ ) . \kappa(P_{\mathrm{add}}^{-1}A_h)\lesssim\left(c_D^2+\frac{H}{h}\right)\left(\frac{H^2}{h^2}+\frac{1}{1-\rho}\right). κ ( P add − 1 A h ) ≲ ( c D 2 + h H ) ( h 2 H 2 + 1 − ρ 1 ) .
A fully multiplicative algorithm
The same ingredients give a fully multiplicative variant by treating level 0 as one more level of the V-cycle. Let S 0 , n s , ω = ( I − ω D 0 − 1 A 0 ) n s S_{0,n_s,\omega} = (I-\omega D_0^{-1}A_0)^{n_s} S 0 , n s , ω = ( I − ω D 0 − 1 A 0 ) n s be the damped Richardson smoother (42) on level 0, which we also denote S h , n s , ω S_{h,n_s,\omega} S h , n s , ω in Sect. 9. Carrying the recursion (43) one level further defines the multiplicative auxiliary space preconditioner P m u l t − 1 ≔ B 0 P_{\mathrm{mult}}^{-1} \coloneqq B_0 P mult − 1 : = B 0 , that is,
I − P m u l t − 1 A 0 = S 0 , n s , ω ( I − I 0 B 1 I 0 ∗ A 0 ) S 0 , n s , ω . I-P_{\mathrm{mult}}^{-1}A_0 = S_{0,n_s,\omega}(I-I_0B_1I_0^*A_0)S_{0,n_s,\omega}. I − P mult − 1 A 0 = S 0 , n s , ω ( I − I 0 B 1 I 0 ∗ A 0 ) S 0 , n s , ω .
Both algorithms therefore share the hierarchy, the transfer operators, the smoothers and the coarse solver of Sect. 8.1, and differ only in whether level 0 is treated additively or multiplicatively. Although we do not provide the analysis for P m u l t P_{\mathrm{mult}} P mult , we will benchmark its performance alongside P a d d P_{\mathrm{add}} P add in the numerical experiments.
Numerical results
We now test the preconditioners numerically in two and three dimensions, on several mesh families and polynomial degrees, and report iteration counts as a function of the mesh size and of the coarsening ratio. To this end, we introduce three families of two-dimensional mesh hierarchies.
Cartesian meshes. First, we consider mesh hierarchies for which the agglomeration is regular and the coarse cells have flat interfaces. To this end, we consider d d d -dimensional Cartesian meshes on the unit cuboid Ω = [ 0 , 1 ] d \Omega=[0,1]^d Ω = [ 0 , 1 ] d . The hierarchy is then built recursively agglomerating blocks of 2 d 2^d 2 d neighbouring cells. After ℓ \ell ℓ agglomeration steps, the coarse mesh T ℓ \mathcal{T}_\ell T ℓ is composed of general polytopes with 2 d 2d 2 d flat interfaces, each composed of ( H / h ) d − 1 (H/h)^{d-1} ( H / h ) d − 1 flat ( d − 1 ) (d-1) ( d − 1 ) -dimensional cuboids, and the coarsening ratio is exactly H / h = 2 ℓ H/h=2^\ell H / h = 2 ℓ .
Simplexified Cartesian meshes with arbitrary agglomeration. Starting from the same Cartesian meshes, which we simplexify, we now let the agglomeration be arbitrary. On each level, connected clusters of cells are agglomerated into polygonal elements, which are not required to be convex or shape-regular. Finding optimal agglomeration strategies for polytopal meshes remains an open research question [2 , 22 ] . Within this work, the colouring of the mesh into clusters is performed using a hierarchical clustering algorithm with complete-linkage clustering and optimal branch ordering [6 ] , provided by the Julia package Clustering.jl [25 ] . The hierarchy is then built by applying the clustering algorithm recursively. The target reduction in the number of cells is specified per direction by a factor θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , so that each level reduces the target number of cells by θ d \theta^d θ d and thus the coarsening ratio between levels is H / h ≈ θ − ℓ H/h\approx\theta^{- \ell} H / h ≈ θ − ℓ . Due to the nature of these algorithms, the actual cluster sizes vary across the different agglomerates, but are on average close to the target. We consider θ = 0.5 \theta=0.5 θ = 0.5 , for which the measured (mean) ratios are within reasonable proximity of the nominal 2 ℓ 2^\ell 2 ℓ .
Complicated geometries with arbitrary agglomeration. The third family starts from meshes T h \mathcal{T}_h T h of Australia, generated using the Julia package GeoGmsh.jl, which extracts the contour from publicly available shapefiles and then meshes the resulting geometry using Gmsh [23 ] . The coarsening is performed in the same way as in the previous example, but now using a k-means clustering algorithm provided by the Julia package Clustering.jl [25 ] . For this set of experiments, we consider θ = 0.25 \theta=0.25 θ = 0.25 , so that H / h ≈ 4 H/h\approx4 H / h ≈ 4 .
In three dimensions, we consider the three-dimensional counterparts of the Cartesian and simplexified meshes, with the same agglomeration strategies, on the unit cube Ω = [ 0 , 1 ] 3 \Omega=[0,1]^3 Ω = [ 0 , 1 ] 3 .
For each family of meshes, we generate several initial meshes of increasing resolution. For each initial mesh T h \mathcal{T}_h T h , we build by agglomeration an associated hierarchy { T ℓ } ℓ = 0 L \{\mathcal{T}_\ell\}_{\ell=0}^L { T ℓ } ℓ = 0 L with T 0 = T h \mathcal{T}_0=\mathcal{T}_h T 0 = T h and T 1 = T H \mathcal{T}_1=\mathcal{T}_H T 1 = T H , so that { T ℓ } ℓ = 1 L \{\mathcal{T}_\ell\}_{\ell=1}^L { T ℓ } ℓ = 1 L is the AMG hierarchy of Section 8. Level ℓ = 0 \ell=0 ℓ = 0 carries the conforming discretisation, and levels ℓ ≥ 1 \ell\geq1 ℓ ≥ 1 the non-conforming ones. The number of cells at every agglomeration level, for each family and each initial mesh, is collected in Table 1 . Examples of these hierarchies are shown in Figure 1 for the simplexified Cartesian and Australian hierarchies.
Table 1. Mesh hierarchies used throughout Sect. 9. Level ℓ = 0 \ell= 0 ℓ = 0 is the fine mesh and ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 the agglomerated levels, so the auxiliary space of the two-level method sits at the ℓ \ell ℓ whose coarsening ratio is quoted in Table 2, and the coarsest level of an n l e v n_{\mathrm{lev}} n lev -level hierarchy of Table 3 is ℓ = n l e v − 1 \ell= n_{\mathrm{lev}} - 1 ℓ = n lev − 1 . CG DoFs are those of the conforming fine space, DG and HHO DoFs those of the coarse space built on each agglomerated level. Entries marked “—” are levels the hierarchy does not provide.
Figure 1. Agglomerated hierarchies for the Mid simplexified Cartesian mesh with θ = 0.5 \theta= 0.5 θ = 0.5 (top) and the Mid Australian mesh with θ = 0.25 \theta= 0.25 θ = 0.25 (bottom). Levels ℓ = 0 \ell= 0 ℓ = 0 to 3 3 3 , from left to right.
On each initial mesh T h = T 0 \mathcal{T}_h=\mathcal{T}_0 T h = T 0 , we consider the conforming discretisation of Section 2 for a given polynomial degree p p p . Then, on each level ℓ ≥ 1 \ell\geq1 ℓ ≥ 1 of the hierarchy we build a space V ℓ V_\ell V ℓ using either the DG or HHO methods, as described in Sections 6 and 7, respectively. In the tables these two variants are labelled CG-DG and CG-HHO. In both cases, the averaging operator W h W_h W h in the prolongation uses the uniform weights α T ( v ) = ∣ N h ( v ) ∣ − 1 \alpha_T(v)=|\mathcal{N}_h(v)|^{-1} α T ( v ) = ∣ N h ( v ) ∣ − 1 of Remark 6.2, which is the classical Oswald interpolation operator. For the DG method, we use the penalty parameter σ = 10 ( q + 1 ) 2 \sigma=10(q+1)^2 σ = 10 ( q + 1 ) 2 throughout, and modify the HHO stabilisation weights to be ≃ ( q + 1 ) 2 / H \simeq(q+1)^2/H ≃ ( q + 1 ) 2 / H . These are typical choices in the literature to obtain a suitable scaling of the stabilisation term with respect to the polynomial order. Neither of these changes has an effect on the analysis, since polynomial order dependence was not tracked.
In the experiments below, we report the number of preconditioned flexible generalised minimal residual (FGMRES) iterations required to reduce the relative residual below 10 − 8 10^{-8} 1 0 − 8 . Using FGMRES is not necessary in theory, as the preconditioners are fixed linear operators, but it is a practical choice to obtain consistent results in the presence of round-off errors. The iteration counts are proxies for the condition number of the preconditioned system, as established by the convergence theory of Krylov methods.
Table 2.
Two-level auxiliary space preconditioners
For each mesh hierarchy, we consider the finest mesh T h \mathcal{T}_h T h and take T H \mathcal{T}_H T H to be any of the coarser meshes T ℓ \mathcal{T}_\ell T ℓ , ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 , in the hierarchy, so that the coarsening ratio is the product of the coarsening ratios of the intermediate levels. By doing this, we create a series of two-level problems with increasing coarsening ratios.
We test both the additive preconditioner P a d d P_{\mathrm{add}} P add of (2) and a multiplicative variant P m u l t P_{\mathrm{mult}} P mult , with the point-Jacobi and vertex-star patch (V-Patch) smoothers described in § 5 . In both cases the smoothing step consists of n s n_s n s iterations of the associated damped Richardson smoother S h , n s , ω S_{h,n_s,\omega} S h , n s , ω . For P a d d P_{\mathrm{add}} P add we take n s = 1 n_s = 1 n s = 1 and ω = 1 \omega= 1 ω = 1 , which recovers D h − 1 D_h^{-1} D h − 1 and matches the analysis of § 5 . For P m u l t P_{\mathrm{mult}} P mult we take n s = 5 n_s = 5 n s = 5 and ω = 0.1 \omega= 0.1 ω = 0.1 in two dimensions and ω = 0.05 \omega= 0.05 ω = 0.05 in three dimensions, as is common practice for GMG methods. In order to isolate the two-level behaviour of the preconditioner, we use a sparse LU factorisation to solve the coarse polytopal problem exactly, that is we set B H = A H − 1 B_H = A_H^{-1} B H = A H − 1 .
We report the iteration counts for all five mesh families and both coarse discretisations in Table 2. The columns are labelled by the nominal H / h = θ − ℓ H/h = \theta^{-\ell} H / h = θ − ℓ . At p = 1 p = 1 p = 1 the vertex-star patches reduce to single-DOF blocks, so the two smoothers are the same operator and a single smoother block is reported.
On the Cartesian families, where mesh regularity is preserved exactly, the results match the theory. For a fixed coarsening ratio the iteration counts are independent of the fine mesh, and they grow mildly and monotonically with H / h H/h H / h , well below the growth allowed by the bounds of § 6 and § 7 . On the unstructured families the behaviour is qualitatively the same, but the counts depend on the quality of the agglomeration. In particular, on the Fine Australian hierarchy the agglomeration quality at ℓ = 3 \ell= 3 ℓ = 3 is noticeably poorer, and as a consequence the iteration counts for HHO are significantly higher than at the other levels, including ℓ = 4 \ell= 4 ℓ = 4 . Comparing the smoothers, the iteration counts with the vertex-star patch smoother are insensitive to the polynomial degree, whereas point-Jacobi degrades markedly as the degree grows. Such p p p -robustness of patch smoothers is well documented for conforming discretisations [31 , 33 ] , but has not, to our knowledge, been analysed for our particular setting. The multiplicative variant P m u l t P_{\mathrm{mult}} P mult generally, but not uniformly, needs fewer iterations than P a d d P_{\mathrm{add}} P add .
Multilevel coarse solvers
We now replace the exact coarse solve by a single iteration of the GMG V-cycle described in § 8 . On the coarser GMG levels, we use the damped Richardson smoother S ℓ , n s , ω S_{\ell,n_s,\omega} S ℓ , n s , ω with n s = 5 n_s = 5 n s = 5 and ω = 0.1 \omega= 0.1 ω = 0.1 in two dimensions and ω = 0.05 \omega= 0.05 ω = 0.05 in three.
Iteration counts for the multilevel preconditioners are reported in Table 3 . Replacing the exact coarse solve by a single GMG V-cycle costs a handful of additional iterations. On the Cartesian families in two and three dimensions, and on the three-dimensional simplexified meshes, adding agglomeration levels leaves the counts unchanged, so neither the fine mesh size nor the number of levels affects them and the preconditioners are scalable. As in the two-level case, the quality of the agglomeration has a significant impact on the unstructured families. On the Fine Australian hierarchy, the DG iteration counts are constant for the two- and three-level hierarchies, increase noticeably when the level ℓ = 3 \ell= 3 ℓ = 3 is added, and stabilise afterwards, whereas the HHO variant is unaffected. This confirms that the quality of the agglomeration, rather than the number of levels, is what matters on the unstructured families.
Table 3. Multilevel preconditioners: iteration counts with the auxiliary space one agglomeration level above the fine mesh and a GMG coarse solver on the remaining levels, n l e v n_{\mathrm{lev}} n lev being the total number of levels, so that n l e v = 2 n_{\mathrm{lev}} = 2 n lev = 2 is the two-level method with an exact coarse solve. The fine-level smoother is V-Patch throughout. “—” marks depths the hierarchy does not provide.
(a) 2D Cartesian meshes
(b) 2D simplexified meshes
(c) Australia meshes
(d) 3D Cartesian meshes
(e) 3D simplexified meshes
Table 2 (PDF p. 24). Two-level preconditioners: iteration counts for the mesh families of Table 1, by coarse space, polynomial degree, smoother and nominal coarsening ratio H / h H/h H / h . “—” marks ratios the hierarchy does not provide.
Remark 9.1 (On the choice of constants). The DG penalty parameter σ \sigma σ and the smoother weights ω \omega ω used throughout this section are, by choice, not optimal. On most experiments the penalty can be taken smaller and the damping weights larger, both improving performance of the solver. To keep the results directly comparable across experiments, we have instead opted for a fixed set of parameters.
Tuning these parameters for a given problem would yield noticeably lower iteration counts than the ones reported.
Conclusions
We have introduced and analysed a family of multilevel auxiliary space preconditioners for conforming Lagrangian FE discretisations of elliptic problems. At the first level, the auxiliary problem is a non-conforming polytopal discretisation posed on an arbitrarily agglomerated coarse mesh, and at the subsequent levels that problem is solved by an agglomeration-based GMG method, so that the whole hierarchy is generated from the fine mesh by agglomeration alone. We have considered two polytopal discretisations, an SIPG DG method and a statically condensed mixed-order HHO method, the latter extending directly to HDG. In both cases, the prolongation is an element-wise interpolation onto the fine mesh followed by nodal averaging, preceded by a local potential reconstruction in the HHO case. Under standard regularity assumptions on the agglomerated mesh, we have proven that the preconditioner satisfies κ ≲ ( H / h ) 3 \kappa\lesssim(H/h)^3 κ ≲ ( H / h ) 3 , and κ ≲ ( H / h ) 2 \kappa\lesssim(H/h)^2 κ ≲ ( H / h ) 2 for the DG variant with penalty σ ≃ H / h \sigma\simeq H/h σ ≃ H / h , for point-Jacobi and vertex-star patch smoothers when the coarse problem is solved exactly. The GMG coarse solver enters these bounds only through the extreme eigenvalues of the preconditioned coarse problem, which are bounded independently of the number of levels by the results of [3 , 4 , 5 ] , so that the whole solver is scalable. Numerical experiments on Cartesian, simplexified and unstructured meshes of a complicated geometry, the last two with agglomerates generated by automatic clustering algorithms, corroborate the theory. The quality of the agglomeration has a visible effect on the preconditioner. Well-shaped agglomerates give iteration counts that are independent of the fine mesh size and of the number of levels, whereas poorly shaped ones increase them. Agglomeration strategies that guarantee well-shaped coarse cells are the main open question for the practical use of these preconditioners.
Acknowledgments
This research was partially funded by the Australian Government through the Australian Research Council (project numbers DP210103092 and DP220103160). This work was also supported by computational resources provided by the Australian Government through NCI and Pawsey under the NCMAS Merit Allocation Schemes.