MULTI-PARAMETERIZED SCHWARZ ALTERNATING METHOD FOR 3D-PROBLEM†

Journal of Applied Mathematics & Informatics.
2015.
Jan,
33(1_2):
33-44

- Received : September 10, 2014
- Accepted : November 05, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

The convergence rate of a numerical procedure based on Schwarz Alternating Method(SAM) for solving elliptic boundary value problems depends on the selection of the interface conditions applied on the interior boundaries of the overlapping subdomains. It has been observed that the
Robin condition
(mixed interface condition), controlled by a parameter, can optimize SAM’s convergence rate. In
[7]
, one formulated the
multi-parameterized SAM
and determined the optimal values of the multi-parameters to produce the best convergence rate for one-dimensional elliptic boundary value problems. Two-dimensional implementation was presented in
[8]
. In this paper, we present an implementation for three-dimensional problem.
AMS Mathematics Subject Classification : 65N35, 65N05, 65F10.
smaller
BVP’s on a number of subdomains with appropriate
interface conditions
on the interior boundaries of the overlapping areas, whose solutions are coupled through some iterative scheme to produce an approximation of the solution of the original BVP. It is known
[1]
,
[6]
that under certain conditions the sequence of the solutions of the subproblems converges to the solution of the original problem.
One of the objectives of this research is to study a class of Schwarz alternating methods (SAM’s) whose interface conditions are parameterized and estimate the values of the parameters involved that speed up the convergence of these methods for a class of BVP’s. In the context of elliptic BVP’s the most commonly used
interface conditions
are of Dirichlet type. For this class of numerical SAM, there are several studies about the convergence, which include
[10]
,
[12]
,
[15]
,
[16]
,
[13]
,
[2]
,
[11]
,
[17]
. The effect of parameterized mixed interface conditions has been considered by a number of researchers
[3]
,
[14]
,
[5]
,
[18]
. Among them, Tang proposed a generalized Schwarz splitting
[18]
. The main part of his approach to the solution of a BVP is to use the mixed boundary condition, known as
Robin condition
,
on the artificial boundaries. In
[5]
, a multi-parameter SAM is formulated in which the mixed boundary conditions
are controlled by a distinct parameter
ω_{i}
for the
i
-th overlapping area. Fourier analysis is applied to determine the values of
ω_{i}
parameters that make the convergence factor of SAM be zero.
In
[7]
, one formulated a multi-parameter SAM at the matrix level where the parameters
α_{i}
are used to impose mixed interface conditions. The relation between the parameters
α_{i}
and
ω_{i}
is given by
(Refer to
[7]
), where
h
is the grid size. One determined analytically the optimal values of
α_{i}
’s for one-dimensional(1-dim) boundary value problems, which minimize the spectral radius of the block Jacobi iteration matrix associated with the SAM matrix.
For two-dimensional (2-dim) boundary value problems
[8]
, we used distinct multi-parameter
α_{i,j}
for each
j
-th grid point of the
i
-th interfaces of the subdomains to get the best convergence, while we used a fixed parameter
α_{i}
along the
i
-th interfaces of the subdomains in the previous paper
[7]
.
In this paper, we consider the case of three-dimensional (3-dim) problem. Here we also use distinct multi-parameter
α_{i,j,k}
for each (
j, k
)-th grid point of the
i
-th interfaces of the subdomains to get sucessfully the best convergence.
In section 2, we summarize the result of the multi-parameterized SAM on 1-dim problem, which has been presented in
[7]
and is nessary for notations in the following section. In section 3, we formulate the multi-parameterized SAM on 3-dim problem where we impose distinct parameters on each grid point on the interfaces of the subdomains. We show that the 3-dim case can be reduced to the one-dimensional ones and obtain the optimal values of the multi-parameters which minimize the spectral radius of the block Jacobi iteration matrix associated with the SAM matrix of 3-dim problem.
with
q
≥ 0 being a constant. We will formulate a numerical instance of SAM based on a
κ
-way decomposition ( i.e. the number of subdomains is
κ
) of the problem domain. An example of
κ
-way decomposition is depicted in
Figure 1
.
An example of the κ -way decomposition of the domain of one dimensional boundary value problem (4).
Let
T_{j}
(
x, y, z
) be a
j
×
j
tridiagonal matrix such that
and let
If we discretize the problem (4) by a second order central divided difference discretization scheme with a uniform grid of mesh size
we obtain a linear system
where
A
=
T_{n}
(
β
) with
β
= 2 +
qh
^{2}
.
If we consider 3-way (
κ
= 3) decomposition, then
Ax
=
f
has three overlapping diagonal blocks as follows.
where
T_{j}
=
T_{j}
(
β, β, β
) in (5) and
m
and
l
are the numbers of nodes in each subdomain and the overlapping regions, respectively, such that
In (8), the matrix
E
have zero elements everywhere except for a 1 at the rightmost top position and the matrix
F
have zero elements everywhere except for a 1 at the leftmost bottom position. So the matrices
E
and
F
have compatible sizes with the following forms.
The numerical version of SAM
[17]
for the problem (4) is equivalent to a
block Gauss-Seidel iteration procedure
for a new linear system, called
Schwarz Enhanced Matrix Equation
,
where
Ã
(
β
) means that
Ã
is a function of
β
. Note that the solution
x
of (7) is obtained from the solution
of (10), vice versa. In
[18]
, it is shown that a good choice of the splitting of
T_{l}
’s can significantly improve the convergence of SAM. Applying for some splittings of
T_{l}
’s into
Ã
in (11), we have a new equation
with
where
B_{i}
,
C′_{i}
,
i
= 1, 2 are some matrices such that (
B_{i}
−
C′_{i}
) is non-singular and
Note that two linear system (10) and (12) are equivalent in the sense that they have the same solutions. If
C′_{i}
and
C_{i}
are chosen such that they are the
l
×
l
matrices with all zero entries except for an
α_{i}
in the positions (1, 1) and (
l, l
), respectively, as follows,
the resulting matrix
A′
is given as follows
where
T_{m}
(
x, y, z
)’s are
m
×
m
matrices defined in (5) and
E′_{i}
’s are the
m
×
m
matrices with zero elements everywhere except that
and
F_{i}′
’s are the
m
×
m
matrices with zero elements everywhere except that
If the number of subdomains
κ
is more than 3, the matrix
A′
is a block
κ
×
κ
matrix of the form
where
a
= (
α
_{0}
,
α
_{1}
,
α
_{2}
, · · · ,
α_{κ}
) with
α_{0}
=
α_{κ}
= 0 and
G_{i}
’s are defined as
We call the matrix
A′
as
Multi-Parameterized Enhanced Matrix
. If we define
with
a
= (
α
_{0}
,
α
_{1}
,
α
_{2}
, · · · ,
α_{κ}
) then we can write the multi-parameterized enhanced matrix
A′
as
which is called
a Multi-Parameterized Schwarz Splitting (MPSS)
.
The convergence behavior of MPSS depends on the spectral radius of the following block Jacobi matrix
Note that
J
is a function of the parameters
α_{i}
’s, which correspond to the parameters
ω_{i}
’s in the mixed interface condition (2), respectively. The convergence rate of SAM can be optimized by controlling these parameters
α_{i}
’s. In
[7]
, one determined the optimal values of the multi-parameter
α_{i}
’s that make the spectral radius of the block Jacobi matrix
J
in (21) to be zero. The result of
[7]
is presented in the following theorem.
Theorem 2.1.
Let
with β
= 2 +
qh
^{2}
and let p
∈ {1, 2, · · · ,
κ
− 1}
and let
If the values α_{i} , i
= 0, 1, · · · ,
κ, are given by
then the spectral radius of the block Jacobi matrix J in (21) is zero.
where Γ is the boundary of Ω ≡ (0, 1)×(0, 1)×(0, 1) and
q
≥ 0 is a constant. We formulate a SAM based on a
κ
-way splitting of the domain Ω, i.e., we decompose our domain into
κ
overlapping subdomains Ω
_{i}
along the
x
_{1}
-axis and make a strip-type decomposition of the cube domain Ω (for instance, see
Figure 2
). Next we apply the interface conditions on the two interior boundaries between subdomains Ω
_{i}
and Ω
_{i}
_{+1}
. Let
ℓ
be the length of the overlap in
x
_{1}
-direction and
η
be the length of each subdomain in the same direction.
Figure 2
depicts such a 3-way splitting of the unit cube Ω.
A 3-way splitting of the unit cube Ω.
To begin our analysis we use a 7-point finite difference discretization scheme with uniform grid of mesh size
on all of
x
_{1}
-,
x
_{2}
- and
x
_{3}
- axes and discretize the BVP in (22) to obtain a linear system of the form
The natural ordering of the nodes is adopted starting from the origin and going in the
x
_{3}
-direction first, and then
x
_{2}
- and
x
_{1}
-direction in turn, so that the resulting matrix
A
can be partitioned into block matrices corresponding to the subdomains, respectively. Using tensor product notation ⊗ (See
[4]
, and
[9]
in which tensor products in connection with BVP’s were introduced.), the matrix
B
in (23) can be written as
where
T_{j}
(
x
) is defined in (6) and
β
= 2 +
qh
^{2}
.
Define
such that
n
=
κm
−
l
(
κ
−1) and
The numerical version of SAM for the problem (22) is equivalent to
a block Gauss-Seidel iteration procedure
for a new linear system, called the
Schwarz Enhanced Matrix Equation
,
with
where
I_{κm}
is the
κm
×
κm
identity matrix and
Ã
(
β
) is the
κ
×
κ
block matrix as that defined in (11), which is the case of
κ
= 3. Note that each diagonal block in
Ã
(
β
) is
m
×
m
matrix. .
Let
X_{n}
be the
n
×
n
orthogonal matrix whose columns are the eigenvectors of the matrix
T_{n}
(2). Since the eigenvalues of the matrix
T_{n}
(2) are known to be
we can write
Let
X
=
I_{κm}
⊗
I_{n}
⊗
X_{n}
, then its inverse is given by
so we have
If
P
is the permutation matrix that maps
for
i
= 1, 2, · · · ,
κm
,
j
= 1, 2, · · · ,
n, k
= 1, 2, · · · ,
n
, then we have
Note that the solution
of linear system (25) is obtained by
if we solve the linear system
where
in (25).
Likewise, using
Y
=
I_{n}
⊗
I_{κm}
⊗
X_{n}
, we have
If
Q
is the permutation matrix that maps
for
i
= 1, 2, · · · ,
κm
,
j
= 1, 2, · · · ,
n, k
= 1, 2, · · · ,
n
, then we have
where
ζ_{j,k}
=
β
+
γ_{j}
+
γ_{k}
for
j
= 1, 2, · · · ,
n
and
k
= 1, 2, · · · ,
n
and
which represents a diagonal matrix of diagonal matrices of entries
s
_{(}
_{j,k}
_{)}
’s.
Note that the solution
of linear system (29) is obtained by
if we solve the linear system
where
with
in (29), so that
with
in (25). Finally
in (25) is computed by
with
in (32).
From (30) and (32), we know that the three-dimensional problem (25) is reduced to
n
^{2}
number of one dimensional problems
where
is the corresponding sub-vector of
.
The
Multi-Parameterized Schwarz Enhanced Matrix
for
in (30) is defined as
where
A′
(
x
,
a
) is defined in (17). If we let
where
M
(
x
,
a
) and
N
(
x
,
a
) are defined in (19), then we can write the multi-parameterized enhanced matrix
B′
in (33) as
which is called a
Multi-Parameterized Schwarz Splitting (MPSS)
. The convergence behavior of MPSS depends on the spectral radius of the following block Jacobi matrix
where
for
j
= 1, 2, · · · ,
n
and for
k
= 1, 2, · · · ,
n
.
In
[7]
, one failed to determine a parameter vector
a
such that the spectral radius of the block Jacobi matrix
J
in (36) is zero because it is not possible to find such a parameter vector
a
that makes all of the spectral radii of the diagonal blocks
L_{j,k}
(
a
)’s in (36) zero simultaneously.
So instead of fixed parameter
a
, we adopt multi-parameter vector
a
_{j,k}
for each diagonal block as follows
where
for
j
= 1, 2, · · · ,
n
and
k
= 1, 2, · · · ,
n
. Note these triple indices (
i, j, k
) in multi-parameter
α_{i,j,k}
are related to the idea that one adopts variable parameter
ω_{i}
(
y, z
) instead of constant parameter
ω_{i}
in (2) along the
i
-th interface, i.e., we have
as the mixed interface condition on the
i
-th interface boundary.
Now, using these triple-index multi-parameter
α_{i,j,k}
’s, we have the following theorem for three-dimensional multi-parameterized Schwarz splitting
B′
=
M
−
N
in (35).
Theorem 3.1.
For j
= 1, 2, · · · ,
n and k
= 1, 2, · · · ,
n
,
with ζ_{j,k} in (30) and let p
∈ {1, 2, · · · ,
κ
− 1}
and let
If the values α_{i,j,k} for each j
= 1, 2, · · · ,
n and each k
= 1, 2, · · · ,
n and each i
= 0, 1, · · · ,
κ are given by
then the spectral radius of the block Jacobi matrix J in (37) is zero.
Multi-Parameterized SAM (MPSAM)
with those of the
Classical SAM
. Consider the following model problem
where Γ is the boundary of Ω, with solution
In all the experiments, the vector with all its components 0.0 was used as initial guess of the solution vector. The
relative residual r_{κ}
is computed as the ratio of
ℓ
_{2}
-norms of the residuals of the corresponding system of equations after
κ
iterations, i.e.,
Table 1
shows the relative residuals of
SAM
computed after
κ
iterations for each number of subdomains (
κ
= 2, 4, 8), and number of local grids (
m
= 8) and minimum and half overlaps (
l
= 1, 4) .
Table 2
shows the performance of
MPSAM
under the same conditions. It shows the optimal convergence. Indeed, the relative residuals by
MPSAM
are less than 5.02 × 10
^{−15}
after
κ
iterations for the case of
κ
subdomains.
The classical SAM is applied to the BVP (39).
The MPSAM is applied to the BVP (39).
The convergence rate is very sensitive to the computed optimal value of parameter
α_{i,j,k}
’s and the symmetric choice of them (i.e. Take
p
= [
κ
/2] in Theorem (3.1)) reduces the error propagation when we compute the optimal value of parameters
α_{i,j,k}
’s.
Sang-Bae Kim received a Ph.D from Purdue University, USA, in 1993. He is a professor of Department of Mathematics, Hannam University, Korea. His research interests are numerical linear algebra, scientific computing.
Department of Mathematics, Hannam University, Daejon 306-791, Korea
e-mail: sbk@hnu.kr

