The completion of locally refined simplicial partitions created by bisection

By Rob Stevenson

Abstract

Recently, in [Found. Comput. Math., 7(2) (2007), 245–269], we proved that an adaptive finite element method based on newest vertex bisection in two space dimensions for solving elliptic equations, which is essentially the method from [SINUM, 38 (2000), 466–488] by Morin, Nochetto, and Siebert, converges with the optimal rate.The number of triangles upper N in the output partition of such a method is generally larger than the number upper M of triangles that in all intermediate partitions have been marked for bisection, because additional bisections are needed to retain conforming meshes.A key ingredient to our proof was a result from [Numer. Math., 97(2004), 219–268] by Binev, Dahmen and DeVore saying that upper N minus upper N 0 less-than-or-equal-to upper C upper M for some absolute constant upper C , where upper N 0 is the number of triangles from the initial partition that have never been bisected. In this paper, we extend this result to bisection algorithms of n -simplices, with that generalizing the result concerning optimality of the adaptive finite element method to general space dimensions.

1. Introduction

Nowadays, adaptive finite element methods are a popular tool for the numerical solution of boundary value problems. Compared to non-adaptive finite element methods, they have the potential to achieve the optimal work-accuracy balance allowed by the polynomial degree, under much milder smoothness conditions on the solution of the boundary value problem.

The basic loop of an adaptive finite element method consists of computing the finite element solution with respect to the current partition; computing an a posteriori error estimator, being a sum of local error indicators associated to the individual elements; a marking of those elements for refinement which correspond to the largest error indicators; and finally, the construction of the next partition by refining the marked elements, generally together with elements in some surrounding in order to retain structural properties of the partition needed to apply the error estimator in the next iteration. We refer to this refinement of elements in the surrounding of the marked ones as the completion of the partition.

In this paper, we confine ourselves to partitions into n -simplices, as a basic refinement step we use bisection, and as the structural property of the partition we require conformity, meaning that the intersection of any two different simplices in the partition is either empty or a common hyperface of both simplices. In this setting, in order to retain conformity, a bisection of a simplex has to be complemented by bisections of some of its neighbours, which in turn may induce bisections of their neighbours and so on. The complexity of this completion process is being studied in this paper. The advantage of the sketched approach is that highly locally refined partitions can be generated, the arising simplices are uniformly shape regular, and that finite element spaces with respect to refined partitions are nested. Alternatively, one may consider non-conforming partitions generated by other refinement strategies. In that case, a valid error estimator will require that the “amount of non-conformity” is bounded, among other things meaning that the number of hanging vertices per element has to be uniformly bounded. So also then refinements cannot be made on a purely individual element basis, and similar questions arise as with the approach studied here.

In ReferenceBDD04, considering conforming partitions into triangles generated by the so-called newest vertex bisection rule starting from some fixed initial conforming triangulation, Binev, Dahmen and DeVore showed that the total number of triangles in the partition at termination of the adaptive finite element method is bounded by some absolute multiple of the number of triangles that were marked for refinement in all iterations. In other words, all additional bisections to retain conformity of all intermediate partitions inflate the final number of triangles by not more than a constant factor. In ReferenceSte06, we used this result to prove optimal computational complexity of an adaptive linear finite element method, essentially the method introduced in ReferenceMNS00, in the following sense: Whenever for some s greater-than 0 , the solution can be approximated within a tolerance epsilon greater-than 0 in energy norm by a continuous piecewise linear function with respect to a partition generated by newest vertex bisection with script upper O left-parenthesis epsilon Superscript negative 1 slash s Baseline right-parenthesis triangles, and one knows how to approximate the right-hand side in the dual norm with the same rate with piecewise constants; then this adaptive method produces approximations that converge with this rate, using a number of operations that is of the order of the number of triangles in the output partition. This result can be generalized to higher order elements and/or more than two space dimensions, for the latter generalization assuming that the result of Binev, Dahmen and DeVore concerning newest vertex bisection of triangles can be generalized to more space dimensions, which is the topic of this paper.

Bisection of n -simplices has been studied in ReferenceBän91ReferenceKos94ReferenceAMP00 for n equals 3 , and in ReferenceMau95ReferenceTra97 for general n , and this work has been inspired by all of these references. See also ReferenceBey00 for refinement strategies not based on bisection. In order to be able to generalize the result from ReferenceBDD04, it will be important that each uniform refinement of the fixed initial conforming partition is conforming. Here with a uniform refinement, we mean a partition in which all simplices have been created by an equal number of bisections. Conformity of all uniform refinements is not guaranteed with the methods from ReferenceBän91ReferenceAMP00. The other methods require conditions on the initial partition in addition to conformity. In this paper, we apply the bisection rules from ReferenceMau95ReferenceTra97. We relax the conditions on the initial partition to their minimum. For n equals 2 , the resulting conditions can be satisfied for any conforming partition. We show that for n greater-than 2 , any conforming partition of n -simplices in any case can be refined to a valid initial partition for our bisection method. For the bisection method being applied inside an adaptive finite element method, we show that the result from ReferenceBDD04 generalizes to n -dimensions: The total number of n -simplices in the partition at termination of the method can be bounded by some absolute multiple of the number of n -simplices that were marked for refinement in all iterations.

This paper is organized as follows: In §2, we recall results concerning recurrent bisections of a single n -simplex. In §3, we show that in order to verify conformity of a partition, we only have to check whether left-parenthesis n minus 1 right-parenthesis -dimensional hyperfaces match to left-parenthesis n minus 1 right-parenthesis -dimensional hyperfaces, where lower-dimensional hyperfaces can then be ignored. In §4, we formulate minimal conditions on the initial partition under which all uniform refinements are conforming. In Appendix A, we show that these conditions can always be satisfied by some initial refinement of any given conforming subdivision into n -simplices. In §5, we demonstrate how local refinements can be made while retaining conformity. Finally, in §6, we prove that the result of Binev, Dahmen and DeVore generalizes to n -dimensions.

2. Bisection of a single simplex

Let 2 less-than-or-equal-to n less-than-or-equal-to m . An n -simplex, or briefly, simplex upper T in bold upper R Superscript m is the convex hull of n plus 1 points x 0 comma period period period comma x Subscript n Baseline element-of bold upper R Superscript m that do not lie on a left-parenthesis n minus 1 right-parenthesis -dimensional hyperplane. We will identify upper T with the set of its vertices StartSet x 0 comma period period period comma x Subscript n Baseline EndSet . For 0 less-than-or-equal-to k less-than-or-equal-to n minus 1 , a simplex spanned by k plus 1 vertices of upper T is called a hyperface of upper T . For k equals n minus 1 , it will be called a true hyperface, and for k less-than-or-equal-to n minus 2 it will called a lower dimensional hyperface.

Corresponding to a simplex StartSet x 0 comma period period period comma x Subscript n Baseline EndSet , we will distinguish between n left-parenthesis n plus 1 right-parenthesis factorial tagged simplices given by all possible ordered sequences left-parenthesis x 0 comma x 1 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma and types gamma element-of StartSet 0 comma period period period comma n minus 1 EndSet . Given a tagged simplex upper T equals left-parenthesis x 0 comma x 1 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma , its children are the tagged simplices

StartLayout 1st Row 1st Column Blank 2nd Column left-parenthesis x 0 comma StartFraction x 0 plus x Subscript n Baseline Over 2 EndFraction comma x 1 comma period period period comma x Subscript gamma Baseline comma x Subscript gamma plus 1 Baseline comma period period period comma x Subscript n minus 1 Baseline right-parenthesis Subscript left-parenthesis gamma plus 1 right-parenthesis normal m normal o normal d n EndLayout

and

StartLayout 1st Row 1st Column Blank 2nd Column left-parenthesis x Subscript n Baseline comma StartFraction x 0 plus x Subscript n Baseline Over 2 EndFraction comma x 1 comma period period period comma x Subscript gamma Baseline comma x Subscript n minus 1 Baseline comma period period period comma x Subscript gamma plus 1 Baseline right-parenthesis Subscript left-parenthesis gamma plus 1 right-parenthesis normal m normal o normal d n Baseline comma EndLayout

