Online Library → Maksymilian Dryja → Substructuring methods for parabolic problems → online text (page 1 of 1)

Font size

Computer Science Department

TECHNICAL REPORT

Substructuring Methods for Parabolic Problems

Maksymilian Dryja

Technical Report 529

November 1990

>Â«itr

NEW YORK UNIVERSITY

IfN (0 a;

I in -H Em

I rH JQ

I a -H iji o

|eh e c i-i

Department of Computer Science

Courant Institute of Mathematical Sciences

_ 251 MERCER STREET, NEW YORK, N.Y. 10012

NEW YORK UNP/ERSirV

COURANT .NSTiTUrt -.i^i^ARY

251 Mercer St Mew Yofh, UX VXn2

Substructuring Methods for Parabolic Problems

Maksymihan Dryja

Technical Report 529

November 1990

SUBSTRUCTURING METHODS FOR PARABOLIC PROBLEMS

Maksymilian Dryja '

Abstract

Domain decomposition methods without overlapping for the approximation of parabolic

problems are considered. Two kinds of methods are discussed. In the first method systems of

algebraic equations resulting from the approximation on each time level are solved iteratively

with a Neumann-Dirichlet preconditioner. The second method is direct and similar to certain

iterative methods with a Neumann-Neumann preconditioner. An analysis of convergence of

the methods is presented.

institute of Informatics, Warsaw University, PKiN p. 850, Poland. This work was supported in part by the

National Science Foundation under Grant NSF-CCR-8903003, and in part by Polish Scientific Grant R.P.I.IO.

1. Introduction. In this paper domain decmposition methods for solving discrete

parabolic problems are discussed. The discrete problems result from finite element and finite

difference approximations of parabolic problems with respect to the space and time variables,

respectively. For simplicity of presentation only piecewise linear, continuous approximation

on triangular elements and the backward Euler and Crank-Nicolson schemes are considered.

Two kinds of substructuring methods, i.e. domain decomposition methods which do not

use overlapping subregions, are constructed and analyzed. In the first method systems of

algebraic equations resulting from the approximation on each time level are solved iteratively

by a conjugate gradient method with a Neumann-Dirichlet preconditioner. As in the elliptic

case, it is shown that the rate of convergence is almost optimal with respect to h, the parameter

of triangulation, and that it is independent of the time step r; see Section 2.

Iterative substructuring methods with a Neumann-Dirichlet preconditioner for elliptic finite

element problems have been analyzed in [3], [4] and [5].

The second method is direct and similar to certain iterative substructuring methods for

elliptic finite element problems using a Neumann-Neumann preconditioner; see [1], [5]. A

solution at each time level is obtained in two fractional steps. The rate of convergence of the

method is of the order t^'^ + h provided that r is proportional to h; see Sections 3 and 4.

Most papers on domain decomposition methods are devoted to elliptic problems, see for

example [5] and the literature cited therein. Extensions of the methods to parabolic problems

have been considered in [2] and [6].

2. The differential and discrete problems. We consider the parabolic problem. Find

ue L^{0,T; H^i^)) n CÂ°{0,T; L'^iQ)) such that

(2.1a) (^ ,) = ifA) , (PeH^in), a.e. /e(o,r)

