2-Dimensional Primal Domain Decomposition Theory in Detail ∗

2-Dimensional Primal Domain Decomposition Theory in Detail ^∗

Dalibor Luk´aˇs

, Jiˇr´ı Bouchala

, Petr Vodstrˇcil

, and Luk´aˇs Mal´y

January 21, 2014

Abstract

We give details of the theory of primal domain decomposition (DD) methods for a 2-dimensional second order elliptic equation with homo- geneous Dirichlet boundary conditions and jumping coefficients. The problem is discretized by the finite element method. The computa- tional domain is decomposed into triangular subdomains that align with the coefficients jumps. We prove that the condition number of the vertex-based DD preconditioner isO (1 + log(H/h))²

, indepen- dently of the coefficient jumps, where H and hdenotes discretization parameters of the coarse and fine triangulations, respectively. Al- though this preconditioner and its analysis date back to the pioneering work by Bramble, Pasciak, and Schatz published in 1986, and it was revisited and extended by many authors including Dryja and Wid- lund in 1989, or Toselli and Widlund in 2005, the theory is hard to understand and some details, to our best knowledge, have never been published. In this paper we present all the proofs in detail by means of fundamental calculus.

Keywords: domain decomposition methods, finite element method, preconditioning

MSC 2010: 65N55, 65N30, 65F08

∗This work was supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070), by the Czech Min- istry of Education under the project MSM6198910027, and by VˇSB-TU Ostrava under the grant SGS SP2013/191.

†VˇSB–Technical University of Ostrava, 17. listopadu 15, 708 33 Ostrava-Poruba, Czech Republic. Emails: {dalibor.lukas,jiri.bouchala,petr.vodstrcil,lukas.maly}@vsb.cz

1 Introduction

We consider the homogeneous Dirichlet problem for the Poisson equation

−div (ρ(x)∇u(x)) = f(x), x∈Ω, u(x) = 0, x∈∂Ω,

where Ω ⊂R² is a bounded polygonal domain with Lipschitz boundary, f ∈ L²(Ω), andρ∈L^∞(Ω) is a positive piecewise constant material function. The domain Ω is decomposed intoN nonoverlapping open triangular subdomains Ωi by means of a conforming finite element (FE) discretization Ω =SN

i=1Ωi. This is referred to as the coarse discretization or the domain decomposition (DD). The decomposition aligns with jumps of the material function so that ρ(x) = ρi > 0 for x ∈ Ωi. We denote by Γ := SM

i=1Ei, the skeleton of the decomposition, where E_i is the interior of an edge apart from ∂Ω, see Fig. 1.

We denote the coarse discretization parameter by H := max

i=1,...,N diam(Ωi).

≈h

≈H

Figure 1: Decomposition of Ω into N = 10 subdomains with n^V = 2 vertices x^V_i (marked by squares); dashed-line depicts ∂Ω; solid-bold-lines denote Γ decomposed into M = 11 edges with edge nodes x^E_i,j (marked by circles);

solid-thin-lines denote the fine triangulation with n = 65 nodes; diamonds depict interior nodes x^I_i,j.

The related weak formulation find u∈H₀¹(Ω) :

XN i=1

ρi

Z

Ωi

∇u(x)∇v(x)dx

| {z }

=:a(u,v)

= Z

Ω

f(x)v(x)dx

| {z }

=:b(v)

∀v ∈H₀¹(Ω)

is discretized by the conforming finite element (FE) method on a subspace V := V^h := hϕ₁(x), . . . , ϕ_n(x)i ⊂ H₀¹(Ω), where (ϕ_i)ⁿ_i=1 denote the linear Lagrange basis functions related to the nodes depicted in Fig. 1. The under- lying fine triangulation align with the domain decomposition. We arrive at the linear system

A u=b, (1)

where (A)i,j := a(ϕi, ϕj), (b)i := b(ϕi), and u^h(x) := Pn

j=1(u)jϕj(x) ap- proximates u(x). By hwe denote the fine discretization parameter, which is the maximal fine-triangle diameter.

Primal DD-methods rely on re-sorting the basis functions (ϕi)ⁿ_i=1 into N sets of functions ϕ^I_i,jn^I_i

j=1, i = 1, . . . , N, related to subdomain interior nodes x^I_i,j ∈Ω_i, see Fig. 1, and a set of functions ϕ^Γ_kn^Γ

k=1 related to skeleton nodes x^Γ_k ∈Γ\∂Ω, which either belongs to an edge Ei, x^Γ_k =x^E_i,j, or it is a subdomain (coarse) vertex x^Γ_k =x^V_i , see Fig. 1. This translates (1) into the saddle-point system









A^I,I₁ 0 . . . 0 A^I,Γ₁ 0 A^I,I₂ . . . 0 A^I,Γ₂ ... ... . .. ... ... 0 0 . . . A^I,I_N A^I,Γ_N A^Γ,I₁ A^Γ,I₂ . . . A^Γ,I_N A^Γ,Γ















 u^I₁ u^I₂ ... u^I_N

u^Γ









=







 b^I₁ b^I₂ ... b^I_N

b^Γ









, (2)

