Explicit-Implicit Finite Difference Domain Decomposition Parallel Algorithms For Parabolic Problems

Mathematical physics and engineering problems can be turned into the problems of solving high dimensional large partial differential equations,such as reservior simulation,the design of spacecraft,the construction of large-scale water conservancy engineering,aerodynamics,astrophysics etc.The domains they are defined on are always large area with high dimension and irregular geometry,which cause much difficulty to computation when seeking their solutions.In practice the requires for their computation precision are more and more exact,but the speed of the single computer is far away from the actual requirements.With the need of great scale scientific computing and the maturity of parallel computing environments,domain decomposition methods have been an effective approach to solve partial differential equations numerically.In short,domain decomposition methods divide the whole domain into several subdomains,and the shape of these subdomains may as well be regular.And then the solutions of the original problems can be translated into solving the questions on the subdomains respectively.Domain decomposition methods have many advantages: first,it can decompose large-scale problems into several small ones,where the computing scale is shortened;second,the computation on the subdomains can be parallel,thus the computing time is shortened;third,different numerical models can be used on different subspaces,so that the whole model adapts to the practical conditions of physics and engineering problems;then,local quasi-uniform grid is permitted,and the whole quasi-uniform grid is in no need,so that different discrete ways can be used on different subdomains;finally,if the shapes on the sub-domains are regular enough,we can adopt the common familiar fast algorithms or the existent efficient softwares to solve the problems.Certainly,the domain decomposition methods have many other advantages,and the essential is to reduce the scale and compute in parallel.Domain decomposition methods for solving partial differential equations numerically have been extensively studied[35,47,48,50,51,52].They have been applied to problems ranging from elliptic equations[59,60],systems of symmetric positive definite linear systems[61],to parabolic equations[31-34,44].Domain decomposition or sub-structuring is also an effective approach for the construction of pre-conditioners[41].The main difficulty of domain decomposition algorithm is how to define the values on the interface and to scrabble up the reasonable approximation of the real solution from the approximations on subdomains.So,there are two kinds of domain decomposition methods:overlapping domain decomposition method or non-overlapping domain decomposition method.The selection of subdomains may be based on considerations of available computing resources and the geometry of the underlying physical problems.The latter is,in particular,applicable to complex systems which consist of possibly different governing equations in different physical subdomains.Overlapping domain decomposition methods become harder to implement in such a setting and the non-overlapping domain decomposition methods may be more directly applicable,while the theoretical analysis of the non-overlapping domain decomposition methods are more difficult.The initial idea of overlapping domain decomposition methods came from the classical Schwarz alternating algorithms.In recent years the theoretical researches and applications on domain decomposition methods based on Schwarz alternating algorithms have been developed adequately.From elliptic equations to parabolic equations,from additive or multiplicative Schwarz algorithms to successive or parallel subspace correction methods,from mixed element to characteristic finite difference [12-16,36]these methods become very powerful and efficient iterative methods. However,as the adjoining subdomains partly overlapped each other,there are some bad affection to the parallel efficiency.Non-overlapping domain decomposition algorithms are important due to high efficiency,adaptability for models and flexibility for domain discretization,which based on a decomposition of the whole domain into various non-overlapping subdomains.The precondition technique at interface boundary must be discussed for these methods.The explicit-implicit scheme domain decomposition method is a kind of method that we give the adjoining subdomains interface approximations explicitly.The explicit-implicit scheme method include both of their advantages.It use simple,explicit scheme calculations on the interfaces between subdomains to predict the inner domain boundary condition.When computing on subdomaius,the large,global equation system turns into several smaller ones.So the parallelism can be achieved.The explicit scheme nature of the interface conditions induces a time step limitation that is necessary to preserve stability, but this constraint is less severe than that which comes with a fully explicit scheme method.Researchers have been studying kinds of domain decomposition methods.X. C.Cai et al.[59,60,61]provided the theoretical analyses on the overlapping mortar finite element method or finite difference method for solving several elliptic problems discretized on overlapping non-matching grids.C.N.Dawson,Q.Du & T.F. Dupont[31-34,44]introduced the algorithms and error estimate for the explicit-implicit domain decomposition method based on finite element or finite difference, but discussed the heat conduction equations only,and also only one direction explicit scheme at interface for higher dimension problems.B.L.Zhang et al.[25,27,30] used the Sanl'yev asymmetric schemes at a pair of interface points,or putted a new well stable explicit scheme at the interface for Dawson's domain decomposition method,but all these schemes did not improve the total accuracy.C.F.Li[1,2,3] discussed the Dawson's domain decomposition finite difference method for variable coefficient heat equations or parabolic equations,and got the similar conclusion.Under the aborative guidance of Professor Hongxing Rui,the author has finished this dissertation based on the above researchers' studies,which discusses some work on domain decomposition methods.Combining with the interface multi-step explicit scheme method proposed by Prof.Qiang Du,we apply the upwind scheme, high accuracy scheme and non-matching grid to the non-overlapping explicit-implicit finite difference domain decomposition algorithms,give the maximum norm error analyses for variable coefficient heat problems or the general parabolic problems. Several numerical solutions are also presented by the numerical experiments,which validated the accuracy of the algorithms.These algorithms not only use the larger space step at interface,but also divided the time step into several levels,using explicit scheme with smaller time step.After getting the interface values,we can concluded the interior values in each subdomains by implicit scheme in parallel. The algorithm not only extends the stable condition of the classic explicit scheme, but also gains good parallel efficiency.The whole dissertation is divided into four chapters.In chapter 1,we consider an explicit-implicit finite difference domain decomposition algorithm for a class of variable coefficient heat equations,as only the constant coefficient problems were mostly considered before.The basic procedure is to define explicit difference schemes at the interface points with the larger spacing step(?)and smaller time step(?),and use the classic implicit scheme at the interior points,so the total accuracy improved to O(Δt+h²+J(?)³).What is more,we not only extend the stable condition of classical explicit scheme by Jd² times,but also present a concise scheme which can simply realized on the computer in parallel.Chapter 1 is organized as follows,the algorithms and error estimates in one or two dimension are derived in§1.2 or§1.3 respectively.Firstly,we present the one-dimensional heat conduction model with variable coefficient in§1.2.1.And then, these are discussed in§1.2.2-§1.2.4 that the uniform mesh problems,the different spacing and time steps problems and the multiple subdomains problems.After listed the two-dimensional heat conduction model with variable coefficient in§1.3.1,the domain decomposition methods for two-dimensional heat conduction problem with two or four subdomains are presented in§1.3.2 or§1.3.3.At last,the numerical experiment is presented to confirm our result in§1.4.Some fundamental results have been published in the core journal J.Shandong Univ.(Natural Science).In chapter 2,we present some high accurate finite difference domain decomposition algorithms with looser stability condition.For one-dimensional parabolic problems,the domain is equally divided into several non-overlapping multiple subdomains. Then,we take the technique of using the high accurate explicit difference scheme at the interface points with smaller time step(?)and larger mesh spacing (?).After the interface values have been computed,there are a few of completely separated high accurate implicit difference problems to solve,which can be done in parallel.In addition,the accuracy of the domain decomposition algorithm is O(Δt²+h⁴+Jq(?)⁵)and the algorithm can be realized on computer easily and quickly.For higher-dimensional parabolic problems,we not only make use of the technique of using a class of two-level explicit difference scheme at the interface points,but also compute the value of interior points with a compact alternating direction implicit scheme.Based on these schemes,we first extend the stability bounds of classical explicit scheme by Jd² times.Secondly,it is explicit both in x and y directions at most interface points.Furthermore,the coefficient matrix of implicit scheme at interior points is tridiagonal in order to improve the parallel efficiency. Finally,and most importantly,the accuracy of the domain decomposition algorithm is O(Δt²+(?)Δt+J(?)³),and improves to O(Δt²+h⁴+Jh⁵)by a special choice of d and mesh ratio(?).Chapter 2 is organized as follows.Firstly,we give the model problem and the detailed presentations for the one dimensional parabolic equation in§2.2.Then the algorithm,error analysis and parallel efficiency are addressed in this section too. Secondly,the domain decomposition algorithms and the convergence results of the numerical solutions for two and three dimensional heat equations are discussed in§2.3 and§2.4,respectively.Finally,in§2.5,some numerical examples are given to show the stability and the accuracy of the algorithms.Some fundamental results have been published in the journal Inter.J.Comp.Math..Chapter 3 discusses the finite difference non-matching domain decomposition method.Non-matching domain decomposition methods have different partitions on subdomains so there are some non-matched points on the interface.In this chapter,we combine the modified Saul'yev asymmetric schemes with the classical implicit scheme to get a simple explicit scheme on the interface,then present the finite difference non-overlapping non-matching domain decomposition algorithm.It is explicit both in the x and y directions at most interface points.Furthermore,the stability condition is r≤1,which increases the stability bounds of classical explicit scheme by 2D² times in one-dimension and 4D² times in two-dimension.After the interface values have been computed,there are two completely separated implicit difference problems to solve,which can be done in parallel.In addition,the accuracy of the domain decomposition algorithm is O(Δt+h₁²+h₁²+H³)and the algorithm can be realized on computer easily and quickly.This chapter is organized as follows. The domain decomposition algorithms and the convergence results of the numerical solutions for one and two dimensional parabolic problems are discussed in§3.2 and§3.3,respectively.In§3.4,some numerical examples are given to confirm our results.In chapter 4,we not only expand the multi-step explicit-implicit scheme for the heat conduction problems in chapter 1 to the general parabolic problems,but also introduce three kinds of upwind difference scheme for domain decomposition method.For one-dimensional parabolic problems,we firstly give the one-dimensional general parabolic model and preliminaries in§4.2,and discuss the finite difference domain decomposition algorithm for this model in§4.3.Secondly,we bring forward three kinds of upwind difference algorithms in§4.4,which are UDA(Upwind Difference Algorithm),IMUDA(Interface Modified Upwind Difference Algorithm) and MUDA(Modified Upwind Difference Algorithm).One-Order upwind difference algorithm applies explicit or implicit one order upwind difference scheme at the interface points or the interior points respectively.Interface modified upwind difference algorithm applies two order explicit modified upwind difference scheme at the interface points,and classic implicit scheme at the interior points as usual.Modified upwind difference algorithm applies explicit or implicit two order modified upwind difference scheme at the interface points or the interior points respectively.Then we also present the multi-step explicit-implicit method for the two-dimensional general parabolic equations in§4.5 and§4.6.Finally,in§4.7,some numerical examples,including a real application problem-the heat conduction problem in radioactive rob, are given to show the stability and the accuracy of the algorithms.The results have been published in the core journals such as J.Shandong Univ.(Natural Science) and Chinese J.Eng.Math..