# A Two-Level Additive Schwarz Preconditioning Algorithm for the Weak Galerkin Method for the Second-Order Elliptic Equation

Authors: Fangfang Qin; Min Zha; Feng Wang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

This paper proposes a two-level additive Schwarz preconditioning algorithm for the weak Galerkin approximation of the second-order elliptic equation. In the algorithm, aP1 conforming finite element space is defined on the coarse mesh, and a stable intergrid transfer operator is proposed to exchange the information between the spaces on the coarse mesh and the fine mesh. With the framework of the Schwarz method, it is proved that the condition number of the preconditioned system only depends on the rate of the coarse mesh size and the overlapping size. Some numerical experiments are carried out to verify the theoretical results.


---

## Body

## 1. Introduction

The weak Galerkin (WG) finite element method (FEM) is a new efficient numerical method for solving partial differential equations. It was first introduced for the second-order elliptic problem in [1]. The central idea of the WG method is using weak derivatives in place of strong derivatives that define the weak formulation for the underlying partial differential equations. Due to the weak derivative, the degrees of freedom can be discontinuous from the element interior to the element boundary, which makes the weak Galerkin method have more choices of the finite elements than the standard FEMs. The WG FEM also has some other properties, such as high-order accuracy and multiphysics capability. The idea of the weak derivative has been generalized to some other problems, such as the biharmonic equation [2] and the two-phase subsurface flow problems [3]. Chen et al. introduced a posteriori error estimates for the WG method for the second-order elliptic problems in [4].Although many works focus on developing WG methods for different problems, there are few works on efficiently solving the discretized systems, of which the condition number isO(h-2), where h denotes the mesh size. Recently, Li and Xie [5] proposed a multigrid algorithm for the WG method using P1 conforming element on the coarser meshes. In [6], Chen et al. also constructed a fast auxiliary space multigrid preconditioner for the WG method, as well as a corresponding reduced system involving only the degrees of freedom on edges/faces. It is proved that the condition number of the preconditioned system is independent of the mesh size.Due to its high parallelizability and scalability, the domain decomposition method is one of the most efficient algorithms for the numerical solutions of partial differential equations (see, e.g., [7]). In this paper, we study an overlapping domain decomposition algorithm and propose a two-level additive Schwarz preconditioner for the WG method for the second-order elliptic equation. The preconditioner is consisted of overlapping local subproblems on a fine mesh and a global subproblem on a coarse mesh. The coarse subproblem is defined by the P1 conforming element method, and an intergrid transfer operator, which has stability and approximability, is introduced to transmit information between the coarse mesh and the fine mesh. Under the Schwarz framework, we prove that the condition number of the preconditioned system is independent of the fine mesh size h and is of O((1+H/δ)2), where H denotes the coarse mesh size and δ stands for the overlapping size.The rest of this paper is organized as follows. In Section2, we recall the WG method and give some notations. In Section 3, we propose an intergrid transfer operator and a two-level additive Schwarz preconditioner. Moreover, we prove the stability and approximation of the intergrid transfer operator. Then we estimate the upper bound of the maximum eigenvalue and the lower bound of minimum eigenvalue, respectively. Section 4 is devoted to numerical experiments, which are carried out to confirm our theoretical results.


## 2. The Weak Galerkin Method for the Second-Order Elliptic Equation