where (A^I,I_k )i,j := a(ϕ^I_k,i, ϕ^I_k,j), (A^I,Γ_k )i,j = (A^Γ,I_k )j,i := a(ϕ^I_k,i, ϕ^Γ_k,j), (b^I_k)i :=

b(ϕ^I_k,i), and (b^Γ)i :=b(ϕ^Γ_i). Using a particular-solution approach, (2) can be solved in three steps:

1. Solve N independent systems A^I,I_i v^I_i =b^I_i, being FE-counterparts of

−ρi△v_i^I(x) = f(x), x∈Ωi, v_i^I(x) = 0, x∈∂Ωi. on subspaces V_i :=V_i^h :=hϕ^I_i,1, . . . , ϕ^I Ii.

2. Solve S u^Γ =b^Γ−PN

i=1A^Γ,I_i v_i^I, where S:=A^Γ,Γ−

XN i=1

A^Γ,I_i

A^I,I_i −1

A^I,Γ_i . (3)

3. SolveN concurrent systemsA^I,I_i w_i^I=−A^I,Γ_i u^Γ, being FE-counterparts of −ρi△w_i^I(x) = 0, x∈Ωi,

w_i^I(x) = u^Γ(x), x∈∂Ω_i∩Γ, w_i^I(x) = 0, x∈∂Ωi∩∂Ω, and set u^I_i :=v_i^I+w_i^I.

The method can be also viewed in terms of the block LDL^T-factorization A=

I^I 0 A^Γ,I A^I,I−1

I^Γ

A^I,I 0 0 S

I^I A^I,I−1

A^I,Γ 0 I^Γ

,

where I^I, I^Γ denote the identity matrices, A^I,I and A^I,Γ = (A^Γ,I)^T is the upper-block-diagonal and off-diagonal part of A, respectively.

The idea of primal DD-preconditioners is to replace the Schur complement S in Step 2 by an approximation S, which is cheap to invert, the conditionb number κ

Sb⁻¹S

increases modestly with H/h and it is independent of (ρ_i)^N_i=1.

The primal DD-methods can be thought as a block Gauss elimination combined with preconditioned Krylov space methods. The idea of re-ordering of the nodes date back to the nested-dissection sparse direct solver developed by George [5]. The base for the analysis of DD-preconditioners was given in a famous series of papers by Bramble, Pasciak, and Schatz, cf. [1]. Analysis in the Schwarz framework was presented by Dryja, Smith, and Widlund [3].

Let us mention at least two other important DD-methods such as balancing DD proposed and analyzed by Mandel and Brezina [6], or finite element tearing and interconnecting proposed by Farhat and Roux [4] and analyzed by Mandel and Tezaur [7]. We refer to the monograph by Toselli and Widlund [9]

for a more comprehensive overview.

The aim of this paper is to present a complete theory for the vertex-based DD-preconditioner in 2 dimensions by means of simple calculus. Although many other DD-preconditioners rely on this theory, to our best knowledge it

has never been presented in a single paper or a monograph without exter- nal references. Neither we have found a complete proof of the 2-dimensional counterpart of the edge lemma, a brief sketch of which is given in [2]. More- over, we found and corrected an inaccuracy in the proof [1] of a frequently- used discrete Sobolev inequality. We hope that our effort will be of some help to researchers, at a position similar to ours, who need to get a deeper understanding of the theory in order to develop their novel DD-methods.

The rest of the paper is organized as follows: In Section 2 we give the construction of the preconditioner. In Section 3 we present the analysis of the condition number of the DD-preconditioned algebraic system.

2 Vertex-based preconditioner

In Section 1 we re-ordered the basis functions (ϕi)ⁿ_i=1 into N sets of interior functions and a set of skeleton functions, which arrived at (2). Similarly we shall now re-order the set of skeleton basis functions ϕ^Γ_in^Γ

i=1 into M, being the number of edges, sets of functions ϕ^E_i,jn^E_i

j=1, i = 1, . . . , M, related to nodes x^E_i,j ∈ Ei, see Fig. 1, and into a set of functions ϕ^V_i n^V

i=1 related to subdomain vertices x^V_i ∈ Γ. This re-ordering induces a permutation of the Schur complement (3), still denoted by S,

S=

S^E,E S^E,V S^V,E S^V,V

, (4)

where the E-blocks of rows or columns are associated to the edge functions ϕ^E_i,j and the V-blocks are associated to the vertex functions ϕ^V_i . The matrix S^E,E admits the following block structure

S^E,E =





S^E,E_1,1 . . . S^E,E_1,M ... . .. ...

S^E,E_M,1 . . . S^E,E_M,M



, (5)

where S^E,E_i,j

k,l is related to interaction of the basis functions ϕ^E_i,k and ϕ^E_j,l. From (3) we can see that the block structure is sparse, since S^E,E_i,j is zero if there is no subdomain adjacent to both E_i and E_j.

Denote the overall number of interior edge nodes by n^E :=PM

i=1n^E_i . We introduce the matrix

R^E= R^E₁, . . . ,R^E_M

∈R^nV×nE, R^E_i ∈R^nV×nEi,

the transpose of which linearly interpolates function values from the coarse vertices x^V_k into interior nodes x^E_i,j of an associated edgeEi. That means the entries of R^E are given by values of the coarse-space basis functions

