二維泊松方程和擴(kuò)散方程的一類顯式并行算法.pdf

1、諸多物理現(xiàn)象都可用泊松方程和擴(kuò)散方程來描述,泊松方程是數(shù)學(xué)中一個(gè)常見于靜電學(xué),機(jī)械工程和理論物理的偏微分方程；擴(kuò)散方程常見于化學(xué)擴(kuò)散,熱傳導(dǎo),醫(yī)學(xué),生化方面和一定的生物反應(yīng)過程.由許多偏微分方程的標(biāo)準(zhǔn)離散化得到的用于求解這兩類方程的若干快速計(jì)算方法,受到了人們的密切關(guān)注.目前,大規(guī)模的科學(xué)工程計(jì)算需要高速度,大容量的并行機(jī)和有效的數(shù)值并行方法和并行算法.考慮到成本與速度,并行機(jī)的使用起到了非常重要的作用.同時(shí),區(qū)域分解方法是一個(gè)很有力的

2、工具,可將整個(gè)問題化為各個(gè)子域問題,然后并行求解,由于其構(gòu)造簡(jiǎn)單,速度快,得到了廣泛應(yīng)用.
　　 在現(xiàn)代數(shù)值方法中,有限差分方法是最早且很完美的求解方法,所以對(duì)于研究拋物型和橢圓型問題的有限差分方法,備受人們的關(guān)注和重視.
　　 有限差分方法對(duì)于橢圓型問題的逼近往往需要求解較大的稀疏矩陣問題[1],隨著現(xiàn)代計(jì)算機(jī)的發(fā)展,迭代方法如Jacobi,Gauss-Seidel,SOR方法[2,3]常被用在此大型計(jì)算中,也是解此大

3、型方程組的一類很好的方法.眾所周知,泊松方程的并行單元是利用Jacobi并行迭代算法[4]來解決的,因其有明顯的并行性.[5]中馮慧等通過不同點(diǎn)的隱式差分格式之間的相互約化來建立新型迭代(Stencil)方法,此方法和Jacobi方法同樣具有并行性,卻比Jacobi收斂快.超松弛(SOR)迭代方法是很有效的方法,卻沒有本質(zhì)的并行性.目前,僅有較少的方法可以實(shí)現(xiàn)并行迭代,如著色法[6]和點(diǎn)并行SOR方法[7]等,但很難拓展.
　　

4、 而對(duì)于求解時(shí)間依賴的擴(kuò)散問題的數(shù)值方法,主要有兩種類型,顯式和隱式差分方法.顯式差分方法很容易在并行機(jī)上實(shí)現(xiàn),有好的并行性,但由于穩(wěn)定性限制[8],對(duì)時(shí)間步長(zhǎng)的限制相當(dāng)苛刻.隱式差分方法是絕對(duì)穩(wěn)定的,但在每一時(shí)間步都需要去求解較大的線性或非線性代數(shù)方程組,計(jì)算效率不高.因此需要構(gòu)造具有良好穩(wěn)定性,并行性和計(jì)算精度的新的差分方法.八十年代初,Evans和Abdullah[9-11]設(shè)計(jì)了分組顯式方法保證了數(shù)值計(jì)算的穩(wěn)定性,同時(shí)由于顯式求

5、解而使該方法具有很好的并行性質(zhì),它是不同類型Saul'yev非對(duì)稱格式[12]的恰當(dāng)組合.在此基礎(chǔ)上,張寶琳等在[13-15]中提出利用Saul'yev非對(duì)稱格式構(gòu)造分段隱式格式的思想,并恰當(dāng)?shù)氖褂媒惶婕夹g(shù)建立了多種顯-隱式和純隱式交替并行方法,取得了穩(wěn)定性和并行兼顧的研究結(jié)果.另外,Peaceman與Rachford在[16]中提出的交替方向隱式方法(ADI)具有一些相當(dāng)好的性質(zhì),但是對(duì)于多指令流多數(shù)據(jù)流(MIMD)并行機(jī)來說,由于每

