Advanced
MULTI-PARAMETERIZED SCHWARZ ALTERNATING METHOD FOR 3D-PROBLEM†
MULTI-PARAMETERIZED SCHWARZ ALTERNATING METHOD FOR 3D-PROBLEM†
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 33-44
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : September 10, 2014
  • Accepted : November 05, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
SANG-BAE KIM

Abstract
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.
Keywords
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 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 ,
PPT Slide
Lager Image
on the artificial boundaries. In [5] , a multi-parameter SAM is formulated in which the mixed boundary conditions
PPT Slide
Lager Image
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
PPT Slide
Lager Image
(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.
2. Multi-Parameterized Schwarz Splitting for 1-dim problem
We consider the two-point boundary value problem:
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
An example of the κ-way decomposition of the domain of one dimensional boundary value problem (4).
Let Tj ( x, y, z ) be a j × j tridiagonal matrix such that
PPT Slide
Lager Image
and let
PPT Slide
Lager Image
If we discretize the problem (4) by a second order central divided difference discretization scheme with a uniform grid of mesh size
PPT Slide
Lager Image
we obtain a linear system
PPT Slide
Lager Image
where A = Tn ( β ) with β = 2 + qh 2 .
If we consider 3-way ( κ = 3) decomposition, then Ax = f has three overlapping diagonal blocks as follows.
PPT Slide
Lager Image
where Tj = Tj ( β, β, β ) in (5) and m and l are the numbers of nodes in each subdomain and the overlapping regions, respectively, such that
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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 ,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
à ( β ) means that à is a function of β . Note that the solution x of (7) is obtained from the solution
PPT Slide
Lager Image
of (10), vice versa. In [18] , it is shown that a good choice of the splitting of Tl ’s can significantly improve the convergence of SAM. Applying for some splittings of Tl ’s into à in (11), we have a new equation
PPT Slide
Lager Image
with
PPT Slide
Lager Image
where Bi , C′i , i = 1, 2 are some matrices such that ( Bi C′i ) is non-singular and
PPT Slide
Lager Image
Note that two linear system (10) and (12) are equivalent in the sense that they have the same solutions. If C′i and Ci 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,
PPT Slide
Lager Image
the resulting matrix A′ is given as follows
PPT Slide
Lager Image
where Tm ( 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
PPT Slide
Lager Image
and Fi ’s are the m × m matrices with zero elements everywhere except that
PPT Slide
Lager Image
If the number of subdomains κ is more than 3, the matrix A′ is a block κ × κ matrix of the form
PPT Slide
Lager Image
where a = ( α 0 , α 1 , α 2 , · · · , ακ ) with α0 = ακ = 0 and Gi ’s are defined as
PPT Slide
Lager Image
We call the matrix A′ as Multi-Parameterized Enhanced Matrix . If we define
PPT Slide
Lager Image
with a = ( α 0 , α 1 , α 2 , · · · , ακ ) then we can write the multi-parameterized enhanced matrix A′ as
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
with β = 2 + qh 2 and let p ∈ {1, 2, · · · , κ − 1} and let
PPT Slide
Lager Image
If the values αi , i = 0, 1, · · · , κ, are given by
PPT Slide
Lager Image
then the spectral radius of the block Jacobi matrix J in (21) is zero.
3. Multi-Parameterized Schwarz Splitting for 3-dim Problem
Consider the three-dimensional boundary value problem
PPT Slide
Lager Image
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 Ω.
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where Tj ( x ) is defined in (6) and β = 2 + qh 2 .
Define
PPT Slide
Lager Image
such that n = κm l ( κ −1) and
PPT Slide
Lager Image
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 ,
PPT Slide
Lager Image
with
PPT Slide
Lager Image
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 Xn be the n × n orthogonal matrix whose columns are the eigenvectors of the matrix Tn (2). Since the eigenvalues of the matrix Tn (2) are known to be
PPT Slide
Lager Image
we can write
PPT Slide
Lager Image
Let X = Iκm In Xn , then its inverse is given by
PPT Slide
Lager Image
so we have
PPT Slide
Lager Image
If P is the permutation matrix that maps
PPT Slide
Lager Image
for i = 1, 2, · · · , κm , j = 1, 2, · · · , n, k = 1, 2, · · · , n , then we have
PPT Slide
Lager Image
Note that the solution
PPT Slide
Lager Image
of linear system (25) is obtained by
PPT Slide
Lager Image
if we solve the linear system
PPT Slide
Lager Image
where
PPT Slide
Lager Image
in (25).
Likewise, using Y = In Iκm Xn , we have
PPT Slide
Lager Image
If Q is the permutation matrix that maps
PPT Slide
Lager Image
for i = 1, 2, · · · , κm , j = 1, 2, · · · , n, k = 1, 2, · · · , n , then we have
PPT Slide
Lager Image
where ζj,k = β + γj + γk for j = 1, 2, · · · , n and k = 1, 2, · · · , n and
PPT Slide
Lager Image
which represents a diagonal matrix of diagonal matrices of entries s ( j,k ) ’s.
Note that the solution
PPT Slide
Lager Image
of linear system (29) is obtained by
PPT Slide
Lager Image
if we solve the linear system
PPT Slide
Lager Image
where
PPT Slide
Lager Image
with
PPT Slide
Lager Image
in (29), so that
PPT Slide
Lager Image
with
PPT Slide
Lager Image
in (25). Finally
PPT Slide
Lager Image
in (25) is computed by
PPT Slide
Lager Image
with
PPT Slide
Lager Image
in (32).
From (30) and (32), we know that the three-dimensional problem (25) is reduced to n 2 number of one dimensional problems
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the corresponding sub-vector of
PPT Slide
Lager Image
.
The Multi-Parameterized Schwarz Enhanced Matrix for
PPT Slide
Lager Image
in (30) is defined as
PPT Slide
Lager Image
where A′ ( x , a ) is defined in (17). If we let
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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 Lj,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
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 ,
PPT Slide
Lager Image
with ζj,k in (30) and let p ∈ {1, 2, · · · , κ − 1} and let
PPT Slide
Lager Image
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
PPT Slide
Lager Image
then the spectral radius of the block Jacobi matrix J in (37) is zero.
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 Multi-Parameterized SAM (MPSAM) with those of the Classical SAM . Consider the following model problem
PPT Slide
Lager Image
where Γ is the boundary of Ω, with solution
PPT Slide
Lager Image
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.,
PPT Slide
Lager Image
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 classicalSAMis applied to the BVP (39).
PPT Slide
Lager Image
The classical SAM is applied to the BVP (39).
TheMPSAMis applied to the BVP (39).
PPT Slide
Lager Image
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.
BIO
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
References
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