kl800.comÊ¡ÐÄ·¶ÎÄÍø

# Multigrid and multilevel methods for nonconforming rotated Q1 elements

Series Logo Volume 00, 19xx

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ROTATED Q1 ELEMENTS
ZHANGXIN CHEN AND PETER OSWALD
Abstract. In this paper we systematically study multigrid algorithms and

multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated Q1 nite elements. We rst derive optimal results for the W -cycle and variable V -cycle multigrid algorithms; we prove that the W -cycle algorithm with a su ciently large number of smoothing steps converges in the energy norm at a rate which is independent of grid number levels, and that the variable V -cycle algorithm provides a preconditioner with a condition number which is bounded independently of the number of grid levels. In the case of constant coe cients, the optimal convergence property of the W cycle algorithm is shown with any number of smoothing steps. Then we obtain suboptimal results for multilevel additive and multiplicative Schwarz methods and their related V -cycle multigrid algorithms; we show that these methods generate preconditioners with a condition number which can be bounded at least by the number of grid levels. Also, we consider the problem of switching the present discretizations to spectrally equivalent discretizations for which optimal preconditioners already exist. Finally, the numerical experiments carried out here complement these theories.

1. INTRODUCTION
In recent years there has been analyses and applications of the nonconforming rotated (NR) Q1 nite elements for the numerical solution of partial di erential problems. These nonconforming rectangular elements were rst proposed and analyzed in 23] for numerically solving the Stokes problem; they are the simplest divergence-free nonconforming elements on rectangles (respectively, rectangular parallelepipeds). Then they were used to simulate the deformation of martensitic crystals with microstructure 17] due to their simplicity. Conforming nite element methods can be used to approximate the microstructure with layers which are oriented with respect to meshes, while nonconforming nite element methods allow the microstructure to be approximated on meshes which are not aligned with the microstructure (see, e.g., 17] for the references).
1991 Mathematics Subject Classi cation. Primary 65N30, 65N22, 65F10. Key words and phrases. Finite elements, mixed methods, nonconforming methods, multigrid methods, multilevel preconditioners, di erential problems.
1
c 0000 American Mathematical Society 0000-0000/00 \$1.00 + \$.25 per page

2

ZHANGXIN CHEN AND PETER OSWALD

Independently, the NR Q1 elements have been derived within the framework of mixed nite element methods 11, 1]. It has been shown that the nonconforming method using these elements is equivalent to the mixed method exploiting the lowest-order Raviart-Thomas mixed elements on rectangles (respectively, rectangular parallelepipeds) 24]. Based on this equivalence theory, both the NR Q1 and the Raviart-Thomas mixed methods have been applied to model semiconductor devices 11]; they have been e ectively employed to compute the electric potential equation with a doping pro le which has a sharp junction. Error estimates of the NR Q1 elements can be derived by the classical nite element analysis 23, 16]. They can be also obtained from the known results on the mixed method based on the equivalence between these two methods 1]. It has been shown that the so-called \nonparametric" rotated Q1 elements produce optimal-order error estimates. As a special case of the nonparametric families, the optimal-order errors can be obtained for partitions into rectangles (respectively, rectangular parallelepipeds) oriented along the coordinate axes. Finally, in the case of cubic triangulations, superconvergence results can be obtained 1, 16]. Unlike the simplest triangular nonconforming elements, i.e., the nonconforming P1 elements, the NR Q1 elements do not have any reasonable conforming subspace. Consequently, there are di erences between these two types of nonconforming elements. The NR Q1 elements can be de ned on rectangles (respectively, rectangular parallelepipeds) with degrees of freedom given by the values at the midpoints of edges of the rectangles (respectively, the centers of faces of the rectangular parallelepipeds), or by the averages over the edges of the rectangles (respectively, the faces of the rectangular parallelepipeds). While these two versions lead to the same de nition for the nonconforming P1 elements, they can produce very di erent results in terms of implementation for the NR Q1 elements. With the second version of the NR Q1 elements, we are able to prove all the theoretical results for the multigrid algorithms and multilevel additive and multiplicative Schwarz methods considered in this paper. However, we are unable to obtain these results with their rst version. In particular, as numerical tests in 22] indicate, the energy norm of the iterates of the usual intergrid transfer operators, which enters both upper and lower bounds for the condition number of preconditioned systems, deteriorates with the number of grid levels for the rst version. But it is bounded independently of the number of grid levels for the second version, as shown here. The other major di erence between the nonconforming P1 and the NR Q1 elements is that the former contains the conforming P1 elements, while the latter does not contain any reasonable conforming subspace, as mentioned above. As a result of this, the convergence of the standard V -cycle algorithm for the nonconforming P1 elements can be shown when the coarse-grid correction steps of this algorithm are established on the conforming P1 spaces 18, 12]. But this is not the case for the NR Q1 elements. On the other hand, within the context of the nonconforming methods, i.e., when the coarse-grid correction steps are de ned on the nonconforming P1 spaces themselves, the convergence of the V -cycle algorithm has not been shown, and the W -cycle algorithm has been proven to converge only under the assumption that the number of smoothing steps is su ciently large 7, 8, 3, 4, 25, 1, 12, 14]. However, we are here able to show the convergence of the W -cycle algorithm with any number of smoothing steps for the Laplace equation using the NR Q1 elements. This optimal property cannot be proven for the nonconforming P1 elements using the present techniques.

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

3

The multigrid algorithms for the NR Q1 elements were rst developed and analyzed in 1], and further discussed in 12] and 9]. The second version of these elements was used in 1] and 12], while their rst version was exploited in 9]. Moreover, the analysis in 9] was given for elliptic boundary value problems which are not required to have full elliptic regularity. However, in all these three papers, only the W -cycle algorithm with a su ciently large number of smoothing steps was shown to converge using the standard proof of convergence of multigrid algorithms for conforming nite element methods 2]. We nally mention that the study of the NR Q1 elements in the context of domain decomposition methods has been given in 13]. In this paper we systematically study multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using the NR Q1 elements. We rst consider the convergence of the W -cycle and variable V -cycle algorithms for these nonconforming elements. We prove that the W -cycle algorithm with a su ciently large number of smoothing steps converges in the energy norm at a rate which is independent of grid number levels, and that the variable V -cycle algorithm provides a preconditioner with a condition number which is bounded independently of the number of grid levels. A main observation in this paper is that the optimal convergence property for the W -cycle algorithm holds with any number of smoothing steps, when the coe cient of the di erential problems is constant. Explicit bounds for the convergence rate and condition number are given. The NR Q1 elements has so far been the rst type of nonconforming elements which are shown to possess this feature for the W -cycle algorithm with any number of smoothing steps. We then study multilevel preconditioners of hierarchical basis and BPX type 5] for the NR Q1 elements. We develop a convergence theory for the multilevel additive and multiplicative Schwarz methods and their related V -cycle algorithms. We follow the general theory introduced in 22] where the analysis of the hierarchical basis and BPX type for nonconforming discretizations of partial di erential equations was carried out. A key ingredient in the analysis is to control the energy norm growth of the iterated coarse-to- ne grid operators, which enters both upper and lower bounds for the condition number of preconditioned systems as outlined above. So far, the energy norm of the iterated intergrid transfer operators has been shown to be bounded independently of grid levels solely for the nonconforming P1 elements 19]. In this paper we prove this property for the NR Q1 elements. Based on the present theory, we derive a suboptimal result for the multilevel preconditioners of hierarchical basis and BPX type for the NR Q1 elements. Finally, we study the problem of switching the NR Q1 discretization system to a spectrally equivalent discretization system for which optimal preconditioners are already available. This switching strategy has been used in the setting of the multilevel additive Schwarz method; see 21] for the references. After we nd a spectrally equivalent reference discretization for the NR Q1 system, we are able to obtain optimal preconditioner results for the NR Q1 elements. Thanks to the equivalence between the rotated Q1 nonconforming method and the lowest-order Raviart-Thomas mixed rectangular method, all the results derived here carry over directly to the latter method 1, 12]. For technical reasons, all the results in this paper are shown for partitions into uniform squares (respectively, cubes). They can be extended to triangulations in which the nest triangulation can be mapped to a square (respectively, cubic)