1. Introduction

Schwarz-type alternating methods have become some of the most important approaches in domain decomposition techniques for solution of the boundary value problems (BVP’s). These methods are based on a decomposition of the BVP domain into overlapping subdomains. The original BVP is reduced to a set of
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

2. Multi-Parameterized Schwarz Splitting for 1-dim problem

We consider the two-point boundary value problem:
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. Multi-Parameterized Schwarz Splitting for 3-dim Problem

Consider the three-dimensional boundary value problem
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. Numerical Experiments

In this section, we present a numerical experiment to prove the result of the previous section. we will compare the results of
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

The classicalSAMis applied to the BVP (39).

PPT Slide

Lager Image

TheMPSAMis applied to the BVP (39).

PPT Slide

Lager Image

BIO

Courant R.
,
Hilbert D.
1962
Methods of mathematical physics, vol 2
Willey
New York

Dryja M.
1989
An additive Schwarz algorithm for two- and three-dimensional finite element elliptic problems, Domain Decomposition Methods (T. Chan, R. Glowinski, J. Periaux, and O. Widlund, eds.)
SIAM
168 -
172

Evans D.J.
,
Kang L.-S.
,
Chen Y.-P.
,
Shao J.-P.
(1987)
The convergence rate of the Schwarz alternating procedure (iv) : With pseudo-boundary relaxation factor
Intern. J. Computer Math.
21
185 -
203
** DOI : 10.1080/00207168708803565**

