| It is well known that most practical problems in engineering can be turned into solving a large scale partial differential equations, such as reservoir simulation [1]-[3], environmental engineering[4, 5], aerodynamics[6], semiconductor devices[7], etc. Parallel algorithms, based upon domain decompositions, are effective ways to solve the large scale of PDE systems (for examples, see [8]-[21]). These methods can decompose a large scale problem into small scale ones, making the computation more easier. Since the 50's of last century, even before the advent of the parallel computers, domain decomposition methods haven been applied on sequential computer. With the development of parallel computers and parallel algorithms, domain decomposition methods have flourished after 80's. Now, super parallel computers have been widely used in energy industry, biology research, weather forecast and simulation, etc.Domain decomposition methods may be partitioned into overlapping domain decomposition methods or nonoverlapping domain decomposition methods. The selection of sub-domains may be based on considerations of the features of the model and the geometry of the domain. The latter is, in particular, applicable to complex systems which consist of possibly different governing equations in different physical sub-domains. Overlapping domain decomposition methods become harder to implement in such a setting and the nonoverlapping domain decomposition method may be more directly applicable, while the theoretical analysis of the nonoverlapping domain decomposition method are more difficult. In this dissertation, our researches are focused on nonoverlapping domain decomposition methods.Domain decomposition methods have many advantages over other standard meth- ods from the following respects: (i) They can decompose large scale problems into several small ones, and thus the computing scale is smaller. (ii) The computation on the sub-domains can be parallel so that the computing time can be shorten. (iii) Many-problems involve more than one mathematical model, which poses on a different domain. Then, domain decomposition occurs naturally and different numerical models can be applied on each different domain. (iv) Local quasi-uniform grids is permitted and the whole quasi-uniform grid is not necessary, so that different discrete ways can be used on different sub-domains.When domain decomposition methods applied to solve a problem, firstly the domain is decomposed into several subdomains according to the features of the problem or the geometry of the domain. That is, a problem is divided into several subproblems. Then, these subproblems must be solved independently on their own subdomains, respectively. As well as we know, the boundary condition must be known to find the solution of an evolution equation. However, domain decomposition is an artificial division. Hence, for a subdomain, there is at least a part of boundary with unknown boundary condition, that is to say, the inner-domain boundary conditions are unknown. To construct a domain decomposition method, one big task is to propose the boundary conditions to the interfaces of the subdomains or give the boundary conditions to the interfaces in the procedure though the boundary conditions can not be given apparently.Among many domain decomposition methods, the explicit/implicit domain decomposition method is a kind of method that gives the inner-domain boundary conditions explicitly and computes subproblems implicitly. An explicit method can achieve parallelism naturally. But, there is a stable constraint for the explicit method and the time step is constrained too. When time marching on, explicit method will need more steps than implicit method. Thus, it will cost more time to find the solution. On the contrary, implicit method is unconditionally stable and there is no constraint to time step. While at each time level, a large, global system of equations must be solved. Especially, the equation systems become larger at the same time when the mesh is refined. The explicit/implicit domain decomposition method includes the advantages of domain decomposition method, explicit method and implicit method. It uses simple, explicit calculations on the boundaries between subdomains to predict the inner-domain boundary condition. Then the equation on the whole domain is decomposed into several equations on subdomains. When computing, the large, global equation system turns into several smaller ones. So the parallelism is achieved. The explicit nature of the inner-domain boundary 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 method.There has been much work on the explicit/implicit domain decomposition methods. In [22], Dawson and his co-worker employed domain decomposition finite difference method, gave the inner-domain boundary conditions explicitly and got an optimal l∞norm error estimates. Based on this method, Q. Du and his co-workers [23] proposed an efficient domain decomposition finite difference method, giving the inner-domain boundary conditions by use of solutions from the last a few levels. Compared with [22], this procedure was more efficient.In [24], Dawson and Dupont applied an explicit/implicit conservative Galerkin domain decomposition procedures for parabolic equations. They used implicit Galerkin procedures in the sub-domains and explicit calculations on the inter-domain boundaryΓto predict the flux by use of some weight functions approximating to the delta functions. These procedures were conservative both in the sub-domains and across inter-domain boundaries. The explicit nature of the flux prediction induced a time step limitation that was necessary to preserve stability, but less severe than that of a fully explicit method. They derived a priori error bounds in terms of the errors of certain elliptic approximations rather than powers of some asymptotic parameter. But, in fact, there was a loss of H-1/2 factor for space variable. It was noted that that loss could be avoided in certain special cases using some techniques of [26] but was not improved in [24]. Dawson-Dupont's schemes were designed for PDEs of special form such as (?)·(a(x)(?)u),a(x) is a function on space domain and special domain such as rectangle-type domain. So there are some difficulties to extend these schemes to problem of general form on general domains.Under the excellent guidance of Professor Danping Yang, the author has finished this doctoral dissertation, which researches parallel Galerkin domain decomposition procedures for three kinds of evolution equations on general domain: parabolic equation, wave equation, convection-diffusion equation. Two classes of parallel Galerkin domain decomposition schemes are proposed, which are also explicit/implicit schemes. They use implicit methods in the sub-domains and two kinds of explicit flux calculations on the inter-domain boundaryΓby integral mean method and extrapolation-integral mean method, respectively. For these schemes, the convergence analysis are presented strictly. Optimal error estimates are derived, which avoid the loss of H-1/2 factor for space variable and thus recover losses of the works of former researchers. For these purposes, new nonstandard elliptic projections are defined and analyzed, which include some terms onΓ. The second class of schemes have higher order accuracy with respect to H than the first class of schemes, which means that the second class of schemes can use larger H than that of the first class of schemes so that the time step constraint is more weaker than of the first class of schemes and larger time step size can be used. Many numerical experiments are also given to confirm theoretical results for these procedures. Compared with the works of the former researchers, the schemes of this dissertation can use larger width H and shorten greatly the CPU time, which are of benefit to practical use. It is worth while to specially emphasize that parallel H1-Galerkin mixed finite element domain decomposition procedures for parabolic equation and parallel Galerkin domain decomposition procedures based on the streamline diffusion method for convection-diffusion problems are considered in Chapter 3 and Chapter 5, respectively. These two research are more creative. No former researcher discussed similarly. The whole dissertation consists of five chapters.In Chapter 1, we present parallel Galerkin domain decomposition procedures for parabolic equation on general domain. These procedures are also explicit/implicit schemes. They use implicit Galerkin methods in the sub-domains and other explicit calculations to predict the flux onΓ. Firstly, an integral mean method is utilized to present a simple explicit flux calculation. This calculation is just the integral mean value of the directional derivative of the solution onΓover a strip domain with width 2H. We call this scheme as integral mean parallel Galerkin scheme (IM-PG scheme). Secondly, in order to improve higher order accuracy with respect to H, we extrapolate the flux calculation and derive another scheme. We call this case as extrapolation-integral mean parallel Galerkin Scheme (EIM-PG scheme). Some constraints for time step are still needed for these procedures to preserve stability, but less severe than that for fully explicit methods. With respect to the accuracy order of h, L2-norm error estimates are optimal. Compared with [24], these L2-norm error estimates avoid the loss of H-1/2 factor.A brief outline of this chapter is as follows.§1.1 is introduction. In§1.2, by the definitions of integral mean value and its extrapolation-integral mean value, we present IM-PG scheme and EIM-PG scheme on a general domain, respectively. In§1.3 and§1.4, L2-norm error estimates are derived for IM-PG scheme and EIM-PG scheme, re- spectively. For these purposes, new elliptic projections axe defined and analyzed, which include some terms onΓ. In§1.5, we present results of some numerical experiments to confirm theoretical results.§1.6 discusses the extensions to other boundary conditions. The result of this chapter has been published online for early view by the journal Numerical Methods for Partial Differential Equations, see [33], and Int. J. Numer. Meth. Fluids, see [34].In Chapter 2, we present dynamic parallel Galerkin domain decomposition procedures with grid modification for parabolic equation. For time-changing localized phenomena, such as sharp fronts and layers, dynamic finite element method [36]-[37] is advantageous over fixed finite element method. The reason is that the former has the capability of self-adaptive local grid modification (refinement or unrefinement) to efficiently capture propagating fronts or moving layers. However, for large-scale such problems, local, grid modification may still lead to very large linear systems. Domain decomposition methods enable one to break large problems into a collection of small ones, each of which may be solved separately by the finite element method.Daoqi Yang [39, 40] analyzed a numerical method for parabolic problems, which allows one to use different domain decompositions, different grids, and/or different interpolation polynomials at different time levels when necessary. This method is based on the one given by Dawson and Dupont [24], and thus relies on an implicit Galerkin procedure in the subdomains and explicit flux calculation on the inter-domain boundaries. The grids on the subdomains need not match up in such a way that they are restrictions of a global regular finite element grid over the whole physical domain, as opposed to other domain decomposition methods [41, 43]. This gives great flexibility for applying grid refinement or uniform fine grids in subdomains that contain local fronts or layers, and grid unrefinement or uniform coarse grids in subdomains over which the solution changes slowly. But, there was still a loss of H-1/2 factor for space variable in error estimates.The purpose of this chapter is to consider parallel Galerkin domain decomposition procedures in Chapter 1 (or [33]) combined with dynamic grid modification for parabolic equation on general domain. These procedures preserve advantages of that method in [39,40], but the L2-norm error estimates avoid the loss of H-1/2 factor. This chapter is organized as follows. In§2.2, two approximation schemes are established. We call these two schemes as integral mean dynamic parallel Galerkin domain decomposition scheme (IM-DPDD scheme) and extrapolation-integral mean dynamic parallel Galerkin domain decomposition scheme (EIM-DPDD scheme), respectively. When different domain decompositions and/or different finite element spaces are used at times tn and tn-1, the previous approximate solution Un-1 is projected into the current finite element space as PnUn-1 by the L2-projection. This projection PnUn-1 is used in IM-DPDD scheme or EIM-DPDD scheme as initial value to calculate Un. In§2.3 and§2.4, stability and convergence analysis in optimal L2-norm are derived for IM-DPDD scheme and EIM-DPDD scheme, respectively. In order to preserve stability, constraints for time step are still needed and less severe than that of fully explicit methods. In§2.5, we present results of some numerical experiments to confirm theoretical results. The fundamental results of this chapter have been submitted.In Chapter 3, we present parallel Galerkin domain decomposition procedures in Chapter 1 combined with H1-Galerkin mixed finite element method for parabolic equation on general domain. Since the pioneering work of Raviart and Thomas [44] and Nedelec [45], the mixed finite element method has become a standard way in many applications(e.g., [46]-[49]). Traditionally, the reason is that the mixed finite element method can approximate both the primary variable u and its fluxσ=(?)u simultaneously and give a high order approximation. Much work has been devoted to the analysis of mixed finite element approximations for second-order parabolic problems, see e.g.[53]-[55]. However, standard mixed finite method has to satisfy the LBB-consistency condition (also called inf-sup condition) on the approximating subspaces and this restricts the choice of finite element spaces. For example, the Raviart-Thomas spaces of index r≥1 are usually used for the standard mixed methods.In order to circumvent the LBB-consistency condition, an alternate procedure called as H1-Galerkin mixed finite element method was introduced by Pani [56] to parabolic equations. First, H1-Galerkin mixed finite element method changes the model into a first-order system about unknown variable u and its fluxσ, then use H1-Galerkin finite element method to it. The approximating finite element spaces Vh×Wh, to variable u and fluxσrespectively, were allowed to be of different polynomial degrees. Hence, estimations can be obtained which distinguished the better approximation properties of Vh and Wh. Compared to standard mixed methods, the H1-Galerkin mixed finite element method was not subject to LBB-consistency condition. It was noted that if the finite element spaces Wh for the flux were of Raviart-Thomas type, then optimal estimates were achieved and coincided with those in Johnson and Thom(?)e [53] using standard mixed method and the Raviart-Thomas finite element spaces. Moreover, the quasi-uniformity condition was not imposed on the finite element mesh for the error estimates in L2 and H1-norms.It is worth while to specially emphasize that the research of this chapter is creative. No former researcher discussed similarly. The procedures of this chapter not only hold the advantages of that of Chapter 1, but also hold the advantages of H1-Galerkin mixed finite element method: the primary variable u and its fluxσ= (?)u can be approximated simultaneously by the spaces of different polynomial degrees. These spaces were not subject to LBB-consistency condition and the quasi-uniformity condition was not imposed on the finite element mesh.An outline of this chapter is as follows. Two mixed approximation schemes are established in§3.2. They use H1-Galerkin mixed finite element method in the sub-domains and explicit calculations as the way in Chapter 1 on the inter-domain boundaryΓ. We call these two schemes as integral mean parallel H1-Galerkin mixed finite element domain decomposition scheme (IM-PMDD scheme) and extrapolation-integral mean parallel H1-Galerkin mixed finite element domain decomposition scheme (EIM-PMDD scheme), respectively. In§3.3 and§3.4, optimal error estimates forσin L2-norm and u in H1norm are derived for IM-PMDD and EIM-PMDD scheme, respectively. Some fundamental results of this chapter have been submitted.In Chapter 4, the extension of parallel Galerkin domain decomposition procedures in Chapter 1 for wave equation on general domain is considered. In most engineering problems, the wave equation is described by a second-order hyperbolic equation. A priori error estimates of Galerkin approximations for the second-order hyperbolic equation were first derived by Dupont [62] using a standard energy argument both for continuous and discrete time schemes, respectively. Dupont [69] used the method of [24] to present domain decomposition methods for wave equation. There was still a loss of H-1/2 factor for space variable in error estimates.Two domain decomposition approximation schemes for wave equation are established in§4.2. They use Crank-Nicolson implicit procedures in the sub-domains and explicit flux calculations as the way in Chapter 1 on the inter-domain boundaryΓ. We call these two schemes as integral mean parallel domain decomposition scheme (Wave-IMPDD scheme) and extrapolation-integral mean parallel domain decomposition scheme (Wave-EIMPDD scheme), respectively. In§4.3 and§4.4, an energy norm is defined for the discrete solution. Then, L2-norm error estimates are derived by energy arguments for Wave-IMPDD and Wave-EIMPDD scheme, respectively. These L2-norm error estimates avoid the loss of H-1/2 factor. The results show these two schemes have convergence orders onΔt and h as same as that of Dupont's method [62]. The time step constraintsΔt≤CH are still needed to preserve stability. These constraints are similar to that of reference work [69]. We present results of some numerical experiments in§4.5. Some fundamental results of this chapter have been submitted.In Chapter 5, we use parallel Galerkin domain decomposition procedures in Chapter 1 with the finite difference streamline diffusion method (FDSD method) for convection-diffusion problem. The time-dependent convection-diffusion problems with a dominating convection term are parabolic problems. However, the dominating convection feature has a hyperbolic nature. It was observed early on that in contrast to the case for general parabolic problems, standard applications of the finite element method to convection dominated problems lead to numerical schemes which frequently do not give reasonable results. To overcome these difficulties, some modified nonstandard finite element methods such as streamline diffusion method and discontinuous Galerkin method, can be used.The research of the streamline diffusion method for linear problems, together with extensions to time-dependent problems using space-time elements, was started by Johnson and Navert [72] and continued in [73]-[77]. These works demonstrated that the streamline diffusion method (SD method) has both good stability properties and higher accuracy, a combination of desirable features not shared by previous known finite element methods.Finite difference streamline diffusion methods (FDSD methods) were proposed and developed by Che Sun and coworkers [78]-[80], by using SD finite element discrete only in space variables and using finite difference discrete in time t. For time-dependent problems in space-domain (?)Rd, from time level t=tn to tn+1, the SD method has to solve the discretization problem in (d + l)-dimensional space-time domain (?)×[tn,tn+1], whereas the FDSD method only needs to solve the discretization problem in d-dimensional space domain (?). Hence, FDSD methods keep the essential aspect of the original SD method but simplify the algorithm structure and reduce the computational work. In general, the computing scale for the FDSD method is corresponding to that of fully discrete Galerkin finite element method.It is worth while to specially emphasize that the research of this chapter is creative. No former researcher discussed similarly. The procedures of this chapter not only hold the advantages of that of Chapter 1, but also hold the advantages of FDSD method: has both good stability properties and higher accuracy, the error estimates along the streamline direction can be achieved. These advantages are not shared by previous known finite element methods.This chapter is organized as follows. Two parallel Galerkin domain decomposition approximation schemes with the FDSD method for time-dependent convection-diffusion problem on a general domain are established in§5.2. They use implicit FDSD method in the sub-domains and explicit flux calculations as the way in Chapter 1 on the inter-domain boundaryΓ. We call these two schemes as integral mean parallel FDSD scheme (IM-PFDSD scheme) and extrapolation-integral mean parallel FDSD scheme (EIM-PFDSD scheme), respectively. In§5.3 and§5.4, artificial diffusion parameters S are given and time step constraints△t≤CH2 are derived also. By analysis, optimal order error estimate is derived in a norm which is stronger than L2-norm for IM-PFDSD scheme and EIM-PFDSD scheme, respectively. This error estimate not only includes the optimal H 1-norm error estimate, but also includes the error estimates along the streamline direction ||βn·(?)(u-U)n||, which can not be achieved by standard finite element method. In§5.5, we present results of some numerical experiments, which confirm our theoretical results. Some fundamental results of this chapter have been submitted.
|
PDF Full Text Request