R^E_i

k,j =ϕ^H_k x^E_i,j

, (6)

where ϕ^H_i n^V

i=1 are FE-functions uniquely defined by the values at vertices x^V_i of the domain decomposition. We change the base ϕ^V_i n^V

i=1 to ϕ^H_i n^V i=1 so that

S=

I^E 0

−R^E I^V

S^E,E eS^E,V Se^V,E Se^V,V

! I^E − R^ET

0 I^V

, (7)

where I^E, I^V are identity matrices. Now the block A^H := Se^V,V is the FE- discretization of the bilinear form a(u, v) in the coarse base.

The primal, so-called vertex-based DD-preconditioner is constructed by neglecting Se^E,V, eS^V,E, and by skipping the off-diagonal blocks in (5), i.e.

b S=

I^E 0

−R^E I^V

S^E,E 0 0 A^H

I^E − R^ET

0 I^V

,

where S^E,E := diag

S^E,E_1,1 , . . . ,S^E,E_M,M .

In each iteration of, e.g., the preconditioned conjugate gradient method an action of Sb⁻¹ is required. We have the formula

Sb⁻¹ =

I^E R^ET

0 I^V 



S^E,E−1

0 0 A^H−1





I^E 0 R^E I^V

=

= XM

i=1

I^E_i

0 S^E,E_i,i −1

I^E_i ,0 +

R^ET

I^V

A^H−1

R^E,I^V

| {z }

=:RH

. (8)

This results in a modification of Step 2 of the three-steps method.

2a. Set

c^Γ :=

c^E c^V

:=b^Γ−A^Γ,Iv^I. 2b. Solve M independent local systems S^E,E_i,i w^E_i =c^E_i .

2c. Solve the global coarse system A^Hw^H =c^V+R^Ec^E. 2d. Set

b u^Γ :=

w^E+ (R^E)^Tw^H w^H

The action of bS⁻¹ comprises solution to a global system with the coarse matrix A^H and solution toM local edge problems with matricesS^E,E_i,i , which are local Schur complements related to the following systems:





A^I,I_j 0 A^I,E_j,i 0 A^I,I_k A^I,E_k,i A^E,I_i,j A^E,I_i,k A^E,E_i







 w_j^I w^I_k w^E_i



=



 0 0 c^E_i



,

where the relation ofi, j, and k is such that the domains Ω_j and Ω_k are con- nected via the edgeEi. We solve the system forw_i^E. It is an FE-discretization on the space Vj +Vk+V_i^E, where V_i^E := hϕ^E_i,liⁿl=1^Ei , of the following problem solved over the patch Ωj∪Ωk:

−ρj△w_j^I(x) = 0, x∈Ωj, w^I_j(x) = 0, x∈∂Ωj \Ei,

−ρk△w_k^I(x) = 0, x∈Ωk, w^I_k(x) = 0, x∈∂Ωk\Ei, w_i^E(x) :=w^I_j(x) = w_k^I(x), x∈Ei, ρj

dw^I_j

dnj(x) +ρkdw^I_k

dnk(x) = c^E_i (x), x∈Ei,

wherenj andnkdenote the outward unit normals to Ωj and Ωk, respectively.

The resulting preconditioner admits the following factorization b

A=

I^I 0 A^Γ,I A^I,I−1

I^Γ

A^I,I 0 0 Sb

I^I A^I,I−1

A^I,Γ 0 I^Γ

. (9)

3 Analysis of the condition number

We shall analyze the condition number κ b A⁻¹A

by means of finding spec- tral bounds λmin >0 and λmax >0 such that

∀u∈V : λminba(u, u)≤a(u, u)≤ λmaxba(u, u),

whereba(u, u) is the quadratic form related to A. It will turn out that underb shape-regularity and quasi-uniformity of both the coarse and fine discretiza- tions the condition number κ is bounded by C(1 + ln(H/h))² from above.

The constant C as well as all the other generic constants that appear in the theory below are independent of H, h, and (ρ_i)^N_i=1.

3.1 Orthogonal space splitting

Let us re-visit the algebraic construction of A. First we re-sorted the basisb functions according to the interior and skeleton nodes. This leads to

V = (V1⊕a· · · ⊕aVN) +V^Γ,

where V^Γ := hϕ^Γ₁, . . . , ϕ^Γ_nΓi and where the a-orthogonality of Vi and Vj, for i6=j, follows from Ωi∩Ωj =∅.

Now we take into account the transformation of base determined by the right factor of (9). It transforms the basis functions ϕ^Γ_i to their discrete har- monic extensions ϕe^Γ_i :=H(ϕ^Γ_i). Recall that the discrete harmonic extension e

u^Γ of u^Γ ∈V^Γ is the solution to the following problem:

find eu^Γ ∈V : eu^Γ(x) =u^Γ(x) on Γ and ∀j ∀v ∈Vj : a(eu^Γ, v) = 0.

Note that eu^Γ|Ωj, j = 1, . . . , N, is an FE-counterpart of

−△eu^Γ(x) = 0, x∈Ωj, e

u^Γ(x) = u^Γ(x), x∈Γ∩∂Ωj, e

