Maksymilian Dryja.

Substructuring methods for parabolic problems online

. (page 1 of 1)
Online LibraryMaksymilian DryjaSubstructuring methods for parabolic problems → online text (page 1 of 1)
Font size
QR-code for this ebook

Computer Science Department


Substructuring Methods for Parabolic Problems

Maksymilian Dryja
Technical Report 529

November 1990



IfN (0 a;

I in -H Em


I a -H iji o

|eh e c i-i

Department of Computer Science
Courant Institute of Mathematical Sciences




251 Mercer St Mew Yofh, UX VXn2

Substructuring Methods for Parabolic Problems

Maksymihan Dryja
Technical Report 529

November 1990


Maksymilian Dryja '


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)



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)


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




( An


( ^11



D =



5('^'> y

\ »


1 ^^

^n ^13 \



A22 A22



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),


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

\ ^23 "^33 /

By using (3.11), we find that

A = L'DL, D

( Au
V 5'^)

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

(3.13) foil + ^)~\l + log^)-\A^^KN,VN) < {A^^^ < 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\^)



([/"+'/', ) ,


Online LibraryMaksymilian DryjaSubstructuring methods for parabolic problems → online text (page 1 of 1)