# The Cascadic Multigrid Method of the Weak Galerkin Method for Second-Order Elliptic Equation

Authors: Shi Sun; Ziping Huang; Cheng Wang; Liming Guo
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This paper is devoted to the analysis of the cascadic multigrid algorithm for solving the linear system arising from the weak Galerkin finite element method. The proposed cascadic multigrid method is optimal for conjugate gradient iteration and quasi-optimal for Jacobi, Gauss-Seidel, and Richardson iterations. Numerical results are also provided to validate our theoretical analysis.


---

## Body

## 1. Introduction

The weak Galerkin (WG) finite element method (FEM) is a recently developed numerical method for solving various types of partial differential equations. A new concept of the discrete weak gradient is introduced, which is the most significant feature of the weak Galerkin method. Due to the definition of weak gradient, the weak Galerkin finite element method is flexible in numerical approximation.There have been some studies and applications of the weak Galerkin finite element method. The method was first introduced by Wang and Ye in [1] for second-order elliptic problems. The corresponding numerical analysis of the weak Galerkin method based on Raviart-Thomas (RT) elements and Brezzi-Douglas-Marini (BDM) elements is given in [2]. A stabilization technique was presented and applied to the weak Galerkin finite element method, and the resulting weak Galerkin finite element method is no longer limited to RT and BDM elements [3]. In [4], the weak Galerkin mixed finite element method for biharmonic equations has been developed. For the applications of the weak Galerkin finite element method for other types of partial differential equations, the readers are referred to [5–8].In this paper, we consider the cascadic multigrid method for solving the linear system generated by the weak Galerkin finite element method for second-order elliptic problems. Multigrid methods [9] have been shown to be very effective in solving large scale system theoretically and numerically. The cascadic multigrid method [10, 11] is a one-way multigrid method and easy to be implemented since it requires no coarse grid corrections at all. Much effort has been made to the analysis of cascadic multigrid method (see, e.g., [12, 13]). Following the idea of [13], we can establish the error estimate in energy norm and the computational complexity estimate of the proposed cascadic multigrid method.The rest of this paper is organized as follows. In Section2, we introduce the weak Galerkin finite element method for second-order elliptic problems. In Section 3, a cascadic multigrid algorithm based on the weak Galerkin finite element discretization is proposed and analyzed, and the error estimates in energy norm and computational complexity are obtained. Numerical experiments are conducted to confirm our theoretical results in Section 4. Finally, we give the conclusion in  Section 5.


## 2. Model Problem and Its WG Finite Element Approximation

