Subscribe Now Subscribe Today
Abstract
Fulltext PDF
References

Research Article
New Finite Difference Domain Decomposition Algorithms for Two-Dimensional Heat Equation

Yuanfeng Jin, Lijie Zhao, Jingyuan Li and Tinghuai Ma
 
ABSTRACT
The domain decomposition scheme is a high efficient and useful method which is widely used in the field of the finite difference parallel computing on parabolic equation. The natural method of parallel solution of the partial differential equation is to divide the solution area into several sub-regions and then independently calculate the problem of each sub-region. To solve the two-dimensional heat equation on parallel computers, we present new domain decomposition algorithms wherein the space domain is divided into two independent sub-regions along with x-axis or divided into four independent sub-regions along with the x-axis and y-axis. The values of the interface points between sub-domains are calculated by Du Fort-Frankel scheme. The values of the interior points are solved by the fully implicit scheme.
Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Yuanfeng Jin, Lijie Zhao, Jingyuan Li and Tinghuai Ma, 2010. New Finite Difference Domain Decomposition Algorithms for Two-Dimensional Heat Equation. Information Technology Journal, 9: 704-709.

DOI: 10.3923/itj.2010.704.709

URL: http://scialert.net/abstract/?doi=itj.2010.704.709

INTRODUCTION

In recent years, with the need of great scale scientific computing and the maturity of parallel computing environments, domain decomposition method (Quarteroni and Valli, 1999; Dawson and Dupont, 1992; Marini Quarteroni, 1988; Mathew et al., 1998) has been an effective approach to solve partial differential equations numerically. There are a lot of good work in this field: Dawson et al. (1991), Wan et al. (2002), who made domain decomposition algorithm of the explicit-implicit scheme to let out D2 times over than the classical explicit scheme on the restriction of the stability and the convergence that is , but the accuracy achieved . The idea in Zhang (1998) is almost same with Dawson et al. (1991), however, the former used explicit scheme of Rodrigue and Wolitzer on the interface point. The stability condition is Δt/h2≤2; the error is o(Δt+h2). Peaceman and Rachford (1995) and Zhou and Yuan (1999) proposed the parallel difference format for parabolic equation with the error . The reference Zhang and Shen (2002) used the Saul’yev asymmetric difference scheme which is adopt the stride step H to use in the interface point, furthermore, constructed a new domain decomposition algorithm and give a prior error estimate which is in circumstances of two sub-regions and the stable condition is . In order to improve the accuracy of the interface point, the reference Du et al. (2001) considered the multi-step explicit scheme and the one-step high-level explicit scheme.

Domain decomposition algorithm for one-dimensional heat equation: Zuo and Yuan (2003) proposed a new domain decomposition algorithm for one-dimensional heat equation by using Du Fort-Frankel scheme at the interface points and the fully implicit scheme at the interior points.

Firstly problem of solving the one-dimensional heat equation is considered:

(1)

where, u°(x) is a given function.

For simplicity, at first we divide domain (0, 1) into only two sub-domains (0, ) and (, 1). Suppose N, M, D are positive integers. Let h=1/N and xi = ih, i = 0, ..., N. Take τ = Δt = T/M and tn = nΔt, with the assumption that = xk>0 for integer K. A related parameter is H = Dh and H≤min(, 1-).

We will refer to points (xi, tn) as boundary points if i = 0 or N, or if n = 0. Similarly, we refered to them as interface points if x = and n>0. Otherwise, they are interior points.

We defined a function u(x, t) at mesh point (xi, tn). Let uin = u(xi, tn). Also we defined two difference operators:

(2)

(3)

The one-dimensional finite difference domain decomposition algorithm designed in Zuo and Yuan (2003) is as follows:

Algorithm 1

Uin = uin at boundary points:

(4)

at interface points, n = 1, 2, ..., M

at interior points, n = 0, 1, 2, ..., M

at interface points, n = 0

where, Uin is the numerical solution of the exact solution of the problem (1). Algorithm 1 can be shown that the computation from time level n-1 to n is at first to solve the interface points by using Du Fort-Frankel scheme and then to solve the interior points on the two sub-domains (0, ) and (, 1) independently. For the solution Uin of Algorithm 1 it holds that:

Theorem 1: The truncation error of Algorithm 1 is:

It is generally required to limit the step site τ and h, when,

in the calculation to achieve the accuracy 0(Δt+h2).

Theorem 2: Algorithm 1 is absolutely stable.

In this study, new domain decomposition algorithms are presented for the two-dimensional heat equation based on Algorithm 1 in Zuo and Yuan (2003). The algorithms are unconditional stable and their truncation errors are:

