多重網(wǎng)格法綜述

摘 要：多重網(wǎng)格法就是由對(duì)偏微分方程里得出的代數(shù)方程組的求解的研究引發(fā)出來(lái)的一種計(jì)算方法，它已經(jīng)成為求解大型科學(xué)與工程計(jì)算問(wèn)題的最有效方法之一。本文以多重網(wǎng)格算法的基本物理背景、應(yīng)用準(zhǔn)則以及已取得的應(yīng)用成果，對(duì)多重網(wǎng)格算法并行效率進(jìn)行研究探討，及基于當(dāng)前并行計(jì)算的特點(diǎn)，展望多重網(wǎng)格并行計(jì)算的研究方向。

關(guān)鍵詞：多重網(wǎng)格算法;偏微分方程;并行計(jì)算

多重網(wǎng)格法，是目前應(yīng)用于大型科學(xué)計(jì)算的一類有效的、新穎的計(jì)算方法，經(jīng)過(guò)幾十年得發(fā)展，多重網(wǎng)格算法已經(jīng)成為數(shù)值計(jì)算領(lǐng)域中的一種加速迭代收斂的技術(shù)，一門(mén)新的學(xué)科，而不僅僅是一種單純的算法。尤其進(jìn)入90年代后，由于O，Widlund，J.Bramble，J.Xu等人的努力，視所有迭代方法為子空間校正，將多重網(wǎng)格融入新的理論框架中，使得以前棘手的收斂性證明在這里變得相對(duì)容易，并與區(qū)域分解算法融為一體，二者僅子區(qū)域的劃分不同，從而使得傳統(tǒng)多重網(wǎng)格技術(shù)煥發(fā)出強(qiáng)大生命力和應(yīng)用前景，尤其在并行計(jì)算機(jī)上的應(yīng)用。多重網(wǎng)格算法，無(wú)論串行和并行，都是當(dāng)今數(shù)值計(jì)算領(lǐng)域最活躍的分支之一。

1 基本原理與應(yīng)用準(zhǔn)則

1.1 基本思想

在一般的數(shù)值求解過(guò)程中，首先是把問(wèn)題離散化，在一個(gè)有限維近似的空間中選擇近似的代數(shù)方程組，然后設(shè)計(jì)一個(gè)數(shù)值過(guò)程，近似地求解這個(gè)離散方程組，然而通常在離散化和求解過(guò)程中并無(wú)相互作用，這就造成了很大浪費(fèi)。

如果在求解過(guò)程中，用一系列逐步加密或減疏的網(wǎng)格去離散求解區(qū)域，在不同疏密的網(wǎng)格層上用迭代法求解，以平滑不同頻率的誤差分量，然后通過(guò)網(wǎng)格層間的適當(dāng)聯(lián)系將在所有各重網(wǎng)格上消除誤差分量的效果綜合起來(lái)，就可以將所有尺度范圍內(nèi)（從整個(gè)定義域到最小的迭代步長(zhǎng)）的誤差分量有效地減弱，這就是多重網(wǎng)格法的基本思想。

多重網(wǎng)格法優(yōu)點(diǎn)的最直觀的理解是，為了在第 k層得到方程的解，可以先將方程離散在第k-1層進(jìn)行松弛迭代，然后插值回到第k層中作為方程在k層中的近似解。由于在k-1層中的迭代格點(diǎn)數(shù)要比第 k層中少得多，從而節(jié)省了計(jì)算時(shí)間，同理k-1層中的近似解可得自于k-2層，依次類推直到k=1層。在數(shù)學(xué)上表現(xiàn)為針對(duì)如下形式的橢圓型方程：

