摘要
区域分裂方法是并行求解大型偏微分方程的有效方法,因为这种方法可以把大型计算问题分解成小型问题,从而简化了计算,上个世纪50年代,在并行机出现之前,区域分裂方法已经在串行机上得到了应用。现在,随着并行计算机和并行算法的发展,自上世纪80年代开始,区域分解算法开始蓬勃发展起来,现在高性能并行计算机已经广泛地应用于能源部门如核工业和实验、石油工业,生物,基因以及气象(天气预报及模拟)等等。
区域分裂方法通常用于以下两种情况:第一,可以通过区域分解的方法把大型问题转化为小型问题,实现问题的并行求解,缩短求解时间;第二,许多问题在不同的区域表现为不同的数学模型,那么可以在不同的区域对数学模型采取不同的方法进行求解,从而自然的引入区域分解方法,实现了并行计算。因为区域分解方法可以把大型问题分解成小型问题,复杂边值问题分解为简单边值问题,串行问题分解成并行问题,因此这种方法的研究十分活跃,具体方法也多种多样。
区域分裂算法是把计算区域分解成若干子域,于是原问题的求解转化为在域上求解,它的优越性表现在:第一,它把大问题化为若干小问题缩小计算规模;第二,允许使用局部拟一致网格,无需用整体拟一致网格,各子域可以用不同离散方法进行计算。这对于形态极不规则问题如锅炉燃烧问题有很大的灵活性;第三,允许不同子域选用不同的数学模型,以便整体模型适合于工程物理实际情况。如油、气藏模拟、气体绕飞体流动等;第四,算法是高度并行的,在各个子域内独立进行。
当用区域分裂方法来数值求解数学模型问题时,我们首先会根据问题的特性或问题求解区域的几何特点对区域进行划分,把整个求解区域划分为若干个子区域,然后在每个子区域上分别求解独立的子问题,实现并行计算。当求解抛物型偏微分方程时,一般情况下我们需要知道方程的初边值条件,但由于区域时认为划分的,那么对于子域而言,至少有一测度非零的边界条件是未知的,即相邻子区域相交内边界上的边界条件是未知的,我们的工作就是给出子区域的边界格式条件,或者虽然不能在求解子问题时明确给出子区域的内边界条件,但是在算法的求解过程中给出子区域相交内边界条件。
显隐格式区域分裂方法就是以显式的格式给出相邻子区域间相交陡边界的边界条件的一种方法。我们知道,如果采用显示方法来求解问题,那么方法可以自然实现并行。但是由于显格式式条件稳定的,对于迭代步长有限制条件,增加了迭代步骤,从而使得计算机求解时间增长,因此一般在求解抛物方程时,普遍会采用隐式方法,隐式方法绝对稳定,对时间没有限制条件,但是在每一步计算时,都要求解一个大型方程组,当剖分加细时,方程组随之变大,求解这样一个方程组耗时较长,从而影响了计算时间。显隐格式区域分裂方法综合了二者的优点,借助前一层数值解的信息,给出在这一层的子问题的未知边界条件,把一个整体区域上的问题化为若干个子区域上的子问题,在每个子区域上用隐式方法求解,从而实现了并行。从计算角度而言,就是把一个整体的大型方程组分解成若干个小型方程组实现了并行。由于给出子区域间内边界条件的方法利用了前层数值解的信息,具有显性性质,导致了算法需要一个稳定性条件,但这个稳定性条件没有显式方法那么严格。
关于显隐格式区域分解方法,前入已经做了很多工作。Dawson,Q.Du和Dupont在文献[3]中采用显隐格式区域分解有限元差分方法,由显式向前差分格式给出子区域间内边界条件,得到了最优阶的ι~∞模误差估计。基于这种方法,Q.Du等人在文献[9]采用一种高效显隐格式区域分解方法,用多层显格式给出内边界条件,最终得到最优的ι~∞模误差估计。Dawson和Dupont在文献[1]中采用了显隐格式区域分裂方法,定义了一个函数,用这个函数给出了区域间内边界条件,得到了L~2模误差估计。在此基础上,Dawson和Dupont在文献[10]中采用了基于中心显隐格式有限差分区域分裂方法,得到了ι~2模误差估计。
本文共分为两部分,第一章为预备知识,第二章研究积分微分方程区域分裂方法,内边界上的函数值由上一层函数值得到,实现算法的并行,误差估计上采用了新的方法,定义一个新的包含边界信息的算子,从而删去了原来误差估计中的H~(1/2),得到了最优估计。
Domain decomposition methods are effective way to solve the large scale problem into small scale problems,making the computation more easier.Because of this,since 50's of last century,even before the advent of the parallel computers,domain decomposition methods have been applied on sequential computers.With the development of parallel algorithms,since the first 80s,this kind of method has flourished.Now,super parallel computers have been used in energy industry like nuclear industry and experiment, oil industry,biology research,weather forecast,etc.
Domain decomposition methods are always employed in tow context.First,the division of large scale problems into several subproblems by the means of domain decomposition is a way to introduce parallelism into large scale problems,and thus the computing time can be shorten.Second,many problems involve more than one mathematical model,each poses on a different domain so that domain decomposition occurs naturally,and so the parallelism is achieved.Because domain decomposition method can turn a large scale problem into smaller ones,turn complicated boundary condition into easier ones,there are very much research work on it.
Domain decomposition methods divide the domain into several sub-domains,so the problem can be solved on the sub-domains,its advantage is:First,it takes large scale problem into small scale problems and saves computations.Second,it can use quasi-uniform grid on sub-domains not on the whole domain,and it can use different discrete procedures to solve problem on sub-domains,which is flexible to many Anomalous problems like boiler combustion,roll designation.Third,it can take different mathematical models on different sub-domains to fit the problems,like oil,gas simulation.Forth,the procedure is parallel,can be computed independently on subdomains.
When we apply domain decomposition methods to solve a mathematical model, we firstly divide the domain into several sub-domain according to the features of the model or the geometry of the domain.Then we solve the subproblems independently on their own sub- domains respectively.When finding the solution of a partial differential equation,we must have known its boundary condition.However,domain decomposition is an artificial division.Then,for a sub-domain,there is at least a part of boundary with unknown boundary condition,that is to say,the inner-domain boundary conditions are unknown.Our task is to give the boundary conditions to the interfaces of the sub-domains or give the boundary conditions to the interfaces in the procedure though the boundary conditions can not be given apparently.
The explicit/implicit domain decomposition method is a kind of method that we give the inner-domain boundary conditions explicitly.We know,if we use an explicit method,the procedure can achieve parallelism naturally.However,there is a stable constraint for the explicit method and the time step is constrained too.So, if we want to march time on,the explicit method will need more steps than implicit method.And thus,it will cost more time to find the solution.Implicit method is unconditionally stable and there is no constraint to time step.While at each time level,we must solve a large,global system of equations.When the mesh is refined, the equation systems become larger at the same time.Solving this kind of equation system also cost much time.The explicit/implicit method include both of the advantage. It use simple,explicit calculations on the boundaries between sub-domains to predict the inner domain boundary condition.Then the equation on the whole domain is decomposed into several equations on sub-domains.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 Ref.[1],Dawson and his co-worker employed domain decomposition finite difference method,give the inner-domain boundary conditions explicitly and get an optimal l~∞normed error estimates.Based on this method,In Ref.[2]Q.Du and his co-workers proposed an efficient domain decomposition finite difference method, giving the inner-domain boundary conditions by the help of solutions from the last a few levels.In Ref.[3],Dawson and Dupont applied a an explicit/implicit domain decomposition finite method,defining a function to predict inner-domain boundary conditions,and derive an L~2 normed error estimates.Then,based on this method, in Ref.[4],Dawson and Dupont used explicit/implicit domain decomposition based on block- centered finite differences and get an l~2 normed error estimates.
This paper includes two parts,in chapter 1,we give preparation knowledge,in chapter 2,we consider the domain decomposition method for integro-differential equations,the function value on the inner-domain boundary is given from the former level,and is parallel,we use new method for error estimates,define a operator including the inner-boundary information to delete the H~(1/2),and get the optimal error estimates.
引文
[1]C.N.Dawson and T.F.Dupont,explicit/implicit conservative Galerkin domain decomposition procedure to solve parabolic problem,Math.Comp.Vol.58,No.197(1992)pp 21-34.
[2]常洛,间断常系数抛物方程组特征修正区域分解有限元法,山东大学学报(理学版),2004,Vol.39,No6.
[3]常洛,对流占优的积分微分方程区域分裂变网格有限元方法,山东大学学报(理学版),2004,Vol.39,No1.
[4]C.N.Dowson,Q.Du,T.F.Dupont,A Finite Diference Domain Decomposition Algorithm for Numerical Solution of The Heat Equation[J],Math Comp.1991.57:63-71.
[5]P.G.Ciarlet,The finite element method for elliptic problems,North-Holland Publ.,Amsterdam,1978.
[6]J.Nitsche,L1-error analysis for finite elements,In the Mathematics of Finite Elements and Applications Ⅲ(Whiteman,J.R.,ed.):173-186;Academic Press,New York,1979.
[7]A.H.Schatz and L.B.Wahlbin,Maximun norm estimates in the finite element method on plane polygonal domains,I,Math.Comp.,32(1978):73-109.
[8]A.H.Schatz and L.B.Wahlbin,Maximun norm estimates in the finite element method on plane polygonal domains,Ⅱ,Math.Comp.,33(1979):485-492.11
[9]Q.Du,M.Mu,Z.N.Wu.Efficient parallel algorithms for parabolic problems[J].SIAM J Numer Anal,2001,39 5 1469-1487
[10]C.N.Dawson and T.F.Dupont.Explicit/implicit conservation domain decomposition procedures for parabolic problems based on block-centered finite differences[J],SIAM J.Numer.Anal.,1994,31:1045-1061.
[11]J.Canon,Y.Lin A prior L~2 error estimates for finite element methods for nonlinear diffusion equations with memory[J].SIAM.J.Numer.Anal.,1990,27:595-602
[12]Y.Lin,V.Thomee,L.B.Wahlbin,Ritz-Volterra projections to finite element spaces and applications to integro-differential and related equations[J].SIAM.J.Numer .Anal.,1991,28:1047-1070.
[13]R.A.Adams,Sobolev Spaces,Academic Press,New York,1975.
[14]G P Liang,A Finite Element Methods of Semidiseretization With Moving Grid[J],J Comput Math,1986,4:86-96.
[15]J.H.Cushman.X.Hu,F.Deng,Nonloeal Reactive Transport With Physical and Chemical Heterogeneity[J],Transport Porous Media,1993.13:123-138.
[16]V.Shelukin.A Nordoeal in Time Model for Radioclides Propagation in Stokes Fluids Dynanlics of Fluids With Free,u,daaes[J].Siberian Russian Acad Sci,lust nyarody,1993,107:180-193.
[17]J.H.Bramble and A.H.Schatz,Higher order local accuracy by averaging in the finite element methot,Math.Comp.31(1977),94-111
[18]M.F.Wheeler.A priori L~2error estimates for Galerkin approximations to parabolic partial defferential equations,SIAM J.Numer.Anal.10(1973),723-759
[19]T.F.Dupont and P.Keenan,An prior estimate for variable-time-step secondorder backward difference methods
[20]C.N.Dawson and Q.Du,A finite element domain decomposition method for parabolic equations,Rice Technical Report TR90-21,Dept.of Mathematical Sciences,Rice University,Houston,Texas.
[21]W.Allegretto,Y.Lin,A.Zhou,A box scheme for coupled systems resulting from micro sensor thermistor problems[J],Dynam Discr Contin Implus Sys,1999,5:209-223
[22]R.A.Adams,Sobolev Spaces,Academic Press,New York,1975
[23]J.Douglas Jr,T.F.Dupont,Galerkin method for parabolic equations[J],SIAM J Numer.Anal.,1970,7(4):575-626.
[24]S.C.Brenner,L.R.Scott,The mathematical theory of finite element methods[M],Spinger Verlag New York Inc.,1994
[25]H.Wang,J.Liu,M.S.Espedal,R.E.Ewing,A characteristic nonoverlapping domain decomposition method for multidimensional convection-diffusion equations[J],Numerical methods for partial differential equations,2005,21(1):89-103.
[26]芮洪兴,Domain decomposition method for parabolic equation on general domain[J],高校应用数学学报(英文版),1995,10B:25-34.
[27]戴培良,沈树民,抛物型积分微分方程的变网格有限元方法[J],高等学校计算数学学报,1994,16(3):242-249
[28]王立俊,双曲型方程的变网格有限元方法[J],计算数学,1988,10(3):266-271.
[29]J.Douglas,Jr.,Finite difference methods for two-phase incompressible flow in porous media[J].SIAMJ Numer.Anal.,1983,20(4):681-696.
[30]Q.Du.Optimization based nonoverlapping domain decomposition algorithms and their convergence[J],SIAM J Numer.Anal.,2001,39(3):1056-1077
[31]袁益让.Characteristic finite difference alternating-direction method and analysis for numerical reservoir simulation[J].应用数学学报(B),2000,20(1):88-96.
[32]R.E.Bank and P.K.Jimack,A new parallel domain decomposition method for the adaptive finite element solution of elliptic partial differential equations[J].Concurrency Computat.:Pract.Exper.2001,13:327-350.
[33]J.H.Cushman,T.R.Ginn.Nonlocal dispersion in media with continuously evolving scales of heterogeneity[J],Transport Porous Media,1993,13:123-138.