(2.16) {u,) , (t>eL^{n)

Here (â€¢,â€¢) is the Z'^-scalar product, a{u,v) = {Vu,Vv) + {u,v) and fi is a bounded polygonal

region in R'^. We assume that / G Z^(0,T; Z^(fi)) and uq Â£ H^{n). The problem (2.1) has a

unique solution and is stable, see for example [7].

We solve the problem (2.1) using a finite difference method (FDM) and a finite element

method (FEM) for the t and x variables, respectively. For simplicity only the backward Euler

and Crank-Nicolson and piecewise linear approximations are discussed. A triangulation of Q

is constructed as follows: We first divide Q. into triangular substructures Q^, with a parameter

H, and we then divide each of the fi,- into triangles Cj, with a parameter h. These form a

coarse and a fine triangulation of fi. We suppose that they are shape regular in the sense

common to finite element theory. V^{^) is the space of continuous, piecewise linear functions

on the fine triangulation, which are zero on dO.. The interval [0,T] is partitioned uniformly,

t^ = nT,n = 0,...,N, Nt = T.

The discrete problem is of the form: For n = 0, 1, . . . , A'^ â€” 1,

(2.2a) ({/^|^,(â€ž^

Combining this with the estimate for ||^j|||,2m.\) we obtain (3.7).

Proof of Theorem 3.1: The right inequality: It is enough to show that

{S^^K3,V3) < C{1 + \0g^f{S^^K3,V3)

n

(3.9)

Using Lemma 3.1, we have

where vd = {vi,^^)'^ is the solution of (3.4) and vd = {vi,V3)'^ with an arbitrary vi. Applying

Lemma 3.2 and then again Lemma 3.1, we obtain (3.9). The proof is complete.

We now define a preconditioner A for A of the form

/ ^11 ^13 \

i = ^22 A23

\ A"^ 4^ 4'^^ 4- 4^ A-'^ A,. I

\ ^13 ^23 ^33 ^ ^13"^11 '^IS /

Theorem 3.2. For any v Â£ V^{Q)

(3.10)

H -

{Av,v) < {Av,v) < 7(1 + log â€” ) {Av,v)

where 7 is a positive constant independent of k, H and r.

Proof: It is easy to see that

A = L'DL and A = V DL

where

(3.11:

D

( An

^

( ^11

A22

,

D =

A22

I

5('^'> y

\ Â»

.s-

1 ^^

^n ^13 \

L=

h

A22 A22

V

h

The generalized eigenvalue problem

Az = XAz , Z = (2l,22i '3)

reduces to

since the matrices D and D have the same first two block rows. Applying Theorem 3.1 we

obtain (3.10) and the proof is complete.

^From Theorem 3.2 foUows that the systems (2.3) with the matrix A can be solved itera-

tively using A as preconditioner in a conjugate gradient method. The number of iterations to

obtain the solution with accuracy e is on the order of log -(1 + log y). In each iteration step

a system with the matrix A is solved. For that the factorization A = {L^D)L is used. In each

step, this invovles solving two sets of the Dirichlet subproblems with the bilinear form b,{u,v)

for the D-type subregions and a set of the Neumann problems for the A'-type subregions.

The D-type subproblems are independent and can be solved in parallel. The Neumann

subproblems are coupled at the cross points, i.e. the vertices of A^-type subregions. We can

use a block Gaussian elimination or a capacitance matrix method for solving the systems

corresponding to these subproblems, cf. [4].

The connections at the cross points provide a mechanism for the global transportation of

information similar to that of a finite element approximation of an elliptic problem. As was

shown in [9], the condition number of any method without such a mechanism deteriorates at

least as fast as H~^. For parabolic problems the situation is different. As we will see below

this mechanism can be dropped if r j H^ is bounded cf. [2]. In particular, the set of Neumann

subproblems can be split into independent subproblems and solved in parallel. We now study

this case.

Let i4(^' denote the matrix

A22 A22,

Note that for u^v ^ V^{^)^ which are the solutions of (3.4),

{S^^K^.V:,) = iA^^Hv2,V3f,{u2,usf = (1 + t){v,u)l,(^^^ + r(VÂ«, VÂ«)^2(n^, ;

cf. Lemma 3.1. To get the preconditioner A for A, we replace /l'^^ by A''^^ which is defined

as follows: Let il^^k and fi// denote the sets of nodal points of the fine mesh in .Qat and the

coarse mesh in fi, respectively. Let Iqu G V'^{Q) be zero for x G ttj^i^h \ ^H and equal to u{x)

for X G fi//. We introduce a bilinear form c{u,v) by

(3.12) c(u,u) = (1 + r)/i^ Y^ u{x)v{x) + T ^ u{x)v{x)

xenN.h ^^"^'

+r(V(u - lou) , V(v - lov) )^2(n^) ,

and the matrix A'^' by

{A^''\u2,Usf ,(V2.Vsf)^r., =c{u,v),

Let

I(^) = ( ^4^ ^S ) , 5(^) = Ag^ - Al,A^^A2s .

\ ^23 "^33 /

By using (3.11), we find that

A = L'DL, D

( Au

A22

V 5'^)

Lemma 3.3. For all v e V'iil), v = {vi,V2,V3y

(3.13) foil + ^)~\l + log^)-\A^^KN,VN) < {A^^^vn.vn) < liiA^^^VN,VN)

where u/v = (^'2,^'3)'^ and the 7, are constants independent of h, H and t.

Proof: We first prove the right inequality. It is easy to show

Using the triangle and inverse inequalities, we get

i^v,Vv)L2^^^) )^Ui^\4>), 4>eV\^)

and

(4.16)

([/"+'/', ) ,

TECHNICAL REPORT

Substructuring Methods for Parabolic Problems

Maksymilian Dryja

Technical Report 529

November 1990

>Â«itr

NEW YORK UNIVERSITY

IfN (0 a;

I in -H Em

I rH JQ

I a -H iji o

|eh e c i-i

Department of Computer Science

Courant Institute of Mathematical Sciences

_ 251 MERCER STREET, NEW YORK, N.Y. 10012

NEW YORK UNP/ERSirV

COURANT .NSTiTUrt -.i^i^ARY

251 Mercer St Mew Yofh, UX VXn2

Substructuring Methods for Parabolic Problems

Maksymihan Dryja

Technical Report 529

November 1990

SUBSTRUCTURING METHODS FOR PARABOLIC PROBLEMS

Maksymilian Dryja '

Abstract

Domain decomposition methods without overlapping for the approximation of parabolic

problems are considered. Two kinds of methods are discussed. In the first method systems of

algebraic equations resulting from the approximation on each time level are solved iteratively

with a Neumann-Dirichlet preconditioner. The second method is direct and similar to certain

iterative methods with a Neumann-Neumann preconditioner. An analysis of convergence of

the methods is presented.

institute of Informatics, Warsaw University, PKiN p. 850, Poland. This work was supported in part by the

National Science Foundation under Grant NSF-CCR-8903003, and in part by Polish Scientific Grant R.P.I.IO.

1. Introduction. In this paper domain decmposition methods for solving discrete

parabolic problems are discussed. The discrete problems result from finite element and finite

difference approximations of parabolic problems with respect to the space and time variables,

respectively. For simplicity of presentation only piecewise linear, continuous approximation

on triangular elements and the backward Euler and Crank-Nicolson schemes are considered.

Two kinds of substructuring methods, i.e. domain decomposition methods which do not

use overlapping subregions, are constructed and analyzed. In the first method systems of

algebraic equations resulting from the approximation on each time level are solved iteratively

by a conjugate gradient method with a Neumann-Dirichlet preconditioner. As in the elliptic

case, it is shown that the rate of convergence is almost optimal with respect to h, the parameter

of triangulation, and that it is independent of the time step r; see Section 2.

Iterative substructuring methods with a Neumann-Dirichlet preconditioner for elliptic finite

element problems have been analyzed in [3], [4] and [5].

The second method is direct and similar to certain iterative substructuring methods for

elliptic finite element problems using a Neumann-Neumann preconditioner; see [1], [5]. A

solution at each time level is obtained in two fractional steps. The rate of convergence of the

method is of the order t^'^ + h provided that r is proportional to h; see Sections 3 and 4.

Most papers on domain decomposition methods are devoted to elliptic problems, see for

example [5] and the literature cited therein. Extensions of the methods to parabolic problems

have been considered in [2] and [6].

2. The differential and discrete problems. We consider the parabolic problem. Find

ue L^{0,T; H^i^)) n CÂ°{0,T; L'^iQ)) such that

(2.1a) (^ ,) = ifA) , (PeH^in), a.e. /e(o,r)

(2.16) {u,) , (t>eL^{n)

Here (â€¢,â€¢) is the Z'^-scalar product, a{u,v) = {Vu,Vv) + {u,v) and fi is a bounded polygonal

region in R'^. We assume that / G Z^(0,T; Z^(fi)) and uq Â£ H^{n). The problem (2.1) has a

unique solution and is stable, see for example [7].

We solve the problem (2.1) using a finite difference method (FDM) and a finite element

method (FEM) for the t and x variables, respectively. For simplicity only the backward Euler

and Crank-Nicolson and piecewise linear approximations are discussed. A triangulation of Q

is constructed as follows: We first divide Q. into triangular substructures Q^, with a parameter

H, and we then divide each of the fi,- into triangles Cj, with a parameter h. These form a

coarse and a fine triangulation of fi. We suppose that they are shape regular in the sense

common to finite element theory. V^{^) is the space of continuous, piecewise linear functions

on the fine triangulation, which are zero on dO.. The interval [0,T] is partitioned uniformly,

t^ = nT,n = 0,...,N, Nt = T.

The discrete problem is of the form: For n = 0, 1, . . . , A'^ â€” 1,

(2.2a) ({/^|^,(â€ž^

Combining this with the estimate for ||^j|||,2m.\) we obtain (3.7).

Proof of Theorem 3.1: The right inequality: It is enough to show that

{S^^K3,V3) < C{1 + \0g^f{S^^K3,V3)

n

(3.9)

Using Lemma 3.1, we have

where vd = {vi,^^)'^ is the solution of (3.4) and vd = {vi,V3)'^ with an arbitrary vi. Applying

Lemma 3.2 and then again Lemma 3.1, we obtain (3.9). The proof is complete.

We now define a preconditioner A for A of the form

/ ^11 ^13 \

i = ^22 A23

\ A"^ 4^ 4'^^ 4- 4^ A-'^ A,. I

\ ^13 ^23 ^33 ^ ^13"^11 '^IS /

Theorem 3.2. For any v Â£ V^{Q)

(3.10)

H -

{Av,v) < {Av,v) < 7(1 + log â€” ) {Av,v)

where 7 is a positive constant independent of k, H and r.

Proof: It is easy to see that

A = L'DL and A = V DL

where

(3.11:

D

( An

^

( ^11

A22

,

D =

A22

I

5('^'> y

\ Â»

.s-

1 ^^

^n ^13 \

L=

h

A22 A22

V

h

The generalized eigenvalue problem

Az = XAz , Z = (2l,22i '3)

reduces to

since the matrices D and D have the same first two block rows. Applying Theorem 3.1 we

obtain (3.10) and the proof is complete.

^From Theorem 3.2 foUows that the systems (2.3) with the matrix A can be solved itera-

tively using A as preconditioner in a conjugate gradient method. The number of iterations to

obtain the solution with accuracy e is on the order of log -(1 + log y). In each iteration step

a system with the matrix A is solved. For that the factorization A = {L^D)L is used. In each

step, this invovles solving two sets of the Dirichlet subproblems with the bilinear form b,{u,v)

for the D-type subregions and a set of the Neumann problems for the A'-type subregions.

The D-type subproblems are independent and can be solved in parallel. The Neumann

subproblems are coupled at the cross points, i.e. the vertices of A^-type subregions. We can

use a block Gaussian elimination or a capacitance matrix method for solving the systems

corresponding to these subproblems, cf. [4].

The connections at the cross points provide a mechanism for the global transportation of

information similar to that of a finite element approximation of an elliptic problem. As was

shown in [9], the condition number of any method without such a mechanism deteriorates at

least as fast as H~^. For parabolic problems the situation is different. As we will see below

this mechanism can be dropped if r j H^ is bounded cf. [2]. In particular, the set of Neumann

subproblems can be split into independent subproblems and solved in parallel. We now study

this case.

Let i4(^' denote the matrix

A22 A22,

Note that for u^v ^ V^{^)^ which are the solutions of (3.4),

{S^^K^.V:,) = iA^^Hv2,V3f,{u2,usf = (1 + t){v,u)l,(^^^ + r(VÂ«, VÂ«)^2(n^, ;

cf. Lemma 3.1. To get the preconditioner A for A, we replace /l'^^ by A''^^ which is defined

as follows: Let il^^k and fi// denote the sets of nodal points of the fine mesh in .Qat and the

coarse mesh in fi, respectively. Let Iqu G V'^{Q) be zero for x G ttj^i^h \ ^H and equal to u{x)

for X G fi//. We introduce a bilinear form c{u,v) by

(3.12) c(u,u) = (1 + r)/i^ Y^ u{x)v{x) + T ^ u{x)v{x)

xenN.h ^^"^'

+r(V(u - lou) , V(v - lov) )^2(n^) ,

and the matrix A'^' by

{A^''\u2,Usf ,(V2.Vsf)^r., =c{u,v),

Let

I(^) = ( ^4^ ^S ) , 5(^) = Ag^ - Al,A^^A2s .

\ ^23 "^33 /

By using (3.11), we find that

A = L'DL, D

( Au

A22

V 5'^)

Lemma 3.3. For all v e V'iil), v = {vi,V2,V3y

(3.13) foil + ^)~\l + log^)-\A^^KN,VN) < {A^^^vn.vn) < liiA^^^VN,VN)

where u/v = (^'2,^'3)'^ and the 7, are constants independent of h, H and t.

Proof: We first prove the right inequality. It is easy to show

Using the triangle and inverse inequalities, we get

i^v,Vv)L2^^^) )^Ui^\4>), 4>eV\^)

and

(4.16)

([/"+'/', ) ,

1

Online Library → Maksymilian Dryja → Substructuring methods for parabolic problems → online text (page 1 of 1)