For the sake of simplicity, we consider the model problem as follows:(1)-∇·A∇u=f,inΩ,u=0,on∂Ω,where Ω⊂R2 is bounded polygonal domain and f∈L2(Ω). Assume that the matrix A is symmetric positive definite (SPD); namely, there exist positive constants α, β such that(2)αξTξ≤ξTAxξ≤βξTξ,∀ξ∈R2,x∈Ω.The variational formulations of (1) is to find u∈H01(Ω) such that(3)au,v=f,v∀v∈H01Ω,where a(u,v)=(A∇u,∇v). It follows from Lax-Milgram’s theorem that problem (3) has a unique solution.LetTh be a quasiuniform triangulation of the domain Ω with the mesh size h. On each T∈Th, the space W(T) denotes the collections of weak functions, each of which is consisted of an interior part and a boundary part; that is, (4)WT≔v=v0,vb:v0∈L2T,vb∈H1/2∂T.For any weak function v∈W(T), the weak gradient of v, denoted by ∇wv∈H(div,T), satisfies (5)∫T∇wv·qdx=-∫Tv0∇·qdx+∫∂Tvbq·nds∀q∈Hdiv,T,where n is the unit outer normal of ∂T. It is easy to see that ∇w is the classical gradient if it actions on a function u∈H1(T).For each elementT∈Th, we denote by T0 and ∂T the interior and the boundary of T. The notation FT stands for the set of edges of T. We also use Fh and Fh∂ to denote the edges of Th in Ω and on ∂Ω. Then the discrete WG space is defined as (6)Wh≔v:vT0∈PjT0∀T∈Th,vF∈PlF∀F∈Fh,vF=0∀F∈Fh∂,where l=j or l=j+1 and Pj(T0) denotes the set of polynomials on T0 with degree no more than j≥0. To define a discrete weak gradient, we use Gj(T) to denote the RT element space [Pj(T)]2+Pj^(T)x if l=j and the BDM element space [Pj+1(T)]2 if l=j+1, where Pj^(T) is the homogeneous polynomial with the degree j.For eachv∈Wh, the discrete weak gradient ∇wv∈Gj(T) is defined as(7)∫T∇wv·qdx=-∫Tv0∇·qdx+∫∂Tvbq·nds∀q∈GjT,where v0 and vb denote the values of v in the interior and on the boundary of T. Then the discrete problem for (3) is to seek uh={u0,ub}∈Wh such that(8)ahuh,vh=f,v0,∀vh=v0,vb∈Wh,where ah(uh,vh)≔(A∇wuh,∇wvh).For anyvh={v0,vb} and uh={u0,ub} in Wh, we use ((uh,vh)) to indicate a special inner product defined as (9)vh,uh≔∑T∈Thv0,u0T+hv0-vb,u0-ub∂T,where (·,·)T and (·,·)∂T denote the L2 inner product on T and ∂T. Accordingly, a norm and seminorm are introduced for any vh={v0,vb}∈Wh by (10)vh0,h≔∑T∈Thvh0,h,T21/2,vh1,h≔∑T∈Thvh1,h,T21/2,where vh0,h,T≔v00,T2+hv0-vb∂T21/2 and vh1,h,T≔(v01,T2+h-1v0-vb∂T2)1/2.LetAh:Wh→Wh be an operator (11)Ahuh,vh=A∇wuh,∇wvh,∀uh,vh∈Wh.It can be proved that Ah is symmetric and positive definite and the condition number is of O(h-2) (see, e.g., [8]), which brings difficulty to solve the discrete problem when the mesh size is small. In the next section, we will present a preconditioner to overcome this difficulty.


## 3. The Overlapping Domain Decomposition Method

### 3.1. A Two-Level Additive Schwarz Preconditioner