4

ZHANGXIN CHEN AND PETER OSWALD

triangulation in an a ne-invariant fashion. Also, the analysis is given for the twodimensional domain; an extension to three space dimensions is straightforward for most of the results below. The rest of the paper is organized as follows. In the next section we prove some preliminary results for the intergrid transfer operators. Then the multigrid algorithms and multilevel preconditioners are discussed in x3 and x4, respectively. The problem of switching to a spectrally equivalent discretization is considered in x5. Finally, the numerical results presented in x6 complement the present theories.

2. PRELIMINARY RESULTS
For expositional convenience, let = (0; 1)2 be the unit square, and let H s ( ) and L2 ( ) = H 0 ( ) be the usual Sobolev spaces with the norm

0Z 11=2 X jjvjjs = @ jD vj2 dxA ;
j j s

where s is a nonnegative integer. Also, let ( ; ) denote the L2 ( ) or (L2 ( ))2 inner product, as appropriate. The L2 ( ) norm is indicated by jj jj. Finally, 1 H0 ( ) = fv 2 H 1 ( ) : vj? = 0g; where ? = @ . Let h1 and Eh1 = E1 be given, where Eh1 is a partition of into uniform squares with length h0 and oriented along the coordinate axes. For each integer 2 k K , let hk = 21?k h1 and Ehk = Ek be constructed by connecting the midpoints of the edges of the squares in Ek?1 , and let Eh = EK be the nest grid. Also, let @ Ek be the set of all interior edges in Ek . In this and the following sections, we replace subscript hk simply by subscript k. For each k, we introduce the rotated Q1 nonconforming space

Vk = v 2 L2 ( ) : vjE = a1 + a2 x + a3 y + a4 (x2 ? y2 ); aiE 2 IR; 8E 2 Ek ; E E E E
if E1 and E2 share an edge e, then and @E\? j? ds = 0 :
1 Note that Vk 6 H0 ( ) and Vk?1 6 Vk , k 2. We introduce the space k X ^ Vk = Vl V k ; 1 ^ the discrete energy scalar product on Vk H0 ( ) by X 1 ^ (rv; rw)E ; v; w 2 Vk H0 ( ); (v; w)E ;k = 1 ^ and the discrete norm on Vk H0 ( ) by

Z

R

e

j@E1 ds =

Z

e

j@E2 ds;

l=1

E 2Ek

jjvjjE ;k = (v; v)E ;k ;

q

1 ^ v 2 Vk H0 ( ):

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

5

automatically preserves the zero average values on boundary edges. Also, it can be seen that (2:1) Pk?1 Ik v = v; v 2 Vk?1 ; k 1: That is, Pk?1 Ik is the identity operator Idk?1 on Vk?1 . This relation is not satis ed when the NR Q1 elements are de ned with degrees of freedom given by the values at the midpoints of edges of elements. We also de ne the iterates of Ik and Pk?1 by K Rk = IK Ik+1 : Vk ! VK ; QK = Pk PK ?1 : VK ! Vk : k Finally, we make the convention on the discrete energy scalar product on the space ^ VK : ^ (v; w)E = (v; w)E ;K ; v; w 2 VK : Obviously, we have the inverse inequality ^ (2:2) jjvjjE C 2k jjvjj; v 2 Vk ; 1 k K; (here and later, by C , c,... we denote generic positive constants which are independent of k). In this section we collect some basic properties of the intergrid transfer operaK tors Pk?1 (respectively, Ik ) and their iterates QK (respectively, Rk ). The crucial k p results are the boundedness of the operators Ik with constant 2 and the uniform K boundedness of the operators Rk with respect to the discrete energy norm jj jjE . Lemma 2.1. It holds that Pk?1 (2 k K ) is an orthogonal projection with respect to the energy scalar product; i.e., for any v 2 Vk , (v ? Pk?1 v; w)E = 0; 8w 2 Vk?1 ; (2:3) 2 = jjv ? Pk?1 v jj2 + jjPk?1 v jj2 : jjvjjE E E Moreover, there are constants C and c, independent of v, such that the di erence ^ v = v ? Pk?1 v 2 Vk satis es ^ (2:4) c2k jjv jj jjvjjE C 2k jjv jj: ^ ^ ^

1 1 1 jej e Pk?1 vds = 2 je1 j e1 vds + je2 j e2 vds ; where e1 and e2 in @ Ek form the edge e 2 @ Ek?1 . Note that the de nition of Pk?1

We introduce two sets of intergrid transfer operators Ik : Vk?1 ! Vk and Pk?1 : Vk ! Vk?1 as follows. Following 1, 12], if v 2 Vk?1 and e is an edge of a square in Ek , then Ik v 2 Vk is de ned by 80 if e @ ; > Z > 1 Z < 1 vds if e 6 @E for any E 2 Ek?1 ; e jej e Ik vds = > je1j Z > : 2jej (vjE1 + vjE2 )ds if e @E1 \ @E2 for some E1 ; E2 2 Ek?1: e If v 2 Vk and e is an edge of an element in @ Ek?1 , then Pk?1 v 2 Vk?1 is given by 1

Z

Z

Z

6

ZHANGXIN CHEN AND PETER OSWALD

j where ej i are the four edges of Ei with the outer unit normals Ei , i = 1; : : : ; 4. E Note that in (2.5) the line integrals over edges interior to E 2 Ek?1 cancel by j continuity of Pk?1 v in the interior of E . Also, if ej i and e^ ^ form an edge of E , it Ei E follows by the de nition of Pk?1 that

Proof. For any E 2 Ek?1 with the four subsquares Ei 2 Ek (i = 1; : : : ; 4, see Figure 1), an application of Green's formula implies that P (r v ? Pk?1 v]; rw)E = 4=1 (r v ? Pk?1 v]; rw)Ei Pi4 P4 @w j R j (v ? P v)j ds; (2:5) = i=1 j=1 @ j eE eE k?1 Ei

Ei

i

i

Z

and that

ej i E

(v ? Pk?1 v)jEi ds +

Z

j e^ ^ Ei

(v ? Pk?1 v)jE^ ds = 0; i

is constant. Then, by (2.5), we see that (r v ? Pk?1 v]; rw)E = 0: Now, sum on all E 2 Ek?1 to derive the orthogonality relations in (2.3). The upper estimate in (2.4) directly follows from (2.2). The lower bound can be easily obtained from a direct calculation of the energy norms of v ? PK ?1 on all E 2 Ek?1 . This completes the proof. #

@w @w j j = ^ ^ j @ Ei eEi @ E^ ejE^ i i

e3 E E2 e2 E E1 e1 E
Figure 1.

E3 e4 E E4

Edges and subsquares of E 2 Ek?1 .

Before we start with the investigation of the prolongations Ik , it will be useful to collect some formulas. For E 2 Ek?1 and any v 2 Vk?1 , de ne 1 Z v d s = bi ; (see Figure 1 for the notation), and set sE = b 1 + b 2 + b 3 + b 4 ; E E E E 0 = b 1 + b 3 ? b2 ? b 4 ; E E E E E

jeiE j

ei E

E

41 = b3 ? b1 ; E E E 42 = b4 ? b2 : E E E

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