Halmos P.R.
1958
Finite-dimensional Vector Spaces
Van Nostrand
Princeton, N.J.

Kang L.-S.
1989
Domain decomposition methods and parallel algorithms, Second International Symposium on Domain Decomposition Methods for Partial Differential Equations (Philadelphia, PA) (Tony F. Chan, Roland Glowinski, Jacques Périaux, and Olof B. Widlund, eds.)
SIAM
207 -
218

Kantorovich L.V.
,
Krylov V.I.
1958
Approximate methods of higher analysis
4th ed.
P. Noordhoff Ltd
Groningen, The Netherlands

Kim S.-B.
,
Hadjidimos A.
,
Houstis E.N.
,
Rice J.R.
(1996)
Multi-parametrized schwarz splittings for elliptic boundary value problems
Math. and Comp. in Simulation
42
47 -
76
** DOI : 10.1016/0378-4754(95)00111-5**

Kim S.-B.
(2011)
Two-dimensional Muti-Parameterized Schwarz Alternating Method
J. Appl. Math. & Informatics
29
161 -
171

Lynch R.E.
,
Rice J.R.
,
Thomas D.H.
(1964)
Direct solution of partial difference equations by tensor products
Numer. Math.
6
185 -
189
** DOI : 10.1007/BF01386067**

