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

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

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

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

1.1 基本思想

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

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

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

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

1.2 實現(xiàn)方案

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

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

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

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

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

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

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

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

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

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

4 回顧與展望

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

參考文獻(xiàn)

[1]李曉梅，莫則堯.多重網(wǎng)格算法綜述[J].中國科學(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].長沙大學(xué)學(xué)報，第2期，1997年6月

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

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

作者簡介

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