# A BDDC Preconditioner for the RotatedQ

Authors: Yaqin Jiang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We propose a BDDC preconditioner for the rotatedQ
1 finite element method for second order elliptic equations with piecewise but discontinuous coefficients. In the framework of the standard additive Schwarz methods, we describe this method by a complete variational form. We show that our method has a quasioptimal convergence behavior; that is, the condition number of the preconditioned problem is independent of the jumps of the coefficients and depends only logarithmically on the ratio between the subdomain size and the mesh size. Numerical experiments are presented to confirm our theoretical analysis.


---

## Body

## 1. Introduction

The balancing domain decomposition by constraints (BDDC) method was first introduced by Dohrmann in [1]. Then Mandel and the author Dohrmann restated the method in an abstract manner and provided its convergence theory in [2]. The BDDC method is closely related to the dual-primal FETI (FETI-DP) method [3], which is one of dual iterative substructuring methods. Each BDDC and FETI-DP method is defined in terms of a set of primal continuity; the primal continuity is enforced across the interface between the subdomains and provides a coarse space component of the preconditioner. In [4], Mandel et al. analyzed the relation between the two methods and established the corresponding theory.In the last decades, the two methods have been widely analyzed and successfully been extended to many different types of partial differential equations. In [3], the two algorithms for elliptic problems were rederived and a brief proof of the main result was given. A BDDC algorithm for mortar finite element was developed in [5]; meanwhile, the authors also extended the FETI-DP algorithm to elasticity problems and stokes problems in [6, 7], respectively. These algorithms were based on locally conforming finite element methods, and the coarse space components of the algorithms were related to the cross-points (i.e., corners), which are often noteworthy points in domain decomposition methods (DDMs). Since the cross-points are related to more than two subregions, thus it is not convenient when designing algorithm.The BDDC method derives from the Neumann-Neumann domain decomposition method (see [8]). The difference is that the BDDC method applies an additive rather than a multiplicative coarse grid correction, and substructure spaces have some constraints which result in nonsingular subproblems, so that we can solve each subproblem and coarse problem in parallel.The rotatedQ
1 element is an important nonconforming element. It was introduced by Rannacher and Turek in [9] for stokes equations originally, and it is the simplest example of a divergence-stable nonconforming element on quadrilaterals. Since its degree of freedom is integral average on element edge which is not related to the corners, and each degree of freedom on subdomain interfaces is only included in two neighboring subdomains, so it is easy to design algorithm.In this paper, we consider the second order problem with discontinuous coefficients, where the discontinuities lie only along the subdomain interfaces. Such problems play an important role in scientific computing. It is well known that large jumps in the coefficients may result in bad convergence for the traditional iterative methods (such asC-G algorithm). To overcome this difficulty, we construct a family of weighted counting functions associated with the substructures. Our counting functions are related to only two neighboring subdomains; this brings convenience for computing. Furthermore, since the rotated Q
1 element is not related to the subdomain’s vertices, we can complete our theoretical analysis conveniently. It is proved that the condition number of the preconditioned operator is independent of the jumps of the coefficients and only depends logarithmically on the ratio between the subdomain size and mesh size. Numerical experiments are presented to confirm our theoretical analysis.The rest of this paper is organized as follows. In Section2, we introduce the model problem and the corresponding Schur complement system. Section 3 gives the BDDC algorithm and proposes the BDDC preconditioner. Several technical tools are presented and analyzed in Section 4. In Section 5, we complete the proof of the main result. Last section provides numerical experiments. For convenience, the symbols ⪯, ≽, and ≍ are used, and x
1
⪯
y
1, x
2
≽
y
2, and x
3
≍
y
3 mean that x
1
≤
C
1
y
1, x
2
≥
C
2
y
2, and c
3
x
3
≤
y
3
≤
C
3
y
3 for some constants C
1, C
2, C
3, and c
3 that are independent of discontinuous coefficients and mesh size.


## 2. Preliminaries

