時(shí)間依賴偏微分方程的區(qū)域分解并行算法.pdf

1、山東大學(xué)博士學(xué)位論文時(shí)間依賴偏微分方程的區(qū)域分解并行算法姓名：田敏申請學(xué)位級別：博士專業(yè)：計(jì)算數(shù)學(xué)指導(dǎo)教師：羊丹平20070415S h a n d o n g U n i v e r s i t yD o c t o r a l D i s s e r t a t i o n展，已成為一種有效的迭代方法。橢圓型方程有限元方法已經(jīng)建立了系統(tǒng)的的理論分析【1 9 ，2 0 ，2 3 ] ；L i o n s [ 2 1 ，2 2 】對熱傳

2、導(dǎo)方程提出了的一類建立在兩個(gè)子區(qū)域基礎(chǔ)上的S c h w a r z 交替算法，給出了收斂性結(jié)果，但沒有給出誤差估計(jì)；X ．C ．C a l 【2 4 ' 2 5 】構(gòu)建了一類加性S c h w a r z 算法和乘性S c h w a r z 算法，并證明了算法的收斂性，但作者沒有詳細(xì)討論收斂率對離散參數(shù)的依賴性；H ．R u ia n dD ．P ．Y a n g [ 2 6 - 3 4 ] 論證了在每一時(shí)間層上收斂性及誤差

3、估計(jì)對子區(qū)域長度、空間網(wǎng)格步長、時(shí)間步長和迭代次數(shù)的依賴性。經(jīng)典的S c h w a r z 交替法不是并行的，隨著并行計(jì)算的發(fā)展，出現(xiàn)了多種可完全并行化的加性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 皆獨(dú)立提出不同的算法，這些算法可克服交替方法的串行性，更利于并行處理。J ．X u [ a 9 ，

4、4 0 l 系統(tǒng)地介紹了求解對稱正定問題的各種迭代方法，主要是利用區(qū)域分解和子區(qū)域校正法從理論上建立了并行子區(qū)域校正和串行子區(qū)域校正這兩類算法。f 4 1 1 將此方法應(yīng)用于拋物型方程有限元方法，并得到了收斂階0 ( 巧m ) ，其中0 < 6 < 1 。非重疊型區(qū)域分解法將計(jì)算區(qū)域分解成若干個(gè)獨(dú)立的不同子區(qū)域，具有高度并行、網(wǎng)格剖分靈活和易于計(jì)算等優(yōu)點(diǎn)。對于此方法，內(nèi)邊界上的預(yù)處理算子是必須要考慮的。一般需要附加三種形式的

5、內(nèi)邊界條件：解的連續(xù)性條件( D D ) 、流量的連續(xù)性條件( N N ) 和混合條件( D N ) 。G e o r g e ，D r y j a ，S m i t h 等在這方面做了很多工作。但各子問題內(nèi)邊界條件需要通過迭代處理，計(jì)算比較復(fù)雜。在許多實(shí)際計(jì)算中，由于對時(shí)間步長穩(wěn)定性的要求，發(fā)展方程的計(jì)算通常采用隱格式，但隱式格式難以直接在并行機(jī)上實(shí)施。顯式差分格式盡管易于實(shí)施，但它的穩(wěn)定性條件苛刻。當(dāng)計(jì)算問題的規(guī)模相當(dāng)大，例如需要具

6、有數(shù)千甚至上萬臺處理器的大型并行計(jì)算機(jī)進(jìn)行計(jì)算時(shí)，數(shù)據(jù)的強(qiáng)相關(guān)與全局通訊等問題就會成為制約實(shí)現(xiàn)高性能計(jì)算的突出瓶頸問題。因此，改造現(xiàn)有的隱式格式，研究適用于大型并行計(jì)算機(jī)上的并行計(jì)算方法是目前大型科學(xué)工程計(jì)算中迫切需要解決的具有挑戰(zhàn)性的問題。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 ，鎬】提出了一類顯／隱非重疊區(qū)域分裂格式，在內(nèi)邊界上采用大步長顯格式，

7、各子域內(nèi)采用隱格式。顯隱結(jié)合無需迭代計(jì)算，得到最優(yōu)的l ∞模誤差估計(jì)，但內(nèi)邊界格式的顯性仍然引入了一定的穩(wěn)定性條件( 丁≤H 2 ) ?！? 1 】、[ 5 2 ] 提出了一類具有界面修正的并行差分算法，并給出了算法的存在唯一性，無條件穩(wěn)定性和w ；’1 模誤差估計(jì)。Y ．L ．Z h o u ，L ．J ．S h e n ＆G ．W ．Y u a n 【4 9 ，5 0 】對非線性和擬線性拋物組提出了一類具有并行本性的有限差分方法，給