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,

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.

 

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

We consider the two-point boundary value 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.

FIGURE 1.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

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 = Tn (β) with β = 2 + qh2.

If we consider 3-way (κ = 3) decomposition, then Ax = f has three overlapping diagonal blocks as follows.

where Tj = Tj (β, β, β) 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 Tl’s can significantly improve the convergence of SAM. Applying for some splittings of Tl’s into à in (11), we have a new equation

with

where Bi, C′i, i = 1, 2 are some matrices such that (Bi − 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 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,

the resulting matrix A′ is given as follows

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

and Fi′’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 Gi’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 + qh2 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.

 

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

Consider the three-dimensional boundary value problem

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 x1-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 x1-direction and η be the length of each subdomain in the same direction. Figure 2 depicts such a 3-way splitting of the unit cube Ω.

FIGURE 2.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 x1-, x2- and x3- 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 x3-direction first, and then x2- and x1-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 Tj (x) is defined in (6) and β = 2 + qh2.

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 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 we can write

Let X = Iκm ⊗ In ⊗ Xn, 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 = In ⊗ Iκm ⊗ Xn, 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 n2 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 Lj,k(a)’s in (36) zero simultaneously.

So instead of fixed parameter a, we adopt multi-parameter vector aj,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.

 

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

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.

TABLE 1.The classical SAM is applied to the BVP (39).

TABLE 2.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.