New algorithms for the two-dimensional heat equation: Consider the following two-dimensional heat conduction equation, u(x, y, t) is a solution of the heat equation on Ω = (0,1)x(0, 1). Specifically, u satisfies:

(5)

We start a simple two-domain scheme. Take:

(6)

Let y1 = jh, j = 0, ..., N. In analogy with the one-dimensional case we will call a points (xi, yj, tn) as boundary points if n = 0 or if. Such a point with xi = will be an interface point if it is not a boundary point. The remaining points (xi, yj, tn) are in (Ω1∪Ω2)x(0, T] and are interior points. The values Uni,j will approximate . Defined the difference operators:

(7)

(8)

(9)

We extended the one-dimensional parabolic equation to two-dimensional one. At interface points we use the improved Du Fort-Frankel scheme; at interior points we use the full-implicit scheme. The algorithm is as follows:

Algorithm 2:

 
(10)

Algorithm 3:

(11)

Algorithm 4:

(12)

Stability and truncation error analysis of the new algorithms: In order to verify the stability of the Algorithm 2, 3 and 4, we developd the following lemmas:

Lemma 1: (Li, 2004) if b and c are real numbers and x1, x2 are the roots of x2-bx-c = 0,then we have |xi|<1, i = 1, 2 if and only if |b|#1-2<2.

Here, we only discuss the stability and error of Algorithm 4.

Theorem 3: Algorithm 4 is unconditional stable.

We only examine the difference scheme at interface points, the formula at interface points of Eq. 12 can be deformed into:

(13)

Transform it into its equivalent two-level difference equations:

(14)

Let U = (U, V)T and make to substitute the above formula, then:

(15)

(16)

the growth matrix is:

(17)

the characteristic equation of G(τ, k) is:

(18)

by Lemma 1, the characteristic roots of G(τ, k) satisfy the following condition:

(19)

It is able to get the growth matrix |G|#1, thus proving that the algorithm is unconditionally stable.

Similar as the proof of Theorem 3, the Algorithms 2 and 3 are unconditionally stable.

Theorem 4: The truncation error of Algorithm 4 is:

Proof: Here, we analysis the truncation error of Eq. 12 at point (i, j, n):

(20)

Similar as Algorithm 4, the truncation errors of Algorithm 2 and 3 are:

it is generally required to limit the step site τ and h, when τ→0, (τ/H)→0, in the calculation to achieve the accuracy 0(Δt+h2).

RESULTS

Let u°(x, y) = sin(πx)sin(πy) in the two-dimensional heat Eq. 5. Then the exact solution of Eq. 5 is:

In Table 1-6, N =20, D = 2, t = 0.5, x = 0.5 absolute error 1 denotes the absolute error between exact solution and Algorithm 1, absolute error 2 denotes the absolute error between exact solution and Algorithm 2, absolute error 3 denotes the absolute error between exact solution and Algorithm 3, absolute error 4 denotes the absolute error between exact solution and Algorithm 4.

Table 1 and 2 show the comparisons of the calculation results between Algorithm 2 and 1 when the grid ratio r is 0.4 and 8, respectively for two dimensional heat equation. From the numerical results we conclude that: if the value r≤2, the degrees of accuracy between two methods are comparable. While when the value r>2, the numerical solution of the Algorithm 1 begins to show the obvious instability. Algorithm 2 maintains the unconditional stability without degrading the overall approximation order.

Table 3 and 4 show the comparisons of the calculation results between Algorithm 3 and Algorithms 1 when the grid ratio r is 0.4 and 8 respectively for two-dimensional heat equation. From the numerical results we conclude that: if the value r≤2, the degrees of accuracy between two methods are comparable. While when the value r>2, the numerical solution of the Algorithm 1 begins to show the obvious instability. Algorithm 3 not only maintains the unconditional stability, but also does not decrease the overall approximation order.


Table 1: The numerical results when h = 0.05, Δt = 0.0001, r = 0.4

Table 2: The numerical results when h = 0.05, Δt = 0.0002, r = 8

Table 3: The numerical results when h = 0.05, Δt = 0.0001, r = 0.4

Table 4: The numerical results when h = 0.05, Δt = 0.0002, r = 8

Table 5: The numerical results when h = 0.05, Δt = 0.0001, r = 0.4

Table 6: The numerical results when h = 0.05, Δt = 0.0002, r = 8

Fig. 1: The exact solution when h = 0.01, Δt = 0.01, y = 0.01

