（计算数学专业论文）时间依赖偏微分方程的区域分解并行算法.pdf

s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 时间依赖偏微分方程的 区域分解并行算法 田敏1 f 山东大学数学与系统稃学学院，济南2 5 0 1 0 0 ) 中文摘要 数学物理及工程问题，如油气藏的勘探与开发，大型结构工程设计，空气动力 学，反应堆等等，无不j j 曩结为求解大型偏微分方穗模型河题。这些问题往往计算规 模大，计算区域形态不规则，给计算带来很大的豳难。与此同时，我们对计算精度 的要求越来越高，而单机计算的速度已接近极限。随着大规模科学计算的需要和 并聿予计算环境的发展成熟，区域分解法( d d m ) 已成为数值求辑偏微分方程最有 效的方法之一。 箍藕言之，区域分解方法就是把计算的区域分裂成若干子区域，子域的形状 尽可能的规则。从而原问题的求解转化成在子区域上分别解决问题。区域分解算 法具有很多其他方法无以比拟的优越性： 1 它把大型静闻题转化为若干小型闷蘧，缩小计算的规模； 2 各子区域上的计算是并行的，缩短计算的时间： 3 允许褒不同的乎域上选惩不同的数学模型，以便整体模型受适合子工程秘 理实际情况。 4 允许使用局部拟一致网格，无需塌整体拟一致网格，甚至备子上可以采用 不同的离散方法进行计算； 5 子区域的形状尽可能规则，其上或者已有熟知通用的快速算法，或者已有 磐这类规羽翔趱的蹇效较件各壤。 用区域分解法来求偏微分方程数值解已有大量研究 1 - 6 1 。他们把这种方法应 用予求解线性椭圆问题、抛物闻题f 7 8 | ，以及非线性方程缎1 9 等。同时，区域分解 法也是构建预条件子的有效方法之一1 1 0 - 18 | 。区域分解法分为两类：重叠型区域分 解法和非重叠型区域分解法。予区域的选择主要考虑区域形状的w 计算性以及问 蓬的物理鹜景。尤其是螽者，特别适震予在不同物理子区域上有水翔控锱方程豹 复合问题。非重叠型区域分解法实现起来比较直观易用，而重叠型区域分解法的 理论分析较为容易些。 熏叠型区域分解法的原始思想来源乎经典的s c h w a r z 交替法。近年来建立在 s c h w a r z 交替法基础上的区域分解法在理论分析和实际应用中取得令人注目的发 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 展，已成为一种有效的迭代方法。椭圆型方程有限元方法已经建立了系统的的理论 分析【1 9 ，2 0 ，2 3 ；l i o n s 2 1 ，2 2 】对热传导方程提出了的一类建立在两个子区域基础上 的s c h w a r z 交替算法，给出了收敛性结果，但没有给出误差估计；x c c a l 【2 4 2 5 】 构建了一类加性s c h w a r z 算法和乘性s c h w a r z 算法，并证明了算法的收敛性，但 作者没有详细讨论收敛率对离散参数的依赖性；h r u ia n dd p y a n g 2 6 - 3 4 论证 了在每一时间层上收敛性及误差估计对子区域长度、空间网格步长、时间步长和 迭代次数的依赖性。经典的s c h w a r z 交替法不是并行的，随着并行计算的发展，出 现了多种可完全并行化的加性s c h w a r z 算法。m d r y j a ，0 b w i l d u n d ，t m s h i h 等【3 5 ，3 6 ，3 7 ，3 ，3 8 j 皆独立提出不同的算法，这些算法可克服交替方法的串行性，更 利于并行处理。j x u a 9 ，4 0 l 系统地介绍了求解对称正定问题的各种迭代方法，主 要是利用区域分解和子区域校正法从理论上建立了并行子区域校正和串行子区域 校正这两类算法。f 4 1 1 将此方法应用于抛物型方程有限元方法，并得到了收敛阶 0 ( 巧m ) ，其中0 6 1 。 非重叠型区域分解法将计算区域分解成若干个独立的不同子区域，具有高度 并行、网格剖分灵活和易于计算等优点。对于此方法，内边界上的预处理算子是必 须要考虑的。一般需要附加三种形式的内边界条件：解的连续性条件( d d ) 、流量 的连续性条件( n n ) 和混合条件( d n ) 。g e o r g e ，d r y j a ，s m i t h 等在这方面做了很 多工作。但各子问题内边界条件需要通过迭代处理，计算比较复杂。在许多实际计 算中，由于对时间步长稳定性的要求，发展方程的计算通常采用隐格式，但隐式格 式难以直接在并行机上实施。显式差分格式尽管易于实施，但它的稳定性条件苛 刻。当计算问题的规模相当大，例如需要具有数千甚至上万台处理器的大型并行计 算机进行计算时，数据的强相关与全局通讯等问题就会成为制约实现高性能计算 的突出瓶颈问题。因此，改造现有的隐式格式，研究适用于大型并行计算机上的并 行计算方法是目前大型科学工程计算中迫切需要解决的具有挑战性的问题。c n d a w s o n ，q d u t f d u p o n t 等【8 ，4 5 ，4 6 ，4 7 ，镐】提出了一类显隐非重叠区域分裂 格式，在内边界上采用大步长显格式，各子域内采用隐格式。显隐结合无需迭代计 算，得到最优的l 模误差估计，但内边界格式的显性仍然引入了一定的稳定性条 件( 丁h 2 ) 。【5 1 】、 5 2 提出了一类具有界面修正的并行差分算法，并给出了算法 的存在唯一性，无条件稳定性和w ；1 模误差估计。y l z h o u ，l j s h e n g w y u a n 【4 9 ，5 0 】对非线性和拟线性抛物组提出了一类具有并行本性的有限差分方法， 给出了州南u 模意义下解的存在唯。性和无条件稳定收敛性理论。g w y u a n & x d h a n g 5 1 ，5 2 】提出了一类具有界面修正的并行差分算法，并研究了算法的无条 件稳定性、收敛性和并行性，但没有给出误差估计。 v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 在导师羊丹平教授的精心指导下，本文作者在前人工作的基础上，对区域分 解方法傲了部分磺究工作。首先，结合许迸超教授提出的予区域校或法，利用单位 分解函数的特性合理地分配在羹叠区域上的校正薰，对抛物型方程和双曲型方程 构造了一类新烈的并行加性s c h w a r z 有限差分算法( m p f d s ) 。从理论上研究了算 法的秃条侔稳寇性和收敛性，论证7 在每一时闻层上的误蒺的l | 芟敛阶对子酝域重 叠度、空间网格步长、时间步长和迭代次数的依赖性，理论分析和数值算例均表 明，算法具有慧度豹势行性，并且在每一时间层上只需迭饯次或两次帮可达到 收敛的最优阶；数值算例还表明，实际计算中无需很大的区域重叠度。在此慕础之 上，我们利用外推法的思想，更精确地预估各子区域并行计算所需的内边界条件， 从而褥到一类具有界蕊修正的并行有限差分方法( i p f d s ) ，使得在每一时闻层上 只需迭代一次即可达到收敛的最优阶。然后，又把这种方法应用予非重叠型的区 域分解法。在子区域界面醚近避舞显格式，面是嗣壤夕 攘法的思想，把蘸几令时 间层的值的线性组合作为实现备子区域中的并行计算所需的内边界条件，同时使 褥差分格式在内乔藏附近妁截断误差与予区域内部的截断误差保持一致。对抛物 方程和波动方程提出一类内边界颊信校礞的非重豢型区域分解并行有限差分算法 ( n i p f d s ) 和并有限元算法( n i p f e s ) ，理论分析和数值实验证实了算法的并行性、 l | 殳敛佼、无条l 牛稔定瞧。文中弓l 入了叛蠹臼内积和范数定义，给密了算法豹 2 揍最 优误麓估计，为实际应用提供了理论基础，并对每种方法给出了数值验证。龛文共 分疆章。 第一章，对热传导方程提出一类修厩的并行加性s c h w a r z 有限差分方法，或 称为修正的并牙亍子空间校正有限差分算法( m p f d s ) 。算法基于区域分解和予区域 校正，通过引入单位分解函数，合理途分配重叠部分的校正量。算法在每个子区 域上分别进行残量修礁，各子域之间的计算可以并行。理论分析表明，在每一时 闻步，只需校正一次或两次，即可达到最优豹收敛阶。数壤试验验谖7 算浚鼹有 效性和优越性。1 1 给出热传导方程模烈问题及其最常用的向后e u k r 和中心差 分两释隐式有限差分格式；1 。2 1 建立熏叠型区域分解的基本框架，并给出经典 的并行加性s c h w a r z 算法( c p f d s ) ，1 2 2 引入单位分解函数，构造出裙威修正 的并行加性s c h w a r z 有限差分算法；1 3 和1 4 分别讨论了两种修征并行算法收 敛性分析，引入新豹内积嚣范数，给出算法的1 2 模误差佶计；1 5 给出数僮算例， 对( m p f d s ) 和( c p f d s ) 两类算法做了对比，分析了收敛率对离散参数，迭代次 数及熏叠长度的依赖性。本章结果已经在山东火学学报( 理学舨) ，( a p p l i e d m a t h e m a t i c sa n dc o m p u t a t i o n ) ，高校计算数学学报等刊物上发表或接受。 第二章，农上一章的基础上对抛物方程提出类具有界面修正的并行有限差 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 分方法( i p f d s ) 。算法利用外推法的思想，在每一时伺层上更精确地预估内边界 的初始值，从而使得并行算法在每一时间层上只需迭代一次即可达到收敛的最优 阶。2 1 1 对热传导方程的两类常用差分格式进行改造，提出具有界面修正的有限 差分并行算法，2 1 2 给出了两种算法的二2 模误差估计，得到最优的收敛阶误差 结果。2 1 3 通过数值算例验证了算法的稳定性，分析了收敛率对离散参数和重叠 长度的依赖性。2 2 将这种方法推广到一般的二维抛物方程。2 2 1 给出问题的模 型和一些基本记号，2 2 。2 提出了具有界面修正的二维区域分解并行差分算法，在 两个方向上同时进行区域分解和子区域校正，使得算法更具有一般意义。2 2 3 通 过数值算例分析了收敛率对离散参数的依赖性，验证了算法的收敛性，稳定性和 高效性。本章主要结果已投稿刊物。 第三章，对抛物方程提出一类建立在内边界预估校正基础上的非重叠型区域 分解有限差分方法( n i p f d s ) 和有限元方法( n i p f e s ) 。我们在内边界面上避开显 格式，而是利用前几个时间层的值的线性组合作为实现各子区域中的并行计算所 需的内边界条件，同时使得差分格式在内边界面附近的截断误差与子区域内部的 截断误差保持一致，并将稳定性条件减弱为下= o ( h 2 ) 。3 1 研究了抛物方程建立 在内边界预估校正基础上的非重叠型区域分解有限差分方法( n i p f d s ) 。3 1 1 给 出抛物方程模型问题及其两类常用的有限差分隐格式。3 1 2 对这两种格式进行 改造，提出具有内边界预估校正的非重叠型区域分解有限差分方法。3 1 3 给出了 这两种算法的收敛性分析，得到最优的2 2 模误差估计。3 2 研究了抛物方程建立 在内边界预估校正基础上的非重叠型区域分解有限元方法( n i p f e s ) 。3 2 1 给出 抛物方程模型问题及其两类常用的时间离散的有限元格式。3 2 2 对这两种格式 进行改造，提出具有内边界预估校正的非重叠型区域分解有限元方法。3 2 3 给出 了这两种算法的收敛性分析，得到最优的三2 模误差估计。3 3 通过数值算例验证 了算法的收敛性，稳定性和有效性，分析了收敛率对离散参数的依赖性。本章主要 结果已投稿刊物。 第四章，研究了双曲型波动方程的区域分解有限差分方法和有限元方法。波 动方程是一种重要的双曲型偏微分方程，它在物理、化学、生物等不同领域都 有非常重要的意义。已有大量文献研究双曲问题的有限差分方法和有限元方法 1 5 3 5 4 ，5 5 ，5 6 ，5 7 】。对于一阶双曲型方程，适于并行计算的差分方法已经很多【5 8 ，5 9 ，7 4 】， 但对于二阶双曲型方程，这方面的文献尚不多 6 0 ，6 1 】。本章我们将前面提出的几类 区域分解方法应用于波动方程，得到波动方程的几类区域分解并行算法。4 1 给 出模型问题和一些基本知识。4 2 研究了波动方程修正的并行加性s c h w a r z 有限 差分方法，给出了算法描述，误差分析和数值算例。在此基础之上，4 3 研究了波 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 动方程具有界面修正的并行有限差分方法，使得算法在每一时间层上只需迭代一 次即可，收敛性分析和数傻算例均诚实了此点。4 4 研究了波动方程建立在内边 界预倍校鬣基础上的菲重叠型区域分解有限差分方法和有限元方法。给出了算法 描述和二维数值算例。本章部分结果已经在山东大学学报( 理学版) 上发表。 论文串提到的参数g ，无论有无下标，都代表一般的正数。它豹嫠因迪丽髯， 但都与空间网格步长h 和时间步长，- 无关，这将在以后提到。 关键谰：区域分解；s c h w a r z 算法；子区域校正；单位分解：界面修正；有限差 分；有限元；收敛髋分板；数值算铡 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n dd e c o m o o s i t i ( p a r a l l e la 1o r i t h m s d o m a i n d e c o m p o s l t l o nl - a r a e la l g o r l t l a m sf “o r t i m e d e p e n d e n tp a r t i a ld i f f e r e n t i a le q u a t i o a s t i a nm i n ( s c h o o lo fm a t h s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) a b s t r a c t m a t h e m a t i c a lp h y s i c sa n de n g i n e e r i n gp r o b l e m sc a nb et u r n e di n t ot h ep r o b - l e m so fs o l v i n gl a r g ep a r t i a ld i f f e r e n t i a le q u a t i o n s ，s u c ha sr e s e r v i o rs i m u l a t i o n ， t h ed e s i g no fl a r g es c a l eo fs p a c e c r a f t ，a e r o d y n a m i c s ，r e a c t o re t c t h ed o m a i n s t h e ya r ed e f i n e do na r ea l w a y sl a r g ea r e aw i t hh i 【g hd i m e n s i o na n di r r e g u l a rg e - o m e t r y , w h i c hc a u s em u c hd i f f i c u l t yt oc o m p u t a t i o nw h e ns e e k i n gt h e i rs o l u t i o n s i np r a c t i c et h er e q u i r e sf o rt h e i rc o m p u t a t i o np r e c i s i o na r em o r ea n dm o r ee x a c t ， b u tt h es p e e do f t h es i n g l ec o m p u t e ri sb ec l o s et ol i m i t v n t ht h en e e do fg r e a t s c a l es c i e n t i f i cc o m p u t i n ga n dt h em a t u r i t yo fp a r a l l e lc o m p u t i n ge n v i r o n m e n t s ， d o m a i nd e c o m p o s i t i o nm e t h o d s ( d d m ) h a v eb e e na ne f f e c t i v ea p p r o a c ht os o l v e p a r t i a ld i f f e r e n t i a le q u a t i o n sn u m e r i c a l l y i ns h o r t d o m a i nd e c o m p o s i t i o nm e t h o d sd i 、r i d et h e - w h o l ed o m a i ni n t os e v e r a l s u b - d o m a i n s ，a n dt h es h a p eo ft h e s es u b - d o m a i n sm a ya sw e l lb er e g u l a r a n d t h e nt h es o l u t i o n so ft h eo r i g i n a lp r o b l e m sc a nb et r a n s l a t e di n t os o l v i n gt h eq u e s - t i o n so nt h es u b - d o m a i n sr e s p e c t i v e l y d o m a i nd e c o m p o s i t i o nm e t h o d sh a v em a n y a d v a n t a g e st h a to t h e rm e t h 石( 1 8c a n n o tc o m p a r e ： 1 i tc a nd e c o m p o s el a r g es c a l ep r o b l e m si n t os e v e r a ls m a l lo n e s ，f r o mw h i c h t h ec o m p u t i n gs c a l ei ss h o r t e n e d ； 2 t h ec o m p u t a t i o no nt h es u b - d o m a i n sc a nb ep a r a l l e l ，f r o mw h i c ht h e c o m p u t i n gt i m ei ss h o r t e n e d ； 3 d i f f e r e n tn u m e r i c a lm o d d s c a nb eu s e do nd i f f e r e n ts u b s p a c e s ，s ot h a tt h e w h o l em o d e la d a p t st ot h ep r a c t i c a lc o n d i t i o n so fp h y s i c sa n de n g i n e e r i n gp r o b l e m s ； 4 l o c a lq u a s i - u n i f o r mg r i d si sp e r m i t t e d ，i tn e e dn o tt h ew h o l eq u a s i - u n i f o r m g r i d s ，s ot h a td i f f e r e n td i s c r e t ew a y sc a nb eu s e do nd i f f e r e n ts u b - d o m a i n s ； 5 i ft h es h a p e so nt h es u b - d o m a i n sa x er e g u l a re n o u g h ，w ec a na d o p tt h e c o m m o nf a m i l i a rf a s ta l g o r i t h m so rt h ee x i s t e n te f f i c i e n ts o f t w a r e st os o l v et h e v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n p r o b l e m s d o m a i nd e c o m p o s i t i o nm e t h o d sf o rs o l v i n gp a r t i a ld i f f e r e n t i a le q u a t i o n sn u - m e r i c a l l yh a v eb e e ne x t e n s i v e l ys t u d i e d i - 6 】t h e yh a v eb e e na p p l i e dt op r o b l e m s r a n g i n gf r o ml i n e a re l l i p t i ce q u a t i o n s ，p a r a b o l i ce q u a t i o n s 7 s j ，t os y s t e m so fn o n - l i n e a re q u a t i o n s 9 1 d o m a i nd e c o m p o s i t i o no rs u b s t r u c t u r i n gi sa l s oa ne f f e c t i v e a p p r o a c hf o rt h ec o n s t r u c t i o no fp r e - c o n d i t i o n e r s 1 0 一1 剐 ad o m a i nm a yb ep a r t i t i o n e di n t oo v e r l a p p i n gs u b - d o m a i n so rn o n o v e r l a p - p i n gs u b - d o m a i n s t h es e l e c t i o no fs u b - d o m a i 璐m a yb eb a s e do nc o n s i d e r a t i o n s o fa v a i l a b l ec o m p u t i n gr e s o u r c e sa n dt h eg e o m e t r yo ft h eu n d e r l y i n gp a y s i c a lp r o b - l e m s t h el a t t e ri s ，i np a r t i c u l a r ，a p p l i c a b l et oc o m p l e xs y s t e m sw h i c hc o n s i s to f p o s s i b l yd i f f e r e n tg o v e r n i n ge q u a t i o n si nd i f f e r e n tp a y s i c a ls u b - d o m a i n s o v e r l a p - p i n gd o m a i nd e c o m p o s i t i o n sb e c o m eh a r d e rt oi m p l e m e n ti ns u c has e t t i n ga n dt h e n o n o v e r l a p p i n gd o m a i nd e c o m p o s i t i o n sm a yb em o r ed i r e c t l ya p p l i c a b l e ，w h i l et h e t h e o r e t i c a la n a l y s i so ft h en o n o v e r l a p p i n gd o m a i nm e t h o di sm o r ed i f f i c u l t t h ei n i t i a li d e ao fo v e r l a p p i n gd o m a i nd e c o m p o s i t i o nm e t h o d sc a m ef r o mt h e c l a s s i c a ls c h w a r za l t e r n a t i n ga l g o r i t h m s i nr e c e n ty e a r st h et h e o r e t i c a lr e s e a r c h e s a n da p p l i c a t i o n so nd o m a i nd e c o m p o s i t i o nm e t h o d sb a s e do ns c h w a r za l t e r n a t i n g a l g o r i t h m sh a v eb e e nd e v e l o p e da d e q u a t e l ys ot h a tt h e s em e t h o d sb e c o m ev e r y p o w e r f u la n de f f i c i e n ti t e r a t i v em e t h o d s as y s t e m a t i ct h e o r yh a sb e e nd e v e l o p e d f o re l l i p t i cf i n i t ee l e m e n tp r o b l e m si nt h ep a s tf e wy e a r s 【1 9 ，2 0 ，2 3 1 l i o n s 【2 1 2 2 】p r e - s e n t e dak i n do fs c h w a r za l t e r n a t i n ga l g o r i t h mi nt w os u b d o m a i nc a s ef o rh e a t e q u a t i o n sa n dg i v e sac o n v e r g e n c er e s u l tb u td o e sn o tg i v ea n ye r r o re s t i m a t e x c c a i 【2 4 ，2 5 】c o n s t r u c t e dak i n do fa d d i t i v es c h w a r za l g o r i t h m sa n dm u l t i p l i c a - t i v es c h w a r zm e t h o da n dp r o v et h a tt h ec o n v e r g e n c er a t ei ss m a l l e rt h a no n ef o r p a r a b o l i ce q u a t i o n s ，t h e r et h ea u t h o rd i dn o tc o n s i d e rt h ed e p e n d e n c eo f t h ec o n - v e r g e n c ea n dt h ed i s c r e t i z a t i o np a r a m e t e r s h r u ia n dd p y a n g 2 6 一叫c o n s i d e r e d h o wt h ec o n v e r g e n c ea n dt h ee r r o re s t i m a t ed e p e n do nt h ed i a m e t e ro fs u b - d o m a i n s ， t h es p a c i a lm e s h - s i z e ，t h et i m es t e pi n c r e m e n ta n dt h en u m b e ro fi t e r a t i o n sa te a c h t i m el e v e l t h ec l a s s i c a ls c h w a r za l t e r n a t i n ga l g o r i t h mi sn o tp a r a l l e l w i t ht h e d e v e l o p m e n to fp a r a l l e lc o m p u t i n g ，m a n ya d d i t i v eo rp a r a l l e ls c h w a r za l g o r i t h m s h a v eb e e nd e v e l o p e d m d r y j a ，0 b w i l d u n d ，t m s h i he t c 【3 5 ，3 6 , 3 7 ，3 ，3 8 】p r o - p o s e dd i f f e r e n ta l g o r i t h m sr e s p e c t i v e l y t h e s ea l g o r i t h m sc o n q u e r e dt h el i m i t a t i o n o fs e r i a ld a t at r a n s f e r ，w h i c hi si nf a v o ro fp a r a l l e lc o m m u n i c a t i o n j x u 3 9 ，4 0 1g i v e s s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n as y s t e m a t i ci n t r o d u c t i o nt oan u m b e ro fi t e r a t i v em e t h o d sf o rs y m m e t r i cp o s i t i v e d e f i n i t ep r o b l e m s t h em a j o rc o n c e r ni si nt h et h e o r e t i c a la s p e c to ft h ea l g o r i t h m s t h a ta r ec l a s s i f i e di n t ot w og r o u p s ，n a m e l y s u c c e s s i v es u b s p a c ec o r r e c t i o n ( s s c ) m e t h o da n dp a r a l l e ls u b s p a c ec o r r e c t i o n ( p s c ) m e t h o db yu s i n gt h en o t i o n so f p a r t i t i o no fu n i t ya n ds u b s p a c ec o r r e c t i o n ，i n 4 1 】，t h i sm e t h o di sa p p l i e dt ot h e f i n i t ee l e m e n tm e t h o do fp a r a b o l i ce q u a t i o na n dp r o v e dt h ec o n v e r g e n c er a t e0 ( 6 m ) w i t h0 6 九) y lz h o u ， l 工s h e n g w y u a n 4 9 ，5 0 c o n s t r u c t e dak i n do fp a r a l l e lf i n i t es c h e m e sw i t h i n t r i n s i cp a r a h e l i s mf o rn o n l i n e a ra n dq u a s i - l i n e a rp a r a b o l i cs y s t e m s ，a n dg a v et h e e x i s t e n c e ，u n i q u ea n dt h eu n c o n d i t i o n a ls t a b i l i t yu n d e rt h ed i s c r e t e 州”l jn o r m g w y u a n x d h a n g 5 1 ，5 2 lp r o p o s e dak i n do fi t e r a t i v em e t h o df o rh e a tc o n - d u c te q u a t i o n sb a s e do ni n t e r f a c ec o r r e c t i o n ，a n dt h es t a b i l i t y , c o n v e r g e n c ea n d s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n t h ep a r a l l e l i s ma r es t u d i e d ，b u tw i t h o u te r r o re s t i m a t ea n a l y s i s u n d e rt h ea b o r a t i v eg u i d a n c eo fp r o f e s s o rd a n p i n gy a n g ，t h ea u t h o rh a sf i n - i s h e dt h i sd i s s e r t a t i o nc o n s i s t i n go fs o m ew o r ko nd o m a i nd e c o m p o s i t i o nm e t h o d s f i r s t l y ，b a s e do nt h ep s cm e t h o dp r o p o s e db yp r o f j i n c h a ox u ，w ec o n s t r u c t an e wk i n do fp a r a l l e la d d i t i v es c h w a r zf i n i t ed i f f e r e n c ea l g o r i t h m s ( m p f d s ) f o r p a r a b o l i ca n dw a v ee q u a t i o n s ，b yu s i n gt h es p e c i a l i t yo ft h ep a r t i t i o nf u n c t i o n so f u n i t yt od i s t r i b u t et h ec o r r e c t i o n so no v e r l a p p i n gd o m a i n sr e a s o n a b l y t h es t a b i l i t y a n dc o n v e r g e n c ea n a l y s i so ft h e s ep a r a l l e la l g o r i t h m si sg i v e n ，a n dw ed i s c u s s e dt h e d e p e n d e n c eo ft h ec o n v e r g e n tr a t eo nt h es p a c i a lm e s hs i z e ，t h et i m ei n c r e m e n t ，t h e i t e r a t i o nt i m e sa n dt h ed o m a i no v e r l a p p i n gd e g r e e b o t ht h e o r e t i c a la n a l y s i sa n d t h en u m e r i c a le x a m p l e ss h o wt h a t ，t h e s ea l g o r i t h m sh a v eh i g hp a r a l l e l i s m n u m e r - i c a le x p e r i m e n t sa l s oi n d i c a t et h a tas m a l ls u b s p a c eo v e r l a p p i n gd e g r e ei se n o u g h f o rt h ep r a c t i c a lc o m p u t a t i o n i nt h en e x tp l a c e ，t os o l v i n gt h ee q u a t i o n so nt h e s u b - d o m a i n sb yi m p l i c i ts c h e m e sm o r ea c c u r a t e l y , w ec o r r e c tt h ei n n e rb o u n d a r y c o n d i t i o n sw i t ht h ei d e ao ft h ee x t r a p o l a t i o nm e t h o d t h u sw eg e ta n o t h e rk i n do f p a r a l l e lf i n i t ed i f f e r e n c ea l g o r i t h m s ( i p f d s ) f o rp a r a b o l i cp r o b l e m sa n dh y p e r b o l i c p r o b l e m s ，w h i c hn e e d1 1 0i t e r a t i o na te a c ht i m el e v e la ta l l ，w ep r o v e dt h i sb ye r r o r a n a l y s i sa n dn u m e r i c a le x p e r i m e n t s t h i r d l y , w ea p p l i e dt h ei n t e r f a c ep r e d i c t i o n - c o r r e c t i o ni d e at on o n o v e r l a p p i n gd o m a i nd e c o m p o s i t i o nm e t h o d a v o i d i n gt h e e x p l i c i tp r o c e d u r e so nt h ei n t e r f a c e ，w eu s et h el i n e a rc o m b i n a t i o no ft h ev a l u e so n f o r m e rs e v e r a lt i m el e v e l 8a st h eb o u n d a r yc o n d i t i o n st or e a l i z ep a r a l l e lc o m p u t i n g o fi m p l i c i ts c h e m e so nt h es u b - d o m a i n s ，a n dt h e nc o n s t r u c tak i n do fn o n o v e r - l a p p i n gd o m a i nd e c o m p o s i t i o np a r a l l e lf i n i t ed i f f e r e n c ep r o c e d u r e s ( n i p f d s ) a n d p a r a l l e lf i n i t ee l e m e n tp r o c e d u r e s ( n i p f e s ) w i t h o u ti 乇e r a t i o n ，t h es t a b i l i t yc o n d i - t i o n so ft h e s ep a r a l l e lp r o c e d u r e sb e c o m ev e r yw e a k a tt h es a m et i m e ，t h eo r d e r