u^Γ(x) = 0, x∈∂Ω∩∂Ωj.

Denoting by Ve^Γ:=H(V^Γ) we arrive at the a-orthogonal decomposition V =V1⊕a· · · ⊕aVN ⊕aVe^Γ.

The Schur complement S is the FE-discretization of the bilinear form s(u^Γ, v^Γ) := a(H(u^Γ),H(v^Γ)), u^Γ, v^Γ ∈V^Γ,

in the base ϕ^Γ_in^Γ

i=1. The latter can be deduced from S =

−A^Γ,I A^I,I−1

I^Γ A^I,I A^I,Γ

A^Γ,I A^Γ,Γ − A^I,I−1

A^I,Γ I^Γ

,

where the transformation factors consist of nodal coordinates of (ϕe^Γ_i)ⁿ_i=1^Γ . Finally, we take a closer look at the last transformation determined by the factorR^H in (8). It transforms functions to the linear interpolation from its vertex values along all the skeleton edges. We denote this interpolation operator by I^H :C0(Ω) →C0(Ω), I^H(v)(x) :=Pn^V

i=1v(x^V_i )ϕ^H_i (x). In partic- ular, I^H ϕ^V_i

=ϕ^H_i , see (6). Since the latter are discrete harmonic, we end up with the following decomposition

V =V|1⊕a· · · ⊕{z aVN}

=:V^I

⊕a(Ve^E+V^H)

| {z }

=eV^Γ

, (10)

whereV^H :=I^H(V),Ve^E :=H V −V^H

=HPM i=1V_i^E

. Therefore, every u=u^I+u^E+u^V∈V admits the unique decomposition

u=ue^I⊕^a ue^E+u^H ,

whereu^H :=I^H(u),eu^E=H u−u^H

, and eu^I:=u−eu^E−u^H. The quadratic forms now read as follows:

a(u, u) = XN

i=1

a ue^I_i,eu^I_i

| {z }

=a(eu^I,eu^I)

+ XM i,j=1

a ue^E_i,ue^E_j

| {z }

=a(ue^E,eu^E)

+2a eu^E, u^H

+a u^H, u^H ,(11)

ba(u, u) = XN

i=1

a ue^I_i,eu^I_i +

XM i=1

a ue^E_i,ue^E_i

+a u^H, u^H

(12) with ue^I =PN

i=1ue^I_i,ue^I_i ∈Vi and ue^E=PM

i=1ue^E_i ,ue^E_i ∈ H V_i^E .

3.2 Upper bound

Theorem 1. For all u∈V we have

a(u, u)≤10ba(u, u), i.e., λmax := 10.

Proof. Let us take an arbitrary u ∈ V and its unique splitting u = u^I ⊕a

e

u^E+u^H

. For each skeleton edge Ei we define its edge-neighbourhood Ni :={j ∈ {1, . . . , M}: i6=j and ∃k ∈ {1, . . . , N}: Ei, Ej ⊂∂Ωk}. Since |Ni| ≤4, as each skeleton edge Ei is associated to at most four other edges via two subdomains, and j ∈Ni ⇔i∈Nj, using 2a(v, w)≤a(v, v) + a(w, w),

a ue^E,ue^E

= XM

i=1

XM j=1

a eu^E_i,eu^E_j

= XM

i=1

(

a eu^E_i,ue^E_i

+X

j∈Ni

a ue^E_i,ue^E_j)

≤ XM

i=1

(

a eu^E_i,eu^E_i

+ X

j∈Ni

1 2

a ue^E_i,eu^E_i

+a ue^E_j,eu^E_j)

≤

1 + 4 2

X^M

i=1

a ue^E_i ,eu^E_i + 4

2 XM

j=1

a ue^E_j,eu^E_j

= 5 XM

i=1

a ue^E_i,ue^E_i .

Using the latter estimate the mixed term is estimated as follows:

a ue^E, u^H

≤ 1 2

a eu^E,ue^E

+a u^H, u^H

≤ 5 2

XM i=1

a ue^E_i ,ue^E_i +1

2a u^H, u^H .

Combining the estimates completes the proof with λmax := 10, a(u, u)≤a ue^I,ue^I

+ 10 XM

i=1

a ue^E_i ,eu^E_i

+ 2a u^H, u^H

≤10ba(u, u).

3.3 Shape-regular quasi-uniform triangulations

