多重网格法是一类通过结合多个分辨率层次上的计算,求解大规模线性方程组和非线性离散方程的算法。它对于求解由偏微分方程离散化得到的方程尤为重要,因为精细的计算网格可能包含数百万乃至数十亿个未知量。在适当的假设下,多重网格法只需与未知量个数成正比的计算工作量,就能将误差缩小至原来的某个固定比例,因此成为大规模科学计算的主要方法之一。
其核心思想是:在一个网格上难以消除的误差,换到另一个网格上可能更容易表示和消除。局部松弛能够迅速衰减某些误差分量,而较粗层次上的问题则为松弛后残留的分量提供校正。在多层结构中反复采用这种分工,可以避免收敛性能随网格加密而恶化。尽管“多重网格”这一名称让人联想到一系列几何网格,代数多重网格法却直接从矩阵构造多层结构,无须显式的几何网格。
多重网格法既可独立用作求解器,也可作为其他求解器的构建模块。其主要变体包括几何多重网格法和代数多重网格法、递归的 V 循环和 W 循环、全多重网格初始化方法,以及用于非线性问题的全逼近格式。这些方法的效果取决于松弛过程、粗空间、传递算子和粗层方程之间如何相互配合。
起源与发展
多重网格法源于数值分析中一个长期存在的问题:随着微分方程离散化分辨率的提高,简单的迭代方法往往会变得越来越慢。局部更新能够高效地校正相邻未知量之间的不平衡,却只能逐步将信息传遍整个计算域。直接消元法避开了这一特定困难,但对于大规模多维问题,其存储需求和运算成本可能相当高。
1961 年,R. P. 费多连科针对泊松方程的有限差分近似,提出了一种已具备明确双网格特征的求解过程。他的工作表明,将松弛与粗网格校正相结合,可以使收敛性对网格间距的敏感程度显著低于单独采用松弛法的情形。随后,尼古拉·巴赫瓦洛夫发展了有关多层求解和最优计算复杂度的理论结果。在多重网格法于国际上得到广泛应用之前,这些贡献为其奠定了重要基础。
20 世纪 70 年代,阿奇·勃兰特发展了多层自适应技术,并系统阐述了多重网格法的通用计算框架。他于 1977 年发表的关于边值问题多层自适应求解的论文,推动人们将这一方法视为一种通用策略,而非孤立的加速技巧。同一时期,沃尔夫冈·哈克布施也独立发展了多重网格算法及其收敛理论。后续理论研究进一步建立了多重网格法与逼近性质、子空间分解及变分方法之间的联系。
早期的实际实现主要采用几何多重网格方法:在一系列网格上离散微分方程,并根据网格的几何结构规定网格间的插值方式。对于采用规则加密网格的矩形区域,这种做法尤其自然。复杂几何形状、不规则网格,以及仅以组装后的矩阵形式给出的问题,推动了代数多重网格法的发展。20 世纪 80 年代,勃兰特、史蒂夫·麦考密克、约翰·鲁格、克劳斯·施蒂本等人的工作确立了多种影响深远的代数方法。
此后的发展既拓宽了所处理的方程类型,也扩展了所面向的计算机体系结构。多重网格法在计算流体力学、结构力学、电磁学和多孔介质模拟中逐渐占据重要地位。高阶离散化推动了既依据网格尺寸、也依据多项式次数构建的层次体系;与此同时,大规模并行计算机使粗层通信和负载分配成为算法设计的核心考量。在这些发展过程中,其根本原则始终未变:必须将难以消除的误差分量表示在能够以低成本加以校正的空间中。
为什么仅靠松弛会变得缓慢
一个标准的模型问题是带齐次狄利克雷边界条件的泊松方程:
这里, 是拉普拉斯算子。在二维均匀网格上采用有限差分法进行离散,可得熟悉的五点格式方程
将内部节点的未知量汇集起来,便得到 ,其中 是稀疏矩阵。下标 表示网格间距。
设 为近似解,其代数误差和残差定义为
它们满足 。无需知道精确解就能计算残差,而误差通常无法直接计算。多重网格法利用这一误差方程构造校正量,而不是试图直接估计解的误差。
松弛方法通过计算成本低廉的局部运算更新近似解。对于加权雅可比松弛,
其中 是由 的对角元素构成的对角矩阵。因此,误差按矩阵 演化。对于一维三点泊松算子,无量纲频率为 的内部傅里叶模态,其放大因子为
当 较小时,这个因子接近于一,即该模态几乎不变。对于振荡模态,选择合适的权重可以产生强得多的衰减。例如,取 ,便可使通常的一维高频范围 内的放大因子绝对值不超过 。
这种选择性衰减称为平滑性质。经过几轮松弛迭代后,剩余误差即使仍然不小,相对于细网格而言也往往已较为平滑。粗网格可以用更少的未知量表示这种缓慢变化的误差。关键在于,“平滑”既是相对于网格而言的,也是相对于算子而言的:对于各向异性或强非均质方程,在代数意义上难以衰减的误差,在通常的几何坐标下未必显得平滑。
如果没有粗网格校正,这些难以衰减的分量就会导致收敛缓慢。对于标准的泊松方程离散格式,条件数按 的量级增长,而随着网格加密,经典定常迭代通常需要越来越多轮迭代。多重网格法通过改变处理剩余误差的尺度来应对这一增长。
双网格校正机制
多重网格法的基本操作是双网格循环。设细网格方程组为 ,规模较小的粗网格方程组采用算子 ,通常有 。两个传递算子将这两个空间联系起来:限制算子 将细网格残差映射为粗网格方程的右端项,而延拓算子 则将粗网格校正量映射回细网格。
一次校正循环包含五个操作:
- 对当前近似解进行若干次前光滑迭代。
- 计算细网格残差 。
- 对残差施加限制算子,并求解 。
- 按 校正近似解。
- 进行若干次后光滑迭代。
粗网格方程求解的是校正量,通常并不是对整个细网格解求取新的近似。因此,递归进行粗网格校正时,初始校正量通常设为零。如果精确求解粗网格方程,则仅经过校正步骤后的误差为
因此,完整的双网格误差传播算子为
其中, 和 分别为前光滑和后光滑的迭代次数。
对于规则嵌套网格,延拓在一维情形下通常采用线性插值,在更高维情形下则采用双线性或三线性插值。一维情形下常用的限制方式是全加权:
另一种选择是简单注入,即保留选定的细网格节点值,但其适用性取决于所求方程及算法的其他环节。限制与延拓不能互换:它们作用于不同的数学对象,而且必须与粗网格算子相配合。
定义 主要有两种方法。重新离散化是在粗网格上直接应用原来的离散化方法。伽辽金构造则采用
对于对称正定矩阵,常用的变分选择 给出 。只要 满列秩,得到的粗网格矩阵也正定。此时,精确校正可以消除所有属于 的值域的误差。
光滑与粗网格校正单独使用时都不够。维数较小的粗空间无法表示任意细网格误差,而计算成本较低的光滑器可能对缓慢变化的分量几乎不起作用。良好的双网格设计能够使二者优势互补。后光滑之所以有用,是因为延拓与粗网格校正可能留下或产生一些光滑器能够高效处理的分量。
递归循环与计算复杂度
如果一个两网格方法的粗网格方程本身也用另一个两网格过程近似求解,就得到了多重网格方法。这一层次结构不断向下延伸,直到最粗层的问题足够小,可以用代价较低的直接法求解,例如高斯消元法。各层不一定对应均匀的空间网格,但通常每一层的未知量都比前一层少。
在 V 循环中,每一层都对下一粗层进行一次递归访问。算法通过平滑和残差限制沿层次结构向下推进,再通过校正延拓和后平滑逐层返回。W 循环在每个非最粗层上对下一粗层进行两次递归访问,以更高的计算代价获得更精确的粗层校正。F 循环采用非均匀的访问模式,介于这两种策略之间;F 循环的具体命名和组织方式并无统一约定。
设最细层含有 个未知量,并假设每一粗层的未知量个数约为上一层的 。如果平滑、残差计算和层间传递的代价都与所在层的规模成正比,那么一次 V 循环的代价为
这里使用的是大O记号,其中的常数取决于离散模板的大小和具体实现。对于 W 循环,其递推关系近似为
当 时,计算量为线性;但当 时,计算量为 。因此,若在每个坐标方向上都采用标准的二倍粗化,W 循环在一维情况下的复杂度与二维或三维情况下不同。
全多重网格法又称嵌套迭代,旨在降低获得良好初始近似解的代价。它先在粗网格上求解,将该解延拓到下一细层,执行少量循环,然后重复这一过程,直到到达最细网格。这与普通的校正循环不同:此时传递的是完整的近似解。
对于 阶稳定离散格式,假设解具有足够的正则性,其离散误差在适当范数下通常为 。如果插值足够精确,且每层执行固定次数的循环就能充分减小误差,那么全多重网格法可以用 的计算量,使代数误差达到与离散误差相当的水平。其目标并不是将每个中间层的离散系统都求解到机器精度。
上述复杂度结论都有适用条件。如果收敛因子随网格加密而恶化,那么单次循环的代价为线性,并不能保证整个求解过程的代价也为线性。同样,当粗层矩阵变得稠密或插值代价升高时,仅凭未知量个数也无法确定计算代价。要达到最优复杂度,既需要每次循环的计算量受到适当约束,也需要收敛性具有足够的层间一致性。
收敛理论与粗空间的作用
多重网格法的收敛依赖于两个互补的要求。首先,平滑器必须削弱那些在粗层上难以充分表示的误差分量。其次,粗空间必须能够逼近平滑器只能微弱削弱的分量。这两个要求通常被形式化为平滑性质和逼近性质,不过其确切的数学形式取决于具体问题和分析方法。
对于对称正定的 ,一种自然的误差度量是能量范数
采用伽辽金算子 时,精确粗网格校正的形式为
校正后的误差满足 。因此,粗网格校正是在 -内积下向粗空间的能量正交补空间所作的正交投影。等价地,它选取使剩余误差的能量范数最小的粗网格校正。
对于准均匀网格上的椭圆型问题,一个典型的逼近估计为
其中采用了适当缩放的离散范数,且常数 与网格尺寸无关。这类估计刻画了粗网格函数对能量受控的细网格函数的逼近能力。将其与适当的松弛估计相结合,可以得到一致小于 1、且不随网格加密而趋近于 1 的收敛因子界。具体假设涉及正则性、网格质量、边界条件,以及离散能量与所对应微分算子之间的关系。
傅里叶变换分析提供了另一种影响深远的视角。局部傅里叶分析研究理想化的无限网格或周期网格,将误差分解为各个频率分量,并考察平滑操作和网格间转移对这些分量的作用。由于不同的细网格模态在粗网格上可能具有相同的采样值,网格粗化会使若干细网格频率相互耦合。因此,仅分析每个孤立频率的衰减,不足以完整预测两网格法的收敛表现。这种方法尤其适合比较结构化网格上的松弛权重、网格转移模板和粗化策略。
更一般的理论通过将向量空间分解为各层对应的子空间来解释多重网格法。这使多重网格法与区域分解和逐次子空间校正方法建立了联系。由此得到的估计通常依赖于稳定分解以及子空间之间可控的相互作用,而非仅仅依赖几何频率。
这些理论解释了为什么收敛并非自然而然就能得到保证。平滑器可能有效地衰减许多模态,却留下一个粗空间无法表示的分量。反过来,即使逼近空间非常出色,也无法弥补松弛过程的不稳定性。稳健的方法不仅要控制收敛性对网格间距的依赖,还必须控制其对系数反差、各向异性、多项式次数和物理参数的依赖。
几何多重网格与考虑离散化特性的设计
几何多重网格基于网格和离散空间构建层次结构。在有限元法中,嵌套网格通常会生成嵌套空间,
此时,延拓就是用更细空间的基来表示粗空间中的有限元函数。对于协调的嵌套空间,如果各层的双线性形式按一致方式组装,便可从变分形式自然导出伽辽金粗层算子。几何信息也有助于确定边界处理方式、数值积分规则,以及具有物理意义的光滑子。
均匀网格加密只是其中一种选择。局部自适应加密将未知量集中在奇异点、界面或边界层附近。这就要求多层求解器处理非均匀加密、悬挂节点约束以及层级之间的界面。局部多重网格的各种变体可避免在未加密区域进行不必要的计算,但需要采用能够在加密区域边界两侧保持相容性的转移与光滑规则。求解器的表现可能取决于这些局部层级的组织方式,而不仅仅取决于最终网格。
各向异性清楚地说明了几何信息为何重要。考虑
沿弱耦合的 -方向快速变化的误差,相对于占主导地位的 -方向耦合,其能量可能很低。尽管这些误差在几何上具有振荡性,点松弛却可能几乎无法削减它们。线松弛沿强耦合方向对成组的耦合未知量进行求解,而半粗化则仅在选定方向上降低分辨率。适当组合这两种方法,可以恢复标准点光滑与均匀粗化所丧失的收敛性。
高阶方法引入了另一个层次参数:多项式次数。-多重网格通过降低逼近多项式的次数来构建层次,以此替代网格粗化,或与网格粗化并用。-多重网格则将降低多项式次数与网格粗化相结合。在谱元法和间断伽辽金方法中,可以将高阶无矩阵运算与低阶粗层表示结合使用。光滑子可采用与单元、顶点或重叠子区域相关联的分块,以处理标量更新难以有效处理的耦合。
边界条件必须在各层之间保持一致。对于狄利克雷边界条件,校正量通常应满足所给定条件对应的齐次形式。对于纯诺伊曼边界条件下的泊松问题,常数属于零空间,因此方程组是奇异的。可解性要求右端项满足相容性条件,而解只能确定到相差一个常数,通常通过施加零均值条件来确定唯一解。层间转移和粗层求解器必须保留相应的零空间,而不能将奇异性视为偶然出现的数值缺陷。
几何多重网格的存储量和运算成本可以很低,因为算子和层间转移可通过紧凑的差分模板或单元计算核来实现。它在实际应用中的主要要求是能够获得可用的离散化层次;而当手头只有组装好的矩阵时,这样的层次可能并不存在。
代数多重网格
代数多重网格主要根据矩阵的元素及其连接关系构造层次结构。因此,当几何网格不可用、使用不便,或不足以描述重要的耦合关系时,这种方法仍然适用。矩阵定义了一个图,其中顶点代表未知量,边代表相互作用。粗化过程选择或合并变量,而插值则决定如何用粗层变量表示细层上持续存在的误差。
经典代数多重网格尤其适用于许多具有类 M 矩阵结构的标量扩散问题离散系统。连接强度准则用于识别可能决定那些衰减缓慢的误差的耦合关系。在具有适当符号结构的情形下,一种典型的基于矩阵行的准则规定:当满足
时,就将 标记为与 强连接,其中阈值满足 。这一公式并非普遍适用:对于非对称矩阵、具有正非对角元素的矩阵以及耦合系统,往往需要采用不同的强度定义。
经典粗化将变量划分为粗变量集和细变量集。插值根据相邻粗变量来估计细变量处的误差,通常利用松弛已失效的点上由 所提示的近似关系。因此,其核心对象是代数光滑误差,而不一定是在物理空间中缓慢变化的函数。选定插值算子和限制算子后,便通过伽辽金乘积逐级构造粗层矩阵。
基于聚合的方法将变量分组为聚合体,并利用这些组构造粗空间基函数。在光滑聚合中,先利用聚合体和候选近零空间向量构造初始插值算子,再通过一个光滑步骤对其进行修正。对于标量扩散问题,常数向量通常是一个重要的候选向量。对于三维线弹性问题,六个刚体模态——三个平移模态和三个旋转模态——则提供了相应的物理信息。提供这些模态,有助于粗空间捕捉与近乎无应变的位移相关的误差。
自适应方法和自举方法利用松弛或近似特征向量计算所生成的代表性误差向量,进一步充实这一过程。其目标是在无法事先可靠指定难以消除的误差分量时,将它们识别出来。这类方法可以提高处理困难算子时的稳健性,但需要额外的预处理工作和存储空间,还需决定保留多少个测试向量。
代数层次结构的质量,部分通过网格复杂度和算子复杂度来衡量:
这里,第 层是最细层, 表示非零元素的数量。即使层数很少,如果粗层矩阵中出现大量填充,整个层次结构的计算代价仍可能很高。插值截断和稀疏化可以降低这部分代价,但也可能削弱逼近质量,或改变算子的重要性质。因此,代数多重网格需要在收敛性与层次结构构造、内存占用及应用代价之间取得平衡。
非线性方程与用作预条件器
对于非线性方程,线性残差校正恒等式不再能直接给出粗网格上的误差方程。全近似格式(通常缩写为 FAS)则传递完整的近似解,并修正粗网格方程的右端项,以保持各层之间的一致性。设细网格方程为 ,当前近似解为 。
令 为近似解的传递算子, 为残差的限制算子。预平滑后,定义
以及
粗网格问题为 。利用其解进行校正:
随后进行后平滑。如果 已经精确满足细网格方程,那么 就满足粗网格方程,因此无需校正。这种不动点一致性是 FAS 的一个标志性特征。
粗网格方程的右端项也常写作 ,其中
τ 校正用于补偿以下两者之间的差异:将粗网格算子作用于传递后的近似解所得的结果,以及将细网格算子的作用结果限制到粗网格所得的结果。它允许细网格与粗网格采用不同的非线性模型,同时在当前近似解处保持一致。当所有算子均为线性算子,且传递算子的选择彼此相容时,FAS 就退化为普通的粗网格校正。
非线性平滑可以采用逐点非线性求解、非线性块松弛,或在局部应用牛顿法。对于非线性扩散问题,以及其他能够构建有效粗网格非线性模型的问题,FAS 很有用。另一种主要策略是牛顿–多重网格法:牛顿法构造出一个含有雅可比矩阵的线性化方程,再用多重网格法近似求解该方程或对其进行预条件处理。这两种方法的区别在于,多层次结构是直接作用于非线性问题,还是作用于逐次线性化得到的问题。
对于线性问题,可以用一个或多个多重网格循环定义近似逆 ,供克雷洛夫子空间法使用。这称为预条件处理。某个循环作为独立迭代方法时可能不够稳健,但放在外层克雷洛夫迭代中却可能十分有效,因为外层迭代会组合历次校正方向。
求解器之间的相容性很重要。标准形式的共轭梯度法要求预条件器具有对称正定性。对称的平滑安排与相容的伽辽金传递算子可以保证这一结构。非对称问题通常采用 GMRES 或相关方法。如果多重网格的作用在各次调用之间发生变化,例如内部迭代采用了变化的停止准则,那么可能需要使用灵活克雷洛夫方法,而不能采用假定预条件器为固定线性算子的方法。
大规模实现、应用与局限
多重网格的实现自然分为构建和求解两个阶段。构建阶段生成网格或粗空间、转移算子、粗层矩阵以及光滑子所需的数据。求解阶段则针对一个或多个右端项执行多重网格循环。代数多重网格的构建成本可能远高于单次循环,因此,在对同一矩阵或密切相关的矩阵反复求解时,复用构建结果很有价值。反之,系数或几何形状的变化可能要求更新层次结构,以维持收敛性。
在并行计算平台上,细层通常能提供充足的独立计算任务,但到了粗层,未知量最终会少到无法高效利用所有处理器。此时,即使算术运算复杂度仍为线性,邻居间的数据交换、同步以及粗层求解也可能占据大部分运行时间。处理器聚合通过减少粗层上参与计算的进程数来缓解这一问题,而数据重分布则通过调整数据归属来改善负载均衡。这些措施以层间转换时额外的数据搬移为代价,换取后续更少的空闲时间和更低的通信开销。
光滑子的选择在很大程度上受硬件影响。加权雅可比光滑子和切比雪夫多项式光滑子具有较高的并行性,通常适合图形处理器。按字典序执行的高斯–赛德尔方法存在顺序依赖;着色或分块变体能够提供更多并发机会,但也会改变收敛行为和通信模式。无矩阵实现可以避免存储细网格矩阵,尤其适用于结构化离散或高阶离散,不过粗层算子和转移数据可能仍需显式存储。
扩散方程和椭圆型方程仍是多重网格的核心应用领域。不可压缩流算法中的压力方程往往形成适合多重网格求解的类泊松方程组。地下水模型会出现差异悬殊的系数,而弹性问题则要求保留刚体模态。电磁问题的某些表述可能包含与梯度相关的零空间,以及普通标量插值无法保持的相容性结构。这些问题促使人们针对具体算子设计粗空间、分块方法和辅助空间构造,而不是采用一套通用方案。
对于不定、强非对称和强耦合系统,多重网格存在显著局限。在高频亥姆霍兹问题中,标准的椭圆型光滑子可能失效,粗网格也可能无法充分分辨波的传播。对流占优方程可能需要考虑方向性的转移算子,以及顾及稳定化处理的松弛方法。纳维–斯托克斯方程及其他鞍点系统通常采用分块预条件子,将多重网格应用于选定的矩阵块,而不是把整个矩阵视为标量扩散算子。
因此,实际评估不能只看迭代次数。相关指标包括构建时间、循环时间、算子复杂度、通信成本,以及达到指定容差所需的总时间。对残差下降也必须谨慎解读:当系统病态时,残差很小并不一定意味着解误差也按相同比例减小。在微分方程的离散求解中,停止准则通常旨在使代数误差充分低于数值解所要求的精度水平,而不是将残差压低至浮点运算的极限。