6、個(gè)并行處理器在奇數(shù)時(shí)間層計(jì)算一列或若干列的數(shù)值,而在偶數(shù)時(shí)間層計(jì)算一行或若干行的數(shù)值,或者是相反,因而在每個(gè)時(shí)間層大部分?jǐn)?shù)據(jù)需要從一個(gè)處理器傳送到另一個(gè)處理器,這是很不經(jīng)濟(jì)的.
　　 在導(dǎo)師王文洽教授的悉心指導(dǎo)下,本文作者基于并行計(jì)算,區(qū)域分解和交替分組顯式思想,對(duì)二維泊松方程和擴(kuò)散方程構(gòu)造了一類有效的顯式并行算法,對(duì)方法進(jìn)行了理論分析并給出了數(shù)值算例,均證實(shí)了我們?cè)诒疚闹兴岬乃惴ㄊ怯行У?實(shí)用的.全文共分四章,下面幾段將簡(jiǎn)要

7、介紹一下各章的主要內(nèi)容.
　　 第一章,基于區(qū)域分解思想,對(duì)二維泊松方程提出了一種新的有限差分并行迭代(FDPI)算法.首先將求解區(qū)域劃分為四個(gè)子區(qū)域,并從經(jīng)典的五點(diǎn)差分格式構(gòu)造出四個(gè)新的迭代格式.然后,在迭代次數(shù)為奇數(shù)或偶數(shù)時(shí),分別給出新算法的實(shí)現(xiàn)過程,且證明了其收斂性.最后給出了數(shù)值算例以驗(yàn)證此迭代算法的有效性和精確性,而且也適用于二維變系數(shù)橢圓型問題.此章內(nèi)容已發(fā)表在《Numerical Methods for Parti

8、alDifferential Equations》.
　　 本章內(nèi)容的創(chuàng)新之處在于雖然迭代格式是半隱式的,但可結(jié)合邊界條件和分組顯式思想,顯式地,并行地計(jì)算.特別地,格式中添加了松弛因子ω并理論分析得到最佳松弛因子ωopt,大大的提高了收斂速率,減少了迭代次數(shù).在與Jacobi,Gauss-Seidel迭代算法和數(shù)學(xué)Stencil[5]方法的數(shù)值結(jié)果比較中發(fā)現(xiàn),我們所提出的FDPI算法具有更少的迭代次數(shù),更短的計(jì)算時(shí)間和更快的收

9、斂速率.
　　 第二章,給出了求解二維泊松方程的另一種新的并行超松弛(P-SOR)迭代算法.利用四個(gè)超松弛(SOR)迭代格式完成算法,實(shí)現(xiàn)過程類似于第一章,最后數(shù)值試驗(yàn)說明此算法的優(yōu)越性.本章內(nèi)容已投到《International Journal of Computer Mathemat-ics》.
　　 此章內(nèi)容的創(chuàng)新之處在于,眾所周知的SOR算法并沒有明顯的并行性,而我們給出的新算法(P-SOR)具有本質(zhì)并行性,并且

10、通過與Jacobi,Gauss-Seidel,數(shù)學(xué)Stencil[5]及第一章中的FDPI算法關(guān)于時(shí)間的消耗,速度及空間復(fù)雜性的比較,表明本節(jié)提出的算法更為有效.
　　 第三章,基于區(qū)域分解和分組顯式思想,給出了求解二維擴(kuò)散方程的一種新的有限差分并行算法.首先構(gòu)造了逼近擴(kuò)散方程的四個(gè)新的差分格式,然后將求解域劃分為四個(gè)子域,在奇數(shù)或偶數(shù)時(shí)間層上算法的實(shí)現(xiàn)過程類似于第一章,并證明了格式的無條件穩(wěn)定性,且誤差階為O(τ+h2).最后

11、數(shù)值試驗(yàn)說明算法的適用性,并且時(shí)間步長(zhǎng)充分小的前提下誤差關(guān)于空間達(dá)到2階.本章內(nèi)容已投到《Applied Mathematicsand Computation》.
　　 第四章,提出了求解二維擴(kuò)散方程一種新的交替分組(N-AGE)算法.采用顯式方法[10],使用第三章中構(gòu)造的四個(gè)差分格式在奇數(shù)或偶數(shù)時(shí)間層上交替使用,來完成新的顯式算法.最后數(shù)值試驗(yàn)通過與第三章中的并行算法和分組顯式方法[10]在同時(shí)間和不同空間參數(shù)下誤差的比較,