Assumption 1. Let us assume that the fine triangulation is from a family of shape-regular discretizations by which we mean that there exists αmin ∈ (0, π/3i independent ofh such that every angle in the FE-triangulation, thus also in the domain decomposition, is bounded by αmin from below. Shape- regularity guarantees the angles to be bounded from above by αmax := π − 2αmin. From the law of sines we have a uniform upper bound on the ratio between the largest and shortest edge of a triangle Ti or a subdomain Ωi, i.e.,

hⁱ_max hⁱ_min,H_maxⁱ

H_minⁱ ∈

1, 1 sinα_min

. (13)

For the sake of simplicity we assume that to each x^V_k being a corner of Ωi

there is exactly one adjacent triangle T such that T ⊂Ωi.

Assumption 2. Let us further assume that both the fine and coarse triangu- lations are from families of quasi-uniform discretizations by which we mean that there exists a common constant CA2 ∈ (0,1i independent of h and H such that for every triangle Ti and every subdomain Ωi the diameter hⁱ_max and H_maxⁱ , respectively, is bounded

hⁱ_max ≥CA2h, H_maxⁱ ≥CA2H. (14) For the sake of simplicity we assume that H ≥2h.

We will need a discrete Sobolev inequality for the FE-functions.

Lemma 1. Given a linear function v on a triangle with vertices A, B, C and an angle α at A, we have

k∇vk²≤ 2 [(v(B)−v(A))²+ (v(C)−v(A))²] min{kB−Ak²,kC−Ak²} sin²α .

Proof. We introduce the coordinate system such that A is in the origin and the line segment AB is the x₁-axis, then

∂v

∂x1

= v(B)−v(A)

kB−Ak , cosα ∂v

∂x1

+ sinα ∂v

∂x2

= v(C)−v(A) kC−Ak =: dv

ds.

The assertion follows from the following manipulations:

k∇vk² = ∂v

∂x1

2

+ 1

sin²α dv

ds −cosα ∂v

∂x1

2

≤ 1 sin²α

"

sin²α ∂v

∂x1

2

+ 2 dv

ds 2

+ 2 cos²α ∂v

∂x1

2#

≤ 2 sin²α

"

∂v

∂x1

2

+ dv

ds 2#

.

Corollary 1. Under Assumptions 1 and 2 there exists CC1 >0 such that

∀i∈ {1, . . . , N} ∀u ∈V : hk∇ukL^∞(Ωi)≤CC1kukL^∞(Ωi). (15)

Proof. For x ∈ Tj ⊂ Ωi with vertices A, B, C Assumption 1 and Lemma 1 yield

k∇u(x)k ≤

√2 h^j_min sinα_min

p4u(A)²+ 2u(B)²+ 2u(C)² ≤ 4kuk^L∞(Ωi)

h^j_min sinα_min. The assertion follows from (13) and (14)

k∇u(x)k ≤ 4kuk^L∞(Ωi)

h^jmax sin²αmin ≤ 1 h

4 CA2 sin²αmin

| {z }

=:CC1

kuk^L∞(Ωi).

3.4 Stability of the coarse space

The next lemma is crucial for the stability of the coarse space in the energy norm. We are inspired by the proof of Bramble, Pasciak, and Schatz in [1, L.3.3].

Lemma 2. Under Assumptions 1 and 2 there exists CL2 > 0 such that for all i∈ {1, . . . , N}

∀u∈V : kuk²L^∞(Ωi) ≤CL2

1 + lnH h

1

H²kuk²L²(Ωi)+|u|²H¹(Ωi)

.

Proof. Without a loss of generality, assume thatkukL^∞(Ωi) =|u(0)|. We shall find an open cone Λ0,KH,γ ⊂ Ωi with the vertex at the origin 0, the radius KH and the angleγ :=αmin withK independent ofH. For the construction of Λ_0,KH,γ we refer to Fig. 2 and the following description. Denote by d_a, db, and dc the distances of the origin to the prolongations of the sides of Ωi with lengths a, b, and c, respectively, and assume that da is the largest distance. We choose KHe :=da. We take the open cone Λ_A,KH,αe ⊂Ωi at the vertex Aof Ωi that is opposite to the sidea, where αdenotes the angle atA.

By moving Λ_A,KH,αe to the origin we get the cone Λ_0,KH,αe ⊂ Ωi. It remains to find K > 0 independent of H such that K ≤ K. The areae |Ωi| can be estimated as follows

|Ωi|= a da+b db+c dc

2 ≤ a+b+c 2 K H.e

By (14) and (13) we have an H-independent estimate for the constant Ke Ke ≥2

1

2H_maxⁱ H_minⁱ sinαmin

3H_maxⁱ H ≥ C_A2 3

H_minⁱ sinα_min

H_maxⁱ ≥ C_A2

3 sin²α_min=:K.

The construction of Λ0,KH,γ is completed by shortening the radius and the angle of Λ_0,KH,αe .

Ωi

A

B

C 0

a

b

c d_a

d_b dc

α

γ Λ_A,KH,αe Λ_0,KH,αe

Λ0,KH,γ

y1

y₂

Figure 2: Construction of Λ0,KH,γ.

We consider the coordinate system according to a side of Λ_0,KH,γ. For y(ρ, ϑ) =ρ(cosϑ,sinϑ)∈Λ0,KH,γ the fundamental theorem of calculus gives

u(0) =u(y(ρ, ϑ))− Z ρ

0 ∇u(y(t, ϑ)) (cosϑ,sinϑ)

| {z }

=:u^′(t,ϑ)

dt.

Integrating ϑ from 0 to γ and applying the triangle inequality yield γ|u(0)| ≤

Z γ 0

u(y(ρ, ϑ))dϑ +

Z γ 0

Z ρ 0

u^′_t(t, ϑ)dt dϑ

. (16) Choose, independently of h and H,δ := min{(√

2−1)/(√

2CC1), K}, where CC1 is the constant in (15). We shall consider two cases. First, if δh < ρ, the Cauchy-Schwarz and triangle inequalities yield

γ|u(0)| ≤√ γ

sZ γ 0

u²(y(ρ, ϑ))dϑ+

Z γ 0

Z δh 0

u^′_t(t, ϑ)dt dϑ +

Z γ 0

Z ρ δh

u^′_t(t, ϑ)dt dϑ

. (17) The second and third term in (17) can be estimated as follows:

Z γ 0

Z δh 0

u^′_t(t, ϑ)dt dϑ

≤γ δ hk∇uk^L∞(Ωi) ≤γ δ CC1|u(0)|,

Z γ

0

Z ρ δh

u^′_t(t, ϑ)dt dϑ =

Z

Λ0,ρ,γ\Λ_0,δh,γ

∇u(y) y kyk²dy

≤ k∇ukL²(Ωi)√γ r

ln ρ δh.

Using the estimates, moving the second term from the right-hand side of (17) to the left, squaring the inequality and dividing by γ² yield

1

2|u(0)|² ≤(1−δ CC1)²|u(0)|² ≤ 2 γ

Z γ 0

u²(y(ρ, ϑ))dϑ+ ln ρ

δhk∇uk²L²(Ωi)

. (18) In the second case, δh≥ρ, we estimate the first term on the right-hand side of (16) by the Cauchy-Schwarz inequality and the second term byγ δ CC1|u(0)|, which leads to

1

2|u(0)|² ≤(1−δ CC1)²|u(0)|² ≤ 2 γ

Z γ 0

u²(y(ρ, ϑ))dϑ. (19) Multiplying (18) and (19) by 2ρ, integrating ρ from δh to KH and from 0 to δh, respectively, and summing up the resulting inequalities yield

(KH)²

2 |u(0)|² ≤ 4 γ

Z KH 0

Z γ 0

ρ u²(y(ρ, ϑ))dϑ dρ +k∇uk²L²(Ωi)

Z KH δh

ρ ln ρ δhdρ

.

By estimating the second term on the right-hand side we complete the proof

|u(0)|² ≤ 4 γ

2

(KH)² kuk²L²(Ωi)+

lnK

δ + lnH h

|u|²H¹(Ωi)

≤ 4 γ max

1, 2

K²,lnK δ

| {z }

=:C_L2

1 + lnH h

1

H² kuk²L²(Ωi)+|u|²H¹(Ωi)

.

Corollary 2. Under Assumptions 1 and 2 there existsCC2>0such that for all i∈ {1, . . . , N}

∀u∈V : ku−uik²L^∞(Ωi) ≤CC2

1 + lnH h

|u|²H¹(Ωi), where ui := _|Ω¹

i|

R

Ωiu(x)dx with |Ωi| being the area of Ωi.

Proof. Combining the previous lemma and the Poincar´e inequality [8]

ku−uik²L²(Ωi) ≤CPH²|u|²H¹(Ωi),

where C_P:= 1/π², the assertion follows with C_C2:=C_L2(1 +C_P).

The next lemma gives stability of the coarse space. It can be found in [9, L.4.12].

Lemma 3. Under Assumptions 1 and 2 there exists CL3 > 0 such that for all i∈ {1, . . . , N}

∀u∈ V : I^H(u)²

H¹(Ωi)≤CL3

1 + lnH h

|u|²H¹(Ωi), as a consequence of which

∀u∈V : a(u^H, u^H)≤CL3

1 + lnH h

a(u, u).

Proof. Denote by P₁, P₂, andP₃ the vertices of a subdomain Ω_i. We have I^H(u)²_H1(Ω

i)=I^H(u)−ui

²_H1(Ω

i) =

X3 j=1

(u(Pj)−ui)ϕ^H_j

2

H¹(Ωi)

. (20) Forj ∈ {1,2,3}and the remaining indicesk and l we employ Lemma 1 with A :=Pk,α :=αk the angle atPk, B :=Pj, andC :=Pl and using (13) yield

|ϕ^H_j |²H¹(Ωi) =k∇ϕ^H_j k²|Ωi| ≤ 2· ¹₂kPj −Pkk kPl−Pkk sinαk

min{kPj −Pkk²,kPl−Pkk²}sin²αk

≤ H_maxⁱ

H_minⁱ sinαk ≤ 1 sin²αmin

=:ec, where |Ωi| denotes the area of Ωi. By (20) and Corollary 2 we have I^H(u)²

H¹(Ωi)≤3 X3

j=1

|u(Pj)−ui|²|ϕ^H_j |²H¹(Ωi)≤9ec CC2

1 + lnH h

|u|²H¹(Ωi),

which completes the proof with CL3 := 9ec CC2.

3.5 Stability of the edge space

To findλmin it remains to estimate the edge-term in (12) by (11) from above.

Being inspired by [9, L.4.23] we introduce a system of edge-based functions (θi(x))^M_i=1 ⊂C(Ω), wheree Ω := Ωe \

x^V_j :j = 1, . . . , n^V . For the construction we refer to Fig. 3 and the following paragraph.

We decompose each subdomain Ωj,j ∈ {1,2, . . . , N}, with all three edges being a part of the skeleton, i.e.,Ej1, Ej2, Ej3 ⊂Γ, into six trianglesωk. With- out loss of generality we take x∈ ω₁\ {P₁} and introduce local coordinates x = (x1, x2). We denote the angle at P1 by α1 and define the related edge functions θj1, θj2, and θj3 in ω1 by

θj1(x) := 1− 2 3 tan^α₂¹

x1

x2

, θj2(x) =θj3(x) := 1 3 tan^α₂¹

x1

x2

. (21) The edge functions are analogously defined in ω2, . . . , ω6. For a subdomain Ωj with only one or two edges assigned to the skeleton the construction of the related edge functions is similar. Note that the system completed by edge-functions assigned to ∂Ω forms a partition of unity on Ω.e

Ej1

Ej2

Ej3

ω1

ω2

ω3

ω4

ω5

ω₆ x x1

x2

P1

P2

P3

α1 α₁/2

α2

α2/2

α3

α₃/2

Figure 3: Decomposition of Ωj used for the construction of θj1, θj2, and θj3. Lemma 4. Under Assumption 1 there exists CL4 > 0 such that for all i ∈ {1, . . . , M}

k∇θi(x)k ≤CL4/r^H(x) almost everywhere in Ω,e where, for x∈Ωj with the verticesP1, P2, and P3, r^H(x) := min

k=1,2,3kx−Pkk. Proof. The assertion follows from the construction above. For x∈ω₁: k∇θj1(x)k= 2

3 tan^α₂¹

p(x1)²+ (x2)²

(x₂)² ≤ 2

3 tan^αmin₂ cos^{2 αmax}₂

| {z }

=:C_L4

p 1

(x1)² + (x2)²

| {z }

≤1/r^H(x)

by Assumption 1. The estimate holds true fork∇θ_j2(x)kandk∇θ_j3(x)k. The other cases, x∈ωk, are analogous.

Similarly to replacing the FE-projection by interpolation when estimat- ing the FE-approximation error, we will estimate the energy of the FE- interpolation of θ_i(u − u^H), rather than the energy of ue^E_i. We need the following, so-called edge lemma, the proof of which is sketched in [2].

Lemma 5. Under Assumptions 1 and 2 there exists C_L5 > 0 such that for all edges Ei, i∈ {1, . . . , M}, both the adjacent domains Ωj, Ei ⊂∂Ωj, and

∀u∈V : |I^h(θiw)|²H¹(Ωj) ≤CL5

1 + lnH h

kwk²L^∞(Ωj)+|w|²H¹(Ωj)

, (22) where w := u−u^H and I^h : C0(Ω) → V is the FE-interpolation operator, i.e., I^h(v)(x) :=Pn

i=1v(xi)ϕi(x), where xi is the node related to ϕi.

Proof. Let us take an edge Ei and an adjacent domain Ωj. By Assumption 1 to each coarse vertex Pk, k = 1,2,3, of Ωj an exactly one fine triangle T with vertices A = Pk, B, and C is associated. In the case that none of B and C lies on Ei, I^h(θiw) vanishes on T. We are left to analyze the other two triangles, for both of which we can consider C ∈ E_i. The contribution of such a triangle to |I^h(θiw)|²H¹(Ωj) is, using (13), as follows:

I^h(θiw)²

H¹(T) = w²(C) kC−Ak² sin²α

kB−Ak kC−Ak sinα 2

≤ h^T_max

2h^T_min sinα_minw²(C)≤ 1 2 sin²αmin

| {z }

=:ek1

kwk²L^∞(Ωj). (23)

In case of a triangle T ⊂ Ωj that none of its vertices A, B, and C is a vertex of Ωj, Lemma 1 yields

∇I^h(θiw)² ≤ 2

[(θ_iw)(B)−(θ_iw)(A)]²+ [(θ_iw)(C)−(θ_iw)(A)]² min{kB −Ak²,kC−Ak²} sin²α , whereαdenotes the angle atA. Sinceθiwis piecewise differentiable along the line segments AB andAC, we can adopt the Lagrange mean value theorem.

The latter combined with (13), the construction (21), and Lemma 4 yields ∇I^h(θiw)² ≤ 2k∇(θiw)k²L^∞(T)

sin²α

kB−Ak²+kC−Ak² min{kB −Ak²,kC−Ak²}

| {z }

≤1+(h^T_max/h^T_min)²

≤ 4

1 + _sin2¹α_min

sin²αmin

| {z }

=:ek2

k∇θik²L^∞(T)kwk²L^∞(T)+kθik²L^∞(T)k∇wk²L^∞(T)

≤ek₂ n

C_L4/r^H,h(x)2

kwk²L^∞(T)+k∇wk²L^∞(T)

o,

wherek∇fkL^∞(T):= ess sup

x∈T k∇f(x)kandr^H,h(x) := dist(T(x),{P₁, P₂, P₃}), whereT(x) is the open triangle containingx, which is a well-defined function up to the interfaces between fine triangles. Denote by Ωej the union of such non-corner triangles. They contribute to |I^h(θiw)|²_H¹_(Ωj) as follows:

I^h(θiw)²

H¹(Ωej)≤ek2

(

kwk²L^∞(Ωj) (CL4)² Z

Ωej

1/r^H,h(x)2

dx+|w|²H¹(eΩj)

) . (24) It remains to estimate the integral. We have

Z

Ωej

1

(r^H,h(x))² dx≤ X3 k=1

Z

Ωej

1

y∈Tinf(x)ky−Pkk²dx. (25) Let us introduce three systems of local polar coordinates so that, each of which has the respective origin at a coarse vertex Pk, the x1-axis coincides with an edge of Ωj, and Ωj lies in the upper half-space. We denote by v_min^T the smallest height of a triangle T. The law of sines, Assumptions 1 and 2 yield

v^T_min ≥h^T_min sinαmin ≥h^T_max sin²αmin ≥CA2h sin²αmin. Thus, by choosing c:=CA2 sin²αmin the domain

Λ :=

x= (x1, x2) =ρ(cosα,sinα)∈R² : ch≤ρ≤H and 0≤α≤αmax

covers Ωe_j with respect to each of the coordinate systems. Let us denote the respective counterparts of Λ associated toP1,P2, andP3 by Λ1, Λ2, and Λ3. Let us adopt the k-th local polar coordinatesx(ρ, α) and note that

y∈Tinf(x(ρ,α))ky−Pkk ≥max{ch, ρ−h}. We have the estimate

Z

Ωej

1

y∈Tinf(x)ky−Pkk² dx≤

αZmax

0

ZH ch

ρ

(max{ch,(ρ−h)})² dρ dα

=αmax

2c+ 1

2c² + lnH−h ch + h

ch− h H−h

≤αmax

4c+ 1 2c²

| {z }

=:ec

+ ln H ch

,

where we used H ≥2h from Assumption 2. Using the latter and (25), (24) is estimated by

I^h(θ_iw)²

H¹(Ωej) ≤ek₂

kwk²L^∞(Ωj) (C_L4)² 3α_max

ec+ ln H ch

+|w|²_H¹₍Ωej)

.

After adding the two contributions (23), the assertion follows with CL5 := maxn

3ek2(CL4)²αmax (ec−lnc) + 2ek1,3ek2(CL4)²αmax,ek2

o.

Now we can analyze the stability of the edge space. The following lemma is proven in [9].

Lemma 6. Under Assumptions 1 and 2 there exists CL6 >0 such that

∀u∈V : XM

i=1

a ue^E_i ,eu^E_i

≤CL6

1 + lnH h

2

a(u, u).

Proof. Denote by Ωi1 and Ωi2 domains adjacent to Ei and by{Eji}^Mi=1^j,Mj ≤ 3, edges adjacent to Ωj. Recall thatw:=u−I^H(u) andeu^E_i :=H(w^E_i), where w^E_i :=w on Ei and w_i^E := 0 elsewhere on Γ∪∂Ω. The discrete harmonicity of ue^E_i and Lemma 5 yield

XM i=1

a ue^E_i ,eu^E_i

= XM

i=1

X2 j=1

ρ_ij eu^E_i²

H¹(Ω_ij) ≤ XM

i=1

X2 j=1

ρ_ijI^h(θ_iw)²

H¹(Ω_ij)

= XN

j=1

ρj Mj

X

i=1

I^h(θjiw)²

H¹(Ωj)

≤ XN

j=1

ρj3CL5

1 + lnH h

kwk²L^∞(Ωj)+|w|²H¹(Ωj)

.

Now (α+β)² ≤2(α²+β²) and Corollary 2 give kwk²L^∞(Ωj)=k(u−u_j)−(I^H(u)−u_j)k²L^∞(Ωj)

≤2

ku−u_jk²_L^∞_(Ωj)+I^H(u)−u_j²

L^∞(Ωj)

| {z }

≤ku−ujk²_L∞(Ωj)

≤4C_C2

1 + lnH h

|u|²H¹(Ωj).

Similarly, Lemma 3 gives

|w|²H¹(Ωj)=u−I^H(u)²

H¹(Ωj) ≤2

|u|²H¹(Ωj)+I^H(u)²

H¹(Ωj)

≤2 (1 +CL3)

1 + lnH h

|u|²H¹(Ωj). Combining the estimates yields CL6 := 3CL5[4CC2+ 2(1 +CL3)].

3.6 Lower bound

Theorem 2. Under Assumptions 1 and 2 there exists C >0 such that

∀u∈V : ba(u, u)≤C

1 + lnH h

2

| {z }

=1/λmin(H,h)

a(u, u).

Proof. Comparing (11) and (12), the assertion is a consequence of Lemma 3 and 6 with C := 1 +CL3+CL6.

We conclude with an estimate of the condition number κ

Ab⁻¹A

≤10C

1 + lnH h

2

with C > 0 independent of H, h, and (ρi)^N_i=1 in a family of shape-regular quasi-uniform triangulations.

References

[1] J.H. Bramble, J.E. Pasciak, A.H. Schatz: The construction of precon- ditioners for elliptic problems by substructuring, I. Math. Comp. 47 (1986), 103–134. Zbl 0615.65112, MR 842125

[2] M. Dryja, O.B. Widlund: Some domain decomposition algorithms for elliptic problems. In Iterative Methods for Large Linear Systems, 273–

291. Academic Press, 1989.