To introduce our preconditioner, we first divide the domainΩ by J overlapping subdomains Ω1,Ω2,…,ΩJ such that each point in Ω belongs to no more than NC subdomains. We assume that the boundary of each subdomain does not cut through any elements in the triangulation Th, and there exist nonnegative C∞ functions θ1,θ2,…,θJ satisfying the following properties: (1) θj=0 in Ω∖Ωj; (2) ∑j=1Jθj=1; (3) there exists a positive constant δ, such that ∇θj≤C/δ, where C is a constant independent of δ, h, and J.On each subdomainΩj, the notation Th,j stands for the triangulation inherited from Th. The corresponding weak Galerkin subspace on Th,j is defined as (12)Vj=v∈Wh:vΩ∖Ωj=0.We introduce an operator Aj:Vj→Vj by(13)Ajuj,vj=A∇wuj,∇wvj,∀uj,vj∈Vj.It is easy to see that Aj is symmetric and positive definite. Since Vj is a subset of Wh, we use Ij to denote a natural injection from Vj to Wh.To define a coarse subproblem, we define a coarse triangulationTH with mesh size H such that each element in Th is a subdivision of the one in TH. The notation VH⊂H01(Ω) stands for P1 conforming finite element space associated with TH. We also introduce an operator AH:VH→VH satisfying(14)AHuH,vH=A∇uH,∇vH,∀uH,vH∈VH.Note that the coarse space VH is a subspace of Wh if the degree of the piecewise polynomials in Wh is greater than 0, and we can choose a natural injection as the intergird transfer operator IH from VH to Wh. For the piecewise constant space case, the intergrid transfer operator IH:VH→Wh is defined as (15)IHvH=IH0vH,IHbvH,∀vH∈VH,where IH0 and IHb satisfy(16)IH0vHT=1T∫TvHdx,IHbvHF=1F∫FvHds,for any T∈Th and F∈Fh. We also need the transpose of the intergrid transfer operators Ijt from Wh to the subspace Vj for j=H,1,2,…,J, defined as(17)Ijtuh,vj=uh,Ijvj,∀uh∈Wh,vj∈Vj.Then our two-level additive Schwarz preconditionerBh is stated as(18)Bh=IHAH-1IHt+∑j=1JIjAj-1Ijt.


### 3.2. Analysis

Our analysis is based on the standard Schwarz framework (see, e.g., [7, 9]).Lemma 1 ([9, Theorem 7.1.20]).
The eigenvalues ofBhAh are positive, and one has the following characterizations of the maximum and minimum eigenvalues:(19)λmaxBhAh=maxv∈Wh,v≠0⁡Ahv,vminv=∑j,vj∈VjIjvj⁡∑jAjvj,vj,λminBhAh=minv∈Wh,v≠0⁡Ahv,vminv=∑j,vj∈VjIjvj⁡∑jAjvj,vj,where the sum is taken over j=H,1,…,J.Lemma 2.
For the intergrid transfer operatorIH, it holds for any vH∈VH that(20)vH-IHvH0,h2+h2IHvH1,h2≲h2vH12.Proof.
We only need consider the case that the functions inWh are the constants in the interior and on the boundary of each element.
It follows from the triangle inequality, the trace inequality, and the Poincaré-Friedrichs inequality that(21)IHvH1,h2=∑T∈Thh-1IH0vH-IHbvH0,∂T2≲∑T∈Thh-1IH0vH-vH0,∂T2+IHbvH-vH0,∂T2=vH12.Similarly, for the lower-order term, we have (22)vH-IHvH0,h2=∑T∈ThvH-IH0vH0,T2+hIH0vH-IHbvH0,∂T2≲h2vH12,which completes the proof.Lemma 3.
There exists an operatorQH from Wh to VH such that for any vh in Wh it holds that (23)vh-QHvh0,h2+H2QHvh12≲H2vh1,h2.Proof.
LetVh be the P1 conforming finite element space defined on Th. Then, for any vh in Wh, we can construct a v~h∈Vh satisfying ([6, Lemma 3.5])(24)vh-v~h0,h+hv~h1,h≲hvh1,h.Define QHvh=QHv~h, where QH is the L2 projection operator from Vh to VH. Using the standard properties of QH (see, e.g., [7]) and the inequality (24), we have (25)QHvh12=QHv~h12≲v~h12≲vh1,h2,vh-QHvh0,h2=vh-QHv~h0,h2≲vh-v~h0,h2+QHv~h-v~h0,h2≲h2vh1,h2+H2v~h12≲H2vh1,h2.The proof is completed.Lemma 4.
Given anyvh∈Wh, there exists a decomposition (26)vh=IHvH+∑j=1JIjvj,where vH∈VH and vj∈Vj, such that(27)AHvH,vH+∑j=1JAjvj,vj≲1+Hδ2Ahvh,vh.Proof.
LetvH=QHv, w=vh-IHvH, and vj=Qh(θjw)={Qh0(θjw0),Qhb(θjwb)}, where Qh0 and Qhb are the piecewise L2 projection to the interior polynomial space Pj(T0) and the edge polynomial space Pl(F), respectively. It is easy to check that (28)IHvH+∑j=1Jvj=IHvH+∑j=1JQhθjw=IHvH+Qh∑j=1Jθjw=IHvH+Qhw=vh.
It follows from Lemma3 that (29)AHvH,vH≲vH12≲vh1,h2≲Ahvh,vh.On the other hand, we have for vj that (30)Ajvj,vj≲∑T∈Th,jvj1,h,T2=∑T∈Th,jQh0θjw01,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2.By the inverse inequality, the stability of L2 projection, the Poincaré inequality, and the scaling argument, we deduce that (31)Qh0θjw01,T2=infc∈R⁡Qh0θjw0-c1,T2≲infc∈R⁡h-1Qh0θjw0-c0,T2≤infc∈R⁡h-1θjw0-c0,T2≲θjw01,T2,which, together with the triangle inequality and the assumption of θj, yields(32)Ajvj,vj≲∑T∈Th,jθjw01,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2≲∑T∈Th,j∫T∇θj·w0+∇w0·θj2dx+h-1Qh0θjw0-Qhbθjwb0,∂T2≤∑T∈Th,j2∇θj·w00,T2+2∇w0·θj0,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2≲∑T∈Th,j1δ2w00,T2+w01,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2.For the last term, the triangle inequality gives(33)Qh0θjw0-Qhbθjwb0,∂T2≲Qh0θjw0-θjw00,∂T2+θjw0-Qhbθjw00,∂T2+Qhbθjw0-Qhbθjwb0,∂T2=I+II+III.We estimate I, II, and III, respectively, as follows.
From the trace theorem, the scaling argument, and the stability and approximation ofQh0, we have (34)I=Qh0θjw0-θjw00,∂T2≲h-1Qh0θjw0-θjw00,T2+hQh0θjw0-θjw01,T2≲hθjw01,T2≲hδ2w00,T2+hw01,T2.Denote θjw0¯=(1/T)∫Tθjw0dx. The trace theorem, the L2 stability of Qhb, and the Poincaré inequality imply that (35)II=θjw0-Qhbθjw00,∂T2≤θjw0-θjw0¯0,∂T2+Qhbθjw0-θjw0¯0,∂T2≲θjw0-θjw0¯0,∂T2≲hθjw01,T2≲hδ2w00,T2+hw01,T2.Simiarily, we obtain (36)III=Qhbθjw0-Qhbθjwb0,∂T2≲θjw0-θjwb0,∂T2≤w0-wb0,∂T2.
Combining the above five inequalities, we find(37)Ajvj,vj≲∑T∈Th,j1δ2w00,T2+w01,T2+h-1w0-wb0,∂T2,which leads to(38)∑j=1JAjvj,vj≲∑j=1J∑T∈Th,j1δ2w00,T2+w01,T2+h-1w0-wb0,∂T2≲1δ2vh-IHvH0,h2+vh-IHvH1,h2≤1δ2vh-vH0,h2+1δ2vH-IHvH0,h2+vh-IHvH1,h2≲1+H2δ2vh1,h2≲1+Hδ2Ahvh,vh.Using (27) and (38), we achieve (39)AHvH,vH+∑j=1JAjvj,vj≲1+Hδ2Ahvh,vh.This ends the proof.Lemma 5.
LetvH∈VH and vj∈Vj, 1≤j≤J. For any vh=IHvH+∑j=1Jvj, it is true that (40)Ahvh,vh≲AHvH,vH+∑j=1JAjvj,vj.Proof.
The inequality can be obtained directly by using the triangle inequality and the assumption on the finite cover of subdomains.As an immediate consequence, we have the following theorem.Theorem 6.
There exists a positive constantC, independent of H, h, δ, and J, such that(41)κBhAh=λmaxBhAhλminBhAh≤C1+Hδ2.Remark 7.
According the theorem, the two-level additive preconditioner is optimal ifH/δ is bounded above by a constant. In particular, when δ=O(H), we have(42)κBhAh⩽C.


## 3.1. A Two-Level Additive Schwarz Preconditioner

To introduce our preconditioner, we first divide the domainΩ by J overlapping subdomains Ω1,Ω2,…,ΩJ such that each point in Ω belongs to no more than NC subdomains. We assume that the boundary of each subdomain does not cut through any elements in the triangulation Th, and there exist nonnegative C∞ functions θ1,θ2,…,θJ satisfying the following properties: (1) θj=0 in Ω∖Ωj; (2) ∑j=1Jθj=1; (3) there exists a positive constant δ, such that ∇θj≤C/δ, where C is a constant independent of δ, h, and J.On each subdomainΩj, the notation Th,j stands for the triangulation inherited from Th. The corresponding weak Galerkin subspace on Th,j is defined as (12)Vj=v∈Wh:vΩ∖Ωj=0.We introduce an operator Aj:Vj→Vj by(13)Ajuj,vj=A∇wuj,∇wvj,∀uj,vj∈Vj.It is easy to see that Aj is symmetric and positive definite. Since Vj is a subset of Wh, we use Ij to denote a natural injection from Vj to Wh.To define a coarse subproblem, we define a coarse triangulationTH with mesh size H such that each element in Th is a subdivision of the one in TH. The notation VH⊂H01(Ω) stands for P1 conforming finite element space associated with TH. We also introduce an operator AH:VH→VH satisfying(14)AHuH,vH=A∇uH,∇vH,∀uH,vH∈VH.Note that the coarse space VH is a subspace of Wh if the degree of the piecewise polynomials in Wh is greater than 0, and we can choose a natural injection as the intergird transfer operator IH from VH to Wh. For the piecewise constant space case, the intergrid transfer operator IH:VH→Wh is defined as (15)IHvH=IH0vH,IHbvH,∀vH∈VH,where IH0 and IHb satisfy(16)IH0vHT=1T∫TvHdx,IHbvHF=1F∫FvHds,for any T∈Th and F∈Fh. We also need the transpose of the intergrid transfer operators Ijt from Wh to the subspace Vj for j=H,1,2,…,J, defined as(17)Ijtuh,vj=uh,Ijvj,∀uh∈Wh,vj∈Vj.Then our two-level additive Schwarz preconditionerBh is stated as(18)Bh=IHAH-1IHt+∑j=1JIjAj-1Ijt.


## 3.2. Analysis

Our analysis is based on the standard Schwarz framework (see, e.g., [7, 9]).Lemma 1 ([9, Theorem 7.1.20]).
The eigenvalues ofBhAh are positive, and one has the following characterizations of the maximum and minimum eigenvalues:(19)λmaxBhAh=maxv∈Wh,v≠0⁡Ahv,vminv=∑j,vj∈VjIjvj⁡∑jAjvj,vj,λminBhAh=minv∈Wh,v≠0⁡Ahv,vminv=∑j,vj∈VjIjvj⁡∑jAjvj,vj,where the sum is taken over j=H,1,…,J.Lemma 2.
For the intergrid transfer operatorIH, it holds for any vH∈VH that(20)vH-IHvH0,h2+h2IHvH1,h2≲h2vH12.Proof.
We only need consider the case that the functions inWh are the constants in the interior and on the boundary of each element.
It follows from the triangle inequality, the trace inequality, and the Poincaré-Friedrichs inequality that(21)IHvH1,h2=∑T∈Thh-1IH0vH-IHbvH0,∂T2≲∑T∈Thh-1IH0vH-vH0,∂T2+IHbvH-vH0,∂T2=vH12.Similarly, for the lower-order term, we have (22)vH-IHvH0,h2=∑T∈ThvH-IH0vH0,T2+hIH0vH-IHbvH0,∂T2≲h2vH12,which completes the proof.Lemma 3.
There exists an operatorQH from Wh to VH such that for any vh in Wh it holds that (23)vh-QHvh0,h2+H2QHvh12≲H2vh1,h2.Proof.
LetVh be the P1 conforming finite element space defined on Th. Then, for any vh in Wh, we can construct a v~h∈Vh satisfying ([6, Lemma 3.5])(24)vh-v~h0,h+hv~h1,h≲hvh1,h.Define QHvh=QHv~h, where QH is the L2 projection operator from Vh to VH. Using the standard properties of QH (see, e.g., [7]) and the inequality (24), we have (25)QHvh12=QHv~h12≲v~h12≲vh1,h2,vh-QHvh0,h2=vh-QHv~h0,h2≲vh-v~h0,h2+QHv~h-v~h0,h2≲h2vh1,h2+H2v~h12≲H2vh1,h2.The proof is completed.Lemma 4.
Given anyvh∈Wh, there exists a decomposition (26)vh=IHvH+∑j=1JIjvj,where vH∈VH and vj∈Vj, such that(27)AHvH,vH+∑j=1JAjvj,vj≲1+Hδ2Ahvh,vh.Proof.
LetvH=QHv, w=vh-IHvH, and vj=Qh(θjw)={Qh0(θjw0),Qhb(θjwb)}, where Qh0 and Qhb are the piecewise L2 projection to the interior polynomial space Pj(T0) and the edge polynomial space Pl(F), respectively. It is easy to check that (28)IHvH+∑j=1Jvj=IHvH+∑j=1JQhθjw=IHvH+Qh∑j=1Jθjw=IHvH+Qhw=vh.
It follows from Lemma3 that (29)AHvH,vH≲vH12≲vh1,h2≲Ahvh,vh.On the other hand, we have for vj that (30)Ajvj,vj≲∑T∈Th,jvj1,h,T2=∑T∈Th,jQh0θjw01,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2.By the inverse inequality, the stability of L2 projection, the Poincaré inequality, and the scaling argument, we deduce that (31)Qh0θjw01,T2=infc∈R⁡Qh0θjw0-c1,T2≲infc∈R⁡h-1Qh0θjw0-c0,T2≤infc∈R⁡h-1θjw0-c0,T2≲θjw01,T2,which, together with the triangle inequality and the assumption of θj, yields(32)Ajvj,vj≲∑T∈Th,jθjw01,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2≲∑T∈Th,j∫T∇θj·w0+∇w0·θj2dx+h-1Qh0θjw0-Qhbθjwb0,∂T2≤∑T∈Th,j2∇θj·w00,T2+2∇w0·θj0,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2≲∑T∈Th,j1δ2w00,T2+w01,T2+h-1Qh0θjw0-Qhbθjwb0,∂T2.For the last term, the triangle inequality gives(33)Qh0θjw0-Qhbθjwb0,∂T2≲Qh0θjw0-θjw00,∂T2+θjw0-Qhbθjw00,∂T2+Qhbθjw0-Qhbθjwb0,∂T2=I+II+III.We estimate I, II, and III, respectively, as follows.
From the trace theorem, the scaling argument, and the stability and approximation ofQh0, we have (34)I=Qh0θjw0-θjw00,∂T2≲h-1Qh0θjw0-θjw00,T2+hQh0θjw0-θjw01,T2≲hθjw01,T2≲hδ2w00,T2+hw01,T2.Denote θjw0¯=(1/T)∫Tθjw0dx. The trace theorem, the L2 stability of Qhb, and the Poincaré inequality imply that (35)II=θjw0-Qhbθjw00,∂T2≤θjw0-θjw0¯0,∂T2+Qhbθjw0-θjw0¯0,∂T2≲θjw0-θjw0¯0,∂T2≲hθjw01,T2≲hδ2w00,T2+hw01,T2.Simiarily, we obtain (36)III=Qhbθjw0-Qhbθjwb0,∂T2≲θjw0-θjwb0,∂T2≤w0-wb0,∂T2.
Combining the above five inequalities, we find(37)Ajvj,vj≲∑T∈Th,j1δ2w00,T2+w01,T2+h-1w0-wb0,∂T2,which leads to(38)∑j=1JAjvj,vj≲∑j=1J∑T∈Th,j1δ2w00,T2+w01,T2+h-1w0-wb0,∂T2≲1δ2vh-IHvH0,h2+vh-IHvH1,h2≤1δ2vh-vH0,h2+1δ2vH-IHvH0,h2+vh-IHvH1,h2≲1+H2δ2vh1,h2≲1+Hδ2Ahvh,vh.Using (27) and (38), we achieve (39)AHvH,vH+∑j=1JAjvj,vj≲1+Hδ2Ahvh,vh.This ends the proof.Lemma 5.
LetvH∈VH and vj∈Vj, 1≤j≤J. For any vh=IHvH+∑j=1Jvj, it is true that (40)Ahvh,vh≲AHvH,vH+∑j=1JAjvj,vj.Proof.
The inequality can be obtained directly by using the triangle inequality and the assumption on the finite cover of subdomains.As an immediate consequence, we have the following theorem.Theorem 6.
There exists a positive constantC, independent of H, h, δ, and J, such that(41)κBhAh=λmaxBhAhλminBhAh≤C1+Hδ2.Remark 7.
According the theorem, the two-level additive preconditioner is optimal ifH/δ is bounded above by a constant. In particular, when δ=O(H), we have(42)κBhAh⩽C.


## 4. Numerical Experiments

In this section, we give some numerical results to demonstrate the efficiency of our preconditioner. For convenience, we consider a simple two-dimensional Poisson equation with homogeneous boundary as follows:(43)-Δu=finΩ,u=0on∂Ω.We choosef to satisfy the exact solution u(x1,x2)=x1(1-x1)x2(1-x2) on Ω=[0,1]×[0,1]. Let TH be a uniform triangulation with the mesh size H=1/4, and let Th be the refinement of TH. All the tests are stopped when the relative error is less than 10-6.In Table1, we list the iteration numbers of the preconditioning conjugate gradient (PCG) method and the conjugate gradient (CG) method with different meshes. From the second and third rows of the table, we see that the iteration numbers of the PCG method are almost the same if the overlapping factors H/δ are fixed. If the overlap becomes small, that is, the rate H/δ is increasing, one needs a little more steps to achieve the tolerance. This indicates that the condition number of the preconditioned system is almost a constant which is independent of the mesh size h and only depends on the rate of the coarse mesh size and the overlap.Table 1
The iteration numbers of the PCG and CG.
h
1/8
1/16
1/32
1/64
1/128
PCG (H/δ = 1)
10
11
11
11
12
PCG (H/δ = 2)
14
15
15
16
16
CG
60
119
231
436
864Finally, we will do some experiments to show the efficiency of our algorithm for problems with checkboard distributed coefficient, which equals1 and 10i (i=1,3,6) on adjacent subdomains. We assume that the coefficient is constant on each coarser element, and the coarser mesh size and the overlap size are fixed (H=1/4,δ=1/8). The iteration numbers, with different mesh sizes h and jumps in the coefficient, are reported in Table 2, from which, we conclude that our preconditioner also works well for problems with discontinuous coefficients at least in two dimensions.Table 2
The iteration numbers with different mesh sizesh and coefficient jumps (10i).
i
h
1/8
1/16
1/32
1/64
1/128
1
14
15
15
16
16
3
15
15
15
15
16
6
15
15
15
15
15



---

*Source: 2685659-2016-03-24.xml*