Overlapping Domain Decomposition Parallel Algorithms For Evolution Equations

Domain decomposition methods were new research direction which grew up in 1980s'. Because they have many advantages, such as they can divide large-scale problems into several small ones, complex boundary problems into several simple boundary ones and successive problems into parallel ones, etc., which other methods don't have, they rapidly become the hot field of computational mathematics. Especially in recent years, with rapid development of computer and parallel algorithms, domain decomposition methods are becoming powerful tools to handle real-life problems with complicated domains or complex processes.Domain decomposition methods may be partitioned into two families: overlapping domain decomposition methods and nonoverlapping decomposition methods. The selection of sub-domains may be based on the availability of the computational domain and the physical background of the 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, while the nonoverlapping domain decomposition methods may be more directly applicable. In addition, the theoretical analysis of the nonoverlapping domain decomposition methods are more difficult. In this dissertation, our researches are focused on overlapping domain decomposition methods.The initial idea of overlapping domain decomposition methods came from the classical Schwarz alternating algorithm. In recent years the theoretical researches and applications on domain decomposition methods based on Schwarz alternating algorithm 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 ( see [16, 17, 20] ). 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 in [82, 83]. In [19, 20], X.C. Cai constructed a kind of additive Schwarz algorithm and multiplicative Schwarz method and proved 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 ( see [26, 27, 28, 29, 30, 31, 32, 33, 34] ). 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 in [22, 23, 24, 25]. These algorithms conquered the limitation of serial data transfer, which is in favor of parallel communication. J. Xu in [42, 43] 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 domain decomposition and subspace correction. In [44], J.H. Yang and Prof. Danping Yang applied this method with Galerkin finite element scheme to parabolic equations and obtained the convergence rate O(δ~m) with 0 <δ< 1. X.C. Tai has done many researches on subspace correction methods combined with domain decomposition (see [36, 37, 38, 39]).Under the guidance of my supervisor Professor Yang Danping, the author has finished this dissertation consisting of some work on overlapping domain decomposition parallel methods. Based on PSC method proposed by Professor Jinchao Xu and combined with the well-known numerical methods, such as classical mixed finite element method, least-squares method, splitting positive definite mixed element method ( SPDME ) etc., by using the property of the partition functions of unity to distribute the corrections on overlapping domains reasonably, several different overlapping domain decomposition methods are presented for solving parabolic problems, second order hyperbolic equations, time-dependent convection-diffusion problems and compressible miscible displacement problem in porous media. We analyze the convergence of each procedure, and study the dependence of the convergent rate on the spacial mesh size, the time increment, the iteration times and the sub-domains overlapping degree. Both theoretical analysis and numerical experiments show that all these algorithms are high parallelism and only one or two iterations are needed to reach to optimal accuracy at each time step.The dissertation is divided into four chapters.In Chapter 1, we present a new family of domain decomposition parallel algorithms for solving second order parabolic equations. Firstly, using the splitting positive definite mixed element method as in [15] with backward difference scheme in time, we give a fully-discrete splitting positive definite mixed element scheme, where the coefficient matrix is symmetric positive definite. And then, based on this scheme and combined with the idea of PSC method proposed by Jinchao Xu in [42], we establish a parallel mixed finite element algorithm I (PMFE algorithm I). We analyze the convergence of PMFE algorithm I and give the error estimate. For PMFE algorithm I, we also give some numerical experiments. From theoretical analysis and these numerical results, we can easily see that only one-cycle or two-cycle iteration is needed to reach the optimal accuracy. In the following part of this chapter, based on the well-known classical mixed finite element scheme, using the idea of PSC method, we construct the other parallel mixed finite element algorithm for the parabolic problems: parallel mixed element algorithmⅡ(PMFE algorithmⅡ). By use of some theoretical results of PMFE algorithmⅠ, we also analyze the convergence of PMFE algorithmⅡand give the corresponding error estimate.In Chapter 2, we focus on the theoretical analysis of the overlapping domain decomposition parallel algorithm for compressible miscible displacement in porous media. As we know, Danping Yang give a splitting positive definite mixed element method for compressible miscible displacement problem in porous media in [15]. In this method, the coefficient matrixes are symmetric positive definite, and the flux equation is separated from pressure equation so that we can obtain an approximate solution of the flux equation fast and independently by using various effective algorithms. The purpose of this chapter is, based on the splitting positive definite mixed element scheme with backward difference in time and the idea as PMFE algorithm I in Chapter 1, to construct a parallel mixed finite element algorithm for solving compressible miscible displacement in porous media. We study the convergence of this parallel algorithm and give the error estimate. From the error result, we can see that at each time level only two-cycle iteration is required to reach the optimal accuracy. In Section 2.1, we introduce the physical background and present the motivation and the goal of this chapter. In Section 2.2 we establish the splitting positive definite mixed element procedure for compressible miscible displacement in porous media, and formulate the parallel mixed finite element algorithm. In Section 2.3 we give some lemmas, which are important to prove the convergence theorem of the approximate solution. In Section 2.4, we prove convergence theorem. The part of the results in this chapter have been published in the " Journal of Shandong University (Natural Science)" (see [58]).In chapter 3, we mainly study the domain decomposition parallel least-squares methods for the time-dependent convection-diffusion problems. A lot of researches on least-squares finite element schemes and their applications to various boundary value problems of elliptic equations or systems have been done and some systematic theory on the ellipticity of schemes and convergence of approximate solution have also been established, e.g., see [62, 63, 64, 65, 66, 67, 68, 69, 72, 74, 76, 77, 78]. The least-squares finite element methods have been extended to time-dependent problems, e.g., see [71, 73, 75, 79, 80, 81]. In this chapter, based on PSC method and combined with two least-squares schemes: Scheme I and SchemeⅢ, which Danping Yang established in [79], we give two parallel least-squares algorithms: Parallel Least-squares algorithmⅠ(PLS algorithm I) and Parallel Least-squares algorithmⅡ(PLS algorithm II). We analyze the convergence of these parallel algorithms, respectively, and give the corresponding error estimates. Finally, we give some experiments and analyze the dependence of the convergent rate on discretization parameters and iteration times. Some fundamental results in this chapter have been submitted (see [60]).In chapter 4, we study the domain decomposition parallel mixed finite element algorithm for second order hyperbolic equations. As we know, hyperbolic equations describe the wave phenomena in nature, which have very significant meanings in physics, chemistry, biology and other scientific fields. A lot of numerical methods for second order hyperbolic equations have been established, e.g., see [85, 86, 87, 88, 89, 90]. For the parallel algorithms of hyperbolic equations, there were many researches. Y.H. Wu and X.C. Cai studied the additive Schwarz methods for one order hyperbolic equations in [40]. Min Tian analyzed the parallel finite difference methods for second-order hyperbolic equations in her doctoral dissertation [46]. The purpose of this chapter is to construct a parallel mixed finite element algorithm for second order hyperbolic equations based on the idea of PMFE algorithm I for parabolic problems in Chapter 1. The convergence of this algorithm is analyzed and the error estimate is given. In Section 4.1, we present the motivation and goal of this chapter. In Section 4.2 we give a splitting positive definite mixed element procedure for the hyperbolic systems and formulate the parallel mixed element algorithm. In Section 4.3 we give some lemmas, which are used to prove the convergence of the approximate solution. In Section 4.4 we analyze the convergence of the approximate solution and give error estimates. Some results in this chapter have been accepted by the "Numerical Methods for Partial Differential Equations'" (see [59]).