7

Then, with the subscript E omitted, we have the next lemma. Lemma 2.2. It holds that ? 1 1 1 jjvjj2 2 (E) = h2?1 16 s2 + 12 f(41)2 + (42)2 g + 40 ( 0 )2 ; k L (2:6) 3 jjrvjj2 2 (E) = (41 )2 + (42)2 + 2 ( 0 )2 ; L and h2 ?1 1 2 k 22 32 4 2 jjvjj2 2 (E) L 10 (b ) + (b ) + (b ) + (b ) (2:7) h2 ?1 (b1 )2 + (b2 )2 + (b3 )2 + (b4 )2 : k 4 Proof. Using the a ne invariance of the local interpolation problem connecting v with its edge averages bi , it su ces to prove (2.6) and (2.7) for the master square E = (?1; 1)2 . A straightforward calculation gives 2 1 3 (2:8) v = v(x; y) = 1 s + 4 x + 4 y ? 8 0 (x2 ? y2 ): 4 2 2 Now direct integration yields the desired results in (2.6). Also, (2.7) follows from the rst equation of (2.6) by computing the eigenvalues of the symmetric 4 4 matrix T t DT , where D =diag(1=16; 1=12; 1=12; 1=40), T stands for the transformation matrix from the vector (b1 ; b3 ; b2 ; b4 ) to (s; 41; 42; 0 ), and T t is the transpose of T . These eigenvalues are 1=10, 1=6, 1=6, and 1=4, which implies (2.7). # Lemma 2.2 is the basis for computing all the discrete energy and L2 norms needed in the sequel. The formula (2.8) valid for the master square can be used to derive explicit expressions for the edge averages of Ik v and Ik v ? v. Toward this end, we rst compute the corresponding values for the master square, and then use the invariance of the local interpolation problem for v under a ne transformations (for the square triangulations under consideration, these transformations are just dilation and translation) to return to the notation on each E 2 Ek?1 .

e1 ?e1 +e2 e2 ?e1

e1 +e2 e2 e1 e2 +e1 e2 2 e1 +e2 2
2

? e1

e1 ?e1

e1 2
An illustration for Lemma 2.3.

e2 +e1 2

Figure 2.

Note that, by the de nition of the triangulation Ek?1 , to each E 2 Ek?1 is uniquely assigned a = ( 1 ; 2 ) such that 0 2k?1 . For notational 1, 2 1 and b2 denote the averages of v 2 Vk?1 over the horizontal and convenience, let b vertical edges e1 and e2 , respectively, in @ Ek?1 (see Figure 2, where e2 , e2 +e2 , 2 2 e1 +e2 , e1 +e2 ?e1 2 @ Ek , e1 = (1; 0), and e2 = (0; 1)). The corresponding quantities 2 2 for Ik v 2 Vk are indicated by aj , j = 1, 2. Now, introduce the notation ^1 = b1 + b1 ?e1 ? b1 +e2 ? b1 +e2 ?e1 ; ^2 = b2 + b2 ?e2 ? b2 +e1 ? b2 +e1 ?e2 :

8

ZHANGXIN CHEN AND PETER OSWALD

With these notation, it follows from the de nition of Ik that the edge averages of Ik v can be written as follows: 1 a1 = b1 + 8 ^2 ; 2 1 a1 +e1 = b1 ? 8 ^2 ; 2 (2:9) 5 1 1 1 a1 +e2 = 8 b2 + 8 b2 +e1 + 8 b1 + 8 b1 +e2 ; 2 1 1 1 a1 +e2 +e1 = 5 b2 +e1 + 8 b2 + 8 b1 + 8 b1 +e2 ; 2 8 and a2 = b2 + 1 ^1 ; 2 8 2 2 = b2 ? 1 ^1 ; a2 +e 8 (2:10) 5 1 1 1 a2 +e1 = 8 b1 + 8 b1 +e2 + 8 b2 + 8 b2 +e1 ; 2 1 1 1 a2 +e2 +e1 = 5 b1 +e2 + 8 b1 + 8 b2 + 8 b2 +e1 ; 2 8 when the edge average aj is associated with an interior edge in @ Ek ; for boundary edges, this value is set to be zero. ^ Note that Ik (as well as Pk?1 ) can be extended to the larger spaces Vk in a ^j : Vk ! Vk , observe that any v 2 Vk ^ ^ natural way. In order to de ne the extension I coincides on each E 2 Ek with a polynomial from Vk jE , so the form of the previous ^ ^ ^ de nition for Ik remains the same for Ij . Clearly, Ik jVk?1 = Ik and Ik jVk = Idk . To express the edge averages of Ik v ? v, set 1 = b1 2 ? b 1 + b 1 1 ? b 1 2 1 ; +e ?e +e ?e 2 = b2 1 ? b 2 + b 2 2 ? b 2 1 2 ; +e ?e +e ?e 1 and e2 are interior edges in @ Ek?1 . For boundary edges, they need to be if e modi ed to give the correct expressions for Ik v ? v. If e1 is a boundary edge, for example, we de ne 2 = 2(b2 1 ? b2 ): +e With these, we see that R R e1 +e2 ?e1 (Ik v ? v )j ?e1 ds = e1 +e2 (Ik v ? v )j ds = 0; 2 2 1 R 1 1 R 2 j e2 (Ik v ? v )j ?e1 ds = je2 2 j e2 2 (Ik v ? v )j ds = ? 8 1 ; (2:11) je2 2 2 +e 2 +R e 1 R 1 1 1 je2 j e2 (Ik v ? v)j ds = je2 2 j e2 2 (Ik v ? v)j ?e1 ds = 8 ; 2 2 where (Ik v ? v)j denotes the restriction of Ik v ? v to the element associated with . The averages of Ik v ? v on other edges are given similarly. Then, by Green's formula and (2.11), we see that (2:12) jjIk vjj2 ? jjvjj2 = jjIk v ? vjj2 ; v 2 Vk?1 : E E E From (2.9){(2.12) and Lemma 2.2, we immediately have the next lemma. Below the notation stands for two-sided inequalities with constants independent of k. Lemma 2.3. It holds that q5 ^ jjvjj; 8v 2 Vk ; jjI^k vjj (2:13) p2 jjIk vjjE 2jjvjjE ; 8v 2 Vk?1 ;
2 +e 2 +e

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

9

and

(2:14)

2k jjIk v ? vjj jjIk v ? vjjE

sX

f( 1 )2 + ( 2 )2 g; 8v 2 Vk?1 :

We now prove the following property of the iterated coarse- ne intergrid transK fer operators Rk .

Lemma 2.4. It holds that K (2:15) jjRk vjjE C jjvjjE ;

8v 2 Vk ; 1 k K:

Proof.

The proof is technical; it follows the idea of the proof of an analogous statement for the P1 nonconforming elements 19]. First, we consider the case of = IR2 . That is, we assume that all our de nitions are extended to in nite square partitions of IR2 ; due to the local character of all constructions, this is easy to do. We keep the same notation for the extended partitions Ek , edges ej 2 @ Ek , squares E 2 Ek , etc. In order to guarantee the niteness of all norm expressions, we restrict our attention to functions v 2 Vk with nite support. By the construction of Ik , K this property is preserved when applying the operators Ik and Rk . 2 , it is clear that it su ces After the extension to the shift-invariant setting of IR k ~ to consider the case of k = 1. Set, for simplicity, Rk = R1 , k = 1; : : : ; K . Our main observation from numerical experiments 21] was that the sequence ~ ~ fjjRk v ? Rk?1 vjj2 ; k = 2; : : : ; K g E decays geometrically. What we want to prove next is the mathematical counterpart to this observation. To formulate the technical result, introduce
j=