where the sequences left-parenthesis x Subscript gamma plus 1 Baseline comma period period period comma x Subscript n minus 1 Baseline right-parenthesis and left-parenthesis x 1 comma period period period comma x Subscript gamma Baseline right-parenthesis should be read as being void for gamma equals n minus 1 and gamma equals 0 , respectively. So these children are defined by bisecting the edge ModifyingAbove x 0 x Subscript n With bar of upper T , i.e., by connecting its midpoint with the other vertices x 1 comma period period period comma x Subscript n minus 1 Baseline , and by an appropriate ordering of their vertices, and by having type left-parenthesis gamma plus 1 right-parenthesis normal m normal o normal d n . See Figure 1 for an illustration.

Corresponding to a tagged simplex upper T equals left-parenthesis x 0 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma , we set

upper T Subscript normal upper R Baseline equals left-parenthesis x Subscript n Baseline comma x 1 comma period period period comma x Subscript gamma Baseline comma x Subscript n minus 1 Baseline comma period period period comma x Subscript gamma plus 1 Baseline comma x 0 right-parenthesis Subscript gamma Baseline comma

which is the tagged simplex that has the same set of children as upper T , and in this sense is equal to upper T . So actually we distinguish between one-half n left-parenthesis n plus 1 right-parenthesis factorial tagged simplices.

The edge ModifyingAbove x 0 x Subscript n With bar is called the refinement edge of upper T . In the n equals 2 case, the vertex opposite to this edge is known as the newest vertex, and the procedure is known as newest vertex bisection. A tagged simplex that is created by applying script l recursive bisections to upper T is called a level script l descendant of upper T . One may verify that the refinement edge of a tagged simplex of type 0 will not be further cut until the creation of level n plus 1 descendants. Generally, this is not true for a tagged simplex of type unequal to 0. Yet, an edge will never be cut on two consecutive levels.

The above bisection rule was introduced in ReferenceTra97 and, in different notation, in ReferenceMau95. The idea behind it is that when starting with a so-called Kuhn simplex, giving it type 0, recurrent bisections always cut the longest edge. A Kuhn simplex is a simplex of the form StartSet x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline EndSet with x Subscript i Superscript pi Baseline equals sigma-summation Underscript j equals 1 Overscript i Endscripts e Subscript pi left-parenthesis j right-parenthesis , pi being a permutation of StartSet 1 comma period period period comma n EndSet , and StartSet e 1 comma period period period comma e Subscript n Baseline EndSet the canonical basis for bold upper R Superscript n . The set of the n factorial Kuhn simplices form a partition of the n -dimensional hypercube. The following result was proven in ReferenceTra97ReferenceMau95

Theorem 2.1

All 2 Superscript script l level script l -descendants of a tagged Kuhn simplex left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 are mutually congruent. Moreover, the level n descendants are congruent to left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 up to a magnification factor one-half . All these congruence mappings between pairs of tagged simplices preserve the ordering of the vertices, showing that all descendants of left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 have at most n different shapes.

