Domain Decomposition Parallel Algorithms For Time-Dependent Partial Differential Equations

Mathematical physics and engineering problems can be turned into the problems of solving large partial differential equations, such as reservior simulation, the design of large scale of spacecraft, aerodynamics, reactor 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 be close to limit. With the need of great scale scientific computing and the maturity of parallel computing environments, domain decomposition methods(DDM) have been an effective approach to solve partial differential equations numerically.In short, domain decomposition methods divide the whole domain into several sub-domains, and the shape of these sub-domains may as well be regular. And then the solutions of the original problems can be translated into solving the questions on the sub-domains respectively. Domain decomposition methods have many advantages that other methods can not compare:1. It can decompose large scale problems into several small ones, from which the computing scale is shortened;2. The computation on the sub-domains can be parallel, from which the computing time is shortened;3. Different numerical models can be used on different subspaces, so that the whole model adapts to the practical conditions of physics and engineering problems;4. Local quasi-uniform grids is permitted, it need not the whole quasi-uniform grids, so that different discrete ways can be used on different sub-domains;5. 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.Domain decomposition methods for solving partial differential equations numerically have been extensively studied . They have been applied to problems ranging from linear elliptic equations, parabolic equations , to systems of nonlinear equations . Domain decomposition or sub-structuring is also an effective approach for the construction of pre-conditioners .A domain may be partitioned into overlapping sub-domains or nonoverlap-ping sub-domains. The selection of sub-domains 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 sub-domains. Overlapping domain decompositions become harder to implement in such a setting and the nonoverlapping domain decompositions may be more directly applicable, while the theoretical analysis of the nonoverlapping domain method is 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 so that these methods become very powerful and efficient iterative methods. A systematic theory has been developed for elliptic finite element problems in the past few years . Lions presented a kind of Schwarz alternating algorithm in two sub-domain case for heat equations and gives a convergence result but does not give any error estimate. X.C. Cai constructed a kind of additive Schwarz algorithms and multiplicative Schwarz method and prove that the convergence rate is smaller than one for parabolic equations, there the author did not consider the dependence of the convergence and the discretization parameters. H. Rui and D.P. Yang considered how the convergence and the error estimate depend on the diameter of sub-domains, the spacial mesh-size, the time step increment and the number of iterations at each time level. The classical Schwarz alternating algorithm is not parallel. With the development of parallel computing, many additive or parallel Schwarz algorithms have been developed. M. Dryja, O.B. Wildund, T.M. Shih etc. proposed different algorithms respectively. These algorithms conquered the limitation of serial data transfer, which is in favor of parallel communication. J. Xu gives a systematic introduction to a number of iterative methods for symmetric positive definite problems. The major concern is in the theoretical aspect of the algorithms that are classified into two groups, namely successive subspace correction (SSC) method and parallel subspace correction (PSC) method by using the notions of partition of unity and subspace correction, In [41], this method is applied to the finite element method of parabolic equation and proved the convergence rate O(δ^m) with 0<δ< 1.Nonoverlapping domain decomposition algorithms are important due to high efficiency, adaptability for models and flexibility for domain discretization, based on a decomposition of the whole domain into various nonoverlapping subdomains. Preconditioners at interface boundary must be discussed for these methods, usually considered in the following three contiuous forms: the Dirichlet-Dirichlet(DD), the Neumann-Neumann(NN), and the Dirichlet-Neumann(DN). Much work has been studied by George, Dryja, Smith and the others, but the use of iteration method reduced the parallelism. In practical simulation, due to the requirement to the time step length, implicit schemes are often chosen for heat conduct equation, but they are hard to parallelize. Although explicit schemes are easy to implicit on parallel computers, they have strict stability constraints. When the problem requires hundreds, thousands even tens of thousands of CPUs to compute together, the strong coupling and the global communication become the bottleneck of high performance computing. It has becomes a challenging problem in large scale scientific and engineering computation to reformulate exist implicit schemes and develop parallel computational for large scale parallel computers. In the 1990s, C.N. Dawson, Q. Du & T.F. Dupont presented explicit/implicit domain decomposition methods. These procedures are non-iterative, and involve dividing the domain into nonoverlapping subdomains, with the optimal convergence in l^∞norm. But the explicit nature of the interface boundary gives rise to a stability constraint involving the time stepÏ„and an interface discretization parameter H (H > h). Y.L. Zhou, L.J. Shen & G.W. Yuan constructed a kind of parallel finite schemes with intrinsic parallelism for nonlinear and quasi-linear parabolic systems, and gave the existence, unique and the unconditional stability under the discrete W₂^2,1 norm. G.W. Yuan & X.D. Hang proposed a kind of iterative method for heat conduct equations based on interface correction, and the stability, convergence and the parallelism are studied, but without error estimate analysis.Under the aborative guidance of Professor Danping Yang, the author has finished this dissertation consisting of some work on domain decomposition methods. Firstly, based on the PSC method proposed by Prof. Jinchao Xu, we construct a new kind of parallel additive Schwarz finite difference algorithms(MPFDs) for parabolic and wave equations, by using the speciality of the partition functions of unity to distribute the corrections on overlapping domains reasonably. The stability and convergence analysis of these parallel algorithms is given, and we discussed the dependence of the convergent rate on the spacial mesh size, the time increment, the iteration times and the domain overlapping degree. Both theoretical analysis and the numerical examples show that, these algorithms have high parallelism. Numerical experiments also indicate that a small subspace overlapping degree is enough for the practical computation. In the next place, to solving the equations on the sub-domains by implicit schemes more accurately, we correct the inner boundary conditions with the idea of the extrapolation method. Thus we get another kind of parallel finite difference algorithms(IPFDs) for parabolic problems and hyperbolic problems, which need no iteration at each time level at all, we proved this by error analysis and numerical experiments. Thirdly, we applied the interface prediction-correction idea to nonoverlapping domain decomposition method. Avoiding the explicit procedures on the interface, we use the linear combination of the values on former several time levels as the boundary conditions to realize parallel computing of implicit schemes on the sub-domains, and then construct a kind of nonoverlapping domain decomposition parallel finite difference procedures(NIPFDs) and parallel finite element procedures(NIPFEs). Without iteration, the stability conditions of these parallel procedures become very weak. At the same time, the order of the truncation error round the interface is consistent with that of the truncation error in sub-domains. 1² norm optimal error estimates are given to evaluate the simulation averagely, and numerical experiments are given for each procedure. The whole dissertation is divided into four chapters.In chapter 1, we present a kind of mended parallel finite difference algo-rithms(MPFDs), or the mended parallel subspace correction methods, for heat equation. Based on domain decomposition and subspace correction method, these algorithms introduced the partition function of unity, so that the corrections on overlapping domain can be distributed reasonably. The residual is corrected on on each subspace, and the computation is completely parallel. Optimal convergent rate is proved, which shows that we just need to iterate once or twice at each time step. Numerical experiments also confirm the efficiency and superiority of the algorithm.In§1.1 we introduce the heat equation model problem and the corresponding backward Euler finite difference scheme and the Crank-Nicolson finite difference scheme; In§1.2.1 we construct the basic frame of discrete overlapping domain decomposition model, and the classical parallel additive schemes(CPFDs) are given.§1.2.2 introduce the partition of unity, and the corresponding mended parallel finite difference algorithms (MPFDs) are constructed.§1.3 and§1.4 discusse the convergence analysis of these two mended parallel algorithms. New inner products and norms are defined to get the l² norm error estimate.§1.5 presented series of numerical experiments. The comparison of two kinds parallel algorithms is given, and so does the dependence of convergence rate on discrete parameters, iteration times and the domain overlapping degree. The results have been published or accepted in the core journals such as Journal of Shandong University (Natural Science) , Applied Mathematics and Computation and Journal of Numerical Mathematics of Chinese university.In chapter 2, we construct the interface corrected parallel finite difference algorithms(IPFDs) for parabolic problems based on above chapter. With the idea of interface correction and the extrapolation method, we use the linear combination of the values of the former two time levels at interface to correct the initial inner boundary conditions more accurately at each time level.In§2.1.1 we construct the interface corrected parallel finite difference algorithms (IPFDs) for the corresponding backward Euler finite difference scheme and the Crank-Nicolson finite difference scheme.§2.1.2 and§2.1.3 give the l² norm error estimates of these two mended parallel algorithms, respectively, and gain the optimal convergence order.§2.2.3 give series numerical examples to verify the stability, efficiency and the dependence of the convergence rate to discrete parameters and overlapping degree.§2.2 extend this method to a general parabolic problems in two dimensions.§2.2.1 give the model problem and some preliminaries.§2.2.2 present the domain decomposition .parallel algorithm with interface correction in two dimension. Here we make domain decomposition and subspace in two directions at the same time. Some representative numerical examples are addressed in§2.2.3 to confirm the theoretical results. Some fundamental results have been submitted.In chapter 3, we propose the nonoverlapping domain decomposition parallel finite difference methods(NIPFDs) and finite element methods(NIPFEs) based on interface prediction-correction for parabolic equation. In this chapter, we avoid the explicit procedure on the interface, instead we use the linear combination of the values on former several time levels as the boundary conditions to realize parallel computing of implicit schemes on the sub-domains. At the same time, it makes the truncation error round the interface according with that of the sub-domains, and reduced the stability condition asÏ„= O(h²), which is a very weak condition.§3.1 study the nonoverlapping domain decomposition parallel finite difference methods based on interface prediction-correction for parabolic equation. In§3.1.1 we introduced the parabolic equation model problem, and the corresponding two common used implicit schemes.§3.1.2 rebuild these schemes with domain decomposition method, and proposed the corresponding nonoverlapping domain decomposition finite difference method based on interface correction.§3.1.3 give the l² norm error estimates of these parallel algorithms.§3.2 study the nonoverlapping domain decomposition parallel finite element methods based on interface prediction-correction for parabolic equation, give the L² norm error estimates. In§3.3, series of numerical experiments are presented to verify the convergence, stability and the efficiency the the parallel algorithms.-Some fundamental results have been submitted.In chapter 4, we study the domain decomposition parallel finite difference methods and finite element methods for the hyperbolic wave equation. Wave equation is an important kind of hyperbolic partial differential equation, which has very significant meanings at physics, chemistry, biology and other scientific terrains. Many finite difference schemes and finite element Galerkin methods have been studied For one order hyperbolic equations, there have already many difference methods suitable to parallel computing. But for the wave equation, there are not so many literature In this chapter, we apply these domain decomposition methods mentioned above to the wave equation, and get several domain decomposition parallel algorithms for wave equation.In§4.1 we introduce the wave equation model problem and some preliminaries. In§4.2 we construct the mended parallel finite difference algorithm for wave equation, and give the description of the algorithm, the convergence analysis, and the numerical examples. Based on this, in§4.3 we present the interface corrected parallel finite difference algorithm for wave equation, such that only one iteration step is needed for the parallel algorithm, both theoretical analysis and numerical experiments can verify this.§4.4 study the nonoverlapping domain decomposition parallel finite difference method and finite element method based on interface prediction-correction for wave equation, in§4.5 numerical examples are presented to verify the efficiency and superiority of the algorithm. Some fundamental results have been published in the core journal Journal of Shandong University (Natural Science) .Throughout this dissertation, C, with or without subscripts, denotes a generic, strictly positive constant. Its value may be different at different occurrences, but is independent of the spatial mesh size h and the time incrementÏ„, which will be introduced later.