X

2Z2

( j )2 ;

j = 0; 1; 2;

where the quantities j are determined from the edge averages of v 2 V1 by the same formulas as above. The corresponding quantities computed for v = I2 v 2 V2 ~ are denoted by ~j and ~j , j = 0; 1; 2. From (2.14) in Lemma 2.3, we see that 2 ~2 ~3 ~2 2 1 + 2 jjR v ? v kE and ~1 + ~2 jjR v ? R v jjE ; moreover, we can iterate this construction. Thus, if we can prove that (2:16) where 0 < and 2.3, (2:17) ~ c ~0 + ~1 + ~2
K jjR1 vjjE

(c

0 + 1 + 2 );

< 1 and c > 0 are constants independent of v, then, by Lemmas 2.2
~ ~ jjvjjE + PK=2 jjRk v ? Rk?1 vkE k PK?1 p( )k p jjvjjE + C k=1 C jjvjjE :

K Since this gives the desired boundedness of Rk (for IR2 ) via dilation, we concentrate on (2.16).

10

ZHANGXIN CHEN AND PETER OSWALD

From (2.9) and (2.10) we nd the following formulas for ~j : 1 0 ~2 +e1 = 1 1 +e1 ? 8 2 + 1 0 ; 8 4 1 0 ~2 = ? 1 1 + 8 2 + 1 0 ; 8 4 1 1 0 ~2 +e2 = 8 1 ? 8 2 +e2 + 1 0 ; 4 1 1 0 ~2 +e1 +e2 = ? 8 1 +e1 + 8 2 +e2 + 1 0 ; 4 1 1 3 1 ~2 = 2 1 ? 8 ( 2 + 2 ?e1 ) ? 8 ( 0 ? 0 ?e1 ); 1 ~2 +e1 = 1 2 ; 4 1 1 ~2 +e2 = 1 1 ? 8 ( 2 +e2 + 2 ?e1 +e2 ) + 3 ( 0 ? 0 ?e1 ); 2 8 1 1 ~2 +e1 +e2 = ? 4 2 +e2 ; 1 3 2 ~2 = 1 2 ? 8 ( 1 + 1 ?e2 ) + 8 ( 0 ? 0 ?e2 ); 2 2 ~2 +e2 = 1 1 ; 4 1 2 ~2 +e1 = 1 2 ? 8 ( 1 +e1 + 1 ?e2 +e1 ) ? 3 ( 0 ? 0 ?e2 ); 2 8 1 2 ~2 +e1 +e2 = ? 4 1 +e1 : These formulas are used to compute the quantities ~j . In order to write them in reasonably short form, we introduce the notation
j =

X

j j

2Z2

+

;

jl =

X

j l

2Z2

+

; k; l = 0; 1; 2 (j 6= l);

if 2 Z2 is the null vector, it is omitted in this notation. With them, we see, by carefully evaluating all squares, that ~0 ~1 = ~2 = =

P

=1 4

1 3 9 e1 1 e1 9 16 0 + 2 1 + 16 2 ? 16 0 + 16 2 ? e2 ) 3 e1 ? ? e2 1( ? 8 | 12 + 12 + {z12e1 + 12?e1 } ? 32 ( 02 + 02e1 +e2 ? 02e1 9 3 1 9 e2 1 e2 16 0 + 16 1 + 2 2 ? 16 0 + 16 1 ? e2 ) 3 ? e2 1( ? 8 | 12 + 12 + {z12e1 + 12?e1 } ? 32 ( 01e2

0 0 0 0 ( ~2 )2 + ( ~2 +e1 )2 + ( ~2 +e2 )2 + ( ~2 +e1 +e2 )2 ?e1 e2 ?e1 ) e2 1 1 ( 0 + 16 ( 1 + 2 ) ? 32 | 12 + 12 + {z + 12 }; 12

( ~0 )2 =

P

?

02

e1 +e2 );

e1 2 e1 2 e2 + 01+e ? 01 ? 01?e ):

~ Thus, introducing A = 1 + 2 and A = ~1 + ~2 , we have 1 1 ~0 = 1 0 + 16 A ? 32 ; 4 (2:18) 11 9 e 1 e e e ~ A = 9 0 + 16 A ? 16 ( 01 + 02 ) + 16 ( 12 + 21 ) ? 1 8 4 where

3 1 ? 32

;

?2 e1 2 ?1 2 e1 2 ?1 e1 2 e1 e2 = 01e + 01+e + 02 + 02e +e ? 01 ? 01?e ? 02e ? 02+e :

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

11

e e e e = 2( 0 +e + 0 ?e ) ? 4( 01 + 02 ) + 4 0 : Substitution of and into (2.18) leads to 1 1 e 1 e ~0 = 1 0 + 32 A ? 32 ( 12 + 22 ) + 64 4 e1 2 e1 2 1 1 5 e e = 16 0 + 32 A + 32 0 ?e + 0 +e ? 2 01 ? 2 02 (2:19) 1 e e ? 32 12 + 21 1 0 + 1 A; 2 16

Next, we simplify and . Note that e ? 2 12 = P 1 ( 2 + 2 +e2 + 2 ?e1 +e2 + 2 ?e1 ? 1 +e2 ? 1 ?e2 ) P 1 ( 0 2 1 + 0 2 ? 0 1 2 ? 0 2 + 2 1 ); = +e ?e ?e ?e ?e +e e1 = P 2 ( 1 + 1 2 + 1 1 2 + 1 1 ? 2 1 ? 2 1 ) ?2 2 P 2 ( 0 2 ?e+ 0 +e??e0 1 +e? 0 +e+ 2 2 )?e ; = ?e ?e1 +e1 +e ?e2 ?e1 so that e2 e1 = 1 + 2 + 2A ? 1 : 2 Analogously, we can simplify as follows: P 0 ?( 1 1 2 + 1 2 + 2 1 + 2 1 2 ) = +e +e ?e +e ?e +e 1 2 + 1 1 2 + 2 1 + 2 1 2) ?( + ? + P 0 ?( +e 1 2 +e ?e 1 2 +e 0 1 +e2 +e 0 1 2 ) 0 0 = +e +e +e ?e ?e ?e ?e +e ?2( 0 +e1 + 0 +e2 + 0 ?e1 + 0 ?e2 ) + 4 0 )
1 2 1 2

where we have used the fact that j j j j ; j = 0; 1; 2, which is valid for arbitrary . With the same argument, we see that 3 1 7 9 9 e e e e ~ A = 8 0 + 16 A ? 16 01 + 02 ? 16 12 + 22 + 32 e1 2 e1 2 7 1 = 5 0 + 16 A + 16 0 ?e + 0 +e 4 (2:20) 3 11 e e e e ? 16 01 + 02 ? 16 12 + 21 11 0 + 5 A: 4 8 ~ = c ~0 . Then it follows from (2.18) and (2.19) that Now, set B = c 0 and B ~ ~ c A 5 + 11 B; B 16 A + 1 B; 8 4c 2 and 5 c 1 ~ ~ (A + B) max 8 + 16 ; 11 + 2 (A + B): 4c Let c = c 3 5 ? 1, so we see that (2.16) holds with p c 11 5 = 5 + 16 = 4c + 1 = 3 16+ 9 < 1: 8 2

p

12

ZHANGXIN CHEN AND PETER OSWALD

