Xiao-Chuan Cai. # Domain decomposition algorithms for indefinite elliptic problems online

. **(page 1 of 2)**

Online Library → Xiao-Chuan Cai → Domain decomposition algorithms for indefinite elliptic problems → online text (page 1 of 2)

Font size

Computer Science Department

TECHNICAL REPORT

Domain Decomposition Algorithms for

Indefinite Elliptic Problems

Xiao-Chuan Cai

Olof B. Wtdlund

Technical Report 506

May 1990

NEW YORK UNIVERSITY

lo

I in

lo:^ (0

Iw o

c a>

O TD

-t C

4J -H

in

e

0)

CO U rH

O O XI

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

lir.il < (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

defined.

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

and

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)

and

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

8

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

valid:

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

â€¢=0

and

6(2) = qWu' = Qou' + J2P'^'-

Â«=i

Each of these terms can be computed by solving a problem in a subspace, since

by equation (3),

and

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

and

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

The special constant Co is introduced in Lemma 1.

Remarks:

(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

N

1=0

and

Â»=0

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

and

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

that

â€¢'fA-

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

bounded.

10

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

then,

N

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

1=0

and

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

and

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

f:B(Q,u\u?)

TECHNICAL REPORT

Domain Decomposition Algorithms for

Indefinite Elliptic Problems

Xiao-Chuan Cai

Olof B. Wtdlund

Technical Report 506

May 1990

NEW YORK UNIVERSITY

lo

I in

lo:^ (0

Iw o

c a>

O TD

-t C

4J -H

in

e

0)

CO U rH

O O XI

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

lir.il < (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

defined.

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

and

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)

and

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

8

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

valid:

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

â€¢=0

and

6(2) = qWu' = Qou' + J2P'^'-

Â«=i

Each of these terms can be computed by solving a problem in a subspace, since

by equation (3),

and

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

and

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

The special constant Co is introduced in Lemma 1.

Remarks:

(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

N

1=0

and

Â»=0

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

and

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

that

â€¢'fA-

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

bounded.

10

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

then,

N

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

1=0

and

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

and

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

f:B(Q,u\u?)

1 2

Online Library → Xiao-Chuan Cai → Domain decomposition algorithms for indefinite elliptic problems → online text (page 1 of 2)