Miller K.
(1965)
Numerical analogs to the Schwarz alternating procedure
Numer. Math.
7
91 -
103
** DOI : 10.1007/BF01397683**

Oliger J.
,
Skamarock W.
,
Tang W.P.
1986
Schwarz alternating methods and its SOR accelerations, Tech. report
Department of Computer Science, Stanford University

Rodrigue G.
(1985)
Inner/outer iterative methods and numerical Schwarz algorithms
J. Parallel Computing
2
205 -
218
** DOI : 10.1016/0167-8191(85)90003-1**

Rodrigue G.
,
Saylor P.
1985
Inner/outer iterative methods and numerical Schwarz algorithms-ii
IBM
Proceedings of the IBM Conference on Vector and Parallel Computations for Scientific Computing

Rodrigue G.
,
Shah S.
1989
Pseudo-boundary conditions to accelerate parallel Schwarz methods, Parallel Supercomputing : Methods, Algorithms, and Applications (New York) (G. Carey, ed.)
Wiley
77 -
87

Rodrigue G.
,
Simon J.
1984
A generalization of the numerical Schwarz algorithm, Computing Methods in Applied Sciences and Engineering VI (Amsterdam,New York,Oxford) (R. Glowinski and J. Lions, eds.)
North-Holland
273 -
281

Rodrigue G.
,
Simon J.
1984
Jacobi splitting and the method of overlapping domains for solving elliptic PDE’s, Advances in Computer Methods for Partial Differential Equations V (R. Vichnevetsky and R. Stepleman, eds.)
IMACS
383 -
386

Tang W.P.
,
Ph.D. thesis
1987
Schwarz Splitting and Template Operators
Department of Computer Science, Stanford University
Ph.D. thesis

Tang W.P.
(1992)
Generalized Schwarz splittings
SIAM J. Sci. Stat. Comput.
13
573 -
595
** DOI : 10.1137/0913032**

Citing 'MULTI-PARAMETERIZED SCHWARZ ALTERNATING METHOD FOR 3D-PROBLEM†
'

@article{ E1MCA9_2015_v33n1_2_33}
,title={MULTI-PARAMETERIZED SCHWARZ ALTERNATING METHOD FOR 3D-PROBLEM†}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.033}, DOI={10.14317/jami.2015.033}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={KIM, SANG-BAE}
, year={2015}
, month={Jan}