Consider the following second-order elliptic problem:(1)-∇·Ax∇u=finΩ,u=0on∂Ω,where Ω is a convex polygonal domain with boundary ∂Ω in R2, A∈[L∞(Ω)]2×2, f∈L2(Ω). Furthermore, assume that A is symmetric uniformly positive definite and uniformly bounded-above diffusion; namely, there exist positive constants α and β such that(2)αξTξ≤ξTAxξ≤βξTξ,∀ξ∈R2,x∈Ω.Here and thereafter, for any subsetD⊆R2, we use the standard notations for the Sobolev spaces Hs(D) and H0s(D) with s≥0. The inner-product, norm, and seminorm in Hs(D) are denoted by (·,·)s,D, ·s,D and ·s,D, respectively, and we skip the subscript D when D=Ω.Since the domainΩ is convex, the unique solution u of problem (1) exists and satisfies the full regularity assumption [14](3)u2≤Cf0.LetK be a polygonal domain with interior K0 and boundary ∂K. Denote by W(K) the space of weak functions on K; that is,(4)WK≔v=v0,vb:v0∈L2K,vb∈H1/2∂K.For anyv∈W(K), the weak gradient of v is defined as ∇wv,(5)∇wv,qK=-v0,∇·qK+vb,q·n∂K,∀q∈Hdiv,K,where H(div,K)={q:q∈[L2(K)]2,∇·q∈L2(K)}.The discrete weak gradient, denoted by∇w,r,Kv∈[Pr(K)]2, is defined as follows:(6)∇w,r,Kv,qK=-v0,∇·qK+vb,q·n∂K,∀q∈PrK2.LetTh be a shape-regular, quasi-uniform triangular mesh of the domain Ω, with the mesh size h. C denotes a generic positive constant independent of the mesh size h throughout this paper. Denote the weak function space on Th by V; that is,(7)V≔v=v0,vb:v0,vbT∈WT,∀T∈Th.For any given integer k≥1, define Wk(T) as the discrete weak function space consisting of polynomials of degree k in T and piecewise polynomials of degree k on ∂T; that is,(8)WkT≔v=v0,vb:v0T∈PkT,vbe∈Pke,e∈∂T.The weak Galerkin finite element spaces are defined as follows:(9)Vh≔v=v0,vb:v0,vbT∈WkT,∀T∈Th,Vh0≔v:v∈Vh,vb=0on∂Ω.It follows from [3] that(10)∇w,k-1vT=∇w,k-1vT,∀v∈Vh,T∈Th.For the discrete weak gradient, we will drop the subscript k-1 in the notation ∇w,k-1 for simplicity.The weak Galerkin finite element method can be written as to finduh={u0,ub}∈Vh0 such that(11)ahuh,v=f,v0,∀v=v0,vb∈Vh0,where(12)ahw,v=∑T∈ThAx∇ww,∇wvT+hT-1w0-wb,v0-vb∂T,for any w={w0,wb}, v={v0,vb}∈V.For each elementT∈Th, denote by Q0 the L2 projection from L2(T) onto Pk(T). Eh is the set of all edges in Th. For each edge e∈Eh, let Qb be the L2 projection from L2(e) onto Pk(e). Define Qh:V→Vh(13)Qhv≔Q0v0,Qbvb,∀v=v0,vb∈V.Denote by Qh the L2 projection onto the local discrete gradient space [Pk-1(T)]2. Lemma 5.1 in [3] shows that, on each T∈Th,(14)∇wQhϕ=Qh∇ϕ,∀ϕ∈H1Ω.For Qh and Qh defined above, the following lemmas provide some estimates.Lemma 1 (see [3], Lemma 5.2).
For anyϕ∈Hk+1(Ω), we have(15)∑T∈Thϕ-Q0ϕ0,T2+∑T∈ThhT2∇ϕ-Q0ϕ0,T2≤Ch2k+1ϕk+12,(16)∑T∈ThA∇ϕ-Qh∇ϕ0,T2≤Ch2kϕk+12.Lemma 2 (see [3], Lemma 5.3).
For anyw∈Hk+1(Ω) and v={v0,vb}∈Vh, we have(17)∑T∈ThhT-1Q0w-Qbw,v0-vb∂T≤Chkwk+1v,(18)∑T∈ThA∇w-Qh∇w·n,v0-vb∂T≤Chkwk+1v,where · is the energy norm; that is, for any v∈Vh, v2=ah(v,v).Lemma 3 (see [3], Theorem 8.1, Theorem 8.2).
Assume the exact solutionu∈Hk+1(Ω); then we have(19)uh-Qhu≤Chkuk+1,(20)Q0u-u00≤Chk+1uk+1.For anyv={v0,vb}, w={w0,wb}∈V, we define an inner-product by(21)v,w=∑T∈Thv0,w0T+∑T∈ThhTv0-vb,w0-wb∂T.Define the following discrete norms:(22)v0,h,T2=v00,T2+hTv0-vb0,∂K2,∀T∈Th,v0,h2=∑T∈Thv0,h,T21/2.It is clear that v0,h2=((v,v)).With the above estimates, the following lemma can be proved, which is needed in Section3.Lemma 4.
Letu∈Hk+1(Ω) be the exact solution of problem (1), and let uh={u0,ub} be the weak Galerkin finite element solution of problem (11); then we have(23)u-uh≤Chkuk+1,(24)u-uh0,h≤Chk+1uk+1.Proof.
Apparently, for any edgee∈Eh, we have(25)Q0u-Qbue≤Q0u-ue.T is an element with e as an edge. For any function φ∈H1(T), the following trace inequality is well known(26)φe2≤ChT-1φ0,T2+hT∇φ0,T2.Using the trace inequalities (26) and (15), we have(27)∑T∈ThQ0u-Qbu0,∂T2≤Q0u-u0,∂T2≤∑T∈ThCh0,T-1Q0u-uT2+hT2∇Q0u-u0,T2≤Ch2k+1uk+12.Then it follows from (14) and (16) that(28)∑T∈ThA∇u-∇wQhu,∇u-∇wQhu≤Ch2kuk+12.Thus, we have(29)u-Qhu2=∑T∈ThA∇u-∇wQhu,∇u-∇wQhuT+hT-1Q0u-Qbu0,∂T2≤Ch2kuk+12.By using the triangle inequality, we get from (19) that(30)uh-u≤uh-Qhu+Qhu-u≤Chkuk+1.According to the definition of ·0,h and ·, we have(31)u-uh0,h2=u-u002+∑T∈ThhT2hT-1u-uh0-u-uhb0,∂T2≤u-u002+h2u-uh2.It follows from (15) and (20) that(32)u-u00≤u-Q0u0+Q0u-u00≤Chk+1uk+1.Combining the above three inequalities, we obtain the aimed result (24).


