多重网格方法

多重网格方法通过将细网格上廉价的平滑处理与在粗网格上计算的校正相结合，加速了离散偏微分方程的求解，从而在每个长度尺度上处理误差，并实现了与网格尺寸无关的收敛速度。

Definition

多重网格方法是一种迭代求解器，它在不同分辨率的网格层次结构上表示误差，利用廉价的松弛方法去除细网格上的振荡误差分量，并利用粗网格求解去除平滑分量，以递归方式跨越所有尺度。

Scope

本主题涵盖了简单迭代的平滑特性、通过限制和延拓在网格之间传递残差和校正、两网格以及V、W和全多重网格循环、几何多重网格与代数多重网格，以及使多重网格成为椭圆问题基准求解器的最优（线性）计算复杂度。

Core questions

• 为什么简单的迭代能快速减少振荡误差，但平滑误差减少缓慢，从而促使使用粗网格？
• 残差如何被限制到粗网格，校正又如何被延拓回细网格？
• 多重网格循环如何结合这些操作以实现与网格无关的收敛？
• 代数多重网格如何将这一思想扩展到没有底层几何网格的问题？

Key theories

平滑和粗网格校正

高斯-赛德尔等经典松弛方法能迅速抑制高频（振荡）误差，但对低频误差几乎没有作用；多重网格利用这一点，将平滑的、收敛缓慢的误差转移到粗网格，在那里它表现为振荡误差并被廉价地消除。

与网格无关的最优复杂度

在V或W循环中递归应用平滑和粗网格校正，可以得到与网格尺寸无关的收敛因子，因此求解到固定容差所需的工作量仅与未知数数量呈线性增长。

Mechanisms

多重网格循环首先在细网格上对系统进行松弛以平滑误差，然后计算残差并将其限制到粗网格，在粗网格上求解残差方程（通过相同的循环递归进行）。粗网格校正随后被延拓回细网格并添加到细网格近似中，之后进行进一步的松弛。由于每个网格层处理其最有效的误差分量，因此组合循环在固定次数的扫描中减少了所有尺度上的误差。代数多重网格直接从矩阵项构建网格层次结构和传递算子，因此不需要几何网格。

Clinical relevance

多重网格是求解由椭圆和抛物线偏微分方程产生的大型稀疏系统最有效的求解器之一，并被用作计算流体动力学、结构力学、电磁学和图像处理中的求解器或预处理器；其接近最优的缩放特性对于并行超级计算机上的超大规模模拟至关重要。

History

多重网格思想由Fedorenko于1961年左右提出，并由Achi Brandt在1970年代发展成为一种实用且广泛适用的方法；Hackbusch的分析为其奠定了严格的基础，代数多重网格后来将其应用范围扩展到非结构化和非几何问题，巩固了其作为最优复杂度求解器的地位。

Key figures

• Radii Fedorenko
• Achi Brandt
• Wolfgang Hackbusch
• Stephen McCormick

Seminal works

• trottenberg2001
• briggs2000

Frequently asked questions

为什么粗网格会有帮助？

细网格松弛缓慢消除的平滑误差在粗网格上看起来是振荡的，松弛可以在粗网格上快速且廉价地消除它。因此，通过不同分辨率的网格循环可以有效地消除每个误差分量。

几何多重网格和代数多重网格有什么区别？

几何多重网格利用问题几何的显式粗网格层次结构，而代数多重网格则自动从矩阵构建粗网格层和传递算子，使其适用于不存在自然网格层次结构的情况。