多重網格法綜述

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

關鍵詞：多重網格算法;偏微分方程;并行計算

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

1 基本原理與應用準則

1.1 基本思想

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

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

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

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

1.2 實現方案

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

2 已取得的成果和待擴充領域

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

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

3 多重網格算法的并行計算

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

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

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

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

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

4 回顧與展望

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

參考文獻

[1]李曉梅，莫則堯.多重網格算法綜述[J].中國科學基金，1996，010（001）：4-11.

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

[3]劉昊，多重網格法應用[J].長沙大學學報，第2期，1997年6月

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

[5]肖映雄.代數多重網格算法研究及其在固體力學計算中的應用[D].湘潭大學，2006.

作者簡介

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