It remains to reduce the assertion of Lemma 2.4 to the shift-invariant situation just considered. To this end, starting with any v 2 Vk on the unit square, we repeatedly use an odd extension. Namely, set v = v on 0; 1]2 and ^ v(x; y) = ?v(?x; y); (x; y) 2 ?1; 0) 0; 1]; ^ ^ after this, de ne v(x; y) = ?v(x; ?y); (x; y) 2 ?1; 1] ?1; 0); ^ ^ and continue this extension process with the unit square replaced by ?1; 1]2 such that after the next two steps v is de ned on ?1; 3]2. Outside this larger square we ^ continue by zero. Clearly, jjv jj2 = 16jjvjj2 , where the norms for v and v are taken ^E ^ E with respect to IR2 and the unit square, respectively. K^ It is not di cult to check by induction that on 0; 1]2 the functions Rk v (ob2 ) and RK v tained by the repeated application of the prolongations de ned on IR k (as de ned above with respect to 0; 1]2) coincide. Also, the values of Ik+1 v on ^ ?2?(k+1); 1 + 2?(k+1) ]2 depend solely on the values of v on the square ?2?k ; 1 + ^ 2?k ]2 , and on this enlarged square Ik+1 v coincides with its odd extension from ^ 0; 1]2. Finally, the zero edge averages are automatically reproduced along the boundary of 0; 1]2 from the above extension procedure. Therefore, by (2.17) and the dilation argument, we obtain K K^ jjRk vjj2 jjRk vjj2 C jjvjj2 = 16C jjvjj2 ; ^E E E E which nishes the proof of Lemma 2.4. # The second inequality in (2.13) is critical for the convergence results of multigrid algorithms developed in the next section, while (2.15) is crucial for the multilevel preconditioner results in x4.

3. MULTIGRID ALGORITHMS
In this section and the next section we consider multigrid algorithms and multilevel preconditioners for the numerical solution of the second-order elliptic problem ?r (Aru) = f in ; (3:1) u = 0 on ?; where IR2 is a simply connected bounded polygonal domain with the boundary 2 ( ), and the coe cient A 2 (L1 ( ))2 2 satis es ?, f 2 L t t A(x; y ) t (3:2) (x; y) 2 ; 2 IR2 ; 1 0 ; with xed constants 1 , 0 > 0. The condition number of preconditioned linear systems to be analyzed later depends on the ratio 1 = 0 . Problem (3.1) is recast in weak form as follows. The bilinear form a( ; ) is de ned as follows: a(v; w) = (Arv; rw); v; w 2 H 1 ( ): 1 Then the weak form of (3.1) for the solution u 2 H0 ( ) is 1 (3:3) a(u; v) = (f; v); 8 v 2 H0 ( ): 1 Associated with each Vk , we introduce a bilinear form on Vk H0 ( ) by X 1 ak (v; w) = (Arv; rw)E ; v; w 2 Vk H0 ( ):
E 2Ek

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

13

The NR Q1 nite element discretization of (3.1) is to nd uK 2 VK such that (3:4) aK (uK ; v) = (f; v); 8 v 2 VK : Let Ak : Vk ! Vk be the discretization operator on level k given by (3:5) (Ak v; w) = ak (v; w); 8 w 2 Vk : The operator Ak is clearly symmetric (in both the ak ( ; ) and ( ; ) inner products) 0 and positive de nite. Also, we de ne the operators Rk?1 : Vk ! Vk?1 and Rk?1 : Vk ! Vk?1 by ak?1 (Rk?1 v; w) = ak (v; Ik w); 8 w 2 Vk?1 ; and ?R0 v; w = (v; I w); 8 w 2 V : k k?1 k?1 It is easy to see that Ik Rk?1 is a symmetric operator wtih respect to the ak form. 0 Note that neither Rk nor Rk is a projection in the nonconforming case. Finally, let k dominate the spectral radius of Ak . The multigrid processes below result in a linear iterative scheme with a reduction operator equal to I ? BK AK , where BK : VK ! VK is the multigrid operator to be de ned below. Multigrid Algorithm 3.1. Let 2 k K and p be a positive integer. Set B1 = A?1 . Assume that Bk?1 has been de ned and de ne Bk g for g 2 Vk as 1 follows: 1. Set x0 = 0 and q0 = 0. 2. De ne xl for l = 1; : : : ; m(k) by xl = xl?1 + Sk (g ? Ak xl?1 ): 3. De ne ym(k) = xm(k) + Ik qp , where qi for i = 1; : : : ; p is de ned by i h 0 qi = qi?1 + Bk?1 Rk?1 g ? Ak xm(k) ? Ak?1 qi?1 : 4. De ne yl for l = m(k) + 1; : : : ; 2m(k) by ? yl = yl?1 + Sk g ? Ak yl?1 : 5. Set Bk g = y2m(k) . In Algorithm 3.1, m(k) gives the number of pre- and post-smoothing iterations and can vary as a function of k. In this section, we set Sk = ( k )?1 Idk in the pre- and post-smoothing steps. If p = 1, we have a V -cycle multigrid algorithm. If p = 2, we have a W -cycle algorithm. A variable V -cycle algorithm is one in which the number of smoothings m(k) increase exponentially as k decreases (i.e., p = 1 and m(k) = 2K ?k ). We now follow the methodology developed in 6] to state convergence results for Algorithm 3.1. The two ingredients in their analysis are the regularity and approximation property and the boundedness of the intergrid transfer operator: (3:6) and (3:7)

A jak (v ? Ik Rk?1 v; v)j C jjpk vjj ak (v; v);
k

p

8 v 2 Vk ;

ak (Ik v; Ik v) Cak?1 (v; v);

8 v 2 Vk?1 ;

14

ZHANGXIN CHEN AND PETER OSWALD

for k = 2; : : : ; K , where k is the largest eigenvalue of Ak . The proof of (3.6) is standard; see the proof of a similar result for the P1 nonconforming elements in 14]. Inequality (3.7) has been shown in 1] using the approximation property of the operator Ik . However, here we see that if A = 0 I is a scalar multiple of the two-by-two identity matrix I, by the second inequality in (2.13) in Lemma 2.3, we actually have (3:8) ak (Ik v; Ik v) 2ak?1 (v; v); 8 v 2 Vk?1 : This leads to the following main result of this section. Let the convergence rate for Algorithm 3.1 on the kth level be measured by the convergence factor k satisfying jak (v ? Bk Ak v; v)j k ak (v; v); 8 v 2 Vk :
Algorithm 3.1. Then there are 0 , 1 > 0, independent of k, such that 8v 2 Vk ; 0 ak (v; v ) ak (Bk Ak v; v ) 1 ak (v; v ); with p p p p m(k)=(C + m(k)) and 1 (C + m(k))= m(k): 0 (ii) De ne Bk by p = 2 and m(k) = m for all k in Algorithm 3.1. Then if A = 0 I is constant, there exists C > 0, independent of k, such that
k

Theorem 3.1. (i) De ne Bk by p = 1 and m(k) = 2K?k for k = 2; : : : ; K in

The same conclusion holds if the assumption that A = 0 I is replaced by requiring that m m0 , where m0 is su ciently large, but independent of k. The proof of this theorem follows from (3.6){(3.8) and Theorems 6 and 7 in 6]. From Theorem 3.1, we have an optimal convergence property of the W -cycle and a uniform condition number estimate for the variable V -cycle preconditioner.

C C + pm :

4. MULTILEVEL PRECONDITIONERS
In this section we discuss multilevel preconditioners of hierarchical basis and BPX 5] type for (3.4). More precisely, we derive the condition numbers of the additive subspace splittings (4:1) and (4:2) (4:3) where
K fVK ; ( ; )E g = R1 fV1 ; ( ; )E g + K fVK ; ( ; )E g = R1 fV1 ; ( ; )E g + K X k=2 K X k=2 K Rk fVk ; 22k ( ; )g;

K Rk f(Idk ? Ik Pk?1 )Vk ; 22k ( ; )g:

The condition number of (4.1) is given by 20] =
max ; min max =

