Journal of Scientific Computing, Vol. 17, Nos. 1–4, December 2002 (© 2002)
Sparse Two-Scale FEM for Homogenization Problems A.-M. Matache 1 Received August 22, 2001; accepted (in revised form) October 17, 2001 We analyze two-scale Finite Element Methods for the numerical solution of elliptic homogenization problems with coefficients oscillating at a small length scale e ° 1. Based on a refined two-scale regularity on the solutions, two-scale tensor product FE spaces are introduced and error estimates which are robust (i.e., independent of e) are given. We show that under additional two-scale regularity assumptions on the solution, resolution of the fine scale is possible with substantially fewer degrees of freedom and the two-scale full tensor product spaces can be ‘‘thinned out’’ by means of sparse interpolation preserving at the same time the error estimates. KEY WORDS: Homogenization; two-scale FEM; sparse two-scale FEM.
1. INTRODUCTION The accurate and efficient numerical solution of partial differential equations with coefficients or geometries that oscillate periodically at a small length scale e ° 1 has received increasing attention recently. Solutions to such problems contain several length scales that differ by many orders of magnitude. Such homogenization problems have been thoroughly analyzed by asymptotic analysis as e Q 0, see [3, 7] and the references there. In this analytical approach the limiting problem as e Q 0 is identified first and then solved numerically by standard methods. In particular, no scale resolution is required, since the fine scales are averaged out (homogenized). However, this analytic homogenization process does not preserve the fine scale information of the solution and the recovery of fine scale features by use of correctors proves as costly as the original problem. The direct numerical treatment of multiple scale problems by the standard Finite Element Method (FEM) [1, 9] on the other hand faces the difficulty of representing the microstructure. The standard FEM yields 1
Seminar for Applied Mathematics, ETH-Zentrum, CH-8092 Zürich, Switzerland. E-mail:
[email protected] 659 0885-7474/02/1200-0659/0 © 2002 Plenum Publishing Corporation
660
Matache
reliable results only under the assumption of scale resolution, i.e., if the FE mesh is refined to the smallest length scale. Such an approach is however infeasible if the difference in scales is sufficiently large. However, a main feature of such problems is that the spatial variation of the solutions is concentrated at length scales which are a-priori known or can be estimated. Moreover, the regular patterns contained in the fine scale data can be used to substantially lower the number of degrees of freedom requested by the resolution of this scale. 1.1. The Homogenization Problem We consider here the following elliptic problem in divergence form Le
1 xe , “ 2 u := − N · 1 A 1 xe 2 Nu 2+a 1 xe 2 u =f(x) e
e
x
e
0
(1)
where e is a small parameter and we assume that A(y), a0 (y) are 1-periodic . 1 1 n×n in each variable and that A( · ) ¥ L . per (Q) symm , a0 ( · ) ¥ L per (Q) satisfy, for 2 2 n 1= some c > 0, t A(y) t \ c |t| , a0 (y) \ c for all t ¥ R and a.e. y ¥ Q 1 =[0, 1] n will be referred to as unit-cell domain. We [0, 1] n. The domain Q consider (1) in a bounded Lipschitz domain W and we complete (1) by Dirichlet boundary conditions on “W, i.e., u e=0
on “W
(2)
1.2. Finite Element Approximation The FEM is based on the variational form of (1), (2) Find u e ¥ H 10 (W): B e(u e, v)=(f, v) e
1 0
-v ¥ H 10 (W)
(3)
1 0
where the bilinear form B : H (W) × H (W) Q R is given by B e(u, v)=F W
1 A 1 xe 2 Nu(x) 2 · Nv(x)+a 1 xe 2 u(x) v(x) dx 0
The variational problem (3) admits for every e > 0 and every f ¥ L 2(W) a unique solution u e ¥ H 10 (W). Let V eN … H 10 (W) be any subspace of dimension N=dim(V eN ) < .. Then u eN ¥ V eN : B e(u eN , v)=(f, v)
-v ¥ V eN
(4)
defines a unique FE solution and there exists C > 0 independent of e such that ||u e − u eN ||H 1(W) [ C mine ||u e − v||H 1(W) v ¥ VN
(5)
Sparse Two-Scale FEM for Homogenization Problems
661
Even if the right hand side f, the domain W and the coefficients A and a0 are smooth (i.e., C .), if e/diam(W) ° 1 the solution u e exhibits oscillations on the e-scale obstructing FE convergence. More specifically, there exist positive constants C=C(W) and C(a)=C(a, W), a ¥ N n, such that ||u e||L 2(W) [ C, ||D au e||L 2(W) [ C(a) e 1 − |a|,
-a ¥ N n, |a| > 0
(6)
Let us denote by VN =S p, 1(W, TH ) the usual FE space of continuous, piecewise polynomials of degree p \ 1 on a quasiuniform mesh TH of meshwidth H. Then, the FE error with respect to VN satisfies the following a-priori estimate ||u e − u eN ||H 1(W) [ C min(1, (H/e) p), with C > 0 being a constant independent of e and H. Standard FEM, as e.g., piecewise linears on a quasiuniform mesh TH of size H, thus converge only if H < e, i.e., if N=dim V eN =O(e −n). This scale resolution requirement is, especially if n=3, computationally very expensive. In view of (5), the key to a robust discretization of (1) is the design of V eN . Rather than incorporating, e.g., the asymptotics of u e (which are not always defined, see [7] and the references there) into V eN , we design V eN based on a refined two-scale regularity theory on u e. In contrast, in [5, 4, 8] a generalized FEM based on non-polynomial FE spaces was proposed and analyzed. For analytic f, this method was shown to give robust exponential rates of convergence. 1.3. Two-Scale Regularity On the unbounded domain R n (i.e., in the absence of boundary layers) the solution u e(x) can be viewed as a map from the ‘‘slow’’ variable x into the ‘‘fast’’ variable x/e: u e(x)=U e(x, x/e), where U e(x, y) depends smoothly on e. In [6] we derived new, two-scale regularity results on u e(x) by analyzing U e(x, y). More precisely, the following two-scale shift theorem holds: Theorem 1.1. Assume that A( · ), a0 ( · ) are smooth and 1-periodic in 1 . Then, for f ¥ H k(R n) (k \ 0), the solution u e(x) of (1) on R n y=x/e ¥ Q can be written as u e(x)=U e(x, y)|y=x/e , x ¥ R n, where U e(x, y) satisfies in W=R n the two-scale regularity estimate ||U e||H r(W, H sper (Q1 )) [ C(k) ||f||H r+s − 1(W)
(7)
provided r+s [ k+1, r, s \ 0, and ||e −1 Ny U e||H r(W, H sper− 1 (Q1 )) [ C(k) ||f||H r+s − 1(W)
(8)
662
Matache
provided r+s [ k+1, r, s − 1 \ 0. Here, C(k) is independent of e, but depends on r+s. This two-scale point of view of regularity gives rise to a ‘‘natural’’ FE discretization of (1) by means of a non-standard two-scale FE-space V eN in W. With the two-scale FE spaces V eN robust convergence rates as h, H Q 0 can be achieved for u eN as we shall show in Section 2. These twoscale approximation results are quite general and applicable whenever the solution has the two-scale regularity. Section 2 is devoted to the definition and error analysis of the two-scale FEM and its sparse version. In Section 3 we present numerical results which support our error estimates. 2. TWO-SCALE FINITE ELEMENT METHOD 2.1. FE-Spaces We assume that the domain W is axis-parallel and we take TH to be a quasiuniform mesh in W of affine quadrilateral elements of size H. We take as macro FE space in W=(0, 1) n the standard FE space S p(W, TH )= 1 ) -K ¥ TH }, where FK : K 1 Q K is the affine {u ¥ H 1(W) |u|K p F K−1 ¥ S p(K 1 ) denotes the space of element map associated to the element K and S p(K 1 =(0, 1) n. polynomials of degree p on the reference element K 1 based on a periodic Next, we resolve the fine scale by a FEM in Q 1h , for simplicity also affine, quasiuniform of width h. Then, we mesh T 1, T 1h ) the finite element space of all continuous, periodic denote by S mper (Q 1h . piecewise polynomials of degree m with respect to T e We take as two-scale FE space V N the space of traces of the two-scale 1, T 1h ))={U(x, y) | -K ¥ T: U(FK (xˆ), y) is polynomial space S p(W, TH ; S mper (Q 1 and continuous, periodic p.w. polynomial w.r.t. T 1h of degree p w.r.t. xˆ in K 1 in y ¥ Q }. More specifically, 1, T 1h )) V eN =R eS p(W, TH ; S mper (Q
(9)
where the trace operator R e is given by (R eU)(x)=U(x, y)|y= xe . Since 1, T 1h ), V eN is a generalized FE-space. Note that the elements of {1} … S mper (Q the FE space V eN have the form u eFE (x)=; i, I ciI Ni (x) fI (x/e), x ¥ W, with 1, T 1h ). ciI ¥ R and shape functions Ni ( · ) ¥ S p(W, TH ), fI ( · ) ¥ S mper (Q 2.2. Two-Scale Finite Element Convergence The goal of this section is to estimate the approximation error (5) for the two-scale FE space V eN (9) and to obtain robust estimates with respect to e for H/e \ 1. We have seen that the solution u e may be interpreted as u e( · )= e 1 and R is the trace operator RU ( · , · /e), where U e( · , · ) is defined on W × Q given by (Rf)(x)=f(x, x). This suggests to use FE-interpolants in W and 1 to approximate U e in W × Q 1 and take traces. Q
Sparse Two-Scale FEM for Homogenization Problems
663
If H denotes the mesh size of the quasiuniform ‘‘macroscopic’’ triangulation on W and h is the mesh size of the quasiuniform ‘‘micro’’ trian1 , we obtain (see [6]): gulation on the unit cell Q Proposition 2.1. For p, m, k, s \ 1 and H/e ¥ N the error in the twoscale FEM based on the space (9) can be estimated as follows: ||u e − u eFE ||H 1(W) [ CH min(p, k)Fn (p, k)(||e −1 Ny U e||H k(W; L 2per (Q1 )) +||U e||H k+1(W; L 2per (Q1 )) ) +Ch min(m, s)Fn (m, s)(||e −1 Ny U e||H n(W; H sper (Q1 )) +||U e||H n(W; H s+1 1 ) per (Q)
(10)
Here C > 0 is a positive constant independent of p, m, k, s and e and the functional Fn (p, k) depends only on n, p and k. For p Q ., Fn (p, k) [ Cp −(k − n+1). The following result is a consequence of Proposition 2.1 and Theorem 1.1. Theorem 2.2. Assume for the solution u e of (3) the two-scale regularity (7)–(8) in W. Then, for H/e ¥ N, it holds: ||u e − u eFE ||H 1(W) [ C1 (k) H min(p, k)Fn (p, k) ||f||H k(W) +C2 (s) h min(m, s)Fn (m, s) ||f||H n+s(W) So far we have only discussed the preasymptotic case when H \ e and we obtained the robust (in e) error estimate ||e eN ||H 1(W) [ C(H p+h m). Let us choose p=m. Then, for h 5 H we obtain ||e eN ||H 1(W) [ Ch p and N= dim(V eN )=O(H −nh −n)=O(h −2n). Hence, in terms of number of degrees of freedom, the two-scale FE error estimate is qualitatively of the form p
||e eN ||H 1(W) [ CN − 2n
for N Q e −2n
(11)
since the total number of degrees of freedom at the critical value H 5 e, h 5 e is N=O(e −2n). At this transition point the fine scale is resolved and we switch from the two scale FE space to full discretization with mesh size H=eh, h [ e. This is achieved by breaking the periodicity to get the full space with mesh width H=eh, h [ e. The dimension of the FE space in this asymptotic regime is N=O(H −n)=O(e −nh −n). Using standard error estimates, i.e., ||e eN ||H 1(W) [ CH p ||u e||H p+1(W) , and the a priori estimate (6) for u e we obtain
1 He 2 =Ch [ Ce p
||e eN ||H 1(W) [ C
p
−p
p
p
N − n [ CN − 2n
for N R e −2n p
We see that we obtain a robust convergence rate of O(N − 2n), as compared p to the (non-robust) rate of O(N − n) of standard FEM. The robustness of
664
Matache
the two-scale FEM was achieved by an increase in dimension and the use 1. of tensor product approximations in W × Q With two-scale FEM resolution, e independent convergence is achieved by inflating the dimension of the approximation: we resolve the fine scales 1 … R n. The tensor by simultaneously approximating in (x, y) ¥ W × Q product two-scale FE space represents full interactions between scales. The 1 and the anisotropic regularity in Theorem 1.1 product structure of W × Q allow, however, to obtain the convergence in Theorem 2.2 with substantially fewer degrees of freedom: the scale interaction is ‘‘thinned out’’ by means of sparse tensor products. 2.3. Sparse Two-Scale Interpolation Let us consider W o … R n, o=1, 2 two Lipschitz bounded domains, 1 . We give first a keeping in mind that for us they will be W 1=W and W 2=Q rather abstract construction of a sparse grid in W 1 × W 2 and it is in this most general setting that we prefer to work out the error estimates. Assume that {S oL } . L=0 , o=1, 2, are two dense hierarchic sequences of finite dimensional subspaces of H 1(W o) S o0 … S o1 … · · · … S oL … H 1(W o)
(12)
At level L, N oL will denote the dimension of S oL . In order to employ this hierarchy in the context of FE methods the following approximation property is needed: mino ||u − v||H 1(W o) [ Y o(N oL , s) ||u||H s+1(W o) ,
-u ¥ H s+1(W o)
(13)
v ¥ SL
where Y o(N, s) Q 0 for s > 0 as N Q .. For regular solutions the usual FE-spaces based on quasiuniform, shape regular meshes are suitable. Let {THL }L ¥ N be a nested sequence of regular affine triangulations of a Lipschitz domain W of meshwidth HL =HL − 1 /2, -L \ 1 and let p \ 1 be a polynomial degree. Then ¯ ) : u|K ¥ S p(K) -K ¥ TH } SL :=S p(W, THL ) :={u ¥ C 0(W L
(14)
satisfies (12), while the approximation property reads min
v ¥ S p(W, TH )
||u − v||H 1(W) [ Y(NL , s) ||u||H s+1(W)
(15)
L
where Y(N, s)=O(N −min(p, s)/n). Estimates similar to (15) also hold for p-version or spectral element methods, i.e., on fixed T as p=pL Q .. Within this abstract setting we follow [10] and introduce the so called hierarchic excess of the scale (12), by W oL :=S oL ı S oL − 1
L\0
(16)
Sparse Two-Scale FEM for Homogenization Problems
665
We also set S o−1 :={0} and we note that complements are uniquely defined by some given Hilbert structure which produces the usual topology in H 1(W o). Further, P oL will be the orthogonal projection on S oL with respect to this Hilbert structure. We remark that (13) still holds for L=−1, by choosing Y o(N o−1 , s) to be the embedding constant of H 1(W o) in H s+1(W o). With respect to the Hilbert structure mentioned above, S oL is an orthogonal sum of the form S oL =Á0 [ i [ L W oi . Using this decomposition, we define the full tensor product FE-space in W 1 × W 2 at level L ¥ N by SL, L :=S 1L é S 2L = Â
(W 1i é W 2j ) … H 1, 1(W 1 × W 2)
(17)
0 [ i, j [ L
and the sparse tensor product FE-space at level L by 3 L, L := Â S
(W 1i é W 2j ) … H 1, 1(W 1 × W 2)
(18)
0 [ i+j [ L
This correlation shows the main difference between standard (full) tensor product spaces and the sparse interpolation spaces: if for the full tensor product space the resolution is defined in each direction separately, the overall resolution for the sparse tensor product spaces is limited by L; the sparse two-scale spaces result therefore from skipping certain subspaces (degrees of freedom). For a given U ¥ H 1(W 1 × W 2) we define the sparse interpolant of U in 3 L, L , as given by S ˆ L := U
(P 1i − P 1i− 1 ) é (P 2j − P 2j− 1 ) U
C
(19)
0 [ i+j [ L
With these notations, the following estimate will enable us to deduce from (13) an approximation property of the sparse scale (SˆL, L )L ¥ N , too. Proposition 2.3. Assume that the sequence (12) of FE-spaces {S oL }L has the approximation property (13) and s, t > 0. Then there exists C > 0 such that for all U ¥ H s+1, t+1(W 1 × W 2) it holds: min ||U − V||H 1, 1(W 1 × W 2)
3 L, L V¥S
ˆ L||H 1, 1(W 1 × W 2) [ ||U − U
35 C Y (N , s) Y (N +5 C Y (N , s) 6 ||U|| L+1
1
[C
1 i−1
2
2 L−i
6
, t) ||U||H s+1, t+1(W 1 × W 2)
i=0 .
1
1 i
H s+1, 1(W 1 × W 2)
4
(20)
i=L+1
Concerning the approximation quality, the accuracy of the sparse grid interpolant is only slightly deteriorated with a logarithmic factor but the
666
Matache
number of dof is reduced to that of the discretization of one subdomain only (here again up to some logarithmic factor): Proposition 2.4. Assume that U ¥ H s+1, s+1(W 1 × W 2). Then, with the hierarchic sequences S 1L =S p(W 1, THL ), S 2L =S m(W 2, ThL ), HL 5 hL , p 5 m, the sparse interpolant converges, as L Q ., with the rate ˆ L ) 1+d N ˆ L−d ||U||H s+1, s+1(W 1 × W 2) min ||U − V||H 1, 1(W 1 × W 2) [ C(log N
3 L, L V¥S
(21)
where d=min(p, s)/n. Proof. Taking into account that Nj =O(2 nj) and using (15) in (20), with s=t, we obtain min ||U − V||H 1, 1(W 1 × W 2) [ C · log NL · N L−d ||U||H s+1, s+1(W 1 × W 2)
3 L, L V¥S
(22)
ˆ L :=dim(SˆL, L )= In (22), NL =dim(SL )=O(2 nL). Also, due to (18), N O(L · 2 nL). Therefore, rephrasing (22) in terms of the number of degrees of ˆ L we obtain (21). freedom N We return now to the two-scale homogenization problem and recall that for sufficiently smooth data the solution u e can be viewed as u e(x)= i U e(x, x/e), where U e(x, y) depends smoothly on e. We have then constructed two-scale FE spaces as traces of full tensor 1 and we have showed that the FE method based on product spaces in W × Q these spaces leads to robust rates of convergence at the price of discretizing 1 , i.e., in R 2n. The anisotropic regularity of U e and the both in W and Q tensor product structure of the two-scale FE-spaces allow to apply the ideas of sparse interpolation. Assume that we have the following two sequences of hierarchic FE 1 ). As before, we have in spaces {S 1i } Li=0 … H 1(W) and {S 2j } Lj=0 … H 1per (Q mind sequences of FE spaces of the form S 1i =S p(W, THi ) and S 2j = 1, T 1h ) where {TH } and {T 1h } are sequences of affine nested FE S mper (Q j i j 1 , respectively, and {T 1h } are periodic. We assume further meshes in W and Q j 3 L, L the sparse FE that p 5 m and Hi 5 hi for all i=0,..., L. We denote by S space associated to these sequences. For the sparse two-scale FEM convergence result we need a slightly 1 . More precisely, the modified approximation property in both W and Q approximation property reads: for all a ¥ N n0 with 0 [ aj [ 1, for all s \ n − 1, t \ 0 and for i, j=0,..., L it holds:
1
||D a(u − P 1i u)|| 2L 2(K)
C
2
1/2
[ Y 1a (N 1i , s) ||u||H s+1(W)
K ¥ TH
i
||v − P 2j v||H 1per (Q1 ) [ Y 2(N 2j , t) ||v||H t+1(Q1 ) ||N(v − P 2j v)||L 2per (Q1 ) [ Y 2(N 2j , t) ||Nv||H t(Q1 )
(23)
Sparse Two-Scale FEM for Homogenization Problems
667
with Y 1a (N, s), Y 2(N, t) Q 0 as N Q .. Using then the same arguments as for the proof of Proposition 2.1, Theorem 2.2 and Proposition 2.3 we obtain the following result on convergence of the sparse two-scale FEM: Assume for the solution u e of (3) the two-scale
Proposition 2.5. regularity
−1 ||U e||H s+1(W, H s+1 Ny U e||H s+1(W, H sper (Q1 )) [ C ||f||H 2s+1(W) 1 +||e per (Q))
for some s \ n − 1, where C=C(s, n) > 0 is a constant independent of e. ˆ eN be the sparse two-scale FE space V ˆ eN :=R e SˆL, L , where R e is the Let V e trace operator given by (R U)(x)=U(x, x/e). Denote by uˆ eFE the FE soluˆ eN . Then, it holds tion with respect to V ˆ L ) 1+d N ˆ L−d ||f||H 2s+1(W) ||u e − uˆ eFE ||H 1(W) [ C(log N
(24)
ˆ L =dim V ˆ eN , d=min(p, s)/n and C > 0 is a constant independent where N ˆ L , e and f. of N Proof. Let us denote by uˆ e, L the sparse two-scale interpolant of u e in ˆ e, L, where U ˆ e, L is the ˆ eN given by uˆ e, L=R eU the sparse two-scale FE space V e sparse interpolant of U in SˆL, L as given by (19). We split the sparse twoscale FE-error in elemental contributions on the macro mesh TH =THL and use the trace Lemma 3.1 in [6] to obtain:
3
||u e − uˆ e, L|| 2H 1(W) [ C C K ¥ TH
L
ˆ e, L)|| 2L 2(K × Q1 ) e 2(|a| − 1) ||D ax (U e − U
C 0 [ aj [ 1 |a| \ 1
ˆ e, L)|| 2L 2(K × Q1 ) e 2 |a| ||D ax (e −1 Ny )(U e − U
+ C
4
(25)
0 [ aj [ 1
Due to the approximation property (23) we have that ˆ e, L|| 2L 2(K × Q1 ) ||D ax (U e − U
C K ¥ TH
L
3 C 5 C ||D (P − P + C 5 C ||D (P − P [ C 3 C Y (N , s) Y (N L
1 i
a x
[C
i=0
1 i−1
) é (Id 2 − P 2L − i ) U e|| 2L 2(K × Q1 )
K ¥ TH
i
.
a x
i=L+1
1 i
6 4 1/2
1 i−1
) é Id 2 U e|| 2L 2(K × Q1 )
K ¥ TH
i
L+1
1 a
1 i−1
2
2 L−i
, t) ||U e||H s+1(W, H t+1(Q1 ))
i=0 .
+ C i=L+1
Y 1a (N 1i , s) ||U e||H s+1(W, H 1per (Q1 ))
4
2
2
6
1/2
668
Matache H- Version Two- Scale Method, ε = 1e -2
0
10
-2
-2
10
10
-4
-4
10
10
-6
10
Energy error
Energy error
H - Version Two - Scale Method, ε = 1e- 4
0
10
-8
10
-10
10
-12
-10
p=µ=1 p=µ=2 p=µ=3 p=µ=4
-12
10
-14
10
-8
10
10
p=µ=1 p=µ=2 p=µ=3 p=µ=4
10
-6
10
-14
-2
-1
10
10
0
10
-2
10
-1
10
0
10
H=h
10
H=h
Fig. 1. Energy error for the full version of the two-scale FEM.
and a similar estimate can be derived for ; K ¥ TH ||D ax (e −1 Ny )(U e − ˆ e, L)|| 2L 2(K × Q1 ) . For the spaces considered here there holds L U Y 1a (N, s)=H −|a|O(N −min(p, s+1)/n)
and
Y 2(N, t)=O(N −min(m, t)/n)
Taking s=t \ n − 1, m 5 p, Hi 5 hi and using that e/HL [ 1 we conclude the proof. i 2.4. Numerical Results We illustrate our error estimates for the two-scale FEM for problem (1), (2) in the one dimensional case W=(0, 1) with data f(x)=e x, A(y)= 2+cos(2py) and a0 (y)=0. The shift Theorem 1.1 applies on W and the solution does not exhibit boundary layers, since u e(x)=U e(x, x/e), with 1 and 1-periodic in y. U e(x, y) smooth on W × Q In Fig. 1 we plot for different p=m ¥ {1, 2, 3, 4} the energy error versus H=h. Computations were performed for two different e-scales, 10 −2 and 10 −4, respectively. We see that the rate of convergence of Relative error in the energy vs. meshwidth H = h; ε = 1e - 3, p = µ = 1
0
Relative error in the energy vs. #dof; ε = 1e- 5, p = µ = 1
0
10
10
full 2scale grid sparse grid -2 4 N *log(N)
-1
10
-1
Relative error in the energy
Relative error in the energy
10
-2
10
-3
10
-2
10
-3
10 -4
10
full 2scale grid sparse grid -5
10
-4
-3
10
-2
-1
10
10 H = h --> 0
0
10
10
0
10
1
10
2
10 #DOF
3
10
4
10
Fig. 2. Two-scale FEM and sparse two-scale FEM with p=m=1: relative error in the energy versus the mesh size H=h Q 0 (left) and versus # dof (right), respectively.
Sparse Two-Scale FEM for Homogenization Problems
669
||u e − u eFE || 2H 1(W) is proportional to H 2p as expected from the error estimates in Theorem 2.2. Moreover, we observe robustness of the convergence rates with respect to the parameter e. In Fig. 2 we compare the performances of the two-scale FEM and its sparse version for e=10 −3. The left plot shows the relative error in the energy versus H=h Q 0 for both methods in the case p=m=1. We see that the error curves are practically at the top of each other. In the right figure we plot the same relative error in the energy versus # dof for the twoscale FEM and for the sparse two-scale FEM. We clearly see the O(N −1) rate of convergence for the two-scale FEM and the O(N −2(log N) 4)convergence rate for the sparse two-scale FEM, as predicted by Proposition 2.5. AKNOWLEDGMENTS This research was supported under the project ‘‘Homogenization and multiple scales’’ HMS2000 of the EC (HPRN-CT-1999-00109) and by the Swiss National Science Foundation under Project ‘‘Hierarchic FE-Models for periodic lattice and honeycomb materials’’ with Number BBW 2158754.99. REFERENCES 1. Babusˇka, I., and Aziz, A. K. (1973). Survey lectures on the mathematical foundation of the finite element method. In Aziz, A. K. (ed.), The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations, Academic Press, New York, pp. 5–359. 2. Bensoussan, A., Lions, J. L., and Papanicolau, G. (1978). Asymptotic Analysis for Periodic Structures, North Holland, Amsterdam,. 3. Cioranescu, D., and Donato, P. (1999). An Introduction to Homogenization, Oxford University Press. 4. Matache, A. M. (2000). Spectral- and p-finite elements for problems with microstructure, Ph.D. thesis, ETH Zürich. 5. Matache, A. M., Babusˇka, I., and Schwab, C. (2000). Generalized p-FEM in homogenization. Numer. Math. 86(2), 319–375. 6. Matache, A. M., and Schwab, C. Two-Scale FEM for Homogenization Problems (submitted), Report 2001-06, Seminar for Applied Mathematics, ETH Zürich. http://www. sam.math.ethz.ch/reports/details/2001/2001-06.shtml. 7. Oleinik, O. A., Shamaev, A. S., and Yosifian, G. A., (1992). Mathematical Problems in Elasticity and Homogenization, North-Holland. 8. Schwab, C., and Matache, A. M. (2000). High order generalized FEM for lattice materials. In Neittaanmäki, P., Tiihonen, T., and Tarvainen, P. (eds.), Proceedings of the 3rd European Conference on Numerical Mathematics and Advanced Applications, Finland, 1999, World Scientific, Singapore. 9. Szabo´, B., and Babusˇka, I. (1991). Finite Element Analysis, Wiley. 10. Zenger, C. (1990). Sparse grids. In Parallel Algorithms for PDEs, Proceedings of the 6th GAMM-Seminar, Kiel.