（1）能對(duì)其尋求形Lu=f（2）的解。式中L為對(duì)式（1）進(jìn)行有限差分近似而形成的離散線性算子，u是該問(wèn)題的精確解，f是一個(gè)隨機(jī)強(qiáng)迫項(xiàng)。如果用v來(lái)表示u的近似值（初猜值），d表示其偏差，則用u=v+d（3）定義剩余r=f–Lv（4）用來(lái)衡量v未能滿足局地線性算子的程度。由式（3）求得v的表達(dá)式后代入式（4），可得到Ld=r（5），可見(jiàn)偏差d滿足解為u的同一方程，問(wèn)題轉(zhuǎn)化為由式（5）求解d，若d得解則可據(jù)式（3）計(jì)算出u。

1.2 實(shí)現(xiàn)方案

多重網(wǎng)格迭代法從最細(xì)網(wǎng)格層上的初猜值v開(kāi)始，用松弛法進(jìn)行迭代直到收斂速度變慢，這時(shí)相對(duì)于此網(wǎng)格距來(lái)說(shuō)小尺度的誤差已大多被平滑掉了，而大尺度的誤差只是稍微有所減弱。為了使收斂加速，應(yīng)使用較粗的網(wǎng)格，這時(shí)須把剩余r轉(zhuǎn)移到下一層較粗的網(wǎng)格上，迭代求解式（5），當(dāng)收斂速度變慢時(shí)再將剩余r轉(zhuǎn)移到下一層更粗的網(wǎng)格上。這一過(guò)程將持續(xù)到將剩余轉(zhuǎn)移到最粗的網(wǎng)格層上，然后在最粗的網(wǎng)格層上精確求解式（5），之后將求得的偏差d內(nèi)插到上一層較細(xì)網(wǎng)格上并加到v上，便可得到在此網(wǎng)格層上一個(gè)經(jīng)改進(jìn)后的u的近似值。反復(fù)循環(huán)進(jìn)行這一過(guò)程直到求得最細(xì)網(wǎng)格層上u的精確值。

2 已取得的成果和待擴(kuò)充領(lǐng)域

現(xiàn)在多重網(wǎng)格方法的研究依然是一個(gè)熱點(diǎn)，特別是在非線性非對(duì)稱問(wèn)題的求解上的使用，另一個(gè)發(fā)展方向是方法的推廣和軟件實(shí)現(xiàn)。

隨著時(shí)間的推移，多重網(wǎng)格算法被推廣到別的領(lǐng)域，取得了大量成果，如統(tǒng)計(jì)物理中的快速M(fèi)onte-Carlo方法，積分變換，人工智能中N個(gè)體的相互關(guān)系識(shí)別，全局優(yōu)化問(wèn)題，圖像處理，量子色動(dòng)力學(xué)（QCD）等等。同時(shí)，多重網(wǎng)格技術(shù)與別的領(lǐng)域中高效方法結(jié)合，產(chǎn)生了許多新方法，如高精度譜多重網(wǎng)格算法，處理非規(guī)則問(wèn)題的代數(shù)多重網(wǎng)格方法，與有限元結(jié)合的協(xié)調(diào)，非協(xié)調(diào)元多重網(wǎng)格算法等等。

3 多重網(wǎng)格算法的并行計(jì)算

并行計(jì)算的最終目的是縮短計(jì)算時(shí)間，實(shí)現(xiàn)的前提是并行計(jì)算的可擴(kuò)展性，當(dāng)前并行計(jì)算朝協(xié)同方向發(fā)展，其典型代表為MMP和工作站機(jī)群。一般具有以下特點(diǎn)：1）分布式存儲(chǔ)，2）擁有大量處理單元，幾十到兒百個(gè)甚至上千個(gè)不等，每個(gè)處理單元功能較強(qiáng)，每秒幾千萬(wàn)次到幾億次甚至幾十億次浮點(diǎn)結(jié)果。3）擁有高性能互聯(lián)網(wǎng)絡(luò)。