jj 2 sup jjjvjjE2 ; v2VK v jjj

jjjvjjj2

=

A similar de nition can be given for (4.2).

vk 2Vk : v=Pk RK vk k

inf

(

inf min = v2V

jjvjj2 ; E K jjjv jjj2

jjv1 E +

jj2

K X k=2

22k jjv jj2
k

)

:

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

15

Theorem 4.1. There are positive constants c and C , independent of K , such that jj 2 (4:4) c jjjvjjE2 CK; 8v 2 VK ; vjjj
and (4:5) where

jj 2 c kkvjjE 2 vkk kkvkk2 = jjQK vjj2 + 1 E

CK;
K X k=2

8v 2 VK ;

22k jj(Idk ? Ik Pk?1 )QK vjj2 : k

That is, the condition numbers of the additive subspace splittings (4.1) and (4.2) are bounded by O(K ) as K ! 1. K ^ Proof. For k = 2; : : : ; K , it follows from the de nitions of Ik , Ik , and Qk , (2.4), and the rst inequality of (2.13) that ^ 22k jj(Idk ? Ik Pk?1 )QK vjj2 = 22k jjIk (Idk ? Pk?1 )QK vjj2 k k 5 22k jj(Idk ? Pk?1 )QK v jj2 k 2 K v jj2 C jj(Idk ? Ik Pk?1 )Qk E = C jjQK v ? QK?1 vjj2 : k k Summing on j and using the orthogonality relations in (2.3), we see that n o P inf vk 2Vk : v=Pk RK vk jjv1 jj2 + K=2 22k jjvk jj2 E k k K v k2 + PK 22k jj(Idk ? Ik Pk?1 )QK v jj2 jjQ1 E k k=2

which implies the lower bounds in (4.4) and (4.5). P K For the upper bounds, we consider an arbitrary decomposition v = K=1 Rk vk k with vk 2 Vk . Then we see, by Lemma 2.4, that

C jjvjj2 ; E

jjvjj2

E

K X k=1

K jjRk vk jjE

!2

K

K X

Consequently, by (2.2), we have

k=1

K jjRk vk jj2 CK E K X k=2

K X k=1

jjvk jj2 : E

jjvjj2

E

CK jjv1 E +

jj2

22k jjv jj2
k

!

:

Now, taking the in mum with respect to all decompositions, we obtain o n jjvjj2 CK inf vk 2Vk : v=Pk RK vk jjv1 jj2 + PK=2 22k jjvk jj2 E E k k P CK jjQK vjj2 + K=2 22k jj(Idk ? Ik Pk?1 )QK vjj2 ; 1 E k k which nishes the proof of the theorem. # We now discuss the algorithmical consequences for the splittings (4.1) and (4.2). Theoretically, Theorem 4.1 already produces suitable preconditioners for the matrix AK using (4.1) and (4.2). However, they are still complicated since they involve L2-projections onto Vk , 1 < k < K , which means to solve large linear systems within each preconditioning step. To get more practicable algorithms, we replace

16

ZHANGXIN CHEN AND PETER OSWALD

the L2 norms in Vk and Wk = (Idk ? Ik Pk?1 )Vk Vk , k = 2; : : : ; K , by their suitable discrete counterparts. We rst consider the splitting (4.1); (4.2) will be discussed later. Let f j ;k g be the basis functions of Vk such that the edge average of j ;k equals one at ej ;k and zero at all other edges. Then each v 2 Vk has the representation

v=

2 XX

Thus, by the uniform L2-stability of the bases, which follows from (2.7) in Lemma 2.2, we see that 2 2 1 2?2k X X(aj )2 jjvjj2 1 2?2k X X(aj )2 : (4:6) 5 2 j =1 j =1 Note that (with the same argument as in Lemma 2.2) 41 (4:7) 22k jj j ;k jj2 = 120 ; ak ( j ;k ; j ;k ) jj j ;k jj2 = 5; E so (4.6) can be interpreted as the two-sided inequality associated with the stability of any of the splittings (4:8) (4:9) and (4:10)

j =1

aj j ;k :

fVk ; 22k ( ; )g =

2 XX

j =1

fV j;k ; 22k ( ; )g; fV j;k ; ( ; )E g;

fVk ; 22k ( ; )g = fVk ; 22k ( ; )g =

2 XX

j =1
2 XX

into the direct sum of one-dimensional subspaces V j;k spanned by the basis functions j ;k . Any of the splittings (4.8){(4.10) can be used to re ne (4.1). As we will see below, the di erence is just in a diagonal scaling (i.e., a multiplication by a diagonal matrix) in the nal algorithms. As example, we consider the splitting (4.10) in detail; the other two cases can be analyzed in the same fashion. With (4.1) and (4.10), we have the splitting (4:11)
K fVK ; aK ( ; )g = R1 fV1 ; a1 ( ; )g + K 2 XXX k=2 j =1 K Rk fV j;k ; ak ( ; )g:

j =1

fV j;k ; ak ( ; )g;

It follows from (4.4), (4.6), and (4.7) that the condition number for (4.11) still behaves like O(K ). Now, associated with this splitting we can explicitly state the additive Schwarz operator (4:12)
K P K = R 1 T1 + K 2 XXX k=2 j =1 K Rk T j ;k ;

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

17

where

and T1 v 2 V1 solves the elliptic problem K a1 (T1 v; w) = aK (v; R1 w); 8 w 2 V1 : Thus the matrix representations of all operators with respect to the bases of the respective Vk are

a (v; RK j ) T j ;k v = K j k j ;k j ;k ; ak ( ;k ; ;k )

Tk =

2 XX

for 2 k K , and

j =1

K T j ;k = Sk (Rk )t AK ;

Sk = diag(aj ( j ;k ; j ;k )?1 );

where for convenience the same notation is used for operators and matrices. Hence it follows from (4.12) that

K T1 = A?1 (R1 )t AK ; 1

a special case of Algorithm 3.1 if one sets m(k) = 1, p = 1, removes the postsmoothing step, and replaces Ak by a zero matrix for all k 2. From (4.13) and the de nitions of Ik and Sk , we see that a multiplication by CK only involves O(nK +: : :+n2 +n3 ) = O(nK ) arithmetical operations, where nk 22k 1 is the dimension of Vk . This, together with (4.4), yields suboptimal work estimates for a preconditioned conjugate gradient method for (3.4) with the preconditioner CK . That is, an error reduction by a factor in the preconditioned conjugate p gradient algorithm can be achieved by O(nK log nK log( ?1 )) operations. We now turn to the discussion of the algorithmical consequences for the splitting (4.2). To do this, we need to construct basis functions in Wk , k = 2; : : : ; K . Starting with the bases f j ;k g in Vk , to each interior edge ej ;k?1 2 @ Ek?1 , we replace the two associated basis functions j ;k ; j +ej ;k with their linear combinations 2 2 j = j + j j j j 2 ;k 2 ;k 2 +ej ;k ; 2 +ej ;k = 2 ;k ? 2 +ej ;k ; j = 1; 2; where ej ;k and ej +ej ;k 2 @ Ek form the edge ej ;k?1 . For all other interior edges 2 2 j , which do not belong to any edge in @ E , we set e ;k k?1 j = j : ;k ;k j g in V is still L2 -stable; i.e., they satisfy an analogous inequalThe new bases f ;k k ity to (4.6). Moreover, if

! K K A?1 (RK )t + X RK Sk (RK )t AK CK AK ; PK = R1 1 1 k k k=2 K which, together with the de nition of Rk = IK Ik+1 , leads to the typical recursive structure for the preconditioner CK t (4:13) Ck = Ik Ck?1 Ik + Sk ; k = K; : : : ; 2; S1 = C1 A?1 : 1 Note that with these choices for Sk , the multiplication of a vector by CK is formally

v=

2 XX

j =1

bj j ;k ;

18

ZHANGXIN CHEN AND PETER OSWALD 2 XX

we have

Pk?1 v =
and
j since 2 ;k j

j =1

bj j ;k?1 ; 2 cj j ;k ;

(Idk ? Ik Pk?1 )v =

2 XX

and similar relations hold for j = 2. Hence any function from Wk has a unique representation by linear combinations of f j ;k : 6= 2 g, and this basis system is L2-stable. With this basis system, as in (4.11), we have the corresponding splitting (4:14)
K fVK ; aK ( ; )g = R1 fV1 ; a1 ( ; )g + K 2 XX X k=2 j =1 6=2 K Rk fW j ;k ; ak ( ; )g

? Ik ;k?1 can be completely expressed by the functions l ;k with 6= 2 only. More precisely, we have 1 c1 +e1 = b1 +e1 ? 8 (b2 + b2 ?e2 ) ? b2 +e1 ) ? b2 +e1 ?e2 ) ); 2 2 2 2( 2( 2( 1 1 2 = b1 2 ? 1 (5b2 + b1 + b2 c2 +e 2 2( +e1 ) + b2( +e2 ) ); 2 +e 8 2 1 1 2 = b1 2 ? 1 (5b2 1 2 1 c2 +e +e 2 +e 8 2( +e1 ) + b2 + b2 + b2( +e2 ) );

j =1 6=2

K K into a direct sum of R1 V1 and one-dimensional spaces Rk W j ;k spanned by the basis j ;k . Then, with the same argument as for (4.13), we derive an additive ^ preconditioner CK for AK recursively de ned by ^ ^ ^ t ^ ^ ^t ^ (4:15) Ck = Ik Ck?1 Ik + Ik Sk Ik ; k = K; : : : ; 2; C1 = S1 A?1 ; 1 where ^ Sk = diag ak ( j ;k ; j ;k )?1 ; 6= 2 ; j = 1; 2 ^ are diagonal matrices and Ik is the rectangular matrix corresponding to the natural embedding Wk Vk with respect to the bases f j ;k g in Wk and f j ;k g in Vk (one may use the bases f j ;k g for all Vk , which would change the Ik representations, but ^ keep Ik maximally simple). (4.15) has the same arithmetical complexity as before. We now summarize the results in Theorem 4.1 and the above discussion in the next theorem. ^ Theorem 4.2. The symmetric preconditioners CK and CK de ned in (4.13) and (4.15) and associated with the multilevel splittings (4.11) and (4.14), respectively, have an O(nK ) operation count per matrix-vector multiplication and produce the following the condition numbers: ^ (4:16) (CK AK ) CK; (CK AK ) CK; K 1: The splitting (4.11) can be viewed as the nodal basis preconditioner of BPX type 5], while the splitting (4.14) is analogous to the hierarchical basis preconditioner.

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

19

We now consider multiplicative algorithms for (3.4). One iteration step of a multiplicative algorithm corresponding to the splitting (4.11) takes the form y 0 = xj ; K K K (4:17) yl+1 = yl ? !RK ?lSK ?l (RK ?l )t (AK yl ? fK ); l = 0; : : : ; K ? 1; xj+1 = yK ; K where ! is a suitable relaxation parameter (the range of relaxation parameters for which the algorithm in (4.17) converges is determined mainly by the constant in the inverse inequality (2.2) 27, 26, 15]. The method (4.17) corresponds to a K K ~ V -cycle algorithm in Algorithm 3.1 with Ak replaced by Ak = (Rk )t AK Rk , one pre-smoothing and no post-smoothing steps. The iteration matrix MK;! in (4.17) is given by K K MK;! = (IdK ? !E1 ) (IdK ? !EK ?1 )(IdK ? !EK ) ; Ek Rk Sk (Rk )t AK : An analogous multiplicative algorithm for (3.4) corresponding to the splitting (4.14) can be de ned. From the general theory on multiplicative algorithms 27] and by the same argument as for Theorem 4.2, we can show the following result. Theorem 4.3. For properly chosen relaxation parameter ! the multiplicative schemes corresponding to the splittings (4.11) and (4.14) possess the following upper bounds for the convergence rate: ^ (4:18) inf jjMK;! jjE 1 ? C ; inf jjMK;! jjE 1 ? C ; K ! 1; ^ where MK;! and MK;! denote the iteration matrices associated with (4.11) and (4.14), respectively. We end with two remarks. First, one example for the choice of ! is that ! K ?1 , which leads to the upper bounds in (4.18). Second, the diagonal matrices ^ Sk and Sk in (4.13) and (4.15) can be replaced by any other spectrally equivalent symmetric matrices of their respective dimension.
!

K

!

K

5. EQUIVALENT DISCRETIZATIONS
To improve the estimates in Theorems 4.2 and 4.3, we now consider the problem of switching the NR Q1 discretization system (3.4) to a spectrally equivalent discretization system for which optimal preconditioners are already available. This switching strategy, as mentioned in the introduction, has been used in the context of the multilevel additive Schwarz method; see 21] for the references. The most natural candidate for a switching procedure is the space of conforming bilinear elements UK = 2 C 0 ( ) : jE 2 Q1 (E ); 8E 2 Ek and j? = 0 ; on the same partition. We introduce two linear operators YK : UK ! VK and ^ YK : VK ! UK as follows. If 2 UK and e is an edge of an element in EK , then YK 2 VK is given by (5:1)

Z

e

YK ds =

Z

e

ds;

20

ZHANGXIN CHEN AND PETER OSWALD

which preserves the zero average values on the boundary edges. If v 2 VK , we ^ de ne YK v 2 UK by ^ (YK v)(z ) = 0 for all boundary vertices z in EK ; (5:2) ^ (YK v)(z ) = average of vj (z ) for all internal vertices z in EK ; where vj = vjEj and Ej 2 EK contains z as a vertex. Another choice for UK is the space of conforming P1 elements ~ UK = 2 C 0 ( ) : jE 2 P1 (E ); 8E 2 EK and j? = 0 ; ~ where EK is the triangulation of generated by connecting the two opposite vertices ^ of the squares in EK . The two linear operators YK : UK ! VK and YK : VK ! UK are de ned as in (5.1) and (5.2), respectively. Moreover, for both the conforming bilinear elements and the conforming P1 elements, it can be easily shown that there is a constant C , independent of K , such that 2K jj ? YK jj C jj jjE ; 8 2 UK ; (5:3) K jjv ? YK v jj C jjv jjE ; ^ 2 8v 2 VK : Since optimal preconditioners exist for the discretization system AK generated by the conforming bilinear elements (respectively, the conforming P1 elements), the next result follows from (5.3) and the general switching theory in 21]. Theorem 5.1. Let C K be any optimal symmetric preconditioner for AK ; i.e., we assume that a matrix-vector multiplication by C K can be performed in O(nK ) arithmetical operations, and that (C K AK ) C , with constant independent of K . Then (5:4) C K = SK + YK C K (YK )t is an optimal symmetric preconditioner for AK .

6. NUMERICAL EXPERIMENTS
In this section we present the results of numerical examples to illustrate the theories developed in the earlier sections. These numerical examples deal with the Laplace equation on the unit square: ? u = f in = (0; 1)2 ; (6:1) u = 0 on ?; 2 . The NR Q1 nite element method (3.4) is used to solve (6.1) where f 2 L with fEk gK=1 being a sequence of dyadically, uniformly re ned partitions of into k squares. The coarsest grid is of size h1 = 1=2. The rst test concerns the convergence of Algorithm 3.1. The analysis of the third section guarantees the convergence of the W -cycle algorithm with any number of smoothing steps and the uniform condition number property for the variable V cycle algorithm, but does not give any indication for the convergence of the standard V -cycle algorithm, i.e., Algorithm 3.1 with p = 1 and m(k) = 1 for all k. The rst two rows of Table 1 show the results for levels K = 3; : : : ; 7 for this symmetric V-cycle, where ( v ; v ) denote the condition number for the system BK AK and the reduction factor for the system IdK ? BK AK as a function of the mesh size on the nest grid hK . While there is no complete theory for this V -cycle algorithm, it is of practical interest that the condition numbers for this cycle remain relatively small.

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

21

1=hK
v v m

8

16

32

64

128

1.54 1.70 1.84 1.96 2.06 0.23 0.27 0.32 0.33 0.35 1.75 1.81 1.84 1.85 1.85

Table 1. Numerical results for the multiplicative V -cycles. For comparison, we run the same example by a symmetrized multilevel multiplicative Schwarz method corresponding to (4.17). One step of the symmetric version consists of two substeps, the rst coinciding with (4.17) and the second ~ repeating (4.17) in reverse order. The condition numbers m for MK;! AK with ?1 are presented in the third row of Table 1, where MK;! = M t MK;! is ~ ! K K;! now symmetric. The results are better than expected from the upper bounds of Theorem 4.3 which seem to be only suboptimal. In the second test we treat the above multigrid algorithm and symmetrized multilevel multiplicative method as preconditioners for the conjugate gradient method. In this test the problem (6.1) is assumed to have the exact solution u(x; y) = x(1 ? x)y(1 ? y)exy : Table 2 shows the number of iterations required to achieve the error reduction 10?6, where the starting vector for the iteration is zero. The iteration numbers (iterv ; iterm ) correspond to Algorithm 3.1 with p = 1 and m(k) = 1 for all k and the symmetrized multiplicative algorithm (4.17), respectively. Note that iterv and iterm remain almost constant when the step size increases. 1=hK 8 16 32 64 128 iterv 8 8 iterm 9 9 9 9 10

9 10 10

Table 2. Iteration numbers for the pcg-iteration. In the nal test we report analogous numerical results (condition numbers and pcg-iteration count) for the additive preconditioner CK associated with the splitting (4.11) (subscript a), and the preconditioner C K (subscript s) which uses the switch from the system arising from (3.4) to the spectrally equivalent system generated by the conforming bilinear elements via the operators in (5.1) and (5.2). We have implemented the standard BPX-preconditioner 5], with diagonal scaling, as C K .

22

ZHANGXIN CHEN AND PETER OSWALD

These results are shown in Table 3. The numbers show the slight growth, which is typical for most of the additive preconditioners and level numbers K < 10. The condition numbers s for the switching procedure are practically identical to the condition numbers for C K AK characterizing the BPX-preconditioner 5] in the conforming bilinear case. The switching procedure is clearly favorable as can be expected from the theoretical bounds of Theorems 4.2 and 5.1; however, the computations do not indicate whether the upper bound (4.16) is sharp or could be further improved. 1=hK
a

8

16

32

64

128 256 512

9.6 12.3 14.4 16.1 17.4 18.3 19.3 18 22 24 26 27 28 28 -

itera
s

3.37 3.87 4.24 4.54 4.80 5.05 10 11 13 13 14 15

iters

Table 3. Results for the preconditioners CK and C K .
1] T. Arbogast and Zhangxin Chen, On the implementation of mixed methods as nonconforming methods for second order elliptic problems, Math. Comp. 64 (1995), 943{972. 2] R. Bank and T. Dupont, An optimal order process for solving nite element equations, Math. Comp. 36 (1981), 35{51. 3] D. Braess and R. Verfurth, Multigrid methods for nonconforming nite element methods, SIAM J. Numer. Anal. 27 (1990), 979{986. 4] J. Bramble, Multigrid Methods, Pitman Research Notes in Math., vol. 294, Longman, London, 1993. 5] J. Bramble, J. Pasciak, and J. Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1991), 1-22. 6] J. Bramble, J. Pasciak, and J. Xu, The analysis of multigrid algorithms with non-nested spaces or non-inherited quadratic forms, Math. Comp. 56 (1991), 1{34. 7] S. Brenner, An optimal-order multigrid method for P1 nonconforming nite elements, Math. Comp. 52 (1989), 1{15. 8] S. Brenner, Multigrid methods for nonconforming nite elements, Proceedings of Fourth Copper Mountain Conference on Multigrid Methods, J. Mandel, et al., eds., SIAM, Philadelphia, 1989, pp. 54{65. 9] S. Brenner, Convergence of nonconforming multigrid methods without full elliptic regularity, Preprint, 1995. 10] Zhangxin Chen, Analysis of mixed methods using conforming and nonconforming nite element methods, RAIRO Model. Math. Anal. Numer. 27 (1993), 9{34. 11] Zhangxin Chen, Projection nite element methods for semiconductor device equations, Computers Math. Applic. 25 (1993), 81{88.

References

MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ELEMENTS

23

12] Zhangxin Chen, Equivalence between and multigrid algorithms for nonconforming and mixed methods for second order elliptic problems, IMA Preprint Series #1218, 1994, East-West J. Numer. Math. 4 (1996), to appear. 13] Zhangxin Chen, R. Ewing, and R. Lazarov, Domain decomposition algorithms for mixed methods for second order elliptic problems, Math. Comp. 65 (1996), to appear. 14] Zhangxin Chen, D. Y. Kwak, and Y. J. Yon, Multigrid algorithms for nonconforming and mixed methods for symmetric and nonsymmetric problems, IMA Preprint Series #1277, 1994. 15] M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), 163{180. 16] P. Kloucek, B. Li, and M. Luskin, Analysis of a class of nonconforming nite elements for crystalline microstructures, Math. Comp. (1996), to appear. 17] P. Kloucek and M. Luskin, The computation of the dynamics of martensitic microstructure, Continuum Mech. Thermodyn. 6 (1994), 209{240. 18] C. Lee, A nonconforming multigrid method using conforming subspaces, Proceedings of the Sixth Copper Mountain Conference on Multigrid Methods, N. Melson et al., eds., NASA Conference Publication, vol. 3224, 1993, pp. 317{330. 19] P. Oswald, On a hierarchical basis multilevel method with nonconforming P1 elements, Numer. Math. 62 (1992), 189{212. 20] P. Oswald, Multilevel Finite Element Approximation : Theory and Application, Teubner Skripten zur Numerik, Teubner, Stuttgart, 1994. 21] P. Oswald, Preconditioners for nonconforming elements, Math. Comp. (1996), to appear. 22] P. Oswald, Intergrid transfer operators and multilevel preconditioners for nonconforming discretizations, Preprint, 1995. 23] R. Rannacher and S. Turek, Simple nonconforming quadrilateral Stokes element, Numer. Meth. Partial Di . Equations 8 (1992), 97{111. 24] P. Raviart and J. Thomas, A mixed nite element method for second order elliptic problems, Mathematical aspects of the FEM, Lecture Notes in Mathematics, 606, Springer-Verlag, Berlin & New York (1977), pp. 292{315. 25] M. Wang, The W-cycle multigrid method for nite elements with nonnested spaces, Adv. in Math. 23 (1994), 238{250. 26] H. Yserentant, Old and new convergence proofs for multigrid methods, Acta Numerica, Cambr. Univ. Press, Cambridge, 1993, pp. 285{236. 27] J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review 34 (1992), 581{613.
Department of Mathematics, Box 156, Southern Methodist University, Dallas, Texas 75275{0156.