A Class Of Explicit Parallel Algorithms For Solving 2D Poisson And Diffusion Equations

Several physical phenomena are modeled by diffusion equations and poisson equa-tions. The former usually exist in electrostatics, mechanical engineering and theoreti-cal physics, and the latter include chemical diffusion, heat conduction, medical science, biochemistry and certain biological process etc.. A lot of attention has been devoted to the introduction of several fast computational methods for solving these equations, which are derived from the discretization of many standard PDE's. At present, the large scale scientific and engineering computations need the parallel computer with massively parallel processors of higher speed and large memory and also need effective parallel numerical methods and parallel algorithms. The utilization of parallel com-puters offers a significant advantage in terms of cost and speed. Meanwhile, domain decomposition is a powerful tool, which can be used to divide the global problem into smaller sub-domains that can be solved in parallel, and also it is paid more attention due to their simpler construction and larger speed-up.Among modern numerical methods, the finite difference method is the earliest and most perfect method. So the finite difference method for solving parabolic and elliptic problems is always a focal which peoples are care about.The application of finite difference approximations to elliptic partial differential equations often results in a large set of simultaneous linear equation[1]. It is well known that iterative methods such as Jacobi, Gauss-Seidel, SOR methods [2,3], ultilizing the great speeds of mordern-day computers, are extensively used in large-scale computa-tions, which are normally considered as suitable approach for solving such system of equations. As we known, the parallel modules for Poisson equation are often solved by Jacobi iterative algorithm[4], since it has obvious parallelization. Fenhui et al.[5] constructed the new iteration method for elliptical equation by elimination between difference scheme of different nodes, and the method had same parallelism as Jacobi method and higher convergence rate. The successive overrelaxation (SOR) iterative algorithm can not be iterated in parallel obviously, at present there is a few of meth-ods, such as coloring method[6] and Parallel Point SOR method[7], which are weak to extend.And for numerical solution of time-dependent diffusion problems, there are two types of finite difference method, explicit and implicit difference methods. The ex-plicit method is easy to implement on parallel computer, and parallel efficiencies are higher, but it has severe time step restriction due to stability constraint [8]. The im-plicit method is not any time step restriction, but in each time step one has to solve a global linear or nonlinear algebraic system of equations which implementation on parallel computer is not straightforward. So it is worthy to constructing other new difference methods which have better stability, parallelism and high-precision. In the early eighties, Evans and Abdullah [9-11] proposed the idea which constructed group explicit method by appropriate combination of different Saul'yev asymmetric schemes. The group explicit method keeps the stability of numerical computing, and has bet-ter parallelism because it can be solved explicitly. Based on this, Zhang Baolin et al. [13-15] give out the idea which constructed the segment implicit schemes by using the Saul'yev [12] asymmetric schemes, and set up a variety of explicit-implicit and pure implicit alternating parallel methods by making use of alternate technology. These methods can keep the stability and parallelism. In addition, Peaceman and Rachford provide the Alternating Direction Implicit (ADI) method [16] which has some good properties. But for multiple instruction and multiple data stream (MIMD) parallel computer, since each parallel processor Layer in the calculation of an odd time or number of column values, and in even time line or number line layer calculated values, or is the opposite, and therefore most of the data at each time layer needs to send a processor to another processor, which is not very economical.Under the aborative guidance of Professor Wenqia Wang, the author constructed some efficient explicit and parallel difference algorithms for two-dimensional Poisson problem and diffusion problem which contain parallel computing, domain decompo-sition and alternating group explicit method. And the stability of these methods are proved to unconditionally stable and some numerical experiments indicate their applicability. Both theoretical analysis and numerical experiments show that these algorithms proposed in this dissertation are effective and reliable. The dissertation is divided into three chapters.In Chapter 1, a new finite difference parallel iterative (FDPI) algorithms for solv-ing 2D Poisson equation based on domain decomposition strategy are introduced. First the domain is divided into four sub-domains and four iterative schemes are constructed from the classical five-point difference scheme. Then the new algorithm is implemented differently with the number of iterations of odd or even. The convergence of the pre-sented algorithm is proved. Finally several numerical experiments are performed to examine the efficiency and accuracy of the iterative algorithm. And the algorithm is applicable to 2D variable coefficient elliptic problems. The work about Chapter 1 is published in《Numerical Methods for Partial Differential Equations》.The new idea of Chapter 1 is that although the iterative schemes are semi-implicit, they can be computed explicitly and in parallel in combining with the boundary condi-tions. Particularly, a relaxation factorωis added into the iterative schemes to improve the convergence rate and decrease the iteration number, in which the optimal relaxation factorωopt is obtained. The comparison between the numerical results that are derived from Jacobi, Gauss-Seidel iterative algorithms, Mathematics Stencil [5] method and the presented algorithm demonstrates that the presented algorithm has smaller num-ber of iterations, shorter computational time and faster convergence rate.Chapter 2 gives a new parallel SOR iterative (P-SOR) algorithm for solving 2D Poisson equation. The four successive overrelaxation (SOR) iterative schemes are used to implement the algorithm differently with the number of iterations of odd or even. Several numerical experiments are presented to examine the superior of the algorithm. The work about Chapter 2 has been submitted to《International Journal of Computer Mathematics》.The new idea of Chapter 2 is that, the well-known SOR iterative algorithm can not be iterated in parallel obviously, while this new algorithm (P-SOR) has intrinsic paral-lelization. Moreover, the results of numerical experiments show that P-SOR iterative algorithm should be adopted by comparing the time complexity, speedup and space complexity with Jacobi, Gauss-Seidel, Stencil [5] and FDPI in Chapter 1 algorithms. In Chapter 3, ar. efficient finite difference parallel algorithm for solving 2D diffusion equation are given, which are based on domain decomposition. First we constructs four new difference schemes to approximate the diffusion equation. Then the solution domain is divided into four sub-domains. Using the idea in Chapter 1 to implement the algorithm differently at odd or even time levels. The algorithm is unconditionally stable and has an accuracy of O(τ+h2). Finally, several numerical experiments indicates the applicability and the rate of convergence is nearly of order 2. The work about Chapter 3 has been submitted to《Applied Mathematics and Computation》.Chapter 4 provides a new alternating group explicit algorithm for 2D diffusion equation. Due to explicit method [10], the four difference schemes constructed in Chapter 3 are used to implement this new explicit algorithm differently in odd or even time levels. Numerical experiments show the efficiency and accuracy of the new algorithm by comparing the errors with the algorithm in Chapter 3 and explicit method in [10] under the same time and space parameters. The work about Chapter 3 has been submitted to《Chinese Journal of Computational Mathematics》. The new idea of Chapter 3 and 4 is that the new difference schemes constructed are implicit, but they can be computed explicitly mainly using explicit group strategy. Moreover, the alternate use of different schemes with truncation errors of opposite signs can lead to the cancelation of error terms at most points on the mesh lines. By numerical experiments, the efficiency of the new algorithms are confirmed and the ratio of convergence is of order 2 in space. And also show that the new algorithms is applicable to 2D variable coefficient diffusion problems.