The Table 5 and 6 show the comparisons of the calculation results between Algorithm 4 and Algorithm 1 when the grid ratio r is 0.4 and 8, respectively for two dimensional heat equation. Based on the numerical results, the following conclusions are drawn: if the value r≤2, the degrees of accuracy between two methods are comparable. When the value r>2, the numerical solution of the Algorithm 1 begins to show the obvious instability. Algorithm 4 maintains both the unconditional stability and the overall approximation order.

The real solution and approximate solution obtained from Algorithm 2 are shown in Fig. 1 and 2, respectively. The experimental results are obtained under the following conditions: h is 0.01; Δt is 0.01; y is 0.01.

From Fig. 1 and 2, we find that the approximate solution of Algorithm 2 is comparable with the exact solution of Algorithm 1. The truncation error of Algorithm 2 is:


Fig. 2: The approximate solution when h = 0.01, Δt = 0.01, y = 0.01

Moreover, this algorithm is absolute stable. This verifies the superiority of our algorithm.

CONCLUSION

In this study, we developd a novel domain decomposition method with better stability and calculation accuracy, while we obtain the stability condition and the maximum norm error estimates.

In the two-dimensional case, through integrating the interface, we use Du Fort-Frankel scheme to establish a series of domain decomposition methods. Those methods improve the stability condition when compared to the other methods which are proposed in the previous study.

Analysis results show that appropriately integrating the interface, particularly, the use of Du Fort-Frankel scheme can realize the domain decomposition, meanwhile, can greatly improve the stability conditions of the algorithm without decreasing the overall approximation order of the algorithm.

ACKNOWLEDGMENTS

This research was also supported by Natural science fund for colleges and universities in Jiangsu Province (08KJD520018), Natural Science Foundation from Nanjing University of Information and Science Technology (20080302).

REFERENCES
Dawson, C.N. and T.F. Dupont, 1992. Explicit/implicit conservative Galerkin domain decomposition procedures for parabolic problems. Math. Comput., 58: 21-34.
Direct Link  |  

Dawson, C.N., Q. Du and T.F. Dupont, 1991. A finite difference domain decomposition algorithm for numerical solution of the heat equation. Mathematics Comput., 57: 63-71.
Direct Link  |  

Du, Q., M. Mu and Z.N. Wu, 2001. Efficient parallel algorithms for parabolic problems. SIAM J. Numer. Anal., 39: 1469-1487.
Direct Link  |  

Li, A.F., 2004. Domain decomposition difference schemes for a class of variable coefficient parabolic probles. J. Shandong Univ., 5: 1-7.
Direct Link  |  

Marini, L.D. and A. Quarteroni, 1988. Domain Decomposition Methods for Partial Differential Equations. Oxford University Press, New York, UK., ISBN: 0198501781.

Mathew, T.P., P.L. Polyakov, G. Russo and J. Wang, 1998. Domain decomposition operator splittings for the solution of parabolic equations. SIAM J. Sci. Comput., 19: 912-932.
Direct Link  |  

Peaceman, A.W. and H.H. Rachford Jr., 1955. The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Applied Mathematics, 3: 28-41.

Quarteroni, A. and A. Valli, 1999. Domain Decomposition Methods for Partial Differential Equations. Oxford Science Publications, New York, UK., ISBN-10: 0198501781, pp: 376.

Wan, Z.S., B.L. Zhang and G.N. Chen, 2002. Design and analysis of finite difference domain decomposition algorithms for the two-dimensional heat equation. Proceeding of the 5th International Conference on Algorithms and Architectures for Parallel Processing, Oct. 23-25, IEEE Computer Society, Washington, DC, USA., pp: 174-178.

Zhang, A.L. and W.D. Shen, 2002. Notes on finite difference domain decomposition algorithm for the solution of heat equation. J. Numer. Methods Comp. Applied, 2: 51-90.
CrossRef  |  Direct Link  |  

Zhang, A.L., 1998. A note on explicit-implicit finite difference domain decomposition algorithm for the heat equation. Aeronautical Comput. Tech., 3: 51-54.
CrossRef  |  Direct Link  |  

Zhou, Y.L. and G.W. Yuan, 1999. General difference schemes with Intrinsic parallelism for semilinear parabolic systems of devergence type. JCM, 14: 337-352.
Direct Link  |  

Zuo, A.L. and G.W. Yuan, 2003. A new intrinsic parallel domain decomposition algorithm and its parallel programming. Int. Parallel Algorithms Comput. Environ. Symp. Memoir, 25: 70-78.

©  2014 Science Alert. All Rights Reserved
Fulltext PDF References Abstract