Printer Friendly

An iterative substructuring algorithm for a [C.sup.0] interior penalty method.

1. Introduction. Consider the following weak formulation of a fourth order model problem on a bounded polygonal domain [OMEGA] in [R.sup.2].

Find u [member of] [H.sup.2.sub.0]([OMEGA]) such that

(1.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all v [member of] [H.sup.2.sub.0]([OMEGA]), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the inner product of the Hessian matrices of the functions w and v.

The model problem (1.1) can be solved by [C.sup.0] interior penalty methods [10, 17, 25, 29]. For simplicity we assume that [OMEGA] has aquasi-uniform triangulation [T.sub.h] consisting of rectangles, and we take [V.sub.h] [subset] [H.sup.1.sub.0]([OMEGA]) to be the [Q.sub.2] Lagrange finite element space associated with [T.sub.h]. The discrete problem for (1.1) is to find [u.sub.h] [member of] [V.sub.h] such that

(1.2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

(1.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[[epsilon].sub.h] is the set of all edges of [T.sub.h], |e| is the length of the edge e, and [sigma] > 0 is a penalty parameter.

The jump [[*]] and the average {{*}} are defined as follows.

If e is an interior edge of [T.sub.h] shared by two elements [D.sub.-]and [D.sub.+] of [T.sub.h], and [n.sub.e] is the unit normal vector pointing from [D.sub.-] to [D.sub.+], then we define on e

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the values of the jumps and averages are independent of the choices of [D.sub.[+ or -]]. For an edge e on the boundary of [OMEGA], we take [n.sub.e] to be the outward pointing unit normal vector and define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The [C.sup.0] interior penalty method is consistent in the sense that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover, for [sigma] > 0 sufficiently large (which is assumed to be the case), there exist positive constants [C.sub.1] and [C.sub.2] independent of h such that

(1.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently, the error [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is quasi-optimal [17].

[C.sup.0] interior penalty methods, which belong to the class of discontinuous Galerkin methods, have certain advantages over the usual finite element methods for fourth order problems. They are simpler than C1finite element methods. They come in a natural hierarchy (which is not the case for classical nonconforming finite element methods), and they preserve the symmetric positive definite property of the continuous problem (which is not the case for mixed finite element methods). They have also been applied to many other fourth order problems [11, 12, 18, 25, 33, 38, 39].

As an approximation of a fourth order differential operator, the condition number of the discrete problem grows at the rate of h-4; cf. [31]. Thus a good preconditioner is essential for solving the discrete problem efficiently and accurately. Previously we have shown in [19] that the two-level additive Schwarz preconditioner for classical finite element methods [24] can be extended to [C.sup.0]interior penalty methods with similar performance. In this paper we will extend the Bramble-Pasciak-Schatz preconditioner [8] to [C.sup.0]interior penalty methods and show that the preconditioned system satisfies similar condition number estimates as in the case of classical finite element methods. This extension requires a new treatment of the degrees of freedom on the interface of the subdomains, which is discussed in Section 2. The techniques developed in this paper can be applied to [C.sup.0]interior penalty methods on general domains with simplicial triangulations, and they are also useful for other discontinuous Galerkin methods for fourth order problems [4, 34]. We note that domain decomposition algorithms for other discontinuous Galerkin methods can be found in [1, 2, 3, 5, 13, 22, 23, 26, 27, 30].

The rest of this paper is organized as follows. We introduce the iterative substructuring algorithm in Section 2. In Section 3 we construct a trace norm that plays a key role in the analysis of the preconditioned system. The condition number estimates are then derived in Section 4, and numerical results are presented in Section 5. Appendix A contains the proof of a lemma that is crucial for the analysis in Section 4.

2. An iterative substructuring algorithm. We begin with a nonoverlapping domain decomposition of [OMEGA] consisting of rectangular (open) subdomains [[OMEGA].sub.1],[[OMEGA].sub.2],...,[[OMEGA].sub.J] aligned with [T.sub.h] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We assume the subdomains are shape regular and denote the typical diameter of the subdomains by H. The interface of the subdomains is the set [GAMMA] =[[union].sup.J.sub.j=1][[GAMMA].sub.j], where [[GAMMA].sub.j] = [partial derivative][OMEGA]j.

REMARK 2.1. Note that [partial derivative][OMEGA] is part of the interface because the boundary condition for the normal derivative is only enforced weakly through the penalty term in (1.3).

The off-interface space [V.sub.h]([OMEGA] \ [GAMMA]) [subset] [V.sub.h] is defined by

[V.sub.h]([OMEGA] \ [GAMMA]) = {v [member of] [V.sub.h]: v vanishes to first order on [GAMMA]},

i.e., v [member of] [V.sub.h]belongs to [V.sub.h]([OMEGA] [GAMMA]) if and only if v and its normal derivative vanish on [GAMMA]. Since the condition that the normal derivative of v vanishes on [GAMMA] is implicit in terms of the standard degrees of freedom (dofs) of the [Q.sub.2] finite element, it is more convenient for both implementation and analysis to modify the dofs for [V.sub.h] as follows.

(i) For an element D away from the interface [GAMMA], we keep the standard dofs, namely the values of v [member of] [V.sub.h]at the four vertices of D, at the four midpoints along [partial derivative]D, and at the center of D (cf. the left-hand side of Figure 2.1).

(ii) For an element D that is away from the corners of the subdomains but has an edge e on [GAMMA], we take the dofs to be the values of v and its normal derivative at the vertices and the midpoint of e and the values of v at the vertices and midpoint of the edge parallel to e (cf. the middle of Figure 2.1).

(iii) Finally, suppose a corner of the subdomain is also a vertex p of an element D and [e.sub.1] and e2are the two edges of D that share p as a common vertex (i.e., [e.sub.1], [e.sub.2][subset] [GAMMA]). In this case we take the dofs to be the value of v at p, the values of its first order derivatives and second order mixed derivative at p, the values of v at the other three vertices of D, and the values of the normal derivative of v at the endpoints of [e.sub.1] and [[epsilon].sub.2] that are different from p (cf. the right-hand side of Figure 2.1).

[FIGURE 2.1 OMITTED]

The dofs for the three cases are depicted in Figure 2.1, where the solid dot * denotes the pointwise evaluation of the shape functions, the arrow [up arrow] denotes the pointwise evaluation of the directional derivatives of the shape functions, and the double arrow [??] denotes the pointwise evaluation of the mixed second order derivative of the shape functions. It is easy to check that in each case a biquadratic polynomial is uniquely determined by the dofs.

REMARK 2.2. If one of the edges of D is on the boundary of the subdomain, then the values of v and [partial derivative]v/[partial derivative]nare uniquely determined by the dofs associated with the nodes on that edge (cf. the middle and the right-hand side in Figure 2.1).

The modified (global) dofs for [V.sub.h]are depicted on the left of Figure 2.2 for a square divided into four subdomains.

[FIGURE 2.2. OMITTED]

Let v [member of] [V.sub.h]. The dofs of v associated with the nodes that are not on [GAMMA] are standard. The dofs of v associated with the nodes on [GAMMA] can be divided into the following cases.

(i) There are three dofs associated with a node on [GAMMA] that is interior to [OMEGA] and not the corner of any subdomain, namely the value of v and the values of the normal derivatives of v from the two sides.

(ii) At a node on [partial derivative][OMEGA] that is not the corner of any subdomain, there is only one dof, namely the value of the normal derivative of v.

(iii) There is also only one dof at a node that is one of the corners of [OMEGA], namely the value of the mixed second order derivative [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(iv) At a node on [GAMMA] [intersection] [partial derivative][OMEGA] that is the common corner of two subdomains, there are three dofs, namely the value of the normal derivative of v and the values of the two mixed second order derivatives of v from the two subdomains.

(v) There are nine dofs associated with a node on [GAMMA] that is the common vertex of four subdomains: the value of v, the values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from left and right, the values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from below and above, and the values of the mixed second order derivatives of v from the four subdomains.

In terms of the new dofs, v [member of] [V.sub.h]([OMEGA] [GAMMA]) if and only if the dofs of v along [GAMMA] are identically 0. We will use these new dofs for [V.sub.h]in the rest of the paper.

REMARK 2.3. Since [V.sub.h] is a subspace of [H.sup.1.sub.0]([OMEGA]), the dofs represented by solid dots on [partial derivative][OMEGA] are not included in the global dofs. On the other hand, the normal derivative and mixed second order derivative of a finite element function in [V.sub.h]are not constrained along [partial derivative][OMEGA] and therefore the dofs represented by arrows and double arrows along [partial derivative][OMEGA] are included in the global dofs.

Next we define the interface space [V.sub.h]([GAMMA]) to be the orthogonal complement of [V.sub.h]([OMEGA]\[GAMMA]) with respect to [A.sub.h](*,*), i.e.,

[V.sub.h]([GAMMA]) = {v [member of] [V.sub.h]: [A.sub.h](v,w) = 0, [for all]w [member of] [V.sub.h]([OMEGA] \ [GAMMA])}.

The functions in [V.sub.h]([GAMMA]) will be referred to as discrete biharmonic functions. They are uniquely determined by the dofs associated with [GAMMA] (cf. the right-hand side of Figure 2.2 for the case where a square is divided into four subdomains). The discrete biharmonic functions enjoy the following minimum energy property.

LEMMA 2.4. We have

[A.sub.h](v,v) [less than or equal to] [A.sub.h](w,w)

for any v [member of] [V.sub.h]([GAMMA]) and w [member of] [V.sub.h]that have identical dofs along [GAMMA].

Proof. Since w - v [member of] [V.sub.h]([OMEGA] \ [GAMMA]), we have by orthogonality

[A.sub.h](w,w) = [A.sub.h]((w - v) + v,(w - v) + v) = [A.sub.h](w - v,w - v) + [A.sub.h](v,v) [greater than or equal to] [A.sub.h](v,v).

The solution of the discrete problem (1.2) can be decomposed as

[u.sub.h]= [[??].sub.h]+ [[bar.u].sub.h],

where [??]sub.h][member of] [V.sub.h]([OMEGA]\[GAMMA]) and [[bar.u].sub.h][member of] [V.sub.h]([GAMMA]), and then (1.2) is equivalent to the following problem.

Find [??]sub.h][member of] [V.sub.h]([OMEGA] \ [GAMMA]) and [[bar.u].sub.h][member of] [V.sub.h]([GAMMA]) such that [A.sub.h]([??]sub.h],v) =

(2.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [V.sub.h]([[OMEGA].sub.j]) be the space of [Q.sub.2] finite element functions on [[OMEGA].sub.j]that vanish to first order on [partial derivative][[OMEGA].sub.j], i.e., it is the restriction of [V.sub.h]([OMEGA] \ [GAMMA]) to [[OMEGA].sub.j]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and we have

(2.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [??] [member of] [V.sub.h] is the trivial extension of v. Therefore, for 1 [less than or equal to] j [less than or equal to] J, [[??]sub.h,j] can be computed by solving the subdomain problems (2.2) in parallel, and it only remains to construct an efficient solver for (2.1).

Let [S.sub.h]: [V.sub.h]([GAMMA]) [right arrow] [V.sub.h]([GAMMA])' be the Schur complement operator defined by

(2.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where <*,*> is the canonical bilinear form between a vector space and its dual. We can rewrite (2.1) as

(2.4) [S.sub.h][[bar.u].sub.h]= [f.sub.h],

where [f.sub.h][member of] [V.sub.h]([GAMMA])?is defined by <[f.sub.h],v> [[integral].sub.[OMEGA]] fv dx for all v [member of] [V.sub.h]([GAMMA]). The last ingredient of the iterative substructuring algorithm is provided by a preconditioner for [S.sub.h] introduced by Bramble-Pasciak-Schatz [8] for classical finite element methods. Equation (2.4) can then be solved efficiently by the preconditioned conjugate gradient method.

The Bramble-Pasciak-Schatz (BPS) preconditioner involves local edge spaces and a global coarse space. Let [E.sub.1], [E.sub.2], ..., [E.sub.L] be the (closed) edges of the subdomains. The edge space [V.sub.l]([subset] [V.sub.h]([GAMMA])) associated with the edge [E.sub.l] is defined as follows. A discrete biharmonic function v belongs to [V.sub.l]if and only if

(i) v vanishes identically outside the subdomains that contain [E.sub.l]as a boundary edge,

(ii) the dofs of v at the nodes on [GAMMA] \ [E.sub.l]are identically 0.

Thus the discrete biharmonic functions in an edge space are determined by the dofs depicted in Figure 2.3, where on the left we have an edge shared by two subdomains and on the right we have an edge on [partial derivative][OMEGA] that belongs to the boundary of only one subdomain.

[FIGURE 2.3 OMITTED]

The edge space [V.sub.l]is connected to [V.sub.h]([GAMMA]) by the natural injection [I.sub.l], and there is an SPD operator [S.sub.L]: [V.sub.l][right arrow] [V?.sub.L]defined by

(2.5) <[S.sub.L]v,w> = [A.sub.h](v,w) [for all]v,w [member of] [V.sub.l].

For the BPS preconditioner, the global communication among subdomains is provided by the coarse space [V.sub.0] = [V.sub.H] [subset] [H.sup.1.sub.0]([OMEGA]), which is the [Q.sub.1] Lagrange finite element space associated with the subdomains [[OMEGA].sub.1],...,[[OMEGA].sub.J]. (The dofs for the [Q.sub.1] Lagrange finite element are depicted on the left-hand side of Figure 2.4.) We define [S.sub.0]: [V.sub.H][right arrow] [V'.sub.H] by

(2.6) <[S.sub.0]v,w> = [A.sub.H](v,w) [for all]v,w [member of] [V.sub.H],

where [A.sub.H] is the analog of [A.sub.h].

The connection between VHand [V.sub.h]([GAMMA]) is given by an operator [I.sub.0] constructed by the following procedure. Let [[??].sub.H] [subset] [H.sup.2.sub.0]([OMEGA]) be the [Q.sub.3]Bogner-Fox-Schmit finite element space associated with [T.sub.H]. (The dofs for this C1element are depicted in the middle of Figure 2.4.) First we define an enriching operator [E.sub.H]: [V.sub.H][right arrow][[??].sub.H] by averaging, i.e., we define the dof of [E.sub.H]v at a node to be the average of the dofs of v at the same node from all the subdomains sharing that node. More precisely, we take

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where p is any subdomain vertex in the interior of [OMEGA], [T.sub.H],pis the set of the four subdomains sharing p as a vertex, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The following result can be easily obtained by a direct calculation; cf. [9, 17, 20] for similar estimates.

LEMMA 2.5. There exists a positive constant [C.sub.3] depending only on the shape regularity of [T.sub.H] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 2.4 OMITTED]

We take [I.sub.0]v [member of] [V.sub.h]([GAMMA]) to be the discrete biharmonic function whose dofs on [GAMMA] (cf. the right-hand side of Figure 2.2) are identical with the corresponding dofs of [E.sub.H]v.

REMARK 2.6. If we define the dofs of [I.sub.0]v directly from v, then the performance of the preconditioner will be adversely affected by the different scalings that appear in the penalty terms for [A.sub.H](*,*) and [A.sub.h](*,*). This problem is avoided by [I.sub.0]defined above because [E.sub.H]v [member of] [H.sup.2.sub.0]([OMEGA]) and the penalty term associated with [A.sub.h](*,*) has no effect on [I.sub.0]v.

We can now define the BPS preconditioner [B.sub.BPS]: [V.sub.h]([GAMMA])?[right arrow] [V.sub.h]([GAMMA]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [I.sup.t.sub.l]: [V.sub.h]([GAMMA])?[right arrow] [V?.sub.L]is the transpose of [I.sub.l]: [V.sub.l][right arrow] [V.sub.h]([GAMMA]), i.e.,

<[I.sup.t.sub.l][phi],v> = <[phi],[I.sub.l]v> [for all]v [member of] [V.sub.l], [phi] [member of] [V.sub.h]([GAMMA])?.

It is easy to see that [V.sub.h]([GAMMA]) = [[SIGMA].sup.L.sub.l=0] [I.sub.l][V.sub.l]. It then follows from the theory of additive Schwarz preconditioners [6, 14, 24, 28, 32, 35, 36, 37, 40, 41] that the eigenvalues of [B.sub.BPS][S.sub.h] are positive and that the maximum and minimum eigenvalues of [B.sub.BPS][S.sub.h]are characterized by the following formulas:

(2.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(2.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3. A trace norm. In this section we construct a trace norm on [V.sub.h]([GAMMA]) that only involves integrals defined on [GAMMA], and which is equivalent to the energy norm [square root of [A.sub.h](*,*)]. It will play an important role in the derivation of a lower bound for [[lambda].sub.min]([B.sub.BPS][S.sub.h]).

To avoid the proliferation of constants, from now on we use the notation A [less than or equal to] B to represent the statement A [less than or equal to] (constant) xB, where the positive constant does not depend on h, H, and J. The notation A ? B is equivalent to A [less than or equal to] B and B [less than or equal to] A.

Let [V.sub.h,j], 1 [less than or equal to] j [less than or equal to] J, be the restrictions of [V.sub.h]to the subdomain [[OMEGA].sub.j], i.e., it is the [Q.sub.2] finite element space associated with [T.sub.h,j](the restriction of [T.sub.h] to [[OMEGA].sub.j]) whose members vanish

on [partial derivative][OMEGA] [intersection] [partial derivative][[OMEGA].sub.j]. We introduce a seminorm [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on [V.sub.h,j]defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can then write

(3.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let [[??].sub.h,j]be the Q4Bogner-Fox-Schmit finite element space on [[OMEGA].sub.j]associated with [T.sub.h,j] such that its members vanish on [partial derivative][OMEGA] [intersection] [partial derivative][[OMEGA].sub.j]. (The dofs for this C1element are depicted on the right-hand side of Figure 2.4.) Our construction of the trace norm on [V.sub.h]([GAMMA]) uses the enriching map [E.sub.j] : [V.sub.h,j] [right arrow][[??].sub.h,j]defined by averaging: at any node of[[??].sub.h,j], we assign a dof of [E.sub.j]v to be the average of the corresponding dofs of v from the elements that share that node. More precisely, for a given v [member of] [V.sub.h,j], the dofs of [E.sub.j]v [member of][[??].sub.h,j] are defined as follows.

(i) [E.sub.j]v equals v at all nodes (vertices, midpoints, centers) of [T.sub.h,j].

(ii) At an interior vertex of [T.sub.h,j], [nabla]([E.sub.j]v) (respectively [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the average of [nabla]v (respectively [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ) at that vertex from the four elements sharing p as a common vertex.

(iii) At a vertex of [T.sub.h,j] on [partial derivative] [[OMEGA].sub.j] that is not a corner of [[OMEGA].sub.j], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] while the tangential (respectively mixed second order) derivative of [E.sub.j]v is the average of the tangential (respectively mixed second order) derivatives of v from the two elements sharing p as a common vertex.

(iv) At the midpoint of an interior edge, the normal derivative of [E.sub.j]v is the average of the two normal derivatives of v (from the two sides) at that midpoint.

(v) At the midpoint of an edge on [partial derivative][[OMEGA].sub.j], the normal derivative [E.sub.j]v equals the normal derivative of v.

(vi) The dofs of [E.sub.j]v at the four corners of [[OMEGA].sub.j]are identical with the dofs of v at the corners.

REMARK 3.1. In view of Remark 2.2, the dofs of [E.sub.j]v on [partial derivative][[OMEGA].sub.j]are determined by the dofs of v on [partial derivative][[OMEGA].sub.j].

The following result again can be obtained by a direct calculation.

LEMMA 3.2. We have, for 1 [less than or equal to] j [less than or equal to] J,

(3.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can also define a map [F.sub.j]:[[??].sub.h,j][right arrow] [V.sub.h,j]by assigning the dofs of [F.sub.j]v [member of] [V.sub.h,j]to be identical with the corresponding dofs of v [member of][[??].sub.h,j]. The following result can be derived by a simple element-wise calculation.

LEMMA 3.3. We have, for 1 [less than or equal to] j [less than or equal to] J,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From the definitions of [E.sub.j]and [F.sub.j], it is easy to see that [F.sub.j]([E.sub.j]v) = v for all v [member of] [V.sub.h,j].

The lemma below follows directly from Lemma 3.2 and Lemma 3.3.

LEMMA 3.4. We have, for 1 [less than or equal to] j [less than or equal to] J,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Given any [v.sub.j][member of] [V.sub.h,j], we define the functions [D.sub.1][v.sub.j]and [D.sub.2][v.sub.j]on [partial derivative][[OMEGA].sub.j] by

(3.3) [ILLUSTRATION OMITTED]

In view of Remark 3.1, the functions [D.sub.1]v and [D.sub.2]v can be computed from the dofs of v associated with [[GAMMA].sub.j]. Recall that the Sobolev seminorm H1/2([partial derivative][[OMEGA].sub.j]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The following result shows that on the space [V.sub.h]([GAMMA]), the energy norm [square root of [A.sub.h](*,*)] is equivalent to a trace norm that only involves integrals defined on [GAMMA]. Its proof is given in Appendix A.

LEMMA 3.5. We have

(3.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4. Condition number estimates. First we consider an upper bound for the eigenvalues of the operator [B.sub.BPS][S.sub.h].

LEMMA 4.1. The maximum eigenvalue of [B.sub.BPS][S.sub.h]satisfies the following estimate:

(4.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Let v [member of] [V.sub.h]([GAMMA]) be arbitrary, and let [v.sub.l][member of] [V.sub.l]for 0 [less than or equal to] l [less than or equal to] L satisfy

(4.2) v = [L.summation over (l=0)] [I.sub.l][v.sub.l].

It follows from (2.3) and the Cauchy-Schwarz inequality that

(4.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let z [member of] [V.sub.h]be defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then z and [I.sub.0]v have identical dofs along [GAMMA] and hence

(4.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by Lemma 2.4, (1.4), (3.1), Lemma 3.3, Lemma 2.5, and (2.6). Here we have also used the fact that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on [GAMMA]. Finally since [A.sub.h]([I.sub.l][v.sub.l],[I.sub.k][v.sub.k]) = 0 unless the subdomains [[OMEGA].sub.l] and [[OMEGA].sub.k] are sufficiently close, we have by (2.5)

(4.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Putting the estimates (4.3)-(4.5) together, we find <[S.sub.h]v,v> [less than or equal to] [[SIGMA].sup.L.sub.l=0] <[S.sub.L][v.sub.l],[v.sub.l]> and therefore

(4.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The bound (4.1) then follows from (2.7) and (4.6).

In order to obtain a lower bound for the eigenvalues of [B.sub.BPS][S.sub.h], we need to construct a particular decomposition (4.2) for any given v [member of] [V.sub.h]([GAMMA]) so that the energy of the functions [v.sub.l][member of] [V.sub.l]can be estimated in terms of the energy of v.

First of all, [v.sub.0][member of] [V.sub.H] is defined by the condition that [v.sub.0](p) = v(p) at the vertices of [T.sub.H], i.e., at the corners of the subdomains [[OMEGA].sub.1],...,[[OMEGA].sub.J]. We can treat [V.sub.0] as the [Q.sub.1]interpolant of the function [[epsilon].sub.h] v [member of] [H.sup.2.sub.0]([OMEGA]), where [[epsilon].sub.h] : [V.sub.h] [right arrow][[??].sub.h] [subset] [H.sup.2.sub.0]([OMEGA]) is defined using averaging and the Q4Bogner-Fox-Schmit finite element space[[??].sub.h]. The operator [[epsilon].sub.h] , which is an analog of [E.sub.H]: [v.sub.H][right arrow][[??].sub.H], satisfies (by a direct calculation) the following analog of the estimate in Lemma 2.5

(4.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

REMARK 4.2. The operators [[epsilon].sub.h] : [V.sub.h][right arrow][[??].sub.h]and [E.sub.j]: [V.sub.h,j][right arrow][[??].sub.h,j]are not related.

LEMMA 4.3. The following estimate holds

(4.8) <[S.sub.0][v.sub.0],[v.sub.0]> [less than or equal to] <[S.sub.h]v,v> [for all]v [member of] [V.sub.h]([GAMMA]).

Proof. By the standard interpolation error estimate for the [Q.sub.1]element, we have

(4.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for 1 [less than or equal to] j [less than or equal to] J. Let E belong to [E.sub.H], the set of the edges of the subdomains. It follows from (4.9) and the trace theorem with scaling that

(4.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [T.sub.H,E] is the set of the subdomains sharing E as a common edge.

Summing up (4.9) over [[OMEGA].sub.j] [member of] [T.sub.H] and (4.10) over E [member of] [E.sub.H], we find by (1.4), (2.6), and (4.7),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let w = v - [I.sub.0][v.sub.0]. It follows from (4.4) and (4.8) that

(4.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We also have a discrete Sobolev inequality.

LEMMA 4.4. We have, for 1 [less than or equal to] j [less than or equal to] J and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Since [nabla][E.sub.j][w.sub.j] [member of] [H.sup.1]([[OMEGA].sub.j]), by a standard discrete Sobolev inequality [8, 16], we Have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Furthermore, since [E.sub.j][w.sub.j]= [w.sub.j]= 0 at the corners of [[OMEGA].sub.j], we also have [15, Lemma 4.8]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now we choose [v.sub.l] [member of] [V.sub.l], for 1 [less than or equal to] l [less than or equal to] L, so that (4.2) holds, i.e., w = [[SIGMA].sup.L.sub.l=1][v.sub.l]. By comparing the dofs for [V.sub.h]([GAMMA]) (cf. the right-hand side of Figure 2.2) and the dofs for the edge spaces (cf. Figure 2.3), we see that the dofs of [v.sub.l] are uniquely determined by the corresponding dofs of w except the mixed second order derivatives at a common corner of four subdomains. At such a node we choose the mixed second order derivative of [v.sub.l] to be 1/2 of the corresponding mixed second order derivative of w.

It follows from Lemma 3.5 that

(4.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [T.sub.H],[E.sub.l]is the set of the subdomains that share [E.sub.l]as a common edge. We begin by estimating the first sum on the right-hand side of (4.12).

LEMMA 4.5. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. We will focus on the estimate for [v.sub.l] associated with an interior vertical (closed) edge [E.sub.l](cf. the left-hand side of Figure 2.3). The cases of horizontal edges and boundary edges can be handled in a similar fashion.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the two subdomains sharing [E.sub.l]as a common edge and e be a (closed) edge in [[epsilon].sub.h] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. There are several possibilities.

(i) If e does not intersect [E.sub.l], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] because the normal derivative of [v.sub.l] is identically 0 from both sides of e.

(ii) If e [subset] [E.sub.l]but does not touch either endpoints of [E.sub.l], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(iii) If e [subset] [E.sub.l]does touch the endpoint p of [E.sub.l], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on e because the derivatives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have been set to 0 at p and the mixed second order derivatives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] equal one half of the corresponding mixed second order derivatives of w at p. In this case we have by scaling

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(iv) If e is one of the four horizontal edges that touch p, say [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then we Have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on e because [v.sub.l] is identically 0 on the other side. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on e is determined by the values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at p, we have by scaling and a standard inverse estimate

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

on the edge e. Note that we have used the defining properties (iii) and (vi) of [E.sub.j]that appear just before Remark 3.1.

Summing up the contributions over all the cases, we find

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by using Lemma 4.4, (3.2), and (3.1).

We now turn to the second sum on the right-hand side of (4.12).

LEMMA 4.6. We have

(4.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. This time we will focus on a horizontal edge [E.sub.l](cf. Figure 4.1). Let [[OMEGA].sub.k] be a subdomain that shares [E.sub.l]as a common edge, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. First we consider [D.sub.1][v.sub.l,k] on [partial derivative][[OMEGA].sub.k]. Since [v.sub.l,k]and [w.sub.k]have identical dofs that define them as piecewise quartic polynomials on [E.sub.l]in the [x.sub.1] variable (cf. Figure 4.1), we have [v.sub.l,k]= [w.sub.k] on [E.sub.l] and hence

(4.14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The dofs of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are identically zero outside [E.sub.l]except those at the endpoints and midpoints of e5and e7(cf. Figure 4.1). It follows that

(4.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 4.1 OMITTED]

Moreover, the dofs of the piecewise quartic polynomial [D.sub.1][v.sub.l,k](in the [x.sub.2] variable) at these nodes are determined by the values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the endpoints of [E.sub.l]. Therefore, by scaling, we have

(4.16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [E.sub.l,k]= [e.sub.6][union][e.sub.5][union][E.sub.l][union] [e.sub.7] [union] [e.sub.8]. By (4.15) and a standard estimate for truncated piecewise polynomials (cf. [8, Section 3], [37, Section 4.6], [14, Section 7.5]), we have

(4.18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Furthermore, we have by the relations (4.14)-(4.16) and scaling

(4.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Combining (4.17)-(4.19), Lemma 4.4, the trace theorem, and Lemma 3.2, we conclude that

(4.20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next we consider [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The dofs of the piecewise quartic polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on [E.sub.l](in the x1variable) are identical with those for the piecewise quartic polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] except at the vertices and midpoints of e1and [e.sub.4](cf. Figure 4.1). It follows that

(4.21) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover, the difference between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on [e.sub.1] [union] [e.sub.2][union] [e.sub.3][union] [e.sub.4] is determined by the values of[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at the two endpoints of [E.sub.l]. Therefore we have

(4.22) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally we observe that

(4.23) the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Using (4.21)-(4.23) and arguments similar to the ones for the derivation of (4.20), we have

(4.24) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The estimate (4.13) follows by summing up (4.20) and (4.24) over the edges [E.sub.1],...,[E.sub.L].

We can now establish a lower bound for the eigenvalues of [B.sub.BPS][S.sub.h].

LEMMA 4.7. The minimum eigenvalue of [B.sub.BPS][S.sub.h]satisfies the following estimate:

[[lambda].sub.min]([B.sub.BPS][S.sub.h]) [greater than or equal to] [(1 + ln(H/h)).sup.-2].

Proof. Letv [member of] [V.sub.h]([GAMMA])bearbitrary, andletvl[member of] [V.sub.l]for0 [less than or equal to] l [less than or equal to] L be the particular decomposition of v that we have constructed. It follows from (4.12), Lemma 4.5, Lemma 4.6, (3.1), and (4.11), that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which together with (2.8) implies the lower bound.

Lemma 4.1 and Lemma 4.7 immediately imply the following bound on the condition number of the preconditioned system [B.sub.BPS][S.sub.h].

THEOREM 4.8. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the positive constant C is independent of h, H, and J.

5. Numerical results. In this section, we report some numerical results for our model problem on the unit square. We take the penalty parameter [sigma] in [A.sub.h],[A.sub.H], and Alto be 5 in the numerical experiments, and we compute the maximum eigenvalue, the minimum eigenvalue, and the condition number of [B.sub.BPS][S.sub.h]for different values of h, H and J.

For each choice of h, H, and J, we generate a vector vh[member of] [V.sub.h]([GAMMA]) randomly as our exact solution and compute the right-hand side g. Then we apply the preconditioned conjugate gradient algorithm to the linear system Shz = g with the Bramble-Pasciak-Schatz preconditioner and 0 as the initial value. The iteration is stopped when the energy norm error is reduced by a factor of 10-6and the minimum and maximum eigenvalues are estimated by the Lanczos algorithm. The average results over 5 random choices of vhare reported in the tables below.

REMARK 5.1. Since we are solving a fourth order problem, the condition number of [S.sub.h] is very large for small h. This is the reason why we use a more stringent stopping criterion than the usual criterion based on the residual error.

The results for the eigenvalues and condition numbers for 4 subdomains, 16 subdomains, and 64 subdomains are reported in Table 5.1, Table 5.2, and Table 5.3, respectively. They agree with the estimates in Lemma 4.1, Lemma 4.7, and Theorem 4.8. The average number of iterations in these computations are presented in Table 5.4, where the scalability of the preconditioner can be observed.

To illustrate the practical performance of the preconditioner, we present in Table 5.5 the number of iterations required to reduce the energy error by a factor of 10-2for various h and H.

Appendix A. Proof of Lemma 3.5. We need two technical results for the proof of Lemma 3.5. The first one is a trace theorem proven in [15, Lemmas 4.1-4.3].

LEMMA A.1. We have, for 1 [less than or equal to] j [less than or equal to] J,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Furthermore, given any w [member of] [H.sup.2]([[OMEGA].sub.j]), there exists [??] [member of] [H.sup.2]([[OMEGA].sub.j]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The second result concerns a Q4 Bogner-Fox-Schmit quasi-interpolant for a function [zeta] [member of] [H.sup.2]([[OMEGA].sub.j]). Suppose that for each edge e [member of] [[epsilon].sub.h] such that e [subset][[bar.[OMEGA]].sub.j], a unit normal vector ne has been chosen. Let [[zeta].sub.e] [member of] [P.sub.4](e) and [[zeta].sup.*.sub.e][member of] [P.sub.4](e) be the L2(e) projections of [zeta][|.sub.e] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively. We then assign the dofs of an quasi-interpolant [v.sub.[zeta]] in the Q4Bogner-Fox-Schmit space associated with [T.sub.h,j]as follows.

If m is the midpoint of an edge e [member of] [[epsilon].sub.h,j] (the set of the edges of [T.sub.h,j]), we define

(A.1) [v.sub.[zeta]](m) = [zeta](m) and ([nabla][v.sub.[zeta]](m))) * [n.sub.e]= [[zeta].sup.*.sub.e](m).

If p is a vertex in [T.sub.h,j], then we choose an edge e [member of] [[epsilon].sub.h] ,j with p as an endpoint and define

(A.2) [v.sub.[zeta]](p) = [zeta](p), [t.sub.e] ([nabla][v.sub.[zeta]](p))) * [n.sub.e]= ([[zeta].sup.*.sub.e])'(p).

and ([nabla][v.sub.[zeta]])(p) to be the vector satisfying

(A.3) ([nabla][v.sub.[zeta]])(p) * [n.sub.e]= [[zeta].sup.*.sub.e](p),

(A.4) ([nabla][v.sub.[zeta]])(p) * [n.sub.e]= [[zeta]'.sub.e](p)

where [t.sub.e] is a unit tangent vector of e and [[zeta]?.sub.e] (respectively ([[zeta].sup.*.sub.e])?) is the derivative of [[zeta].sub.e](respectively [zeta]* e) in the direction of [t.sub.e]. Finally, for the center c of an element D [member of] [T.sub.h], we define

(A.5) [v.sub.[zeta]](c) = [zeta](c).

Note that the choice of the dofs of [v.sub.[zeta]]at a vertex p is not unique since there are many edges sharing p as a common endpoint. In order to control the behavior of [v.sub.[zeta]]on [partial derivative][[OMEGA].sub.j]for any p on [partial derivative][[OMEGA].sub.j], we choose e to be an edge on [partial derivative][[OMEGA].sub.j]. Furthermore, we choose e to be an edge on [partial derivative][OMEGA] [intersection] [partial derivative][[OMEGA].sub.j]if p belongs to [partial derivative][OMEGA] [intersection] [partial derivative][[OMEGA].sub.j]. (Admissible edges represented by thick lines for various vertices represented by bullets are depicted in Figure A.1.)

[FIGURE A.1 OMITTED]

REMARK A.2. If both [zeta] and [partial derivative][zeta]/[partial derivative]n belong to [P.sub.4](e) on all the boundary edges e on [partial derivative][[OMEGA].sub.j], then [[zeta].sub.e]= [zeta] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on all the boundary edges, which implies [v.sub.[zeta]] = [zeta] to first order on [partial derivative][OMEGA].

REMARK A.3. If [zeta] = 0 on [partial derivative][OMEGA] [intersection] [partial derivative][[OMEGA].sub.j], then [v.sub.[zeta]]= 0 on [partial derivative][OMEGA] [intersection] [partial derivative][[OMEGA].sub.j]and hence [v.sub.[zeta]][member of] [V.sub.h,j].

LEMMA A.4. We have, for 1 [less than or equal to] j [less than or equal to] J,

(A.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Let [D.sub.*][member of] [T.sub.h,j]be arbitrary, and let [e.sub.1], [e.sub.2] be the two edges of [D.sub.* ]sharing p as a common endpoint. Suppose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are defined by (A.2)-(A.4) using [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are defined by (A.2)-(A.4) using [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [zeta] [member of] [P.sub.1]([D.sub.*]), then it is clear that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by the Bramble-Hilbert Lemma [7] and scaling, we have

(A.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(A.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The estimates (A.7) and (A.8) measure the effect of choosing different edges (from the same element) in the definition of the quasi-interpolant [v.sub.[zeta]].

Suppose now the interpolant [v.sub.[zeta]],[D.sub.*] of [zeta] is defined on [D.sub.*]by (A.1)-(A.5) in a particular way, namely the dofs of [v.sub.[zeta]],[D.sub.*]at a vertex p of [D.sub.*]are defined by using the edge that precedes p in the counterclockwise direction. The triangle inequality and a standard inverse estimate [21, 14] imply that

(A.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

First we claim that

(A.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Indeed, since all the dofs of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] defined by (A.1)-(A.5) are bounded by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the seminorm [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is bounded by a multiple of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, [v.sub.[zeta]],[D.sub.*]= [zeta] if [zeta] [member of] P1([D.sub.*]), and the seminorm |[v.sub.[zeta]],[D.sub.*]|[H.sup.2]([D.sub.*])is invariant under addition of linear polynomials. Therefore the estimate (A.10) follows from the Bramble-Hilbert Lemma and scaling.

Secondly it follows from the definitions of [v.sub.[zeta]]and [v.sub.[zeta]],[D.sub.*]and (A.7)-(A.8) that

(A.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where S([D.sub.*]) is the union of all D [member of] [T.sub.h,j] that share at least one common vertex with [D.sub.*]. Combining (A.9)-(A.11), we have

(A.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The estimate (A.6) is obtained by summing up (A.12) over all [D.sub.*][member of] [T.sub.h,j].

Proof of Lemma 3.5. Let v [member of] [V.sub.h]([GAMMA]) be arbitrary, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It follows from (3.3), Lemma A.1, and Lemma 3.4 that

(A.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Combining (A.13), (3.1), and (1.4), we find

(A.14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, it follows from Lemma A.1 that there exist functions [[zeta].sub.j] [member of] [H.sup.2]([[OMEGA].sub.j]) for 1 [less than or equal to] j [less than or equal to] J such that

(A.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(A.16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a [Q.sub.4] Bogner-Fox-Schmit quasi-interpolant of [[zeta].sub.j]. In view of (A.15) and Remark A.2, we have

(A.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It follows from the definition of [F.sub.j], Lemma 3.3, Lemma A.4, (A.16), and (A.17) that

(A.18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(A.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now we take z [member of] [V.sub.h]such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It follows from (A.18) that z = v up to first order on [GAMMA]. Therefore we can apply Lemma 2.4, (1.4), (3.1), (A.18), (A.19), and (3.3) to obtain

(A.20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The equivalence (3.4) follows from (A.14) and (A.20).

REFERENCES

[1] P. ANTONIETTI AND B. AYUSO DE DIOS, Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case, M2AN Math. Model. Numer. Anal., 41 (2007), pp. 21-54.

[2] --, Two-level Schwarz preconditioners for super penalty discontinuous Galerkin methods, Commun. Comput. Phys., 5 (2009), pp. 398-412.

[3] P. ANTONIETTI, B. AYUSO DE DIOS, S. C. BRENNER, AND L.-Y. SUNG, Schwarz methods for a preconditioned WOPSIP method for elliptic problems, Comput. Methods Appl. Math., 12 (2012), pp. 241-272.

[4] G. BAKER, Finite element methods for elliptic equations using nonconforming elements, Math. Comp., 31 (1977), pp. 45-89.

[5] A. BARKER, S. C. BRENNER, E.-H. PARK, AND L.-Y. SUNG, Two-level additive Schwarz preconditioners for a weakly over-penalized symmetric interior penalty method, J. Sci. Comput., 47 (2011), pp. 27-49.

[6] P. BJORSTAD AND J. MANDEL, Onthespectraofsumsoforthogonalprojectionswithapplicationstoparallel computing, BIT, 31 (1991), pp. 76-88.

[7] J. BRAMBLE AND S. HILBERT, Estimation of linear functionals on Sobolev spaces with applications to Fourier transforms and spline interpolation, SIAM J. Numer. Anal., 7 (1970), pp. 112-124.

[8] J. BRAMBLE, J. PASCIAK, AND A. SCHATZ, The construction of preconditioners for elliptic problems by substructuring. I., Math. Comp., 47 (1986), pp. 103-134.

[9] S. C. BRENNER, Two-level additive Schwarz preconditioners for nonconforming finite element methods, Math. Comp., 65 (1996), pp. 897-921.

[10] --, [C.sup.0]Interior Penalty Methods, in Frontiers in Numerical Analysis-Durham 2010, J. Blowey and M. Jensen, eds., Lecture Notes in Computational Science and Engineering, 85, Springer, Berlin, 2012, pp. 79-147.

[11] S. C. BRENNER, S. GU, T. GUDI, AND L.-Y. SUNG, A quadratic [C.sup.0]interior penalty method for linear fourth order boundary value problems with boundary conditions of the Cahn-Hilliard type, SIAM J. Numer. Anal., 50 (2012), pp. 2088-2110.

[12] S. C. BRENNER AND M. NEILAN, A [C.sup.0]interior penalty method for a fourth order elliptic singular perturbation problem, SIAM J. Numer. Anal., 49 (2011), pp. 869-892.

[13] S. C. BRENNER, E.-H. PARK, AND L.-Y. SUNG, A balancing domain decomposition by constraints preconditioner for a weakly over-penalized symmetric interior penalty method, Numer. Linear Algebra Appl., in press, doi:10.1002/nla.1838.

[14] S. C. BRENNER AND L.R. SCOTT, The Mathematical Theory of Finite Element Methods, 3rd ed., Springer, New York, 2008.

[15] S. C. BRENNER AND L.-Y. SUNG, Balancing domain decomposition for nonconforming plate elements, Numer. Math., 83 (1999), pp. 25-52.

[16] --, Discrete Sobolev and Poincare inequalities via Fourier series, East-West J. Numer. Math., 8 (2000), pp. 83-92.

[17] --, [C.sup.0]interior penalty methods for fourth order elliptic boundary value problems on polygonal domains, J. Sci. Comput., 22/23 (2005), pp. 83-118.

[18] S. C. BRENNER, L.-Y. SUNG, AND Y. ZHANG, Finite element methods for the displacement obstacle problem of clamped plates, Math. Comp., 81 (2012), pp. 1247-1262.

[19] S. C. BRENNER AND K. WANG, Two-level additive Schwarz preconditioners for [C.sup.0]interior penalty methods, Numer. Math., 102 (2005), pp. 231-255.

[20] S. C. BRENNER, K. WANG, AND J. ZHAO, Poincare-Friedrichs inequalities for piecewise H2functions, Numer. Funct. Anal. Optim., 25 (2004), pp. 463-478.

[21] P. CIARLET, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978.

[22] L. DIOSADY AND D. DARMOFAL, A unified analysis of balancing domain decomposition by constraints for the discontinuous Galerkin discretizations, SIAM J. Numer. Anal., 50 (2012), pp. 1695-1712.

[23] M. DRYJA, J. GALVIS, AND M. SARKIS, BDDC methods for discontinuous Galerkin discretization of elliptic problems, J. Complexity, 23 (2007), pp. 715-739.

[24] M. DRYJA AND O. WIDLUND, An additive variant of the Schwarz alternating method in the case of many subregions, Tech. Report 339, Department of Computer Science, Courant Institute, New York, 1987.

[25] G. ENGEL, K. GARIKIPATI, T. HUGHES, M. LARSON, L. MAZZEI, AND R. TAYLOR, Continuous/discontinuous finite element approximations of fourth order elliptic problems in structural and continuum mechanics with applications to thin beams and plates, and strain gradient elasticity, Comput. Methods Appl. Mech. Engrg., 191 (2002), pp. 3669-3750.

[26] X. FENG AND O. KARAKASHIAN, Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems, SIAM J. Numer. Anal., 39 (2001), pp. 1343-1365.

[27] --, Two-level non-overlapping Schwarz preconditioners for a discontinuous Galerkin approximation of the biharmonic equation, J. Sci. Comput., 22/23 (2005), pp. 289-314.

[28] M. GRIEBEL AND P. OSWALD, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math., 70 (1995), pp. 163-180.

[29] T. GUDI, H. GUPTA, AND N. NATARAJ, Analysis of an interior penalty method for fourth order problems on polygonal domains, J. Sci. Comp., in press, doi:10.1007/s10915-012-9612-9.

[30] C. LASSER AND A. TOSELLI, An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems, Math. Comp., 72 (2003), pp. 1215-1238.

[31] S. LI AND K. WANG, Condition number estimates for [C.sup.0]interior penalty methods, in Domain Decomposition Methods in Science and Engineering XVI, O. Widlund and D. Keyes, eds., Lecture Notes in Computational Science and Engineering, 55, Springer, Berlin, 2007, pp. 675-682.

[32] T. MATHEW, Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations, Springer, Berlin, 2008.

[33] L. MOLARI, G. N. WELLS, K. GARIKIPATI, AND F. UBERTINI, A discontinuous Galerkin method for strain gradient-dependent damage: study of interpolations and convergence, Comput. Methods Appl. Mech. Engrg., 195 (2006), pp. 1480-1498.

[34] I. MOZOLEVSKI AND E. SULI, A priori error analysis for the hp-version of the discontinuous Galerkin finite element method for the biharmonic equation, Comput. Methods Appl. Math., 3 (2003), pp. 596-607.

[35] S. NEPOMNYASCHIKH, On the application of the bordering method to the mixed boundary value problem for elliptic equations and on mesh norms in [W.sup.1/2.sub.2] (S), Soviet J. Numer. Anal. Math. Modelling, 4 (1989), pp. 493-506.

[36] B. SMITH, P. BJORSTAD, AND W. GROPP, DomainDecomposition, CambridgeUniversityPress, Cambridge, 1996.

[37] A. TOSELLI AND O. WIDLUND, Domain Decomposition Methods - Algorithms and Theory, Springer, New York, 2005.

[38] G. WELLS, K. GARIKIPATI, AND L. MOLARI, A discontinuous Galerkin formulation for a strain gradient-dependent damage model, Comput. Methods Appl. Mech. Engrg., 193 (2004), pp. 3633-3645.

[39] G. WELLS, E. KUHL, AND K. GARIKIPATI, A discontinuous Galerkin method for the Cahn-Hilliard equation, J. Comput. Phys., 218 (2006), pp. 860-877.

[40] J. XU, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34 (1992), pp. 581-613.

[41] X. ZHANG, Studies in Domain Decomposition: Multilevel Methods and the Biharmonic Dirichlet Problem, PhD Thesis, Department of Computer Science, Courant Institute, New York, 1991.

* Received April 16, 2011. Accepted July 20, 2012. Published online on October 15, 2012. Recommended by U. Langer. This work was supported in part by the National Science Foundation under Grant No. DMS-10-16332 and by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.

SUSANNE C. BRENNER ([dagger]) AND KENING WANG ([double dagger])

([dagger]) Department of Mathematics and Center for Computation and Technology, Louisiana State University, Baton Rouge, LA 70803 (brenner@math.lsu.edu).

([double dagger]) Department of Mathematics and Statistics, University of North Florida, Jacksonville, FL 32224 (kening.wang@unf.edu).
Table 5.1

Eigenvalues and condition numbers for H = 1/2 (4 subdomains).

          [[lambda]      [[lambda]                    [square root
          .sub.max]      .sub.min]       [kappa]      of [kappa]]
         ([B.sub.BPS]   ([B.sub.BPS]   ([B.sub.BPS]   ([B.sub.BPS]
          [S.sub.h])     [S.sub.h])     [S.sub.h])    [S.sub.h])]

h=1/4       6.6170         0.4945        13.3825         3.6582
h=1/8       6.5345         0.2617        24.9672         4.9967
h=1/16      6.5354         0.1675        39.0163         6.2463
h=1/32      6.5359         0.1157        56.5020         7.5168
h=1/64      6.5360         0.0845        77.3800         8.7966

Table 5.2

Eigenvalues and condition numbers for H = 1/4 (16 subdomains).

           [[lambda]       [[lambda]                    [square root
           .sub.max]       .sub.min]       [kappa]      of [kappa]]
         ([B.suub.BPS]   ([B.suub.BPS]   ([B.sub.BPS]   ([B.sub.BPS]
           {S.sub.h]       {S.sub.h]      [S.sub.h])    [S.sub.h])]

h=1/8       6.8434          0.2235         30.6210         5.5336
h=1/16      6.6952          0.1387         48.2550         6.9466
h=1/32      6.6847          0.0978         68.3611         8.2681
h=1/64      6.6808          0.0725         92.1217         9.5980

Table 5.3

Eigenvalues and condition numbers for H = 1/8 (64 subdomains).

           [[lambda]       [[lambda]                    [square root
           .sub.max]       .sub.min]       [kappa]      of [kappa]]
         ([B.suub.BPS]   ([B.suub.BPS]   ([B.sub.BPS]   ([B.sub.BPS]
           {S.sub.h]       {S.sub.h]      [S.sub.h])    [S.sub.h])]

h=1/16      6.8785          0.1742         39.4859         6.2838

h=1/32      6.7239          0.1173         57.3270         7.5715

h=1/64      6.7102          0.0825         81.3200         9.0178

Table 5.4

Average number of iterations for reducing the energy norm error
by a factor of [10.sup.-6].

           H = 1/2   H = 1/4   H = 1/8   H = 1/16   H = 1/32

H/h = 2      22        37        43         43         43
H/h = 4      21        36        41         41         --
H/h = 8      20        38        42         --         --
H/h = 16     21        39        --         --         --
H/h = 32     22        --        --         --         --

Table 5.5

Average number of iterations for reducing the energy norm error
by a factor of [10.sub.-6]

           H = 1/2   H = 1/4   H = 1/8   H = 1/16   H = 1/32

H/h = 2       9        13        14         14         14
H/h = 4       9        10        11         11         --
H/h = 8       9        10        10         --          --
H/h = 16      8         8         --         --          --
H/h = 32      7         --         --         --          --
COPYRIGHT 2012 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Brenner, Susanne C.; Wang, Kening
Publication:Electronic Transactions on Numerical Analysis
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2012
Words:9477
Previous Article:Optimizing Runge-Kutta smoothers for unsteady flow problems.
Next Article:Cascadic multigrid preconditioner for elliptic equations with jump coefficients.
Topics:

Terms of use | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters