A Nonoverlapping Domain Decomposition Methodwith Inexact Solvers
1
Qiya Hu and Dudu Sun
LSEC, Institute of Computational Mathematics and Scientiﬁc/Engineering Computing,Academy of Mathematics and Systems Science, Chinese Academy of Sciences,
Abstract
In this paper we are concerned with nonoverlapping domain decomposition methodsfor the secondorder elliptic problems in threedimensional domains. We develop anew kind of substructuring method, in which one can use an inexact solver both ineach subdomain and on each local interface. The main ideas are to decompose theinterface space into the sum of small local subspaces and a series of coarse subspacesspanned by
constantlike
basis functions, and to design a cheap approximate harmonicextension of the
constantlike
function. It will be shown that the condition number of the preconditioned system grows only as the logarithm of the dimension of the localproblem associated with an individual substructure, and is independent of possible jumps of the coeﬃcient in the elliptic equation.
Key words
. domain decomposition, interface space, multilevel decomposition,constantlike function, nearly harmonic extension, preconditioner, inexact solvers,condition number
AMS(MOS) subject classiﬁcation
65F10, 65N30, 65N55
1 Introduction
Nonoverlapping domain decomposition methods (DDMs) have been shown to be powerful techniques for solving largescale partial diﬀerential equations, especially for solvingpartial diﬀerential equations with large jump coeﬃcients, and for solving coupled partialdiﬀerential equations. One’s main task in nonoverlapping DDMs is the construction of aneﬃcient substructuring preconditioner for discretization system associated with the partialdiﬀerential equations. The construction of this preconditioner has been investigated fromvarious ways and to various models in literature, see, for example, [1][9], [11][15], [17][21],[23][24], [26].Most nonoverlapping DDMs studied so far require exact subdomain solvers; we refer[25] and [29] (and the references cited therein). Such a requirement severely degrade the efﬁciency of the methods. There are only a few works studying substructuring methods withinexact subdomain solvers [3], [4] and [9]. In [3], analysis and numerical experiments withinexact algorithms of NeumannDirichlet type was done under the additional assumptionof high accuracy of the inexact solvers. The essential diﬃculty is that discrete harmonicextensions on each subdomain are used in nonoverlapping domain decomposition methods.In [4], the harmonic extension on a subdomain was replaced by a simple
average
extension,and substructuring preconditioners with the average extension are constructed. Because of such
average
extension, nearly optimal convergence can not be gotten for these substructuring preconditioners. To avoid harmonic extensions, [9] considered so called
approximate
harmonic basis functions, which still involve high accuracy of the inexact solvers. It seemsdiﬃcult to construct a nearly optimal substructuring preconditioner with inexact solverswithout any additional assumption.
1
The work is was supported by Natural Science Foundation of China G10771178, The Key Projectof Natural Science Foundation of China G10531080, and National Basic Research Program of ChinaG2005CB321702. (email: hqy@lsec.cc.ac.cn)
1
In the present paper, inspired by [9] and [4], we make a new attempt for the designof substructuring preconditioner with inexact solvers. The core work is the constructionof a kind of multilevel
nearly
harmonic basis on general quasiuniform meshes. The mainingredients in our construction are: (i) develop a special multilevel space decomposition tothe interface space; (ii) design a cheap
nearly
harmonic extension for each basis function of the subspaces involved in the decomposition. It will be shown that the new substructuringpreconditioner possesses nearly optimal convergence, which is independent of possible large jumps of the coeﬃcient across the interface. For the new method, no additional assumptionis required , and the total computational complexity is optimal.The outline of the remainder of the paper is as follows. In Section 2, we introducesome notation and our motive. In Section 3, we present a multilevel decomposition for theinterface space. The main results on the substructuring preconditioner are described inSection 4. In Section 5, we give an analysis of the convergence of the preconditioner. Insection 6, we prove the stability of the extension of
constantlike
function, which is used inSection 5. Some numerical results are reported in Section 7.
2 Preliminaries
2.1 Domain decomposition
Let Ω be a bounded polyhedron in
R
3
. Consider the model problem
−
div
(
ω
∇
u
) =
f, in
Ω
,u
= 0
, on ∂
Ω
,
(2.1)where
ω
∈
L
∞
(Ω) is a positive function.Let
H
10
(Ω) denote the standard Sobolev space, and let (
·
,
·
) denote the
L
2
(Ω)innerproduct. The weak formulation of (2.1) in
H
10
(Ω) is then given by the following.
Find
u
∈
H
10
(Ω)
such that
A
(
u,v
) = (
f,v
)
∀
v
∈
H
10
(Ω)
,
(2.2)where (
·
,
·
) is the scalar product in
L
2
(Ω), and
A
(
u,v
) =
Ω
ω
∇
u
·∇
vdp.
We will apply a kind of nonoverlapping domain decomposition method to solving (2.2).For simplicity of exposition, we consider only the case with matching grids in this paper.Let
T
h
=
{
τ
i
}
be a regular and quasiuniform triangulation of Ω with
τ
′
i
s
being nonoverlapping simplexes of size
h
(
∈
(0
,
1]). The set of notes of
T
h
is denoted by
N
h
. We thendeﬁne
V
h
(Ω) to be the piecewise linear ﬁnite element subspace of
H
10
(Ω) associated with
T
h
:
V
h
(Ω) =
{
v
∈
H
10
(Ω) :
v

τ
∈ P
1
∀
τ
∈ T
h
}
,
where
P
1
is the space of linear polynomials. Then the ﬁnite element approximation for(2.2) is to ﬁnd
u
h
∈
V
h
(Ω) such that
A
(
u
h
,v
h
) = (
f,v
h
)
,
∀
v
h
∈
V
h
(Ω)
.
(2.3)Let Ω be decomposed into the union of
n
polyhedrons Ω
1
,
···
,
Ω
n
, which satisfy Ω
i
∩
Ω
j
=
∅
when
i
=
j
. We assume that each
∂
Ω
k
can be written as a union of boundaries of elements in
T
h
, and all Ω
k
are of size
H
in the usual sense (see [5] and [29]). Without loss of 2
generality, we assume that the coeﬃcient
ω
(
p
) is piecewise constant, then each subdomainΩ
k
is chosen such that
ω
(
p
) equals to a constant
ω
k
in Ω
k
. Note that
{
Ω
k
}
may notconstitute a triangulation of Ω.The common part of two neighboring subdomains Ω
i
and Ω
j
may be a vertex, an edgeor a face. In particular, we denote by Γ
ij
the common face of two neighboring subdomainsΩ
i
and Ω
j
(i.e., Γ
ij
=
∂
Ω
i
∩
∂
Ω
j
). The union of all Γ
ij
is denoted by Γ, which is called theinterface. In this paper, we choose Dirichlet data as the interface unknown.Deﬁne the operator
A
h
:
V
h
(Ω)
→
V
h
(Ω) by(
A
h
v, w
) =
A
(
v,w
) =
N
k
=1
ω
k
Ω
k
∇
v
·∇
wdx, v
∈
V
h
(Ω)
,
∀
w
∈
V
h
(Ω)
.
The equation (2.3) can be written as
A
h
u
h
=
f
h
, u
h
∈
V
h
(Ω)
.
(2.4)The goal of this paper is to construct a substructuring preconditioner for
A
h
based on thedomain decomposition described above.
2.2 Notations
To introduce the new method, we need some more notations. Throughout this paper, asubset
G
of Ω are always understood as an open set. The closure of
G
is denoted by ¯
G
.
•
subdomain spacesFor subdomain Ω
k
, deﬁne
V
h
(Ω
k
) =
{
v

Ω
k
:
∀
v
∈
V
h
(Ω)
}
,
and
V
ph
(Ω
k
) =
{
v
h
∈
V
h
(Ω) :
supp v
h
⊂
Ω
k
}
.
SetΩ
ij
= Ω
i
∪
Γ
ij
∪
Ω
j
,
and deﬁne
V
ph
(Ω
ij
) =
{
v
h
∈
V
h
(Ω) :
supp v
h
⊂
Ω
ij
}
.
•
interface space and face spacesAs usual, we deﬁne the (global) interface space by
W
h
(Γ) =
{
v

Γ
:
∀
v
∈
V
h
(Ω)
}
.
For each
∂
Ω
k
, set
W
h
(
∂
Ω
k
) =
{
v

∂
Ω
k
:
∀
v
∈
W
h
(Γ)
}
.
For a subset
G
of Γ, deﬁne˜
W
h
(
G
) =
{
φ
h
∈
W
h
(Γ) :
supp φ
h
⊂
G
}
.
In particular, for
G
= Γ
ij
, the face space ˜
W
h
(Γ
ij
) will be used repeatedly.
•
interpolationtype operator and
constantlike
basisFor a subset
G
of Γ, deﬁne the interpolationtype operator
I
0
G
:
W
h
(Γ)
→
W
h
(Γ) as(
I
0
G
φ
h
)(
p
) =
φ
h
(
p
)
,
if
p
∈ N
h
∩
G,
0
,
if
p
∈ N
h
∩
(Γ
\
G
)
.
3
In particular, we have(
I
0
G
1)(
p
) =
1
,
if
p
∈ N
h
∩
G,
0
,
if
p
∈ N
h
∩
(Γ
\
G
)
.
If
G
is just the union of some elements on Γ, we call
φ
G
=
I
0
G
1 to be
constantlike
basisfunction on
G
, which will be used repeatedly.
•
integration average and algebraic averageFor a function
ϕ
h
∈
W
h
(Γ), let
γ
G
(
ϕ
h
) denote the integration average of
ϕ
h
on
G
, andlet
γ
h,G
(
ϕ
) denote the algebraic average of the values of
ϕ
on the nodes in
G
.
•
sets of faces, edges, vertices and subdomainsFor convergence, let
F
Γ
denote the set of all the faces Γ
ij
. Besides, let
E
Γ
and
V
Γ
denotethe set of the interior edges and the set of interior vertices generated by the decomposition¯Ω =
¯Ω
k
,
respectively. For an edge
e
∈ E
Γ
, let
Q
e
denote the set of the indices
k
of the subdomainsΩ
k
which contain
e
as an edge. Namely,
Q
e
=
{
k
:
e
⊂
∂
Ω
k
}
.
DeﬁneΩ
e
=
k
∈Q
e
Ω
k
,
e
∈ E
Γ
.
•
face innerproducts, scaling norm and interface normFor a subset
G
of Γ, let
·
,
·
G
denote the
L
2
inner product on
G
. In particular, the
·
,
·
Γ
is abbreviated as
·
,
·
. Let
·
0
, G
denote the norm induced from
·
,
·
G
.For a subfaces
G
of Γ, let
H
G
denote the “size” of
G
. Deﬁne the scaling norm
φ
12
, G
= (

φ

2
12
, G
+
H
−
1
G
φ
20
, G
)
12
,
∀
φ
∈
H
12
(
G
)
.
For convenience, deﬁne
φ
h
∗
,
Γ
= (
n
k
=1
ω
k

φ
h

2
12
,∂
Ω
k
)
12
,
∀
φ
h
∈
W
h
(Γ)
.
•
discrete norms and discrete innerproductDiscrete norms (or seminorms) of ﬁnite element functions will be used repeatedly inthis paper, since the discrete norms are deﬁned on a set of nodes only, and do not dependon the geometric shape of the underlying domain.We ﬁrst give deﬁnitions of three well known discrete norms (refer to [29]), which areequivalent to their respective continuous norms. For
v
h
∈
V
h
(Ω
k
), the discrete
H
1
seminorm is deﬁned by

v
h

21
, h,
Ω
k
=
h
3
p
i
, p
j
∈N
h
∩
Ω
k

v
h
(
p
i
)
−
v
h
(
p
j
)

2
,
where
p
i
and
p
j
denote two neighboring nodes. Similarly, the discrete
L
2
norm on an edge
e
of Ω
k
is deﬁned by
v
h
20
, h,
e
=
h
p
∈N
h
∩
e

v
h
(
p
)

2
.
Let
G
⊂
Γ
ij
be the union of some elements. Deﬁne the discrete
H
12
seminorm on
W
h
(
G
)by

ϕ
h

2
h,
12
, G
=
p
∈N
h
∩
G
q
∈N
h
∩
G

ϕ
h
(
p
)
−
ϕ
h
(
q
)

2

p
−
q

3
, ϕ
h
∈
W
h
(
G
)
,
4
where
p
and
q
denote two diﬀerent nodes on
G
.Then, we deﬁne a discrete innerproduct. For each
∂
Ω
k
, set
φ,ψ
h, ∂
Ω
k
=
p
∈N
h
∩
∂
Ω
k
q
∈N
h
∩
∂
Ω
k
(
φ
(
p
)
−
φ
(
q
))(
ψ
(
p
)
−
ψ
(
q
))

p
−
q

3
, φ, ψ
∈
W
h
(
∂
Ω
k
)
,
where
p
and
q
denote two diﬀerent nodes on
∂
Ω
k
. Deﬁne discrete
H
12
innerproduct on
W
h
(Γ) by
φ,ψ
h,
Γ
=
n
k
=1
ω
k
φ,ψ
h,∂
Ω
k
, φ, ψ
∈
W
h
(Γ)
.
•
H
12
00
normsLet
G
⊂
Γ
ij
be the union of some elements. For a function
ϕ
h
satisfying
supp ϕ
h
⊂
G
,deﬁne

ϕ
h

2
H
1200
(
G
)
=

ϕ
h

2
12
, G
+
G

ϕ
h
(
x
)

2
dist
(
x, ∂G
)
ds
(
x
)
.
It is known that

ϕ
h

2
H
1200
(
G
)
=
∼ 
˜
ϕ
h

2
12
,
Ω
i
=
∼ 
˜
ϕ
h

2
12
,
Ω
j
,
where ˜
ϕ
h
∈
W
h
(Γ) denotes the zero extension of
ϕ
h
. Moreover, we have

ϕ
h

2
H
1200
(
G
)
=
∼
G

ϕ
h
(
x
)

2
dis
(
x, ∂G
)
ds
(
x
)
.
The corresponding discrete seminorm is deﬁned by

ϕ
h

2
h, H
1200
(
G
)
=
p
∈N
h
∩
G

ϕ
h
(
p
)

2
dis
(
p, ∂G
)
.
•
spectrally equivalencesFor simplicity, we will frequently use the notations
<
∼
and =
∼
. For any two nonnegativequantities
x
and
y, x <
∼
y
means that
x
≤
Cy
for some constant
C
independent of meshsize
h
, subdomain size
d
and the related parameters.
x
=
∼
y
means
x <
∼
y
and
y <
∼
x
.
2.3 Motivation
We ﬁrst recall the main ideas of the existing substucturing preconditions.Let
E
k
:
W
h
(
∂
Ω
k
)
→
V
h
(Ω
k
) be the discrete harmonic extension. Deﬁne the
harmonic
subspace
V
Γ
h
(Ω) =
{
v
h
∈
V
h
(Ω) :
v
h

Ω
k
=
E
k
(
φ
h

∂
Ω
k
) (
k
= 1
,
···
,
n
) for some
φ
h
∈
V
h
(Γ)
}
.
Then, we have the initial space decomposition
V
h
(Ω) =
n
k
=1
V
ph
(Ω
k
) +
V
Γ
h
(Ω)
.
Let
A
h,k
:
V
ph
(Ω
k
)
→
V
ph
(Ω
k
) be the restriction of the operator
A
h
on the local space
V
ph
(Ω
k
), and let
B
h,
Γ
:
V
Γ
h
(Ω)
→
V
Γ
h
(Ω) be a symmetric and positive deﬁnite operator whichis spectrally equivalent to the restriction of the operator
A
h
on the harmonic subspace5