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

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

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

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

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

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

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

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

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

9、斂速率.
　　 第二章,給出了求解二維泊松方程的另一種新的并行超松弛(P-SOR)迭代算法.利用四個超松弛(SOR)迭代格式完成算法,實現(xiàn)過程類似于第一章,最后數(shù)值試驗說明此算法的優(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)于時間的消耗,速度及空間復(fù)雜性的比較,表明本節(jié)提出的算法更為有效.
　　 第三章,基于區(qū)域分解和分組顯式思想,給出了求解二維擴散方程的一種新的有限差分并行算法.首先構(gòu)造了逼近擴散方程的四個新的差分格式,然后將求解域劃分為四個子域,在奇數(shù)或偶數(shù)時間層上算法的實現(xiàn)過程類似于第一章,并證明了格式的無條件穩(wěn)定性,且誤差階為O(τ+h2).最后

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