## 3. Cascadic Multigrid Algorithm

In this section, the error estimate and computational complexity of the cascadic multigrid method are analyzed.Assume thatThl(l≥0) is a triangular partition of Ω with the mesh size hl, Ehl is the set of all edges in Thl, and Vhl is the corresponding weak discrete space on mesh Thl. Noting that Tl+1 is obtained by connecting the midpoints of three edges of all triangles in Tl, we have hl=2-lh0, where h0 is the mesh size of T0. For simplicity, define Tl≔Thl, El≔Ehl, Vl≔Vhl0, ·0,hl≔·0,l, and ·hl≔·l. The weak Galerkin finite element approximation of problem (11) on level l can be rewritten as to find ul={u0,ub}∈Vl such that(33)alul,vl≔ahlul,vl=f,v0,∀vl=v0,vb∈Vl.Define an intergrid transfer operatorIl:Vl-1→Vl, for any v∈Vl-1(1)
Ifx∈Kl0 and the element Kl∈Tl is obtained by refining Kl-1∈Tl-1, then(34)Ilv0x=v0x.(2)
Ifx∈el and edge el∈El locates in the interior of Kl-1∈Tl-1, then(35)Ilvbx=v0x.(3)
Ifx∈el and edge el∈El is part of edge el-1∈El-1, then(36)Ilvbx=vbx.Then the cascadic multigrid method can be written as follows.Step 1.
Setu00=u0∗=u0.Step 2.
Forl=1,…,L, set ul0=Ilul-1∗, and do iterations(37)ulml=Clmlul0.Step 3.
Setul∗=ulml.The notationCl in Step 2 denotes the iterative operator on level l. For the operator Cl, we assume that there exists a linear operator Rl:Vl→Vl such that(38)ul-Clmlul0=Rlmlul-ul0,Rlmlvl≤Chl-1mlγv0,l,∀v∈Vl,Rlmlvl≤vl,∀v∈Vl,where ml represents the number of iteration steps on level l and the parameter 0≤γ≤1. As a matter of fact, the assumptions above hold for the Richardson, Jacobi, and Gauss-Seidel iterations with γ=1/2 and for conjugate gradient iteration with γ=1. We refer to [9, 13] for details on these results.The following two lemmas can be proved based on the definition ofIl.Lemma 5.
I
l is the intergrid transfer operator. For any v={v0,vb}∈Vl-1, we have(39)Ilv0,l≤v0,l-1,(40)Ilvl≤Cvl-1.Proof.
For any elementKl-1∈Tl-1, let El0 be the collection of edges el located in Kl-1. It follows from the definition of Il that(41)Ilv0-Ilvb0,el=0,∀el∈El0.Thus, we have(42)Ilv0,l2=∑Kl∈TlIlv00,Kl2+∑el∈∂KlhlIlv0-Ilvb0,el2=∑Kl-1∈Tl-1Ilv00,Kl-12+∑el-1∈∂Kl-1hlIlv0-Ilvb0,el-12≤∑Kl-1∈Tl-1Ilv00,Kl-12+∑Kl-1∈Tl-1hl-1Ilv0-Ilvb0,∂Kl-12=v0,l-12.For any K∈Tl-1, from the definition of weak gradient (5), we have(43)∇v0,qK=∇wv,qK+v0-vb,q·n∂K,∀q∈Hdiv,Ω.If φ is a polynomial in K, from trace inequality (26) and the standard inverse inequality, we have(44)φe2≤ChK-1φ0,K2.Setting q=∇v0, with (44), we have(45)∇v0K2=∇wv,∇v0K+v0-vb,∇v0·n∂K≤∇wv0,K∇v00,K+hK-1/2v0-vb0,∂KhK1/2∇v0·n0,∂K≤CvK∇v00,K.This implies(46)∇v00,K≤CvK.
Note thatK consisted of some elements in Tl; that is, there exist Ki∈Tl, i=1,…,m, such that K=∪i=1mKi.
Application of (44) yields(47)∇wIlv·n0,∂Ki≤ChKi-1/2∇wIlv0,Ki,∀v∈Vl-1.By the definition of ∇wv, (46) and (47), we have(48)∇wIlv0,Ki2=∇wIlv,∇wIlvKi=∇Ilv0,∇wIlvKi-Ilv0-Ilvb,∇wIlv·n∂Ki≤∇v00,Ki∇wIlv0,Ki+Ilv0-Ilvb0,∂Ki∇wIlv·n0,∂Ki≤∇v00,K∇wIlv0,Ki+v0-vb0,∂K∇wIlv·n0,∂Ki≤vK∇wIlv0,Ki+hK1/2vKhKi-1/2∇wIlv0,Ki≤CvK∇wIlv0,Ki.Since(49)hKi-1Ilv0-Ilvb0,∂Ki2≤hKi-1v0-vb0,∂K2≤ChK-1v0-vb0,∂K2≤CvK,we obtain(50)Ilvl2=∑T∈TlA∇wIlv,∇wIlvT+hT-1Ilv0-Ilvb,Ilv0-Ilvb∂T≤C∑T∈Tl∇wIlv0,T2+hT-1Ilv0-Ilvb0,∂T2≤Cvl-12,which completes the proof of this lemma.Lemma 6.
Assume thatul and ul-1 are the weak Galerkin finite element solutions associated with Vl and Vl-1, respectively; then(51)ul-Ilul-10,l≤Chl2f0.Proof.
LetulF and ul-1F be the finite element solutions associated with Tl and Tl-1, respectively. By the triangle inequality, (39), (24), and the regularity (3), we have(52)ul-Ilul-10,l≤ul-u0,l+u-ul-1F0,l+Ilul-1F-Ilul-10,l≤ul-u0,l+u-ul-1F0+ul-1F-ul-10,l-1≤Chl2u2≤Chl2f0.which completes the proof of this lemma.LetVl-1F be the standard finite element space associated with Tl-1. Define the projection operator Pl-1:Vl-1→Vl-1F by(53)alPl-1u,v=alIlu,v,∀v∈Vl-1F.It is easy to check that(54)alPl-1u,v=al-1Pl-1u,v,v∈Vl-1F,(55)alIlu,v=al-1u,v,v∈Vl-1F,(56)Pl-1vl≤vl-1,∀v∈Vl-1.The following lemma is needed in the convergence analysis.Lemma 7.
For the projection operatorPl, we have(57)Ilv-Pl-1v0,l≤Chlvl-1,∀v∈Vl-1.Proof.
SinceΩ is a convex polygonal domain, for a given v∈Vl-1, we introduce an auxiliary problem, that is, to find ξ∈H2(Ω) such that(58)-∇·A∇ξ=Ilv-Pl-1v0inΩ,(59)ξ=0on∂Ω.The solution ξ satisfies the following inequality:(60)ξ2≤Ilv-Pl-1v00.
Letη={η0,ηb}=Ilv-Pl-1v. By the definition of Pl, we have(61)alIlv-Pl-1v,w=alη,w=∑T∈Tl∇wη,∇wT,∀w∈Vl-1F.
Then (58), the definition of weak gradient, and (14) give (62)η002=-∑T∈Tl∇·A∇ξ,η0T=∑T∈TlAQl∇ξ,∇η0-A∇ξ·n,η0∂T=∑T∈Tl-∇·AQl∇ξ,η0+AQl∇ξ·n,η0∂T-A∇ξ·n,η0∂T=∑T∈TlA∇wQlξ,∇wη+AQl∇ξ·n-A∇ξ·n,η0-ηb∂T-A∇ξ·n,ηb∂T.
Since(63)∑T∈TlA∇ξ·n,ηb∂T=0,we get from (18) that(64)η002≤alQlξ,η+Chlξ2ηl. For any ξl-1F∈Vl-1F, we have(65)alIlv-Pl-1v,ξl-1F=0, which implies(66)∑T∈TlA∇wη,∇ξl-1F=∑T∈TlA∇wIlv-Pl-1v,∇ξl-1F=0. Thus, combining (16) and (18), we have(67)alQlξ,Ilv-Pl-1v=alQlξ-ξl-1F,Ilv-Pl-1v≤∑T∈TlA∇wQlξ-ξ,∇wηT+A∇ξ-ξl-1F,∇wηT+hT-1Q0ξ-Qbξ,η0-ηb∂T≤Chlξ2ηl.
By using the regularity (60), we obtain(68)η00=Ilv-Pl-1v00≤ChlIlv-Pl-1vl.Then it follows from (40) and (56) that(69)η00≤Chlvl-1.
It is easy to show that(70)∑T∈TlhTη0-ηb,η0-ηb∂T≤hl2∑T∈TlhT-1Ilv0-Ilvb,Ilv0-Ilvb∂T≤Chl2∑T∈Tl-1hT-1v0-vb,v0-vb∂T≤Chl2vl-12.
Combining (68) and (70), we obtain (71)Ilv-Pl-1v0,l2=η002+∑T∈TlhTη0-ηb,η0-ηb∂T≤Chl2vl-12,which completes the proof of this lemma.The following two theorems are the main results of this paper, which can be proved in a similar way of [13] based on the above lemmas.Theorem 8.
If we take the CG iteration as the smoother, and the number of iterations on the levell is the minimum integer satisfying(72)ml≥βL-1mLwith some fixed β>1 and mL, then the cascadic multigrid method is optimal: that is, the error(73)uL-uL∗L≈u-uLL and the computational complexity(74)amountofwork=OnL, where nl denotes the dimension of the space VL on level l.Theorem 9.
If we take the Richardson, Jacobi, and Gauss-Seidel iterations as the smoother, the number of iterations on the levell is the minimum integer satisfying(75)ml≥βL-1mL,while the number of iterations on the level l is the minimum integer satisfying(76)mL≥m∗L2, with some fixed m∗≥1, then the cascadic multigrid method is quasi-optimal: that is, the error(77)uL-uL∗L≤ChLm∗1/2f and the computational complexity(78)∑k=1Lmknk≤Cm∗nL1+log⁡nL3.