實(shí)踐證明高效率的獲取一般通過(guò)以下途徑：1）數(shù)據(jù)并行或區(qū)域分解：將任務(wù)按區(qū)域進(jìn)行分割，分配給各臺(tái)處理機(jī)完成。2）大粒度并行，相對(duì)增加數(shù)值計(jì)算比重。而影響并行效率的關(guān)鍵因素為：（1）負(fù)載平衡;（2）通訊與負(fù)載的比例;3）計(jì)算與通訊的重疊，屏蔽通訊延遲時(shí)間。

針對(duì)以上并行計(jì)算特點(diǎn)，獲取較高的經(jīng)典多重網(wǎng)格算法并行效率難度比較大，因此必須尋求新的途徑，與當(dāng)前流行的另一數(shù)值方法：區(qū)域分解算法有效結(jié)合。

區(qū)域分解算法將問(wèn)題的求解區(qū)域劃分成幾個(gè)或幾十個(gè)相互重疊或不重疊子區(qū)域，分配給各臺(tái)處理機(jī) 。早期典型代表為Schwarz類型算法，具有很好的局部性，負(fù)載平衡能力強(qiáng)，并行效率高，程序設(shè)計(jì)簡(jiǎn)單。O.Widlund指出，類似于這種沒(méi)有任何全局信息交換的區(qū)域分解算法，迭代條件數(shù)至少為，其中H為所有子區(qū)域直徑的最大值，

即隨著子區(qū)域個(gè)數(shù)的增加，條件數(shù)呈平方增長(zhǎng)，這無(wú)疑給大規(guī)模并行計(jì)算帶來(lái)困擾，迫切要求出現(xiàn)條件數(shù)與子區(qū)域個(gè)數(shù)無(wú)關(guān)的區(qū)域分解算法。為此，早期有J.Bramble等人的迭代子結(jié)構(gòu)方法，實(shí)際上為非重疊區(qū)域分解算法，程序設(shè)計(jì)稍微復(fù)雜。后來(lái)出現(xiàn)了Dryja與O.Widlund針對(duì)對(duì)稱正定問(wèn)題提出的疊加型Schwarz算法，或小區(qū)域重疊型區(qū)域分解算法，其條件數(shù)與子區(qū)域個(gè)數(shù)無(wú)關(guān)，且適合于大規(guī)模并行。

4 回顧與展望

回顧多重網(wǎng)格方法的發(fā)展歷程，我們可以看到，就如一個(gè)學(xué)科發(fā)展的一般規(guī)律，這一方法提出之初，并沒(méi)有受到人們的重視。當(dāng)人們認(rèn)識(shí)到它的優(yōu)越性，大量的人力物力投入到這一方法的研究中。于是這一方法得到了極大的發(fā)展。當(dāng)然由于問(wèn)題的不斷深化，問(wèn)題的廣度已經(jīng)很大，這一研究的熱潮還沒(méi)有過(guò)去，某種程度上還在升溫。同時(shí)一種方法的理論研究已經(jīng)初具規(guī)模，而方法的實(shí)際應(yīng)用還在推廣中。

參考文獻(xiàn)

[1]李曉梅，莫?jiǎng)t堯.多重網(wǎng)格算法綜述[J].中國(guó)科學(xué)基金，1996，010（001）：4-11.

[2]Brandt A. Multiscale computational methods：research activties，Multigard Comput92，PB93-133916，1992.

[3]劉昊，多重網(wǎng)格法應(yīng)用[J].長(zhǎng)沙大學(xué)學(xué)報(bào)，第2期，1997年6月

[4]鄭祚芳，沈桐立，多重網(wǎng)格方法在資料同化中的應(yīng)用[J].氣象科技，第31卷第4期，2003年8月

[5]肖映雄.代數(shù)多重網(wǎng)格算法研究及其在固體力學(xué)計(jì)算中的應(yīng)用[D].湘潭大學(xué)，2006.

作者簡(jiǎn)介

楊志博（1986-），男，河南商丘，助教，碩士，研究方向：計(jì)算數(shù)學(xué)。