Now let upper T equals left-parenthesis x 0 comma period period period comma x Subscript n Baseline right-parenthesis Subscript 0 be an arbitrary tagged n -simplex of type 0 . Then given arbitrary tagged Kuhn simplices left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 of type 0 , there is a unique affine mapping upper F Subscript upper T Baseline colon bold upper R Superscript n Baseline right-arrow bold upper R Superscript n such that upper F left-parenthesis x Subscript i Baseline right-parenthesis equals x Subscript i Superscript pi ( 0 less-than-or-equal-to i less-than-or-equal-to n right-parenthesis . The definition of the bisection rule shows that the level script l descendants of upper T are the images under upper F Subscript upper T Superscript negative 1 of the level script l descendants of left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 . From Theorem 2.1 we conclude that the smallest angle of any descendant of upper T stays away from zero only dependent on the smallest angle in upper T . The same is true for upper T being a tagged simplex of type gamma element-of StartSet 0 comma period period period comma n minus 1 EndSet since its 2 Superscript n minus gamma level n minus gamma descendants are of type 0 .

3. Partitions and conformity

Let normal upper Omega subset-of bold upper R Superscript n be an open set. A locally finite collection upper P of mutually essentially disjoint n -simplices in bold upper R Superscript n is called a partition of normal upper Omega when normal upper Omega overbar equals union Underscript upper T element-of upper P Endscripts upper T . Usually a partition upper P is called conforming when the intersection of any two different upper T comma upper T prime element-of upper P is either empty, or a hyperface of both simplices. In case normal upper Omega lies simultaneously on both sides of an left-parenthesis n minus 1 right-parenthesis -dimensional part of its boundary, this condition is unnecessarily restrictive. Instead, we will call upper P to be conforming when:

StartLayout 1st Row with Label left-parenthesis upper C 1 right-parenthesis EndLabel 1st Column Blank 2nd Column For any upper T element-of upper P comma partial-differential normal upper Omega intersection upper T is the union of hyperfaces of upper T period 2nd Row with Label left-parenthesis upper C 2 right-parenthesis EndLabel 1st Column Blank 2nd Column Each x element-of upper T intersection upper T Superscript prime Baseline left-parenthesis upper T comma upper T prime element-of upper P right-parenthesis for which for any open ball upper B contains-as-member x comma any 3rd Row 1st Column Blank 2nd Column y element-of upper T intersection upper B intersection normal upper Omega comma y prime element-of upper T Superscript prime Baseline intersection upper B intersection normal upper Omega are connected by a path through upper B intersection normal upper Omega comma 4th Row 1st Column Blank 2nd Column lies on a joint hyperface of upper T and upper T Superscript prime Baseline period EndLayout

See Figure 2 for an illustration.

Remark 3.1

When normal upper Omega nowhere lies simultaneously on both sides of an left-parenthesis n minus 1 right-parenthesis -dimensional part of its boundary, a path as meant in EquationC2 always exists, so that EquationC2 means that each x element-of upper T intersection upper T prime lies on a joint hyperface of upper T and upper T prime , or, that upper T intersection upper T prime is the union of joint hyperfaces of upper T and upper T prime . Since furthermore upper T intersection upper T prime is convex, we conclude that in this case upper T intersection upper T prime , if not empty, is a joint hyperface, i.e., EquationC2 is equivalent to the commonly used definition of conforming.

If, in addition, partial-differential normal upper Omega is everywhere left-parenthesis n minus 1 right-parenthesis -dimensional, i.e., if normal upper Omega equals int left-parenthesis normal upper Omega overbar right-parenthesis , then EquationC2 implies EquationC1. Indeed, let upper T element-of upper P such that partial-differential normal upper Omega intersection upper T is not the union of hyperfaces of upper T . Since int left-parenthesis upper T right-parenthesis subset-of int left-parenthesis union Underscript upper T prime element-of upper P Endscripts upper T Superscript prime Baseline right-parenthesis equals normal upper Omega , this means that upper T has a hyperface upper F that contains in its interior both an x element-of partial-differential normal upper Omega and an y element-of normal upper Omega . Since normal upper Omega is open, there is an open ball upper B subset-of bold upper R Superscript n such that, with upper P Subscript y Baseline colon equals StartSet upper T prime element-of upper P colon upper T prime contains-as-member y EndSet , y element-of upper B subset-of union Underscript upper T prime element-of upper P Subscript y Endscripts upper T prime . Since the intersection of any two simplices from upper P Subscript y is a joint hyperface that contains y , we have that upper F equals intersection Underscript upper T prime element-of upper P Subscript y Baseline Endscripts upper T prime . As a consequence, there exists an open ball upper B prime element-of bold upper R Superscript n , such that x element-of upper B prime subset-of union Underscript upper T prime element-of upper P Subscript y Endscripts upper T prime , and so x element-of int left-parenthesis union Underscript upper T prime element-of upper P Subscript y Baseline Endscripts upper T Superscript prime Baseline right-parenthesis subset-of normal upper Omega , which gives a contradiction.

The next theorem simplifies the task of verifying whether a partition is conforming. Basically it says that if in a partition true hyperfaces coincide with true hyperfaces, then this automatically holds true for lower dimensional hyperfaces. Different upper T comma upper T prime element-of upper P that share a true hyperface, and for which upper T intersection upper T prime intersection normal upper Omega not-equals normal empty-set , will be called neighbours.

Theorem 3.2

A partition upper P satisfies EquationC2 if and only if any upper T comma upper T prime element-of upper P , for which upper T intersection upper T prime intersection normal upper Omega contains a point interior to a true hyperface of upper T (or upper T prime ), are neighbours.

Proof.

Let upper P satisfy EquationC2 and let x element-of upper T intersection upper T prime intersection normal upper Omega . Then for any open ball upper B contains-as-member x , upper B intersection upper T intersection upper T prime intersection normal upper Omega is connected, and so x lies on a joint hyperface of upper T and upper T prime . When x is interior to a true hyperface of upper T , we conclude that upper T and upper T prime are neighbours.

For proving the opposite implication, let upper B contains-as-member x in the definition of EquationC2 be small enough such that, with upper P Subscript x Baseline colon equals StartSet upper S element-of upper P colon upper S contains-as-member x EndSet , upper B intersection upper T intersection upper T prime intersection normal upper Omega subset-of union Underscript upper S element-of upper P Subscript x Endscripts upper S . Consider a path in upper B intersection normal upper Omega connecting points y element-of upper T intersection upper B intersection normal upper Omega , y prime element-of upper T prime intersection upper B intersection normal upper Omega . Since upper B intersection normal upper Omega is open, such a path can be arranged not to cross lower dimensional hyperfaces of any upper S element-of upper P Subscript x . Let upper T equals upper S 0 comma period period period comma upper S Subscript p Baseline equals upper T prime be the ordered sequence of simplices in upper P Subscript x that is passed when traveling along this path connecting y and y prime . By assumption, and the construction of the path, for any 1 less-than-or-equal-to i less-than-or-equal-to p , upper S Subscript i minus 1 and upper S Subscript i are neighbours. We will now show that for 1 less-than-or-equal-to q less-than-or-equal-to p , intersection Underscript i equals 0 Overscript q Endscripts upper S Subscript i is a hyperface of upper S Subscript q . For q equals 1 it is true, and let us assume that it is true for a q minus 1 greater-than-or-equal-to 1 . Then intersection Underscript i equals 0 Overscript q Endscripts upper S Subscript i , being the intersection of the hyperfaces intersection Underscript i equals 0 Overscript q minus 1 Endscripts upper S Subscript i and upper S Subscript q minus 1 Baseline intersection upper S Subscript q of upper S Subscript q minus 1 , is a hyperface of upper S Subscript q minus 1 that is contained in upper S Subscript q minus 1 Baseline intersection upper S Subscript q , and thus is a hyperface of upper S Subscript q . The point x is contained in intersection Underscript i equals 0 Overscript p Endscripts upper S Subscript i , which by applying the above result for q equals p , is a hyperface of upper T prime , and similarly of upper T .

4. Partitions created by refinements

In the remainder of this paper, we will exclusively consider partitions of tagged simplices that can be created by recurrent bisections, as discussed in §2, starting from some fixed initial partition upper P 0 of tagged simplices of some fixed type gamma . So whenever we refer to a partition upper P , we mean a partition of this kind, and any upper T element-of upper P is a descendant, with some level script l left-parenthesis upper T right-parenthesis , of a simplex from upper P 0 . A partition upper P is a uniform refinement of upper P 0 when all its simplices have the same level.

From Theorem 2.1, we infer that all partitions are uniformly shape regular only dependent on upper P 0 and n , meaning that the ratio of the radii of the smallest circumscribed and largest inscribed balls of any upper T is uniformly bounded, only dependent on upper P 0 and n . More particular, there exist constants d comma upper D greater-than 0 , only dependent on upper P 0 and n , such that for any upper T ,

StartLayout 1st Row with Label left-parenthesis 4.1 right-parenthesis EndLabel d 2 Superscript minus script l left-parenthesis upper T right-parenthesis Baseline less-than-or-equal-to normal m normal e normal a normal s left-parenthesis upper T right-parenthesis comma normal d normal i normal a normal m left-parenthesis upper T right-parenthesis less-than-or-equal-to upper D 2 Superscript minus script l left-parenthesis upper T right-parenthesis slash n Baseline period EndLayout

In the following we will call two neighbouring tagged simplices upper T equals left-parenthesis x 0 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma , upper T prime equals left-parenthesis x prime 0 comma period period period comma x prime Subscript n right-parenthesis Subscript gamma prime reflected neighbours when the ordered sequence of vertices of either upper T or upper T Subscript normal upper R coincides with that of upper T prime on all but one position. We will always assume that upper P 0 satisfies the following 2 conditions:

(a)

upper P 0 is conforming.

(b)

Any two neighbouring tagged simplices upper T equals left-parenthesis x 0 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma , upper T prime equals left-parenthesis x prime 0 comma period period period comma x prime Subscript n right-parenthesis Subscript gamma from upper P 0 match in the sense that if ModifyingAbove x 0 x Subscript n With bar or ModifyingAbove x prime 0 x prime Subscript n With bar is on upper T intersection upper T prime , then upper T and upper T prime are reflected neighbours. Otherwise, the pair of neighbouring children of upper T and upper T prime are reflected neighbours.

Remark 4.1

If upper T and upper T prime are reflected neighbours, then the pair(s) of their neighbouring children are reflected neighbours. The opposite statement, however, is not true. E.g., for n equals 2 and arbitrary gamma element-of StartSet 0 comma 1 EndSet , neighbours upper T equals left-parenthesis x 0 comma x 1 comma x 2 right-parenthesis Subscript gamma and upper T prime equals left-parenthesis x prime 0 comma x prime 1 comma x prime 2 right-parenthesis Subscript gamma are reflected neighbours when ModifyingAbove x 0 x 2 With bar equals ModifyingAbove x prime 0 x prime 2 With bar or x 1 equals x prime 1 . They are already matching when ModifyingAbove x 0 x 2 With bar equals ModifyingAbove x prime 0 x prime 2 With bar or x 1 comma x prime 1 element-of upper T intersection upper T prime ; see Figure 3 for an illustration.

Remark 4.2

Instead of (b), in ReferenceMau95ReferenceTra97 it was required that for any neighbouring tagged simplices upper T and upper T prime the ordered sequence of their vertices coincides on all but one position (being the definition of reflected neighbours in ReferenceTra97), which is thus an even stronger condition than being reflected neighbours in our terminology. As shown in ReferenceTra97, for a simply connected domain, it can be satisfied if and only if each left-parenthesis n minus 2 right-parenthesis -dimensional hyperface not on the boundary of the domain is shared by an even number of simplices. For n equals 2 , it means that the valence of any interior vertex should be even. On the other hand, for n equals 2 condition (b) corresponds to the condition described in ReferenceBDD04, Lemma 2.1. There it is shown that for any conforming partition into triangles there exists a local numbering of the vertices that satisfies (b).

We do not know whether for n greater-than 2 , condition (b) can be satisfied for each conforming partition. Therefore, inspired by such a construction for n equals 3 in ReferenceKos94, in Appendix A we show that any conforming partition of n -simplices can be refined to a conforming partition upper P 0 of tagged simplices of type n minus 1 such that any two neighbours are reflected neighbours, which is thus stronger than needed for (b).

We now proceed assuming upper P 0 satisfies (a) and (b).

Theorem 4.3

Any uniform refinement upper P of upper P 0 is conforming.

Proof.

Since upper P is a refinement of upper P 0 , it satisfies EquationC1. Thanks to Theorem 3.2, it only remains to show that any upper T comma upper T prime element-of upper P , for which upper T intersection upper T prime intersection normal upper Omega contains a point interior to a true hyperface of upper T (or upper T prime ), are neighbours. If upper T and upper T prime have the same ancestor in upper P 0 , then this has been shown in ReferenceTra97, §5. Otherwise, with different ancestors upper S equals left-parenthesis x 0 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma and upper S prime equals left-parenthesis x prime 0 comma period period period comma x prime Subscript n right-parenthesis Subscript gamma from upper P 0 of upper T and upper T prime , respectively, upper S intersection upper S prime intersection normal upper Omega contains a point interior to a true hyperface of upper S (or upper S prime ), and so upper S and upper S prime are neighbours by (a).

If ModifyingAbove x 0 x Subscript n With bar or ModifyingAbove x prime 0 x prime Subscript n With bar is on upper S intersection upper S prime , then upper S and upper S prime are reflected neighbours by (b), and so on any level script l the subdivision of upper S into 2 Superscript script l descendants is a reflection in upper S intersection upper S prime of the corresponding subdivision of upper S prime . This is easily seen when the ordered sequences of vertices of upper S and upper S prime coincide on all but one positions, but the same is true when the ordered sequences of vertices of upper S Subscript normal upper R and upper S prime coincide on all but one positions, since upper S Subscript normal upper R and upper S have the same children. We conclude that in this case upper T and upper T prime are neighbours.

Otherwise, (b) shows that the children of upper S and upper S prime that have upper S intersection upper S prime as a hyperface, and thus which contain upper T and upper T prime , respectively, are reflected neighbours. The same argument shows that upper T and upper T prime are neighbours also in this case.

Remark 4.4

Giving our bisection rule, (b) and obviously (a) are actually also necessary conditions for conformity of all uniform refinements of upper P 0 . Indeed, since an edge is never cut on two consecutive levels, if upper T and upper T prime as in (b) both have their refinement edge not on upper T intersection upper T prime , then the pair of their neighbouring children have their refinement edges on their common true hyperface. So, to show the necessity of (b), it is sufficient to show that, for any gamma , if any of two neighbours upper T equals left-parenthesis x 0 comma period period period comma x Subscript n Baseline right-parenthesis Subscript gamma , upper T prime equals left-parenthesis x prime 0 comma period period period comma x prime Subscript n right-parenthesis Subscript gamma have their refinement edge on upper T intersection upper T prime , then the union of their level script l descendants can only form conforming partitions for any script l when upper T and upper T prime are reflected neighbours. Suppose they are not, meaning that the ordered sequences of vertices of both upper T , upper T prime and upper T Subscript normal upper R , upper T prime differ on more than one position. It is needed that ModifyingAbove x 0 x Subscript n Baseline With bar equals ModifyingAbove x prime 0 x Subscript n Superscript prime Baseline With bar , since otherwise already their level 1 descendants do not form a conforming partition. By possibly replacing upper T by upper T Subscript normal upper R , we may assume that x 0 equals x prime 0 and x Subscript n Baseline equals x prime Subscript n . By the assumption that the ordered sequences of vertices differ on more than one position, and the fact that upper T and upper T prime are neighbours, there exists an i element-of StartSet 1 comma period period period comma n minus 1 EndSet with x Subscript i Baseline not-equals x prime Subscript i and x Subscript i or x prime Subscript i on upper T intersection upper T prime . For each script l , there exists one level script l descendant upper T Subscript script l ( upper T prime Subscript script l ) of upper T ( upper T prime ) having vertex x 0 ( x prime 0 ) and a true hyperface on upper T intersection upper T prime . So as long as for increasing script l , the union of the level script l descendants of upper T and upper T prime form a conforming partition, upper T Subscript script l and upper T prime Subscript script l are neighbours. At some level script l , however, depending on i and gamma , upper T Subscript script l will be cut along ModifyingAbove x 0 x Subscript i With bar and upper T prime Subscript script l along ModifyingAbove x prime 0 x prime Subscript i With bar , meaning that on level script l plus 1 the partitions are nonconforming, completing the proof of the necessity of (b).

Remark 4.5

In ReferenceBän91ReferenceAMP00, algorithms for bisection tetrahedra, i.e., for n equals 3 , are formulated that do not require a matching of neighbours in the initial partition. With these methods, however, Theorem 4.3 is generally not valid; only uniform refinements with levels divisible by n are guaranteed to be conforming. The result of Theorem 4.3, however, will be heavily used in the following. An interesting open question is whether the tetrahedra on level n generated by the algorithms from ReferenceBän91ReferenceAMP00 can be retagged so that (b) is satisfied. In contrast to the construction from Appendix A, this would give an initial refinement based on bisections. For n equals 2 , starting with an arbitrary tagging of the triangles, the triangles on level 2 can always be locally retagged such that (b) is valid (see ReferenceBDD04, p. 229), whereas a suitable tagging of the initial partition might not be easy to find.

In the following, tagged neighbours will be called compatibly divisible when they have the same refinement edge. For a partition upper P , and upper T element-of upper P , we set

upper N left-parenthesis upper P comma upper T right-parenthesis colon equals StartSet neighbours upper T prime of upper T in upper P that contain the refinement edge of upper T EndSet period

Corollary 4.6

For any partition upper P , upper T element-of upper P , and upper T prime element-of upper N left-parenthesis upper P comma upper T right-parenthesis , either

script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis and upper T comma upper T prime are compatibly divisible, or

script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis minus 1 and upper T is compatibly divisible with one of the children of upper T prime .

Proof.

For some p greater-than-or-equal-to 2 , let upper T 1 comma upper T 2 be neighbours with script l left-parenthesis upper T 1 right-parenthesis equals script l left-parenthesis upper T 2 right-parenthesis minus p . Then there is a level p descendant of upper T 1 that contains a point of upper T 2 intersection normal upper Omega interior to a true hyperface. Theorem 4.3 shows that this level p descendant is a neighbour of upper T 2 , i.e., that it has a true hyperface in common with upper T 2 and thus with upper T 1 . Since a level p greater-than-or-equal-to 2 descendant of upper T 1 has less than n minus 1 vertices in common with upper T 1 , we arrive at a contradiction, and conclude that the levels of neighbours differ at most one.

Now let upper T prime element-of upper N left-parenthesis upper P comma upper T right-parenthesis with script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis plus 1 . Then again Theorem 4.3 shows that one of both children of upper T is a neighbour of upper T prime . However, since upper T has its refinement edge on upper T intersection upper T prime this cannot be the case.

Concerning the two remaining cases, if script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis , then upper T comma upper T prime are indeed compatibly divisible, since otherwise the uniform refinement with simplices of level script l left-parenthesis upper T right-parenthesis plus 1 would not be conforming.

If script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis minus 1 , then one of both children of upper T prime has a point of upper T intersection normal upper Omega interior to a true hyperface, so that they are neighbours by Theorem 4.3. Since the uniform refinement with simplices of level script l left-parenthesis upper T right-parenthesis plus 1 is conforming, we conclude that this child and upper T are compatibly divisible.

5. Local refinements while retaining conformity

Let upper P be a conforming partition, and let upper M subset-of upper P be a subset of simplices that have been marked for bisection. After bisecting the simplices from upper M , a generally nonconforming partition upper P prime arises. To restore conformity, one may apply the following completion algorithm:

Since the only way to cure the situation as described in the for-statement, or towards curing it, is to bisect upper T , complete left-bracket upper P prime right-bracket outputs the smallest conforming refinement of upper P prime , assuming that a conforming refinement exists. This, however, holds true, since with script l equals max Underscript upper T prime element-of upper P Superscript prime Baseline Endscripts script l left-parenthesis upper T prime right-parenthesis , the uniform partition with simplices of level script l is a conforming refinement of upper P prime . When implementing complete, care has to be taken to ensure that the computational work is of the order of the number of bisections that are made.

An alternative for first bisecting all simplices in upper M and then restoring conformity by a call of complete, is, when running over upper T element-of upper M , for each of those upper T to replace the current partition upper P by its smallest conforming refinement in which upper T has been bisected. A call of the routine refine left-bracket upper P comma upper T right-bracket given below determines such a partition. Since it bisects generally more simplices than only upper T , it may happen that it bisects upper T prime element-of upper M for which a call has not yet been made, which call thus can be skipped. In other words, the number of calls of refine is never larger, but might be smaller than the number of marked simplices. Since also with this approach, only simplices are bisected that either are marked, or whose bisection is unavoidable for obtaining a conforming partition, again we end up with the smallest conforming partition in which all marked simplices are bisected.

The routine refine left-bracket upper P comma upper T right-bracket is a generalization to n -dimensions of such a routine by Kossaczký in ReferenceKos94 for bisecting tetrahedra. Based on Corollary 4.6, the idea is to determine, possibly by recursive calls, a closed set of compatibly divisible neighbours that share the refinement edge with upper T , after which this set of simplices can be simultaneously bisected without introducing nonconformities.

Theorem 5.1

upper P prime colon equals bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T right-bracket terminates, and upper P prime is the smallest conforming refinement of upper P in which upper T has been bisected. If upper T prime element-of upper P prime is newly created by the call, then script l left-parenthesis upper T prime right-parenthesis less-than-or-equal-to script l left-parenthesis upper T right-parenthesis plus 1 .

Proof.

Let script l left-parenthesis upper T right-parenthesis equals 0 . Then Corollary 4.6 shows that there will be no recursive calls of refine, and that just before any evaluation of the until-statement, all upper T prime element-of upper K have the same refinement edge as upper T , and satisfy script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis and upper N left-parenthesis upper P comma upper T Superscript prime Baseline right-parenthesis subset-of upper K union upper F . If upper F not-equals normal empty-set , then in the next iteration of the do-until loop, the set upper K will be extended. Since, on the other hand, from the uniform shape regularity we know that the cardinality of upper K is bounded, we conclude that this loop terminates. After termination, upper F equals normal empty-set , and so for all upper T prime element-of upper K , upper N left-parenthesis upper P comma upper T Superscript prime Baseline right-parenthesis subset-of upper K , by Theorem 3.2 meaning that by bisecting all upper T prime element-of upper K conformity is retained. It is clear that we cannot confine bisection to a smaller set of simplices, and that script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis plus 1 for any newly created upper T prime .

Assuming that for some script l minus 1 greater-than-or-equal-to 1 , the statement is true for upper T with script l left-parenthesis upper T right-parenthesis equals script l minus 1 , let us consider upper T with script l left-parenthesis upper T right-parenthesis equals script l . Possible recursive calls of bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T double-prime right-bracket are unavoidable, where Corollary 4.6 shows that script l left-parenthesis upper T double-prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis minus 1 . The induction hypothesis then shows that such a call outputs the smallest conforming partition in which upper T double-prime has been bisected, and moreover, that it does not bisect any simplex that is already in upper K union upper F , since that would create simplices with levels larger than script l left-parenthesis upper T right-parenthesis equals script l left-parenthesis upper T double-prime right-parenthesis plus 1 . Now the proof is completed using the same arguments as in the script l left-parenthesis upper T right-parenthesis equals 0 case.

Assuming that the data structures allow that the determination of upper N left-parenthesis upper P comma upper T right-parenthesis requires not more than an absolute constant number of operations, note that the number of operations needed for upper P prime colon equals bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T right-bracket is script upper O left-parenthesis number-sign upper P Superscript prime Baseline minus number-sign upper P right-parenthesis .

In addition to the properties of refine shown in Theorem 5.2, we have

Theorem 5.2

With the constant upper D from Equation4.1, any newly created upper T prime by the call bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T right-bracket satisfies

d left-parenthesis upper T prime comma upper T right-parenthesis colon equals inf Underscript x prime element-of upper T Superscript prime Baseline comma x element-of upper T Endscripts StartAbsoluteValue x prime minus x EndAbsoluteValue less-than-or-equal-to upper D 2 Superscript 1 slash n Baseline sigma-summation Underscript k equals script l left-parenthesis upper T Superscript prime Baseline right-parenthesis Overscript script l left-parenthesis upper T right-parenthesis Endscripts 2 Superscript negative k slash n Baseline left-parenthesis less-than StartFraction upper D 2 Superscript 1 slash n Baseline Over 1 minus 2 Superscript negative 1 slash n Baseline EndFraction 2 Superscript minus script l left-parenthesis upper T Super Superscript prime Superscript right-parenthesis Baseline right-parenthesis period

Proof.

For script l left-parenthesis upper T right-parenthesis equals 0 , any newly created upper T prime is a child of a upper T overTilde that has its refinement edge on partial-differential upper T , so that d left-parenthesis upper T prime comma upper T right-parenthesis equals 0 . Note that in this case the sum over k is empty since script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis plus 1 .

Assuming that the theorem holds for script l left-parenthesis upper T right-parenthesis equals script l minus 1 greater-than-or-equal-to 0 , let us consider upper T with script l left-parenthesis upper T right-parenthesis equals script l . If upper T prime is created by bisection of any simplex from the set upper K , then the statement is proven as in the script l left-parenthesis upper T right-parenthesis equals 0 case. If upper T prime is created by a recursive call bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T double-prime right-bracket , then using upper T intersection upper T Superscript double-prime Baseline not-equals normal empty-set , the induction hypothesis shows that

StartLayout 1st Row 1st Column d left-parenthesis upper T prime comma upper T right-parenthesis 2nd Column less-than-or-equal-to d left-parenthesis upper T prime comma upper T Superscript double-prime Baseline right-parenthesis plus normal d normal i normal a normal m left-parenthesis upper T double-prime right-parenthesis 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to upper D 2 Superscript 1 slash n Baseline sigma-summation Underscript k equals script l left-parenthesis upper T Superscript prime Baseline right-parenthesis Overscript script l left-parenthesis upper T Superscript double-prime Baseline right-parenthesis Endscripts 2 Superscript negative k slash n Baseline plus upper D 2 Superscript minus script l left-parenthesis upper T Super Superscript double-prime Superscript right-parenthesis slash n Baseline equals upper D 2 Superscript 1 slash n Baseline sigma-summation Underscript k equals script l left-parenthesis upper T Superscript prime Baseline right-parenthesis Overscript script l left-parenthesis upper T right-parenthesis Endscripts 2 Superscript negative k slash n Baseline comma EndLayout

by script l left-parenthesis upper T double-prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis minus 1 .

The routine refine provides an alternative for the straightforward bisection of marked simplices complemented with a call of complete. Here, it is mainly discussed because, in the next section, its properties proven in Theorems 5.1 and 5.2 will allow us to bound the complexity of a recurrent marking and completion process. It turns out, however, that an implementation of this process by means of calls of refine is particularly efficient. For this reason, this approach is followed in the adaptive finite element package ALBERTA (ReferenceSS05).

Remark 5.3

Inside adaptive finite element methods, simplices can be marked for multiple bisections. This means that not only these simplices should be bisected, but also some of their descendants, with the obvious restriction that a descendant can only be on the list for bisection when its parent is. For example, for n equals 2 , the adaptive finite element method introduced in ReferenceMNS00 selects triangles for their bisection, and that of their children and 2 of their 4 grandchildren. The evaluation of such multiple markings can be done by scheduling them as an ordered sequence of groups of single markings, where the marking of a child is in the next group as that of its parent. After finding the smallest conforming refinement in which all simplices from a group are bisected, it may happen that bisections corresponding to markings from the next groups have already taken place, so that these markings can be deleted.

6. The complexity of a recurrent marking and completion process

We study the following algorithm:

As we have seen, the output partition of this algorithm is the smallest conforming refinement of upper P 0 in which all marked simplices have been bisected. After the preparations from the previous sections, the proof of the following main theorem concerning this algorithm follows the lines of the proof of the corresponding theorem for n equals 2 by Binev, Dahmen and DeVore. Since there are some small modifications, we include the proof for the reader’s convenience.

Theorem 6.1 (generalizes ReferenceBDD04, Theorem 2.4 for n equals 2 ).

With upper M being the set of simplices for which a call of refine is made in the above algorithm, which set is thus not larger than the union of all marked simplices, for the output partition upper P it holds that number-sign left-parenthesis upper P minus left-parenthesis upper P intersection upper P 0 right-parenthesis right-parenthesis less-than-or-equivalent-to number-sign upper M , only dependent on the constants d comma upper D from Equation4.1, and n .

Proof.

Fixing n , let a colon bold upper N 0 union StartSet negative 1 EndSet right-arrow bold upper R Superscript plus , b colon bold upper N 0 right-arrow bold upper N be some sequences with sigma-summation Underscript p equals negative 1 Overscript normal infinity Endscripts a left-parenthesis p right-parenthesis less-than normal infinity , sigma-summation Underscript p equals 0 Overscript normal infinity Endscripts b left-parenthesis p right-parenthesis 2 Superscript negative p slash n Baseline less-than normal infinity , and inf Underscript p greater-than-or-equal-to 0 Endscripts b left-parenthesis p right-parenthesis a left-parenthesis p right-parenthesis greater-than 0 . Valid instances are a left-parenthesis p right-parenthesis equals left-parenthesis p plus 2 right-parenthesis Superscript negative 2 and b left-parenthesis p right-parenthesis equals 2 Superscript p slash left-parenthesis n plus 1 right-parenthesis . Let upper A colon equals upper D left-parenthesis StartFraction 2 Superscript 1 slash n Baseline Over 1 minus 2 Superscript negative 1 slash n Baseline EndFraction plus 1 right-parenthesis sigma-summation Underscript p equals 0 Overscript normal infinity Endscripts b left-parenthesis p right-parenthesis 2 Superscript negative p slash n .

Inside this proof, upper P will always denote the output partition of the algorithm, whereas any intermediate partition will be denoted as upper P overbar . We define lamda colon upper P times upper M by

lamda left-parenthesis upper T prime comma upper T right-parenthesis equals StartLayout Enlarged left-brace 1st Row 1st Column a left-parenthesis script l left-parenthesis upper T right-parenthesis minus script l left-parenthesis upper T prime right-parenthesis right-parenthesis 2nd Column if d left-parenthesis upper T prime comma upper T right-parenthesis less-than upper A 2 Superscript minus script l left-parenthesis upper T Super Superscript prime Superscript right-parenthesis slash n Baseline and script l left-parenthesis upper T Superscript prime Baseline right-parenthesis less-than-or-equal-to script l left-parenthesis upper T right-parenthesis plus 1 comma 2nd Row 1st Column 0 2nd Column otherwise period EndLayout

For any fixed upper T element-of upper P , and script l prime element-of bold upper N 0 with script l prime less-than-or-equal-to script l left-parenthesis upper T right-parenthesis plus 1 , there exists a uniformly bounded number, only dependent on d and upper D , of upper T prime element-of upper P with d left-parenthesis upper T prime comma upper T right-parenthesis less-than upper A 2 Superscript minus script l left-parenthesis upper T prime right-parenthesis slash n and script l left-parenthesis upper T prime right-parenthesis equals script l prime . In view of the definition of lamda , we thus have sigma-summation Underscript upper T prime element-of upper P Endscripts lamda left-parenthesis upper T prime comma upper T right-parenthesis less-than-or-equivalent-to sigma-summation Underscript p equals negative 1 Overscript normal infinity Endscripts a left-parenthesis p right-parenthesis less-than normal infinity , and so sigma-summation Underscript upper T element-of upper M Endscripts sigma-summation Underscript upper T prime element-of upper P Endscripts lamda left-parenthesis upper T prime comma upper T right-parenthesis less-than-or-equivalent-to number-sign upper M .

In the second part of this proof, we are going to show that for all upper T prime element-of upper P minus left-parenthesis upper P intersection upper P 0 right-parenthesis ,

StartLayout 1st Row with Label left-parenthesis 6.1 right-parenthesis EndLabel sigma-summation Underscript upper T element-of upper M Endscripts lamda left-parenthesis upper T prime comma upper T right-parenthesis greater-than-or-equivalent-to 1 comma EndLayout

only dependent on d , upper D and n , so that

number-sign left-parenthesis upper P minus left-parenthesis upper P intersection upper P 0 right-parenthesis less-than-or-equivalent-to sigma-summation Underscript upper T prime element-of upper P minus left-parenthesis upper P intersection upper P 0 right-parenthesis Endscripts sigma-summation Underscript upper T element-of upper M Endscripts lamda left-parenthesis upper T prime comma upper T right-parenthesis less-than-or-equal-to sigma-summation Underscript upper T element-of upper M Endscripts sigma-summation Underscript upper T prime element-of upper P Endscripts lamda left-parenthesis upper T prime comma upper T right-parenthesis less-than-or-equivalent-to number-sign upper M comma

as required.

Let upper T 0 element-of upper P minus left-parenthesis upper P intersection upper P 0 right-parenthesis . For j greater-than-or-equal-to 0 , given that upper T Subscript j has been defined and assuming that it is not in upper P 0 , we let upper T Subscript j plus 1 Baseline element-of upper M be such that upper T Subscript j has been created by the call bold r bold e bold f bold i bold n bold e left-bracket upper P overbar comma upper T Subscript j plus 1 Baseline right-bracket . Let s be the smallest integer such that script l left-parenthesis upper T Subscript s Baseline right-parenthesis equals script l left-parenthesis upper T 0 right-parenthesis minus 1 . Note that such an s exists since at some point the sequence ends with a upper T Subscript modifying above d with tless j overTilde Baseline element-of upper P 0 , thus with script l left-parenthesis upper T Subscript modifying above d with tless j overTilde Baseline right-parenthesis equals 0 , whereas the value script l left-parenthesis upper T 0 right-parenthesis minus 1 cannot be passed without being attained because script l left-parenthesis upper T Subscript j plus 1 Baseline right-parenthesis greater-than-or-equal-to script l left-parenthesis upper T Subscript j Baseline right-parenthesis minus 1 by Theorem 5.1. From Theorem 5.2 and Equation4.1, for 1 less-than-or-equal-to j less-than-or-equal-to s we have

StartLayout 1st Row 1st Column d left-parenthesis upper T 0 comma upper T Subscript j Baseline right-parenthesis 2nd Column less-than-or-equal-to d left-parenthesis upper T 0 comma upper T 1 right-parenthesis plus normal d normal i normal a normal m left-parenthesis upper T 1 right-parenthesis plus d left-parenthesis upper T 1 comma upper T Subscript j Baseline right-parenthesis 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to sigma-summation Underscript k equals 1 Overscript j Endscripts d left-parenthesis upper T Subscript k minus 1 Baseline comma upper T Subscript k Baseline right-parenthesis plus sigma-summation Underscript k equals 1 Overscript j minus 1 Endscripts normal d normal i normal a normal m left-parenthesis upper T Subscript k Baseline right-parenthesis 3rd Row 1st Column Blank 2nd Column less-than sigma-summation Underscript k equals 1 Overscript j Endscripts StartFraction upper D 2 Superscript 1 slash n Baseline Over 1 minus 2 Superscript negative 1 slash n Baseline EndFraction 2 Superscript minus script l left-parenthesis upper T Super Subscript k minus 1 Superscript right-parenthesis slash n Baseline plus sigma-summation Underscript k equals 1 Overscript j minus 1 Endscripts upper D 2 Superscript minus script l left-parenthesis upper T Super Subscript k Superscript right-parenthesis slash n Baseline 4th Row 1st Column Blank 2nd Column less-than upper D left-parenthesis 1 plus StartFraction 2 Superscript 1 slash n Baseline Over 1 minus 2 Superscript negative 1 slash n Baseline EndFraction right-parenthesis sigma-summation Underscript k equals 0 Overscript j minus 1 Endscripts 2 Superscript minus script l left-parenthesis upper T Super Subscript k Superscript right-parenthesis slash n Baseline 5th Row 1st Column Blank 2nd Column equals upper D left-parenthesis 1 plus StartFraction 2 Superscript 1 slash n Baseline Over 1 minus 2 Superscript negative 1 slash n Baseline EndFraction right-parenthesis sigma-summation Underscript p equals 0 Overscript normal infinity Endscripts m left-parenthesis p comma j right-parenthesis 2 Superscript minus left-parenthesis script l left-parenthesis upper T 0 right-parenthesis plus p right-parenthesis slash n Baseline comma EndLayout

where m left-parenthesis p comma j right-parenthesis denotes the number of k less-than-or-equal-to j minus 1 with script l left-parenthesis upper T Subscript k Baseline right-parenthesis equals script l left-parenthesis upper T 0 right-parenthesis plus p .

In case m left-parenthesis p comma s right-parenthesis less-than-or-equal-to b left-parenthesis p right-parenthesis for all p , then the definition of the constant upper A shows that d left-parenthesis upper T 0 comma upper T Subscript s Baseline right-parenthesis less-than upper A 2 Superscript minus script l left-parenthesis upper T 0 right-parenthesis slash n , and so by definition of lamda , we conclude that lamda left-parenthesis upper T 0 comma upper T Subscript s Baseline right-parenthesis equals a left-parenthesis script l left-parenthesis upper T Subscript s Baseline right-parenthesis minus script l left-parenthesis upper T 0 right-parenthesis right-parenthesis equals a left-parenthesis negative 1 right-parenthesis , which shows Equation6.1.

Otherwise, there exist p with m left-parenthesis p comma s right-parenthesis greater-than b left-parenthesis p right-parenthesis . For each of those p , there exists a smallest j equals j left-parenthesis p right-parenthesis with m left-parenthesis p comma j left-parenthesis p right-parenthesis right-parenthesis greater-than b left-parenthesis p right-parenthesis . We denote p that gives rise to the smallest j left-parenthesis p right-parenthesis as p Superscript asterisk , and denote j left-parenthesis p Superscript asterisk Baseline right-parenthesis as j Superscript asterisk . Thus m left-parenthesis p comma j Superscript asterisk Baseline minus 1 right-parenthesis less-than-or-equal-to b left-parenthesis p right-parenthesis for all p , and m left-parenthesis p Superscript asterisk Baseline comma j Superscript asterisk Baseline minus 1 right-parenthesis equals b left-parenthesis p Superscript asterisk Baseline right-parenthesis . As in the case that m left-parenthesis p comma s right-parenthesis less-than-or-equal-to b left-parenthesis p right-parenthesis for all p , we find that for all k less-than-or-equal-to j Superscript asterisk Baseline minus 1 , d left-parenthesis upper T 0 comma upper T Subscript k Baseline right-parenthesis less-than upper A 2 Superscript minus script l left-parenthesis upper T 0 right-parenthesis slash n and lamda left-parenthesis upper T 0 comma upper T Subscript k Baseline right-parenthesis equals a left-parenthesis script l left-parenthesis upper T Subscript k Baseline right-parenthesis minus script l left-parenthesis upper T 0 right-parenthesis right-parenthesis . In view of the definition of m left-parenthesis dot comma dot right-parenthesis , we find that

StartLayout 1st Row 1st Column sigma-summation Underscript StartSet k less-than-or-equal-to j Superscript asterisk Baseline minus 2 colon script l left-parenthesis upper T Subscript k Baseline right-parenthesis equals script l left-parenthesis upper T 0 right-parenthesis plus p Superscript asterisk Baseline EndSet Endscripts lamda left-parenthesis upper T 0 comma upper T Subscript k Baseline right-parenthesis 2nd Column equals m left-parenthesis p Superscript asterisk Baseline comma j Superscript asterisk Baseline minus 1 right-parenthesis a left-parenthesis p Superscript asterisk Baseline right-parenthesis 2nd Row 1st Column Blank 2nd Column equals b left-parenthesis p Superscript asterisk Baseline right-parenthesis a left-parenthesis p Superscript asterisk Baseline right-parenthesis greater-than-or-equal-to inf Underscript p greater-than-or-equal-to 0 Endscripts b left-parenthesis p right-parenthesis a left-parenthesis p right-parenthesis greater-than 0 comma EndLayout

showing Equation6.1 also in this case.

The only properties that have been used in this proof are Equation4.1, and that of refine given in Theorems 5.1 and 5.2.

Appendix A. An initial refinement to satisfy condition (b)

Suppose we are given some conforming partition of n -simplices. Generalizing upon the construction by Kossaczký in ReferenceKos94 for n equals 3 , in this appendix we construct a conforming refinement of tagged simplices of type n minus 1 such that any two neighbours are reflected neighbours.

We start with constructing a conforming subdivision of any n -simplex into one-half left-parenthesis n plus 1 right-parenthesis factorial subsimplices, together with a global labeling of vertices and a marking of edges in this subdivision that satisfy the following conditions:

a vertex on a marked edge has no label,

the other vertices are labeled with numbers 1 comma period period period comma n minus 1 ,

each subsimplex contains vertices with labels 1 comma period period period comma n minus 1 and two vertices on a marked edge,

the subdivision and labeling/marking is symmetric in the barycentric coordinates of the original (macro-) simplex.

For n equals 2 , we subdivide a triangle into three subtriangles by connecting the vertices with the centroid. This centroid is labeled with number 1, and the edges of the original (macro-) triangle are marked. Clearly, the above conditions are satisfied.

For n greater-than-or-equal-to 3 , assuming we have defined a valid subdivision and labeling and marking of any left-parenthesis n minus 1 right-parenthesis -simplex, we define this for an n -simplex as follows: Create left-parenthesis n plus 1 right-parenthesis subsimplices by connecting the vertices with the centroid. Label the centroid with number n minus 1 . Each of the subsimplices shares a face with the original (macro-) simplex. Use the subdivision of any left-parenthesis n minus 1 right-parenthesis -simplex to subdivide these faces into one-half n factorial labeled/marked left-parenthesis n minus 1 right-parenthesis -simplices. Connect the vertices on the faces with the centroid to end with a subdivision into left-parenthesis n plus 1 right-parenthesis asterisk one-half n factorial equals one-half left-parenthesis n plus 1 right-parenthesis factorial simplices with a valid labeling/marking. See Figure 4 for an illustration.

Returning to the given conforming partition of n -simplices, we subdivide each of its simplices into one-half left-parenthesis n plus 1 right-parenthesis factorial subsimplices as above. Clearly this refined partition, that will serve as the initial partition upper P 0 , is also conforming. Tagging the simplices in upper P 0 means specifying a type, that will be n minus 1 , as well as a local ordering of the vertices in each simplex. We simply let each simplex inherit the labeling of the vertices from the macro-simplex that contains it, with the addition that both vertices on the marked edge are numbered 0 and n in arbitrary order; see Figure 5 for an illustration for n equals 2 . Neighbours within one macro-simplex are obviously reflected neighbours, since their numbering of the vertices on the hyperface between them is the same modulo permutations of 0 and n . The same is valid for neighbours from different macro-simplices, because of the symmetry of the labeling in the barycentric coordinates. We conclude that upper P 0 satisfies condition (b).

Acknowledgment

The author would like to thank Dr. Michael Bader (Technische Universität München) for pointing out a serious problem with the bisection rule from an earlier version of this work.

Figures

Figure 1.

Bisection of a tagged tetrahedron of type 0 with the next two level cuts indicated

Figure 2.

Tetrahedra in a conforming (left) or nonconforming (right) partition of bold upper R cubed minus left-bracket 0 comma 1 right-bracket squared times StartSet 0 EndSet . Dashed edges are in bold upper R squared times StartSet 0 EndSet

Figure 3.

Matching neighbours for n equals 2 , and their level 1 and 2 descendants. The neighbours in the rightmost picture are not reflected neighbours, but the pair of their neighbouring children are.

Figure 4.

Subdivision of a tetrahedron into 4 times 3 tetrahedra with the labeling of vertices and marking of edges

Figure 5.

Local numbering of the vertices of the subtriangles of a macro-triangle

Mathematical Fragments

Theorem 2.1

All 2 Superscript script l level script l -descendants of a tagged Kuhn simplex left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 are mutually congruent. Moreover, the level n descendants are congruent to left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 up to a magnification factor one-half . All these congruence mappings between pairs of tagged simplices preserve the ordering of the vertices, showing that all descendants of left-parenthesis x 0 Superscript pi Baseline comma period period period comma x Subscript n Superscript pi Baseline right-parenthesis Subscript 0 have at most n different shapes.

Equations (C1), (C2)
StartLayout 1st Row with Label left-parenthesis upper C 1 right-parenthesis EndLabel 1st Column Blank 2nd Column For any upper T element-of upper P comma partial-differential normal upper Omega intersection upper T is the union of hyperfaces of upper T period 2nd Row with Label left-parenthesis upper C 2 right-parenthesis EndLabel 1st Column Blank 2nd Column Each x element-of upper T intersection upper T Superscript prime Baseline left-parenthesis upper T comma upper T prime element-of upper P right-parenthesis for which for any open ball upper B contains-as-member x comma any 3rd Row 1st Column Blank 2nd Column y element-of upper T intersection upper B intersection normal upper Omega comma y prime element-of upper T Superscript prime Baseline intersection upper B intersection normal upper Omega are connected by a path through upper B intersection normal upper Omega comma 4th Row 1st Column Blank 2nd Column lies on a joint hyperface of upper T and upper T Superscript prime Baseline period EndLayout
Theorem 3.2

A partition upper P satisfies EquationC2 if and only if any upper T comma upper T prime element-of upper P , for which upper T intersection upper T prime intersection normal upper Omega contains a point interior to a true hyperface of upper T (or upper T prime ), are neighbours.

Equation (4.1)
StartLayout 1st Row with Label left-parenthesis 4.1 right-parenthesis EndLabel d 2 Superscript minus script l left-parenthesis upper T right-parenthesis Baseline less-than-or-equal-to normal m normal e normal a normal s left-parenthesis upper T right-parenthesis comma normal d normal i normal a normal m left-parenthesis upper T right-parenthesis less-than-or-equal-to upper D 2 Superscript minus script l left-parenthesis upper T right-parenthesis slash n Baseline period EndLayout
Theorem 4.3

Any uniform refinement upper P of upper P 0 is conforming.

Corollary 4.6

For any partition upper P , upper T element-of upper P , and upper T prime element-of upper N left-parenthesis upper P comma upper T right-parenthesis , either

script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis and upper T comma upper T prime are compatibly divisible, or

script l left-parenthesis upper T prime right-parenthesis equals script l left-parenthesis upper T right-parenthesis minus 1 and upper T is compatibly divisible with one of the children of upper T prime .

Theorem 5.1

upper P prime colon equals bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T right-bracket terminates, and upper P prime is the smallest conforming refinement of upper P in which upper T has been bisected. If upper T prime element-of upper P prime is newly created by the call, then script l left-parenthesis upper T prime right-parenthesis less-than-or-equal-to script l left-parenthesis upper T right-parenthesis plus 1 .

Theorem 5.2

With the constant upper D from Equation4.1, any newly created upper T prime by the call bold r bold e bold f bold i bold n bold e left-bracket upper P comma upper T right-bracket satisfies

d left-parenthesis upper T prime comma upper T right-parenthesis colon equals inf Underscript x prime element-of upper T Superscript prime Baseline comma x element-of upper T Endscripts StartAbsoluteValue x prime minus x EndAbsoluteValue less-than-or-equal-to upper D 2 Superscript 1 slash n Baseline sigma-summation Underscript k equals script l left-parenthesis upper T Superscript prime Baseline right-parenthesis Overscript script l left-parenthesis upper T right-parenthesis Endscripts 2 Superscript negative k slash n Baseline left-parenthesis less-than StartFraction upper D 2 Superscript 1 slash n Baseline Over 1 minus 2 Superscript negative 1 slash n Baseline EndFraction 2 Superscript minus script l left-parenthesis upper T Super Superscript prime Superscript right-parenthesis Baseline right-parenthesis period
Equation (6.1)
StartLayout 1st Row with Label left-parenthesis 6.1 right-parenthesis EndLabel sigma-summation Underscript upper T element-of upper M Endscripts lamda left-parenthesis upper T prime comma upper T right-parenthesis greater-than-or-equivalent-to 1 comma EndLayout

References

[AMP00]
D. N. Arnold, A. Mukherjee, and L. Pouly. Locally adapted tetrahedral meshes using bisection. SIAM J. Sci. Comput., 22(2):431–448, 2000. MR 1780608 (2002h:65204)
[Bän91]
E. Bänsch. Local mesh refinement in 2 and 3 dimensions. Impact Comput. Sci. Engrg., 3(3):181–191, 1991. MR 1141298 (92h:65150)
[BDD04]
P. Binev, W. Dahmen, and R. DeVore. Adaptive finite element methods with convergence rates. Numer. Math., 97(2):219 – 268, 2004. MR 2050077 (2005d:65222)
[Bey00]
J. Bey. Simplicial grid refinement: on Freudenthal’s algorithm and the optimal number of congruence classes. Numer. Math., 85(1):1–29, 2000. MR 1751367 (2001f:65132)
[Kos94]
I. Kossaczký. A recursive approach to local mesh refinement in two and three dimensions. J. Comput. Appl. Math., 55(3):275–288, 1994. MR 1329875 (95m:65207)
[Mau95]
J. Maubach. Local bisection refinement for n -simplicial grids generated by reflection. SIAM J. Sci. Comput., 16(1):210–227, 1995. MR 1311687 (95i:65128)
[MNS00]
P. Morin, R. Nochetto, and K. Siebert. Data oscillation and convergence of adaptive FEM. SIAM J. Numer. Anal., 38(2):466–488, 2000. MR 1770058 (2001g:65157)
[SS05]
A. Schmidt and K. G. Siebert. Design of adaptive finite element software, volume 42 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, Berlin, 2005. The finite element toolbox ALBERTA. MR 2127659 (2005i:65003)
[Ste06]
R.P. Stevenson. Optimality of a standard adaptive finite element method. Found. Comput. Math., 7(2):245–269, 2007.
[Tra97]
C. T. Traxler. An algorithm for adaptive mesh refinement in n dimensions. Computing, 59(2):115–137, 1997. MR 1475530 (98d:65152)

Article Information

MSC 2000
Primary: 65N50 (Mesh generation and refinement), 65Y20 (Complexity and performance of numerical algorithms), 65N30 (Finite elements, Rayleigh-Ritz and Galerkin methods, finite methods)
Keywords
  • Adaptive finite element methods
  • conforming partitions
  • bisection
  • n -simplices
Author Information
Rob Stevenson
Department of Mathematics, Utrecht University, P.O. Box 80.010, NL-3508 TA Utrecht, The Netherlands
Address at time of publication: Korteweg de Vries Institute for Mathematics, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands
stevenson@math.uu.nl, stevenson@science.uva.nl
Additional Notes

This work was supported by the Netherlands Organization for Scientific Research and by the European Community’s Human Potential Programme under contract HPRN-CT-2002-00286.

Journal Information
Mathematics of Computation, Volume 77, Issue 261, ISSN 0025-5718, published by the American Mathematical Society, Providence, Rhode Island.
Publication History
This article was received on , revised on , and published on .
Copyright Information
Copyright 2007 American Mathematical Society; reverts to public domain 28 years from publication
Article References

Settings

Change font size
Resize article panel