多重网格法综述

摘 要：多重网格法就是由对偏微分方程里得出的代数方程组的求解的研究引发出来的一种计算方法，它已经成为求解大型科学与工程计算问题的最有效方法之一。本文以多重网格算法的基本物理背景、应用准则以及已取得的应用成果，对多重网格算法并行效率进行研究探讨，及基于当前并行计算的特点，展望多重网格并行计算的研究方向。

关键词：多重网格算法;偏微分方程;并行计算

多重网格法，是目前应用于大型科学计算的一类有效的、新颖的计算方法，经过几十年得发展，多重网格算法已经成为数值计算领域中的一种加速迭代收敛的技术，一门新的学科，而不仅仅是一种单纯的算法。尤其进入90年代后，由于O，Widlund，J.Bramble，J.Xu等人的努力，视所有迭代方法为子空间校正，将多重网格融入新的理论框架中，使得以前棘手的收敛性证明在这里变得相对容易，并与区域分解算法融为一体，二者仅子区域的划分不同，从而使得传统多重网格技术焕发出强大生命力和应用前景，尤其在并行计算机上的应用。多重网格算法，无论串行和并行，都是当今数值计算领域最活跃的分支之一。

1 基本原理与应用准则

1.1 基本思想

在一般的数值求解过程中，首先是把问题离散化，在一个有限维近似的空间中选择近似的代数方程组，然后设计一个数值过程，近似地求解这个离散方程组，然而通常在离散化和求解过程中并无相互作用，这就造成了很大浪费。

如果在求解过程中，用一系列逐步加密或减疏的网格去离散求解区域，在不同疏密的网格层上用迭代法求解，以平滑不同频率的误差分量，然后通过网格层间的适当联系将在所有各重网格上消除误差分量的效果综合起来，就可以将所有尺度范围内（从整个定义域到最小的迭代步长）的误差分量有效地减弱，这就是多重网格法的基本思想。

多重网格法优点的最直观的理解是，为了在第 k层得到方程的解，可以先将方程离散在第k-1层进行松弛迭代，然后插值回到第k层中作为方程在k层中的近似解。由于在k-1层中的迭代格点数要比第 k层中少得多，从而节省了计算时间，同理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转移到下一层更粗的网格上。这一过程将持续到将剩余转移到最粗的网格层上，然后在最粗的网格层上精确求解式（5），之后将求得的偏差d内插到上一层较细网格上并加到v上，便可得到在此网格层上一个经改进后的u的近似值。反复循环进行这一过程直到求得最细网格层上u的精确值。

2 已取得的成果和待扩充领域

现在多重网格方法的研究依然是一个热点，特别是在非线性非对称问题的求解上的使用，另一个发展方向是方法的推广和软件实现。

随着时间的推移，多重网格算法被推广到别的领域，取得了大量成果，如统计物理中的快速Monte-Carlo方法，积分变换，人工智能中N个体的相互关系识别，全局优化问题，图像处理，量子色动力学（QCD）等等。同时，多重网格技术与别的领域中高效方法结合，产生了许多新方法，如高精度谱多重网格算法，处理非规则问题的代数多重网格方法，与有限元结合的协调，非协调元多重网格算法等等。

3 多重网格算法的并行计算

并行计算的最终目的是缩短计算时间，实现的前提是并行计算的可扩展性，当前并行计算朝协同方向发展，其典型代表为MMP和工作站机群。一般具有以下特点：1）分布式存储，2）拥有大量处理单元，几十到儿百个甚至上千个不等，每个处理单元功能较强，每秒几千万次到几亿次甚至几十亿次浮点结果。3）拥有高性能互联网络。

实践证明高效率的获取一般通过以下途径：1）数据并行或区域分解：将任务按区域进行分割，分配给各台处理机完成。2）大粒度并行，相對增加数值计算比重。而影响并行效率的关键因素为：（1）负载平衡;（2）通讯与负载的比例;3）计算与通讯的重叠，屏蔽通讯延迟时间。

针对以上并行计算特点，获取较高的经典多重网格算法并行效率难度比较大，因此必须寻求新的途径，与当前流行的另一数值方法：区域分解算法有效结合。

区域分解算法将问题的求解区域划分成几个或几十个相互重叠或不重叠子区域，分配给各台处理机 。早期典型代表为Schwarz类型算法，具有很好的局部性，负载平衡能力强，并行效率高，程序设计简单。O.Widlund指出，类似于这种没有任何全局信息交换的区域分解算法，迭代条件数至少为，其中H为所有子区域直径的最大值，

即随着子区域个数的增加，条件数呈平方增长，这无疑给大规模并行计算带来困扰，迫切要求出现条件数与子区域个数无关的区域分解算法。为此，早期有J.Bramble等人的迭代子结构方法，实际上为非重叠区域分解算法，程序设计稍微复杂。后来出现了Dryja与O.Widlund针对对称正定问题提出的叠加型Schwarz算法，或小区域重叠型区域分解算法，其条件数与子区域个数无关，且适合于大规模并行。

4 回顾与展望

回顾多重网格方法的发展历程，我们可以看到，就如一个学科发展的一般规律，这一方法提出之初，并没有受到人们的重视。当人们认识到它的优越性，大量的人力物力投入到这一方法的研究中。于是这一方法得到了极大的发展。当然由于问题的不断深化，问题的广度已经很大，这一研究的热潮还没有过去，某种程度上还在升温。同时一种方法的理论研究已经初具规模，而方法的实际应用还在推广中。

参考文献

[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-），男，河南商丘，助教，硕士，研究方向：计算数学。