Project topics and materials
Get Complete Project Material File(s) Now! »
An adaptive hp-re nement strategy with computable guaranteed bound on the error reduction factor
This chapter consists of the article Daniel et al. (2018a) published in the journal Computers & Mathematics with Applications, vol. 76 (2018) pp. 967-983, written with Alexandre Ern, Iain Smears and Martin Vohral k.
Abstract
We propose a new practical adaptive re nement strategy for hp- nite element approximations of elliptic problems. Following recent the-oretical developments in polynomial-degree-robust a posteriori error analysis, we solve two types of discrete local problems on vertex-based patches. The rst type involves the solution on each patch of a mixed nite element problem with homogeneous Neumann boundary condi-tions, which leads to an H(div; )-conforming equilibrated ux. This, in turn, yields a guaranteed upper bound on the error and serves to mark mesh vertices for re nement via Dor er’s bulk-chasing criterion. The second type of local problems involves the solution, on patches associated with marked vertices only, of two separate primal nite ele-ment problems with homogeneous Dirichlet boundary conditions, which serve to decide between h-, p-, or hp-re nement. Altogether, we show that these ingredients lead to a computable guaranteed bound on the ratio of the errors between successive re nements (error reduction fac-tor). In a series of numerical experiments featuring smooth and singular solutions, we study the performance of the proposed hp-adaptive strat-egy and observe exponential convergence rates. We also investigate the accuracy of our bound on the reduction factor by evaluating the ratio of the predicted reduction factor relative to the true error reduction, and we nd that this ratio is in general quite close to the optimal value of one.
Introduction
Adaptive discretization methods constitute an important tool in computa-tional science and engineering. Since the pioneering works on the hp- nite el-ement method by Gui and Babuska (1986b,a) and Babuska and Guo (1986a,b) in the 1980s, where it was shown that for one-dimensional problems hp-re nement leads to exponential convergence with respect to the number of degrees of freedom on a priori adapted meshes, there has been a great amount of work devoted to developing adaptive hp-re nement strategies based on a posteriori error estimates. Convergence of hp-adaptive nite element ap-proximations for elliptic problems, has, though, been addressed only very recently in Dor er and Heuveline (2007), Burg and Dor er (2011), and Bank et al. (2013). The rst optimality result we are aware of is by et al. Canuto et al. (2017a), where an important ingredient is the hp-coarsening routine by Binev (2013, 2018). These works extend to the hp-context the previous h-convergence and optimality results by Dor er (1996), Morin et al. (2002, 2003), Stevenson (2007), Cascon et al. (2008), Carstensen et al. (2014), see also Nochetto et al. (2009) and the references therein. It is worth mention-ing that most of the available convergence results are formulated for adaptive methods driven by residual-type a posteriori error estimators; other estimators have in particular been addressed by Cascon and Nochetto (2012) and Kreuzer and Siebert (2011).
A key ingredient for adaptive hp-re nement is a local criterion in each mesh cell marked for re nement that allows one to decide whether h-, p-, or hp-re nement should be performed. There is a substantial amount of such criteria proposed in the literature; a computational overview can be found in Mitchell and McClain (2014, 2011). Some of the mathematically moti-vated hp-decision criteria include, among others, those proposed by Eibner and Melenk (2007), Houston and Suli (2005) which both estimate the local regularity of the exact weak solution. Our proposed strategy ts into the group of algorithms based on solving local boundary value problems allowing us to forecast the bene ts of performing h- or p-re nement, as recently consid-ered in, e.g., Burg and Dor er (2011), Dor er and Heuveline (2007). Similarly to Dor er and Heuveline (2007), we use the local nite element spaces associ-ated with a speci c type of re nement to perform the above forecast and to take the local hp-re nement decision. We also mention the work of Demkowicz et al. (2002) for an earlier, yet more expensive, version of the look-ahead idea, where it is proposed to solve an auxiliary problem on a global nite element space corresponding to a mesh re ned uniformly either in h or in p.
In the present work, we focus on the Poisson model problem with (homo-geneous) Dirichlet boundary conditions. In weak form, the model problem reads as follows: Find u 2 H01( ) such that (ru; rv) = (f; v) 8v 2 H01( ); (1.1) where Rd, d = 2; 3, is a polygonal/polyhedral domain (open, bounded, and connected set) with a Lipschitz boundary, f 2 L2( ), H01( ) denotes the Sobolev space of all functions in L2( ) which have all their rst-order weak derivatives in L2( ) and a zero trace on @ , and ( ; ) stands for the L2( ) or [L2( )]d inner product. Our rst goal is to propose a reliable and computationally-e cient hp-adaptive strategy to approximate the model prob-lem (1.1) that hinges on the recent theoretical developments on polynomial-degree-robust a posteriori error estimates due to Braess et al. (2009) and Ern and Vohral k (2015, 2016). The present hp-adaptive algorithm follows the well-established paradigm based on an iterative loop where each step consists of the following four modules:
Here, SOLVE stands for application of the conforming nite element method on a matching (no hanging nodes) simplicial mesh to approximate the model problem (1.1); spatially-varying polynomial degree is allowed. The module ESTIMATE is based on an equilibrated ux a posteriori error estimate, obtained by solving, for each mesh vertex, a local mixed nite element problem with a (homogeneous) Neumann boundary condition on the patch of cells sharing the given vertex. The module MARK is based on a bulk-chasing criterion inspired by the well-known Dor er’s marking proposed in Dor er (1996); here we mark mesh vertices and not simplices since we observe a smoother performance in practice and since we later work with some vertex-based auxiliary quantities.
The module REFINE, where we include our hp-decision criterion, is orga-nized into three steps. First, we solve two local nite element problems on each patch of simplices attached to a mesh vertex marked for re nement, with either the mesh re ned or the polynomial degree increased. This is inspired by the key observation from (Ern and Vohral k, 2015, Lemma 3.23) that guaranteed local e ciency can be materialized by some local conforming nite element solves. These conforming residual liftings allow us, in particular, to estimate the e ect of applying h- or p-re nement, and lead to a partition of the set of marked vertices into two disjoint subsets, one collecting the mesh vertices agged for h-re nement and the other collecting the mesh vertices agged for p-re nement. The second step of the module REFINE uses these two subsets to ag the simplices for h-, p, or hp-re nement. Finally, the third step of the module REFINE uses the above sets of agged simplices to build the next simplicial mesh and the next polynomial-degree distribution. Let us mention that recently, Dolejs et al. (2016) also devised an hp-adaptive algorithm driven by polynomial-degree-robust a posteriori error estimates based on the equili-brated uxes from Braess et al. (2009), Ern and Vohral k (2015, 2016). The di erences with the present work are that the interior penalty discontinuous Galerkin method is considered in Dolejs et al. (2016), and more importantly, that the present hp-decision criterion hinges on local primal solves on patches around marked vertices.
The second goal of the present work is to show that the proposed hp-adaptive strategy automatically leads to a computable guaranteed bound on the error reduction factor between two consecutive steps of the adaptive loop (1.2). More precisely, we show how to compute explicitly a real number Cred 2 [0; 1] so that kr(u u‘+1)k Credkr(u u‘)k; (1.3) where u‘ denotes the discrete solution on ‘-th iteration of the adaptive loop, see Theorem 1.5.2. Thus the number Cred gives a guaranteed (constant-free) bound on the ratio of the errors between successive re nements. This must not be confused with saying that the error is guaranteed to be reduced, since the case Cred = 1 cannot be ruled out in general without additional assumptions (e.g. an interior node property, see Morin et al. (2002) for further details). The computation of Cred crucially relies on a combined use of the equilibrated uxes and of the conforming residual liftings, which were already used for the error estimation and hp-re nement decision criterion respectively. It is worth noting that we consider a homogeneous Dirichlet boundary condition for the local residual liftings in order to obtain an estimate on the error reduction factor that is as sharp as possible.
The rest of this chapter is organized as follows. Section 1.2 describes the discrete setting and introduces some useful notation. Section 1.3 presents the modules SOLVE, ESTIMATE, and MARK, whereas Section 1.4 presents the module REFINE. Section 1.5 contains our main result on a guaranteed bound on the error reduction factor. Finally, numerical experiments on two-dimensional test cases featuring smooth and singular solutions are discussed in Section 1.6, and conclusions are drawn in Section 1.7.
Discrete setting
The main purpose of the adaptive loop (1.2) is to generate a sequence of nite-dimensional H01-conforming nite element spaces (V‘)‘ 0, where the integer ‘ 0 stands for the iteration counter in (1.2). H01-conformity means that V‘ H01( ) for all ‘ 0. In this work, we shall make the following nestedness assumption: V‘ V‘+1;8‘ 0: (1.4)
The space V‘ is built from two ingredients: (i) a matching simplicial mesh T‘ of the computational domain , that is, a nite collection of (closed) non-overlapping simplices K 2 T‘ covering exactly and such that the intersection of two di erent simplices is either empty, a common vertex, a common edge, or a common face; (ii) a polynomial-degree distribution described by the vector p‘ := (p‘;K )K2T‘ that assigns a polynomial degree to each simplex K 2 T‘. The conforming nite element space V‘ is then de ned as V‘ := Pp‘ (T‘) \ H01( ); 8‘ 0; where Pp‘ (T‘) denotes the space of piecewise polynomials of total degree p‘;K 1 on each simplex K 2 T‘. In other words, any function v‘ 2 V‘ satis es v‘ 2 H01( ) and v‘jK 2 Pp‘;K (K) for all K 2 T‘, where for an integer p 1, Pp(K) stands for the space of polynomials of total degree at most p on the simplex K.
The initial mesh T0 and the initial polynomial-degree distribution p0 are given, and the purpose of each step ‘ 0 of the adaptive loop (1.2) is to produce the next mesh T‘+1 and the next polynomial-degree distribution p‘+1. In order to ensure the nestedness property (1.4), the following two properties are to be satis ed: (i) The sequence (T‘)‘ 0 is hierarchical, i.e., for all ‘ 0 and all Ke 2 T‘+1, there is a unique simplex K 2 T‘, called the parent of Ke so that Ke K; (ii) The local polynomial degree is locally increasing, i.e., for all ‘ 0 and all Ke 2 T‘+1, p‘+1;Ke p‘;K where K 2 T‘ is the parent of Ke. Moreover, we assume the following shape-regularity property: There exists a constant T > 0 such that maxK2T‘ hK = K T for all ‘ 0, where hK is the diameter of K and K is the diameter of the largest ball inscribed in K.
Before closing this section, we introduce some further useful notation. The set of vertices V‘ of each mesh T‘ is decomposed into V‘int and V‘ext, the set of inner and boundary vertices, respectively. For each vertex a 2 V‘, the so-called hat function ‘a is the continuous, piecewise a ne function that takes the value 1 at the vertex a and the value 0 at all the other vertices of V‘; the function ‘a is in V‘ for all a 2 V‘int. Moreover, we consider the simplex patch T‘a T‘ which is the collection of the simplices in T‘ sharing the vertex a 2 V‘, and we denote by !‘a the corresponding open subdomain. Finally, for each simplex K 2 T‘, VK denotes the set of vertices of K.
In this section we present the modules SOLVE, ESTIMATE, and MARK from the adaptive loop (1.2). Let ‘ 0 denote the current iteration number.
The module SOLVE
The module SOLVE takes as input the H01-conforming nite element space V‘ and outputs the discrete function u‘ 2 V‘ which is the unique solution of (ru‘; rv‘) = (f; v‘) 8v‘ 2 V‘: (1.5)
The module ESTIMATE
Following Destuynder and Metivet (1999), Braess et al. (2009), Ern and Vohral k (2015), Dolejs et al. (2016), Ern and Vohral k (2016), see also the references therein, the module ESTIMATE relies on an equilibrated ux a pos-teriori error estimate on the energy error kr(u u‘)k. The module ESTIMATE takes as input the nite element solution u‘ and outputs a collection of local error indicators f K gK2T‘ . The equilibrated ux is constructed locally from mixed nite element solves on the simplex patches T‘a attached to each ver-tex a 2 V‘. For this construction, we consider as in Dolejs et al. (2016) the local polynomial degree pesta := maxK2T‘a p‘;K (any other choice so that pesta maxK2T‘a p‘;K can also be employed). We consider the local Raviart{ Thomas{Nedelec mixed nite element spaces (V‘a; Qa‘) which are de ned for all a 2 V‘int by V‘a := fv‘ 2 H(div; !‘a); v‘jK 2 RTNpesta (K); 8K 2 T‘a; v‘ n!‘a = 0 on @!‘ag; Qa‘ := fq‘ 2 Ppesta (T‘a); (q‘; 1)!‘a = 0g.
Table of contents :
Introduction
1 An adaptive hp-renement strategy with computable guaranteed bound on the error reduction factor
1.1 Introduction
1.2 Discrete setting
1.3 The modules SOLVE, ESTIMATE, and MARK
1.3.1 The module SOLVE
1.3.2 The module ESTIMATE
1.3.3 The module MARK
1.4 The module REFINE
1.4.1 hp-decision on vertices
1.4.2 hp-decision on simplices
1.4.3 hp-renement
1.4.4 Summary of the module REFINE
1.5 Guaranteed bound on the error reduction factor
1.6 Numerical experiments
1.6.1 Smooth solution (sharp Gaussian)
1.6.2 Singular solution (L-shape domain)
1.7 Conclusions
2 An adaptive hp-renement strategy with inexact solvers and computable guaranteed bound on the error reduction factor
2.1 Introduction
2.2 Setting and notation
2.3 Guaranteed total and algebraic a posteriori error bounds
2.4 The inexact hp-adaptive algorithm
2.4.1 The module ONE_SOLVER_STEP
2.4.2 The module ESTIMATE
2.4.3 Adaptive stopping criteria for the algebraic solver
2.4.4 The module MARK
2.4.5 The module REFINE
2.5 Guaranteed bound on the error reduction
2.6 Numerical experiments
2.6.1 Smooth solution (sharp Gaussian)
2.6.2 Exponential convergence
2.6.3 Smooth solution (asymmetric wave front)
2.6.4 Singular solution (L-shape domain)
2.7 Conclusions
3 Convergence of adaptive hp-renement strategies with computable guaranteed bound on the error reduction factor
3.1 Introduction
3.2 Framework and notation
3.3 The hp-adaptive algorithm { exact setting
3.3.1 The modules SOLVE and ESTIMATE
3.3.2 The module MARK
3.3.3 The module REFINE
3.3.4 Discrete lower bound on the incremental error on marked simplices
3.4 Discrete stability of equilibrated uxes in an exact setting
3.5 The proof of convergence with an exact solver
3.6 The inexact hp-adaptive algorithm
3.6.1 Adaptive sub-loop of ONE_SOLVER_STEP and ESTIMATE
3.6.2 Adaptive stopping criterion for the algebraic solver
3.6.3 Modules MARK and REFINE
3.6.4 Discrete lower bound on the incremental error on marked simplices
3.6.5 Conditions on the adaptive stopping criterion parameter
3.7 Discrete stability of equilibrated uxes in an inexact setting
3.8 The proof of convergence with an inexact solver
3.9 Conclusions and outlook
Appendix A Implementation details of hp-AFEM