## 4. Numerical Examples

In this section, we give some numerical experiments of the cascadic multigrid algorithm based on the weak Galerkin finite element method to verify the theoretical results proved in Section3.For simplicity, we choosek=1; that is, the weak Galerkin finite element space is (79)Vl=v=v0,vb,v0∈P1T,vb∈P1∂T,vb=0on∂Ω,∀T∈Tl, and the weak gradient space is (80)Gl=q∈P0T2,∀T∈Tl.For the model problem (1) in the domain Ω=(0,1)2, we give the following numerical examples.Case 1.
Let the exact solutionu=sin(πx)sin(πy) and set A(x,y)=ex+y. The numerical results are reported in Table 1.Table 1
Results of Case1: mL=30, β=3.
h
n
L
L
u
L
∗
-
u
L
Time (seconds)
1
64
49408
1
5.5032
e
-
02
13.30
2
5.5067
e
-
02
0.92
3
5.5067
e
-
02
0.73
1
128
197120
1
2.7503
e
-
02
109.7200
2
2.7530
e
-
02
5.41
3
2.7530
e
-
02
4.56
4
2.7530
e
-
02
3.73
1
256
787456
1
1.3750
e
-
02
942.54
2
1.3765
e
-
02
30.45
3
1.3766
e
-
02
18.30
4
1.3766
e
-
02
17.10
5
1.3766
e
-
02
17.04
1
512
3147776
1
6.8749
e
-
03
7816.06
2
6.8826
e
-
03
180.41
3
6.8830
e
-
03
84.72
4
6.8830
e
-
03
72.63
5
6.8830
e
-
03
71.39
6
6.8830
e
-
03
70.92Case 2.
Let the exact solutionu=x(1-x)y(1-y) and set A(x,y)=1. The numerical results are reported in Table 2.Table 2
Results of Case2: mL=30, β=3.
h
n
L
L
|
|
|
u
L
∗
-
u
|
|
|
L
Time (seconds)
1
64
49408
1
3.6360
e
-
03
4.49
2
3.6355
e
-
03
0.75
3
3.6355
e
-
03
0.72
1
128
197120
1
1.8181
e
-
03
36.11
2
1.8181
e
-
03
4.10
3
1.8181
e
-
03
3.78
4
1.8181
e
-
03
3.76
1
256
787456
1
9.0907
e
-
04
246.85
2
9.0906
e
-
04
21.19
3
9.0906
e
-
04
17.41
4
9.0906
e
-
04
16.90
5
9.0906
e
-
04
16.87
1
512
3147776
1
4.5454
e
-
04
2125.11
2
4.5453
e
-
04
106.25
3
4.5457
e
-
04
75.06
4
4.5457
e
-
04
71.62
5
4.5457
e
-
04
70.23
6
4.5457
e
-
04
70.14Case 3.
Let the exact solutionu=x(1-x)y(1-y) and set (81)Ax,y=x2+1001. The numerical results are reported in Table 3.Table 3
Results of Case3: mL=30, β=3.
h
n
L
L
|
|
|
u
L
∗
-
u
|
|
|
L
Time (seconds)
1
64
49408
1
3.6360
e
-
03
4.43
2
3.6355
e
-
03
0.94
3
3.6355
e
-
03
0.72
1
128
197120
1
1.8181
e
-
03
36.08
2
1.8181
e
-
03
4.10
3
1.8181
e
-
03
3.68
4
1.8181
e
-
03
3.59
1
256
787456
1
9.0907
e
-
04
264.49
2
9.0906
e
-
04
21.37
3
9.0906
e
-
04
17.39
4
9.0906
e
-
04
16.91
5
9.0906
e
-
04
16.92
1
512
3147776
1
4.5454
e
-
04
2126.06
2
4.5453
e
-
04
106.97
3
4.5457
e
-
04
74.85
4
4.5457
e
-
04
71.07
5
4.5457
e
-
04
70.65
6
4.5457
e
-
04
70.53The right-hand functionf in the performed numerical examples is chosen to match the given u and A. We take the parameters of the cascadic multigrid method as β=3 and mL=30. The numerical experiments are conducted in the computer of Intel(R) Core(TM) i5-2500 CPU 3.30 GH, 12.0 GB, Windows 7 (x64). The time each experiment takes is also listed in the tables.The numerical results obtained by using the conjugate gradient iteration to solve these examples directly are also provided at the rows withL=1. We can observe that the proposed cascadic multigrid method is optimal for both convergence rate and computation complexity, which confirms our theoretical results.


## 5. Conclusion

This paper gives error and complexity estimates of the cascadic multigrid algorithm of the weak Galerkin finite element. The numerical solution is convergent with rateO(h) and the computing time is proportional to the number of unknowns, which verify the theoretical results.



---

*Source: 7912845-2017-10-18.xml*