Xiao-Chuan Cai.

Domain decomposition algorithms for indefinite elliptic problems online

. (page 1 of 2)
Online LibraryXiao-Chuan CaiDomain decomposition algorithms for indefinite elliptic problems → online text (page 1 of 2)
Font size
QR-code for this ebook

Computer Science Department


Domain Decomposition Algorithms for
Indefinite Elliptic Problems

Xiao-Chuan Cai
Olof B. Wtdlund

Technical Report 506

May 1990


I in

lo:^ (0

Iw o

c a>

-t C
4J -H





au-1 o

o w Oj
o e

_, _ £1 u

Pl4 (0 "O ■ •'-'

£ -H -H 4-1

o X c i-i cu
Cj -M o •■-<

CD -H B rH rH

!>1 (0 o 0, then, the GMRES
method converges and after m steps, the norm of the residual is bounded by < (1 - c&) Ikoll-

4 Algorithms on Overlapping Subregions

In this section, we introduce two variants of an additive Schwarz algorithm and
provide bounds on their convergence rates; see Theorem 1. The analysis is valid
for both two and three dimensions.

We first form a basic decomposition of the domain Q, into overlapping sub-
regions and then introduce the projections in terms of which our algorithms are

We use the ff -level subdivision {Jl,} of fi. Each subregion ft, is extended to
a larger region $7-, i.e. ft, C ft',. The overlap is generous in the sense that there
exists a constant a > 0, such that

distance(an ■ n Q, dfl, n fi) > aH„ Vz.

We assume that 5fi- does not cut through any ^-level elements. We use the
same construction for the subregions that intersect the boundary dCl except that
we cut off the part that is outside Q.

We also use the notation fig = ^•

We note that the larger the a, the fewer iterations can be expected. However,
if we increase the overlap, the size of the subproblems increases and with it the
cost of the subproblems. It is an important practical issue to balance the total
number of iterations and the cost of solving the subproblems.

For each fi,, a regTilar finite element subdivision is inherited from the /^-level
subdivision of d. The corresponding finite element space is defined by

The elements of this subspace of V* can be extended continuously by zero to the
complement of n[. We also use the subspace

Vo'' = V".

It is easy to see that our finite element function space V* can be represented
as the sum of the A'' -|- 1 subspaces,

y'> = v^^ + y^'' +...+ v^.

We can now define the projection operators, which are the main building
blocks of our algorithms. These operators map the finite element space V* onto
the subspaces V/* and are defined in terms of the bilinear forms B{; ■) and A{-, •).

Definition: Fori = 0, - ',N:

For any w^ 6 V*, QiW^ G V/* is the solution of the finite element equation

B{Qiw\v!:) = B{w\v'^), Vt;feV;\

For any w'* € V", PiW^ G V/" is the solution of the finite element equation

We now introduce the two operators, which define our transformed equations


g(2) = Qo + Pi +... + p^.

Our mzdn effort goes into the study of the spectra of these two operators. The
only difference between Q^^^ and Q*^^ is that, for i > 0, we replace the projection
Q,, corresponding to fi,, by P,. The coarse mesh projection is not changed.

The computation of Qiw'* or PiW^^ for t > and an arbitrary function
w^ G V*, involves the solution of a standard finite element linear system of
algebraic equations on the small subregion Q.-. The former gives rise to a nonsym-
metric linear system of equations and the latter to a positive definite, symmetric
problem. For i = 0, the problem is a standard finite element equation on the H-
level, coarse space. One can view P^ as a preconditioner of Qi in the subspace V/*;
cf. the discussion in Dryja and Widlund [8], [9]. The cost of the computation can
often be decreased by introducing such simplified problems. In particular, if it is
possible to choose some of the n[ to be rectangular and the corresponding mesh
to be uniform, a Fast Poisson solver can be used to compute the contribution
from V/*. It is an easy exercise to modify our theory to cover such a case.

We will consider two additive Schwaxz algorithms:

Algorithm 1: Obtain the solution of equation (S) by solving the equation

Q(^)u'* = b^'\ (4)


Algorithm 2: Obtain the solution of equation (S) by solving the equation

Q(2)u'' = b^'\ (5)

In order for equations (4) and (5) to have a unique solution, the operators
Q^^^ and Q'^) must be invertible. This follows from Theorem 1. To obtain the
same solution as equation (3), the right hand sides 6*^^ and 6'^^ must be chosen


correctly. The crucial observation is that these right hand sides can be computed
without knowledge of the solution of equation (3). The following formulas are

6(1) = QW^h = J2q,u'^



6(2) = qWu' = Qou' + J2P'^'-
Each of these terms can be computed by solving a problem in a subspace, since
by equation (3),


A{P.u\v'^) = B{u\v^) = {f,v^), Vi^fel^A

The main result of this paper is Theorem 1. By combining it with the Theorem
given in Section 3, we establish that the two algorithms converge at a rate which
is independent of the mesh parameters h and H, if the coarse mesh is fine enough.

Theorem 1 There exist constants Ho > 0, c{Ho) > and C{Ho), such that if
H < Ho, then, for i = 1,2


A(Q('V,(3('\'') < c(/fo)A(u^u'•).

The special constant Co is introduced in Lemma 1.

(a) The operator Qo is very important, since it provides global transportation
of information. All the other projections are local mappings. Without using
Qo, information would travel only from one subregion to its neighbors in each
iteration and it would take 0{1/H) iterations for the information to propagate
across the region. Without such a global mechanism, it would also be impossible
to confine the spectrum to the right half plane.

(b) The constant Hq determines the minimal size of the coarse mesh problem
and it depends on the operator L. In general. Ho decreases if we increase the
coefficients of the skew-symmetric terms, it decreases with c, while it increases
if we increase the overlap. Hq also depends on the shape of the domain fi. If
the domain is not convex, the estimate of Hq, imphcit in our proof of Lemma 5,
depends on the parameter 7. We do not have an explicit formula for Ho but we
know from experience that it can be determined by numerical experiments.

(c) K the operator L is positive definite, synmietric, there is no restriction on
the coarse mesh size H, i.e. Ho = cx).

The proof of Theorem 1 is based on the following results.

Lemma 1 There exists a constant Cq, which is independent of h and H, such
that, for all u'' e V*, there exist uf G V;'* xvith




This lemma is also central in the theorj' previously developed for positive
definite, symmetric problems. For a proof see Dryja and Widlund [8]; cf. also
Lions [15]. Note that this lemma is independent of the skew-symmetric and zero
order terms of the elliptic operator. In the symmetric, positive definite case,
Lemma 1 is combined with an abstract argument to give a lower bound for the
spectrum of the iteration operator.

The next lemma is a variation of a result by Schatz; cf. [22]. In his proof,
Garding's inequality, (ii), and the regularity result, (iv), are used. The proof
of Lemma 2 follows directly from Schatz's work by replacing the approximate
solution by the coarse mesh solution and the exact solution of the continuous
problem by the finite element solution in V^.

Lemma 2 There exist constants Ho > and C{Ho), such that if H < Hq, then,

HQou'^Wa < C{Ho)\\u^\\a


IIQou'' - u'^Wl^ < C{Ho)H''\\Qou'' - u'^Wa-

Lemma 3 The restriction of the quadratic form B{-, •) to the subspaces V-^, i >
0, is strictly positive definite for H sufficiently small, i.e.

cA{u\u'') < B(u\u''),Vu'' e V^ .

Proof of Lemma 3: We have to prove that the second order term dominate
the other symmetric term. This follows from the fact that the smallest eigenvalue
for the Dirichlet problem for —A on the region Q,[ is on the order of H~^.

Lemma 4 Let v'* = J^v^ , where v^ € V/*. Then there exists a constant C, such


Proof of Lemma 4: The proof follows from the observation that for each
X 6 n, the number of terms in the sum, which differ from zero, is uniformly


Lemma 5 There exist constants Hq > 0, c{Ho) and C{Hq), such that if H < Hq,


c{Ho)Co'A{u\u'') < J2MQ>^\Qi^'') < C{Ho)A{u\u'')



c{Ho)Co^A{u\ u*") < AiQou\ Qou'*) + Eili A{Piu\ P.«'')

< C{Hq)A{u'',u'').

Proof of Lemma 5: An upper bound for A{Qou'^, Qou'*) is given in Lemma
2. To obtain an upper bound for the sum of the other terms, we iise Lemma 3

B(QiU^Q.u'') = B(u^Q.u'')

to show that

cf2A{Q.u\Qiu'') < B{u\f2Q,u').

The right hand side can be estimated by using inequality (i) and Lemma 4. The
other upper bound is established in a similar way.

To prove the lower bounds, we begin by using Lemma 2 and the triangle
inequality to obtain

Wu'W]^ < C{H'-'A{u\u') + WQou'Wh).

Since the eigenvalues of the Dirichlet problem for —A are bounded from below
and Lemma 2 holds, the last term can be replaced by C||(5ou''|U||"''|U- By using
Garding's inequality, (ii), it follows that

(1 - CH'-')A{u\u'') < B{u\u'') + C||(?ou''|U||u''|U •

By the definition of the operators Q, and Lemma 1, we find that

B{u\ ti") = Yl B{u\ ul) = X: B{Q,u\ uj-).

t=0 »=0

The boundedness of B{-, •), (i), can now be used to obtain



Online LibraryXiao-Chuan CaiDomain decomposition algorithms for indefinite elliptic problems → online text (page 1 of 2)