LetΩ
⊂
ℛ
2 be a bounded, simply connect rectangular or L-shaped domain. We divide Ω into several nonoverlapping regular rectangular subdomains Ω
i  (
i
=
1
,
…
,
N
); that is, Ω
-
=
⋃
i
=
1
N
‍
Ω
-
i. Consider the following model problem: find u
∈
H
0
1
(
Ω
) such that
(1)
a
(
u
,
v
)
=
f
(
v
)
,
∀
v
∈
H
0
1
(
Ω
)
,
where
(2)
a
(
u
,
v
)
=
∑
i
=
1
N
‍
∫
Ω
i
‍
ρ
i
(
x
)
∇
u
·
∇
v
d
x
,
f
(
v
)
=
∑
i
=
1
N
‍
∫
Ω
i
‍
f
v
d
x
,
where f
∈
L
2
(
Ω
), and the coefficients ρ
i
(
x
)
(
i
=
1
,
…
,
N
) are positive constants over Ω
i  (
i
=
1
,
…
,
N
).We only consider the geometrically conforming case; that is, the intersection between the closure of two different subdomains is empty, or a vertex, or an edge. The subdomains{
Ω
i
}
i
=
1
N together form a coarse partition 𝒯
H
(
Ω
); we denote the diameter of each Ω
i by H
i. Let 𝒯
h
(
Ω
i
) be a quasiuniform partition with mesh size O
(
h
i
), made up of rectangles in Ω
i; then 𝒯
h
(
Ω
)
=
⋃
i
=
1
N
‍
𝒯
h
(
Ω
i
) is the global quasiuniform partition on Ω. The nodes on the boundaries of neighboring subdomains match across the interface Γ
=
(
⋃
i
=
1
N
‍
∂
Ω
i
)
∖
∂
Ω. We define by Γ
i
j the interface between Ω
i and Ω
j, and let Γ
i
=
∂
Ω
i
∖
∂
Ω. We denote the sets of edges of the partition 𝒯
h
(
Ω
i
) in Ω
i, ∂
Ω
i, Γ, and Γ
i
j by Ω
i
,
h
e, ∂
Ω
i
,
h
e, Γ
h
e, and Γ
i
j
e, respectively, and let Ω
i
,
h, ∂
Ω
i
,
h be the sets of vertices of the triangulation 𝒯
h
(
Ω
i
) that are in Ω
-
i, ∂
Ω
-
i, respectively.The global rotatedQ
1 element space is defined as follows:
(3)
X
h
(
Ω
)
=
{
∫
e
‍
v
∈
L
2
(
Ω
)
|
v
|
E
=
a
E
1
+
a
E
2
x
+
a
E
3
y
+
a
E
4
(
x
2
-
y
2
)
,
a
E
i
∈
ℛ
,
∫
e
‍
v
d
s
=
0
,
∀
e
∈
∂
E
∩
∂
Ω
,
E
∈
𝒯
h
(
Ω
)
;
for
E
1
,
E
2
∈
𝒯
h
(
Ω
)
,
if
∂
E
1
∩
∂
E
2
=
e
,
then
∫
e
‍
v
|
∂
E
1
d
s
=
∫
e
‍
v
|
∂
E
2
d
s
}
.The discrete approximation of the original problem (1) is to find u
h
∈
X
h
(
Ω
) such that
(4)
a
h
(
u
h
,
v
h
)
=
(
f
,
v
h
)
,
∀
v
h
∈
X
h
(
Ω
)
,
where
(5)
a
h
(
u
h
,
v
h
)
=
∑
i
=
1
N
‍
a
h
,
i
(
u
h
,
v
h
)
,
a
h
,
i
(
u
h
,
v
h
)
=
∑
E
∈
𝒯
h
(
Ω
i
)
‍
∫
E
‍
ρ
i
∇
u
h
∇
v
h
d
x
,
(
f
,
v
h
)
=
∫
Ω
‍
f
v
h
d
x
.
For each space X
h
(
Ω
i
) (X
h
(
Ω
i
)
=
X
h
(
Ω
)
|
Ω
i), we equip the following seminorm and norm:
(6)
|
v
|
H
h
1
(
Ω
i
)
2
=
∑
E
∈
𝒯
h
(
Ω
i
)
‍
|
v
|
H
1
(
E
)
2
,
|
v
|
H
ρ
1
(
Ω
i
)
2
=
a
h
,
i
(
v
,
v
)
,
∥
v
∥
L
ρ
2
(
Ω
i
)
2
=
∫
Ω
i
‍
ρ
i
v
2
d
x
.It can be easily shown thata
h
(
·
,
·
) is positive definite on X
h
(
Ω
), which yields the existence and uniqueness of the discrete solution.We define a discrete harmonic operatorℋ
i associated with the rotated Q
1 element: for any v
∈
X
h
(
Ω
i
), let ℋ
i
v
∈
X
h
(
Ω
i
) such that
(7)
a
h
,
i
(
ℋ
i
v
,
w
)
=
0
,
∀
w
∈
X
h
0
(
Ω
i
)
,
1
|
e
|
∫
e
‍
ℋ
i
v
d
s
=
1
|
e
|
∫
e
‍
v
d
s
,
∀
e
∈
∂
Ω
i
,
h
e
,
here X
h
0
(
Ω
i
)
=
{
v
∈
X
h
(
Ω
i
)
|
∫
e
‍
v
d
s
=
0
,
∀
e
∈
∂
Ω
i
,
h
e
}. We define a corresponding piecewise harmonic operator ℋ by ℋ
|
Ω
i
=
ℋ
i on the global rotated Q
1 element space X
h
(
Ω
).In order to introduce our domain decomposition method, we decompose the discrete spaceX
h
(
Ω
) as follows:
(8)
X
h
(
Ω
)
=
X
h
P
(
Ω
)
⊕
X
h
(
Γ
)
,
X
h
P
(
Ω
)
=
⋃
i
=
1
N
‍
X
h
0
(
Ω
i
)
,
where the space X
h
(
Γ
) is a piecewise harmonic function space defined as
(9)
X
h
(
Γ
)
=
ℋ
(
X
h
(
Ω
)
)
=
{
v
∈
X
h
(
Ω
)
∣
v
|
Ω
i
=
ℋ
i
(
v
|
Ω
i
)
,
i
=
1,2
…
,
N
}
.We assumeu to be the solution of (4) and u
i
∈
X
h
0
(
Ω
i
) to be the solution of the local homogeneous Dirichlet problem:
(10)
a
h
,
i
(
u
i
,
v
)
=
(
f
,
v
)
Ω
i
,
∀
v
∈
X
h
0
(
Ω
i
)
,
where (
f
,
v
)
Ω
i
=
∫
Ω
i
‍
f
v
d
x. Let u
P
∈
X
h
P
(
Ω
) be the function that is equal to u
i on the subdomain Ω
i; then u
Γ
=
u
-
u
P obviously satisfies
(11)
a
h
(
u
Γ
,
v
)
=
(
f
,
v
)
-
a
h
(
u
P
,
v
)
,
∀
v
∈
X
h
(
Ω
)
,
and we get u
Γ
∈
X
h
(
Γ
). So we can equivalently derive the Schur complement system of (4) easily: find u
Γ
∈
X
h
(
Γ
) such that
(12)
a
h
(
u
Γ
,
v
Γ
)
=
(
f
,
v
)
-
a
h
(
u
P
,
v
)
=
(
f
,
v
Γ
)
,
∀
v
∈
X
h
(
Ω
)
,
where v
Γ is the piecewise harmonic function of v in Ω; that is, v
Γ
=
ℋ
v.For the sake of completeness, we define a Schur complement operatorS
h
:
X
h
(
Γ
)
→
X
h
(
Γ
) by
(13)
(
S
h
u
Γ
,
v
Γ
)
=
a
h
(
u
Γ
,
v
Γ
)
,
∀
u
Γ
,
v
Γ
∈
X
h
(
Γ
)
.
Our goal is therefore to construct a preconditioner for the operator S
h.


## 3. BDDC Algorithm

In this section, we introduce our BDDC preconditioner and describe the BDDC algorithm. LetX
h
(
Γ
i
)
=
X
h
(
Γ
)
|
Ω
i; we define the space X
~
h
(
Γ
)
=
{
v
∈
∏
i
=
1
N
‍
X
h
(
Γ
i
)
∣
∫
Γ
i
j
‍
v
|
Ω
i
d
s
=
∫
Γ
i
j
‍
v
|
Ω
j
d
s
,
∀
Γ
i
j
⊂
Γ
}. The space X
~
h
(
Γ
) is intermediary between X
h
(
Γ
) and ∏
i
=
1
N
‍
X
h
(
Γ
i
); our BDDC preconditioner is constructed based on this space.As we know, the technical aspect in DDMs is that the preconditioner includes a coarse problem which can enhance the convergence. In view of the characteristic of the spaceX
~
h
(
Γ
), we select the standard coarse space X
H
(
Ω
) which is the rotated Q
1 finite element space associated with the coarse partition 𝒯
H
(
Ω
), and it satisfies primal constraints on subdomain interfaces.The substructure spaceX
Δ
(
Γ
i
) with constraints is defined by
(14)
X
Δ
(
Γ
i
)
=
{
v
∈
X
h
(
Γ
i
)
∣
∫
Γ
i
j
‍
v
d
s
=
0
,
∀
Γ
i
j
⊂
∂
Ω
i
}
.
Denote X
Δ
(
Γ
)
=
∏
i
=
1
N
‍
X
Δ
(
Γ
i
).The coarse space and product spaceX
Δ
(
Γ
) play an important role in the description and analysis of our iterative method. In essence, we give a decomposition of the space X
~
h
(
Γ
) as follows:
(15)
X
~
h
(
Γ
)
=
ℋ
(
X
H
(
Ω
)
)
+
X
Δ
(
Γ
)
.To present our BDDC preconditioner, we introduce several space transfer operators. Define the interpolation operatorI
H
:
X
h
(
Γ
)
→
X
H
(
Ω
) by
(16)
∫
Γ
i
j
‍
I
H
v
d
s
|
Γ
i
j
|
=
∫
Γ
i
j
‍
v
d
s
|
Γ
i
j
|
,
∀
Γ
i
j
⊂
Γ
.
The intergrid transfer operator I
h
:
X
H
(
Ω
)
→
X
~
h
(
Γ
) is defined by
(17)
∫
e
‍
I
h
v
d
s
|
e
|
=
∫
e
‍
v
d
s
|
e
|
,
∀
e
∈
∂
Ω
i
,
h
e
(
i
=
1
,
…
,
N
)
.
We define the extension operator R
i
T
:
X
h
(
Γ
i
)
→
X
h
(
Γ
) as
(18)
∫
e
‍
R
i
T
v
d
s
|
e
|
=
{
∫
e
‍
v
d
s
|
e
|
,
∀
e
∈
∂
Ω
i
,
h
e
,
0
,
∀
e
∈
Γ
∖
∂
Ω
i
,
h
e
.
Its transpose R
i is defined by
(19)
(
R
i
w
,
v
)
=
(
w
,
R
i
T
v
)
,
∀
w
∈
X
h
(
Γ
)
,
v
∈
X
h
(
Γ
i
)
.
Denote R
Δ
i
T
:
X
Δ
(
Γ
i
)
→
X
h
(
Γ
) by R
Δ
i
T
=
R
i
T
|
X
Δ
(
Γ
i
); the corresponding transpose is defined by
(20)
(
R
Δ
i
w
,
v
)
=
(
w
,
R
Δ
i
T
v
)
,
∀
w
∈
X
h
(
Γ
)
,
v
∈
X
Δ
(
Γ
i
)
.To overcome the discontinuous coefficientsρ
i
(
i
=
1
,
…
,
N
), we define a family of weighted counting functions δ
i associated with Γ
i as follows:
(21)
δ
i
|
e
=
∑
j
∈
𝒩
e
ρ
j
ρ
i
,
∀
e
∈
∂
Ω
i
,
h
e
∖
∂
Ω
,
here 𝒩
e is the set of indices j of the subregions such that e
∈
∂
Ω
j
,
h
e. Actually, δ
i are piecewise constants associated with Γ. Let δ
i
+ be the corresponding pseudoinverse; for any u
∈
X
h
(
Γ
), they provide a partition of unity as follows:
(22)
∑
i
‍
R
i
T
δ
i
+
(
u
|
Ω
i
)
≡
u
.
By an elementary argument, we can see
(23)
ρ
i
δ
j
+
2
≤
min
⁡
{
ρ
i
,
ρ
j
}
.
According to the construction of R
i
T, given the scaling factors δ
i
+ at the subdomain interface elements' edges, we can define the two scaled extension operators. R
D
,
i
T
:
X
h
(
Γ
i
)
→
X
h
(
Γ
)
(24)
∫
e
‍
R
D
,
i
T
v
d
s
|
e
|
=
{
δ
+
∫
e
‍
v
d
s
|
e
|
,
∀
e
∈
∂
Ω
i
,
h
e
,
0
,
∀
e
∈
Γ
∖
∂
Ω
i
,
h
e
,where R
D
,
Δ
i
T
:
X
Δ
(
Γ
i
)
→
X
h
(
Γ
), R
D
,
Δ
i
T
=
R
D
,
i
T
|
X
Δ
(
Γ
i
). Following (19) the corresponding transposes are denoted by R
D
,
i and R
D
,
Δ
i, respectively.In what follows, we describe our BDDC preconditioning algorithm, by using the basic framework of additive Schwarz method (or parallel subspace correction method [10]). From the decomposition (15), we only need to define appropriate subspace solvers.First of all, the coarse subspace solverB
H
:
X
H
(
Ω
)
→
X
H
(
Ω
) is defined by
(25)
(
B
H
u
H
,
v
H
)
=
a
h
(
u
H
,
v
H
)
,
∀
u
H
,
v
H
∈
X
H
(
Ω
)
.
On each subdomain, the similar solver B
i
:
X
Δ
(
Γ
i
)
→
X
Δ
(
Γ
i
) is given by
(26)
(
B
i
u
,
v
)
=
a
h
,
i
(
u
,
v
)
,
∀
u
,
v
∈
X
Δ
(
Γ
i
)
.Remark 1.
The bilinear forms on the coarse space can be different from substructure space; here we only use the exact solvers; on each subdomain, we avoid the possible singularity of local subproblem.Now we define the BDDC preconditioner as(27)
B
b
d
d
c
=
R
0
T
B
H
-
1
R
0
+
∑
i
=
1
N
‍
R
D
,
Δ
i
T
B
i
-
1
R
D
,
Δ
i
,
where R
0
T
=
∑
i
=
1
N
‍
R
D
,
i
T
I
h, R
0 is the corresponding transpose defined by
(28)
(
R
0
w
,
v
)
=
(
w
,
R
0
T
v
)
,
∀
w
∈
X
h
(
Γ
)
,
v
∈
X
H
(
Ω
)
.
Let P
0 be the operator from X
h
(
Γ
) to X
H
(
Ω
) defined by
(29)
a
h
(
P
0
u
,
v
)
=
a
h
(
u
,
R
0
T
v
)
,
∀
u
∈
X
h
(
Γ
)
,
v
∈
X
H
(
Ω
)
,
and let P
i be the operator from X
h
(
Γ
) to X
Δ
(
Γ
i
) defined by
(30)
a
h
,
i
(
P
i
u
,
v
)
=
a
h
(
u
,
R
Δ
,
i
T
v
)
,
∀
u
∈
X
h
(
Γ
)
,
v
∈
X
Δ
(
Γ
i
)
.
Then the BDDC preconditioned operator P
b
d
d
c can be written as
(31)
P
b
d
d
c
=
R
0
T
P
0
+
∑
i
=
1
N
‍
R
D
,
Δ
i
T
P
i
,
B
b
d
d
c
S
h
=
P
b
d
d
c
.
The next key theorem gives an estimate on P
b
d
d
c.Theorem 2.
The BDDC preconditioned operatorsP
b
d
d
c satisfies
(32)
a
h
(
u
,
u
)
⪯
a
h
(
P
b
d
d
c
u
,
u
)
⪯
(
1
+
log
⁡
H
h
)
2
a
h
(
u
,
u
)
,
∀
u
∈
X
h
(
Γ
)
,
where H
/
h
=
max
⁡
i
(
H
i
/
h
i
).


## 4. Technical Tools

In this section we state and prove a technical lemma necessary for the proof of Theorem2. Our theoretical analysis is based on substructuring theory of conforming element.We assumeV
h
(
Ω
i
) to be the bilinear conforming element space associated with the partition 𝒯
h
(
Ω
i
). We split the interface ∂
Ω
i into four open edges ℰ and define a zero prolong operator I
ℰ
0 on V
h
(
∂
Ω
i
)
=
V
h
(
Ω
i
)
|
∂
Ω
i as for any v
∈
V
h
(
∂
Ω
i
)
(33)
I
ℰ
0
v
=
{
v
,
on
⁡
ℰ
,
0
,
on
⁡
∂
Ω
i
∖
ℰ
.
For the operator I
ℰ
0, we introduce the following result (cf. [11]).Lemma 3.
For an edgeℰ of ∂
Ω
i, for any v
∈
V
h
(
∂
Ω
i
), one has
(34)
∥
I
ℰ
0
v
∥
H
1
/
2
(
∂
Ω
i
)
⪯
(
log
⁡
H
i
h
i
)
∥
v
∥
H
1
/
2
(
∂
Ω
i
)
.Remark 4.
The above lemma is related to vertex-edge-face arguments in substructuring methods, in view of characteristic for the rotatedQ
1 element; here the results only concern the inequalities for faces.LetV
h
/
2
(
Ω
i
) be the conforming element space of bilinear continuous functions on the triangulation 𝒯
h
/
2
(
Ω
i
) which is constructed by joining the midpoints of the edges of elements of 𝒯
h
(
Ω
i
). We now introduce a local equivalence map ℳ
i
:
X
h
(
Ω
i
)
→
V
h
/
2
(
Ω
i
) as follows (cf. [12]).Definition 5.
Givenv
∈
X
h
(
Ω
i
), we define ℳ
i
v
∈
V
h
/
2
(
Ω
i
) by the values of ℳ
i
v at the vertices of the partition 𝒯
h
/
2
(
Ω
i
).  (i)
IfP is a central point of E, E
∈
𝒯
h
(
Ω
i
), then
(35)
(
ℳ
i
v
)
(
P
)
=
1
4
∑
e
i
∈
∂
E
‍
1
|
e
i
|
∫
e
i
‍
v
d
s
.
(ii)
IfP is a midpoint of one edge e
∈
∂
E, E
∈
𝒯
h
(
Ω
i
), then
(36)
(
ℳ
i
v
)
(
P
)
=
1
|
e
|
∫
e
‍
v
d
s
.
(iii)
IfP
∈
Ω
i
,
h
∖
∂
Ω
i
,
h, then
(37)
(
ℳ
i
v
)
(
P
)
=
1
4
∑
e
i
‍
1
|
e
i
|
∫
e
i
‍
v
d
s
,
where the sum is taken over all edges e
i with the common vertex P, e
i
∈
∂
E
i, E
i
∈
𝒯
h
(
Ω
i
).
(iv)
IfP
∈
∂
Ω
i
,
h, then
(38)
(
ℳ
i
v
)
(
P
)
=
|
e
l
|
|
e
l
|
+
|
e
r
|
(
1
|
e
l
|
∫
e
l
‍
v
d
s
)
+
|
e
r
|
|
e
l
|
+
|
e
r
|
(
1
|
e
r
|
∫
e
r
‍
v
d
s
)
,
where e
l
∈
∂
E
1
⋂
‍
∂
Ω
i and e
r
∈
∂
E
2
⋂
‍
∂
Ω
i are the left and right neighbor edges of P, E
1
,
E
2
∈
𝒯
h
(
Ω
i
). If P is a vertex of Ω
i, then E
1
=
E
2.Remark 6.
Forv
∈
X
h
ℰ
(
Ω
i
), we define an operator ℳ
i
ℰ
:
X
h
ℰ
(
Ω
i
)
→
V
h
/
2
(
Ω
i
) [12, Definition 3.2]; that is, if P is a vertex of Ω
i, let (
ℳ
i
ℰ
v
)
(
P
)
=
0, and their stable pseudoinverse is denoted by ℳ
i
+ [12, Lemma 3.2]; here X
h
ℰ
(
Ω
i
)
=
{
v
∈
X
h
(
Ω
i
)
∣
∫
e
‍
v
d
s
=
0
,
∀
e
∈
∂
Ω
i
,
h
e
∖
ℰ
}.For the operatorsℳ
i and ℳ
i
+, we have the following results (see [12]):
(39)
|
ℳ
i
v
|
H
1
(
Ω
i
)
≍
|
v
|
H
h
1
(
Ω
i
)
,
∀
v
∈
X
h
(
Ω
i
)
;
|
ℳ
i
+
v
|
H
h
1
(
Ω
i
)
⪯
|
v
|
H
h
1
(
Ω
i
)
,
∀
v
∈
V
h
/
2
(
Ω
i
)
.
For the rotated Q
1 element, we have the following inequality.Lemma 7.
For anyu
i
∈
X
Δ
(
Γ
i
), we can split u
i into u
i
=
∑
Γ
i
j
⊂
∂
Ω
i
‍
u
i
j, and one has
(40)
|
u
i
j
|
H
h
1
(
Ω
i
)
⪯
(
1
+
log
⁡
(
H
i
h
i
)
)
|
u
i
|
H
h
1
(
Ω
i
)
,
where u
i
j
∈
X
Δ
(
Γ
i
), and for any e
∈
Γ
i
j
e, ∫
e
‍
u
i
j
d
s
/
|
e
|
=
∫
e
‍
u
i
d
s
/
|
e
|; for any e
∈
∂
Ω
i
,
h
e
∖
Γ
i
j, ∫
e
‍
u
i
j
d
s
/
|
e
|
=
0.Proof.
By (39), Lemma 3, the inverse trace theorem, trace theorem, and Poincáre inequality, we obtain
(41)
|
u
i
j
|
H
h
1
(
Ω
i
)
≤
|
ℳ
i
+
ℋ
i
I
ℰ
0
ℳ
i
u
i
j
|
H
h
1
(
Ω
i
)
⪯
|
ℋ
i
I
ℰ
0
ℳ
i
u
i
j
|
H
h
1
(
Ω
i
)
⪯
|
I
ℰ
0
ℳ
i
u
i
j
|
H
1
/
2
(
∂
Ω
i
)
⪯
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
∥
ℳ
i
u
i
∥
H
1
/
2
(
∂
Ω
i
)
≤
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
∥
ℳ
i
u
i
∥
H
1
(
Ω
i
)
⪯
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
|
ℳ
i
u
i
|
H
1
(
Ω
i
)
⪯
(
1
+
log
⁡
(
H
i
h
i
)
)
|
u
i
|
H
h
1
(
Ω
i
)
,
where ℋ
i is a piecewise bilinear harmonic operator, and we have used the minimal energy property of discrete harmonic functions.


## 5. Proof of Theorem2

In the proof of Theorem2 we use the abstract framework of ASM methods (see [13]); we have necessary to prove three assumptions. Assumption II follows from the standard coloring argument; now we need to prove Assumption I and Assumption III.First we show the following stable decomposition.Lemma 8 (Assumption I).
For anyu
∈
X
h
(
Γ
), there is the following decomposition:
(42)
u
=
R
0
T
u
H
+
∑
i
=
1
N
‍
R
D
,
Δ
i
T
u
i
,
u
H
∈
X
H
(
Ω
)
,
u
i
∈
X
Δ
(
Γ
i
)
that satisfies
(43)
a
h
(
u
H
,
u
H
)
+
∑
i
=
1
N
‍
a
h
,
i
(
u
i
,
u
i
)
⪯
a
h
(
u
,
u
)
.Proof.
First we show the decomposition (42). For any function u
∈
X
h
(
Γ
), let u
H
=
I
H
u, and u
Δ
=
u
-
I
h
u
H, u
i
=
u
Δ
|
Ω
i. From the definitions of I
H and I
h, we have
(44)
∫
Γ
i
j
‍
u
i
d
s
=
∫
Γ
i
j
‍
u
Δ
d
s
=
∫
Γ
i
j
‍
(
u
-
I
h
u
H
)
d
s
=
∫
Γ
i
j
‍
(
u
-
u
H
)
d
s
=
0
;
by (22) and the definition of R
D
,
Δ
i
T, we get
(45)
R
0
T
u
H
+
∑
i
=
1
N
‍
R
D
,
Δ
i
T
u
i
=
∑
i
=
1
N
‍
R
D
,
i
T
I
h
u
H
+
∑
i
=
1
N
‍
R
D
,
i
T
(
u
-
I
h
u
H
)
=
u
.
Then u
i
∈
X
Δ
(
Γ
i
) and the equality (42) holds.
Now, we prove stable decomposition (43). We assume u
-
Γ
i
j
=
∫
Γ
i
j
‍
u
d
s
/
|
Γ
i
j
|; then using Lemma 3.5 in [14], Poincaré-Friedrichs' inequality, and scaling argument, we can derive
(46)
∑
Γ
i
j
,
Γ
i
k
⊂
∂
Ω
i
‍
|
u
-
Γ
i
j
-
u
-
Γ
i
k
|
2
=
∑
Γ
i
j
,
Γ
i
k
⊂
∂
Ω
i
‍
(
1
|
Γ
i
j
|
∫
Γ
i
j
(
u
-
u
-
Γ
i
k
)
‍
)
2
⪯


∑
Γ
i
k
⊂
∂
Ω
i
‍
(
1
H
i
2
∥
u


-


u
-
Γ
i
k
∥
L
2
(
Ω
i
)
2

+


|
u
|
H
h
1
(
Ω
i
)
2
)
⪯
|
u
|
H
h
1
(
Ω
i
)
2
.
From (46) and discrete equivalent norm, we deduce
(47)
a
h
(
u
H
,
u
H
)
=
∑
i
=
1
N
‍
a
h
,
i
(
u
H
,
u
H
)
≍
∑
i
=
1
N
‍
ρ
i
∑
Γ
i
j
,
Γ
i
k
⊂
∂
Ω
i
‍
|
u
-
Γ
i
j
-
u
-
Γ
i
k
|
2
⪯
a
h
(
u
,
u
)
.
Meanwhile, from the fact that the harmonic function has minimal energy norm and (47), we get
(48)
∑
i
=
1
N
‍
a
h
,
i
(
u
i
,
u
i
)
=
a
h
(
u
Δ
,
u
Δ
)
=
a
h
(
u
-
I
h
u
H
,
u
-
I
h
u
H
)
⪯
a
h
(
u
,
u
)
.
So (47) and (48) lead to (43), and the proof is completed.Next we state the local stability as follows.Lemma 9 (Assumption III).
For anyu
∈
X
Δ
(
Γ
i
), we have
(49)
a
h
(
R
D
,
Δ
i
T
u
,
R
D
,
Δ
i
T
u
)
⪯
(
1
+
log
⁡
H
i
h
i
)
2
a
h
,
i
(
u
,
u
)
.
And for any u
H
∈
X
H
(
Ω
), one has
(50)
a
h
(
R
0
T
u
H
,
R
0
T
u
H
)
⪯
(
1
+
log
⁡
H
h
)
2
a
h
(
u
H
,
u
H
)
.Proof.
To prove (49) we first define θ
Γ
i
j
∈
X
h
(
Γ
) associated with Γ
i
j
⊂
Γ which satisfies
(51)
1
|
e
|
∫
e
‍
θ
Γ
i
j
d
s
=
{
1
,
∀
e
∈
Γ
i
j
e
,
0
,
∀
e
∈
Γ
∖
Γ
i
j
e
,
and define a zero prolong operator E
i
:
X
h
(
Ω
i
)
→
X
h
(
Ω
) as
(52)
∫
e
‍
E
i
v
d
s
=
{
∫
e
‍
E
i
v
d
s
,
∀
e
∈
Ω
i
,
h
e
⋃
‍
∂
Ω
i
,
h
e
,
0
,
others
.
Then we can decompose R
D
,
Δ
i
T
u as follows:
(53)
R
D
,
Δ
i
T
u
=
R
D
,
i
T
u
=
ℋ
(
∑
Γ
i
j
⊂
Γ
i
‍
ℐ
h
(
θ
Γ
i
j
(
E
i
δ
i
+
u
)
)
)
=
∑
Γ
i
j
⊂
Γ
i
‍
ℋ
(
ℐ
h
(
θ
Γ
i
j
(
E
i
δ
i
+
u
)
)
)
,
here ℐ
h is the integral average interpolation operator on the interface Γ
i
j, satisfying
(54)
∫
e
‍
ℐ
h
(
θ
Γ
i
j
(
E
i
δ
i
+
u
)
)
d
s

=

∫
e
‍
θ
Γ
i
j
d
s
·
∫
e
‍
E
i
δ
i
+
u
d
s
,
∀
e
∈
Γ
i
j
e
.
Note that the support of R
D
,
i
T
u is contained in Ω
i
⋃
Γ
i
j
⊂
∂
Ω
i
‍
(
Ω
j
⋃
‍
Γ
-
i
j
); we denote u
~
j
=
(
R
D
,
i
T
u
)
|
Ω
j, u
~
i
=
(
R
D
,
i
T
u
)
|
Ω
i. From Lemma 7 and the definition of δ
i
+, we derive
(55)
|
u
~
i
|
H
ρ
1
(
Ω
i
)
2
=
|
R
D
,
i
T
u
|
H
ρ
1
(
Ω
i
)
2
⪯
∑
Γ
i
j
⊂
∂
Ω
i
‍
|
ℋ
(
ℐ
h
(
θ
Γ
i
j
(
E
i
δ
i
+
u
)
)
)
|
H
ρ
1
(
Ω
i
)
2
=
∑
Γ
i
j
⊂
∂
Ω
i
‍
|
ℋ
i
(
ℐ
h
(
θ
Γ
i
j
(
E
i
δ
i
+
u
)
)
)
|
H
ρ
1
(
Ω
i
)
2
⪯
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
2
|
ℋ
i
(
E
i
δ
i
+
u
)
|
H
ρ
1
(
Ω
i
)
2
≤
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
2
|
ℋ
i
u
|
H
ρ
1
(
Ω
i
)
2
=
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
2
|
u
|
H
ρ
1
(
Ω
i
)
2
.
Moreover, sinceu
~
j is discrete harmonic in Ω
j with ∫
e
‍
u
~
j
d
s
=
0 for any e
∈
∂
Ω
j
e
∖
Γ
i
j, then from Lemma 3.3 in [12], we have
(56)
|
u
~
j
|
H
h
1
(
Ω
j
)
⪯
∥
ℳ
j
ℰ
u
~
j
∥
H
00
1
/
2
(
Γ
i
j
)
.
Since the meshes on subdomain Ω
i and Ω
j align across the interface Γ
i
j, using the above inequality yields
(57)
|
u
~
j
|
H
ρ
1
(
Ω
j
)
2
=
ρ
j
|
u
~
j
|
H
h
1
(
Ω
j
)
2
⪯
ρ
j
∥
ℳ
j
ℰ
u
~
j
∥
H
00
1
/
2
(
Γ
i
j
)
2
=
ρ
j
∥
ℳ
i
ℰ
u
~
i
j
∥
H
00
1
/
2
(
Γ
i
j
)
2
,
where u
~
i
j
∈
X
Δ
(
Γ
i
), and for any e
∈
Γ
i
j
e, ∫
e
‍
u
~
i
j
d
s
/
|
e
|
=
∫
e
‍
u
~
i
d
s
/
|
e
|; for any e
∈
∂
Ω
i
,
h
e
∖
Γ
i
j, ∫
e
‍
u
~
i
j
d
s
/
|
e
|
=
0.
Using (23), the trace theorem, and Lemma 3, we obtain
(58)
ρ
j
∥
ℳ
i
ℰ
u
~
i
j
∥
H
00
1
/
2
(
Γ
i
j
)
2
=
ρ
j
∥
ℳ
i
ℰ
ℋ
i
(
ℐ
h
(
θ
Γ
i
j
(
E
i
δ
i
+
u
)
)
)
∥
H
00
1
/
2
(
Γ
i
j
)
2
⪯
ρ
i
|
ℳ
i
ℰ
u
i
j
|
H
1
/
2
(
∂
Ω
i
)
2
⪯
ρ
i
|
ℳ
i
ℰ
u
i
j
|
H
h
1
(
Ω
i
)
2
⪯
ρ
i
|
u
i
j
|
H
h
1
(
Ω
i
)
2
⪯
(
1
+
log
⁡
⁡
(
H
i
h
i
)
)
2
|
u
|
H
ρ
1
(
Ω
i
)
2
,
where u
i
j
∈
X
Δ
(
Γ
i
), and for any e
∈
Γ
i
j
e, ∫
e
‍
u
i
j
d
s
/
|
e
|
=
∫
e
‍
u
d
s
/
|
e
|; for any e
∈
∂
Ω
i
,
h
e
∖
Γ
i
j, ∫
e
‍
u
i
j
d
s
/
|
e
|
=
0.
From (57) and (58), we complete the proof of (49).
Using the similar techniques in (49) and summing over all subdomains, we can complete the proof of (50).


## 6. Numerical Results

In this section, we show numerical results of our method using the model problem(59)
-
div
⁡
(
ρ
∇
u
)
=
f
,
in
Ω
,
u
=
0
,
on
⁡
∂
Ω
,
where Ω
=
[
0,1
]
2. The domain is composed of M
×
M subsquares; their mesh sizes are H, and the subsquares are divided into smaller ones with mesh sizes h. The coefficient ρ is either 1 or 1
0
k
(
k
=
2
,
4
,
6
).We use the preconditioned conjugate gradient (PCG) method with zero initial guess for the discrete system of equations. The stopping criterion for the PCG method is when the 2-norm of the residual is reduced by the factor of1
0
-
6 of the initial guess. An estimate for the condition number of the corresponding system is computed by using the Lanczos algorithm.In Table1, we show the number of iterations and the condition numbers with different ratio H
/
h. In Figure 1, we plot the condition numbers as the function of (
1
+
log
⁡
(
H
/
h
)
)
2 for 16 domains. From the results in Table 1 and Figure 1, we can see that the convergence of our method is quasioptimal since the number of iterations is independent of jumps in coefficients and almost independent of mesh sizes.Table 1
The number of iterations and condition numbers.
M
×
M
H
/
h
=
4
H
/
h
=
16
k
=
2
k
=
4
k
=
6
k
=
2
k
=
4
k
=
6
4
×
4
9 (2.68)
9 (2.87)
9 (2.87)
11 (3.84)
11 (3.83)
11 (3.76)
8
×
8
10 (2.78)
10 (2.74)
10 (2.73)
13 (4.25)
13 (4.16)
13 (4.17)
16
×
16
10 (2.86)
11 (2.84)
12 (2.83)
13 (4.39)
14 (4.34)
14 (4.34)
32
×
32
10 (2.89)
11 (2.86)
12 (2.84)
13 (4.45)
13 (4.45)
14 (4.39)Figure 1
Plot of the condition numbers as the function of(
1
+
log
⁡
(
H
/
h
)
)
2.



---

*Source: 859424-2014-01-16.xml*