多网格和多级域分解方法有很多共同点，以至于每一种方法通常都可以写成另一种的特例。由于每个领域的不同哲学，分析框架有些不同。一般来说，多重网格方法使用适度的粗化率和简单的平滑器，而域分解方法使用极快的粗化率和强平滑器。

多重网格 (MG)

Multigrid 使用适度的粗化率，并通过修改插值和平滑器来实现鲁棒性。对于椭圆问题，插值算子应该是“低能量”的，这样它们就可以保持算子的近零空间（例如刚体模式）。Wan, Chan, Smith (2000)是这些低能量插值的示例几何方法，与平滑聚合Vaněk, Mandel, Brezina (1996)的代数构造相比（通过 PCGAMG 在ML和PETSc中并行实现，替代Prometheus） . Trottenberg、Oosterlee 和 Schüller 的书是关于多重网格方法的很好的通用参考。

大多数多重网格平滑器涉及逐点松弛，或者是加法（Jacobi）或乘法（Gauss Seidel）。这些对应于微小的（单节点或单元素）狄利克雷问题。使用切比雪夫平滑器可以实现一些光谱自适应性、鲁棒性和矢量化能力，参见Adams、Brezina、Hu、Tuminaro (2003)。对于非对称（例如传输）问题，通常需要像 Gauss-Seidel 这样的乘法平滑器，并且可以使用逆风插值。或者，可以通过受 Schur-complement 启发的“块预处理器”或相关的“分布式松弛”转换为简单平滑器有效的系统，从而构建鞍点和刚性波问题的平滑器。

教科书的多重网格效率是指在精细网格上以少数残差评估（少至四次）的成本的一小部分解决离散化误差。这意味着对于固定代数容差的迭代次数随着级别数的增加而下降。同时，时间估计涉及由于多重网格层次结构隐含的同步而产生的对数项。

域分解 (DD)

第一个域分解方法只有一个层次。在没有粗略级别的情况下，预处理算子的条件数不能小于其中是域的直径，是标称子域大小。在实践中，一级 DD 的条件数介于此界限和之间，其中是元素大小。请注意，Krylov 方法所需的迭代次数与条件数的平方根成比例。优化的 Schwarz 方法(Gander 2006)改善了常数和对$\mathcal O\big( \frac{L^2}{H^2}\big)$$L$$H$$\mathcal O\big( \frac{L^2}{hH} \big)$$h$$H/h$相对于 Dirichlet 和 Neumann 方法，但通常不包括粗略水平，因此在许多子域的情况下会退化。有关域分解方法的一般参考，请参见Smith、Bjørstad 和 Gropp (1996)或Toselli 和 Widlund (2005)的书籍。

对于最优或准最优收敛速度，需要多个级别。大多数 DD 方法都被视为两级方法，有些很难扩展到更多级别。DD方法可以分为重叠或非重叠。

重叠

这些 Schwarz 方法使用重叠，通常基于解决 Dirichlet 问题。可以通过增加重叠来增加方法的强度。这类方法通常是稳健的，不需要局部零空间识别或针对局部约束问题的技术修改（在工程固体力学中很常见），但由于重叠而涉及额外的工作（尤其是在 3D 中）。此外，对于不可压缩等约束问题，通常会出现重叠条带的 inf-sup 常数，从而导致次优收敛速度。Dorhmann、Klawonn 和 Widlund（2008 年）以及Dohrmann 和 Widlund（2010 年）开发了使用与 BDDC/FETI-DP 相似的粗空间（下文讨论）的现代重叠方法。

不重叠

这些方法通常解决某种类型的 Neumann 问题，这意味着与 Dirichlet 方法不同，它们不能使用全局组装矩阵，而是需要未组装或部分组装的矩阵。最流行的 Neumann 方法要么通过在每次迭代时进行平衡来强制子域之间的连续性，要么通过拉格朗日乘数来强制连续性，只有在达到收敛时才会强制连续性。这类早期方法（平衡 Neumann-Neumann 和 FETI）需要对每个子域的零空间进行精确表征，以构建粗略级别并使子域问题非奇异。后来的方法（BDDC 和 FETI-DP）选择子域角和/或边缘/面矩作为粗略的自由度。参见Klawonn 和 Rheinbach (2007)深入讨论 3D 弹性的粗略空间选择。Mandel、Dohrmann 和 Tazaur (2005)表明 BDDC 和 FETI-DP 具有所有相同的特征值，除了可能的 0 和 1。

两级以上

大多数 DD 方法只提出了两级方法，有的选择了不方便使用两级以上的粗略空间。不幸的是，尤其是在 3D 中，粗略级别的问题很快成为瓶颈，限制了可以解决的问题规模。此外，预处理算子的条件数，尤其是基于 Neumann 问题的 DD 方法，往往会缩放为

其中是级别数。只要使用激进的粗化，这可能不是那么关键，因为应该能够解决超过自由度的问题，但肯定是一个问题。有关此限制的进一步讨论，请参阅此问题。$L$$L \le 4$$10^{12}$

这是一篇出色的文章，但我认为说（多级）DD 和 MG 有很多共同点是不准确的，或者至少没有用处。这些方法非常不同，我认为其中一种方法的专业知识对另一种方法没有多大用处。

首先，两个社区使用不同的复杂度定义：DD 优化预条件系统的条件数，MG 优化工作/记忆复杂度。这是一个很大的根本区别——“最优性”在这两种情况下具有完全不同的含义。当您添加并行复杂性时，事情不会改变（尽管您在 MG 中添加了一个对数项）。这两个社区几乎说着不同的语言。

其次，MG 内置了多级，并且多级 DD 方法都已通过两级理论和实现来开发。这限制了您可以在 MG 中使用的粗网格空间的空间——它们必须是递归的。例如，您不能在 MG 框架中实现 FETI。正如 Jed 提到的，人们做了一些多级 DD 方法，但至少目前流行的一些 DD 方法似乎不能递归实现。

第三，在实践中，我认为算法本身非常不同。定性地说，我会说 DD 方法投射到域边界并解决这个接口问题。MG 直接使用原生方程。避免这种投影允许 MG 轻松应用于非线性和不对称问题。尽管对于非线性和不对称问题，该理论几乎消失了，但它们已为很多人工作。MG 还明确地将问题解耦为两部分：用于缩放的粗网格空间和用于求解物理的迭代求解器（更平滑）。这对于理解和与 MG 合作至关重要，对我来说是一个有吸引力的属性。

尽管理论上平滑器和粗网格空间是紧密耦合的，但在实践中，您通常可以交换不同的平滑器作为优化参数。正如 Jed 提到的，点或顶点平滑器很受欢迎并且通常更快，但对于具有挑战性的问题，更重的平滑器可能很有用。该图来自我的论文，显示了 Jacobi、块 Jacobi 和“additive Schwarz”（重叠）的求解时间与泊松比的函数关系。它有点难以阅读，但在最高泊松比 (0.499) 下，重叠 Schwarz 比（顶点）Jocobi 快约 2 倍，而在行人泊松比下慢约 3 倍。

根据 Jed 的回答，MG 使用中度粗化，而 DD 使用快速粗化。我认为这在它们并行化时会有所不同。MG 将进行多次通信和同步，以经历相当于 DD 的单次粗化的多个粗化级别。Jed回答的另一点是MG使用便宜的平滑器，DD使用强平滑器。考虑到这两点，据报道，粗略级别的 MG 将具有较差的通信/计算比率。所以根据 阿姆达尔定律，并行加速并不好。对此的补救措施是并行粗网格校正，例如BPX 预处理器. 此外，MG 可以像 Adams 指出的那样更平滑地使用 DD，并且 MG 也可以在 DD 的子域内使用。根据 Barker 指出的考虑，我猜在 DD 中使用 MG 会更好，它既利用了 DD 的并行性，又利用了 MG 的最优复杂度。

我想对 Jed 的出色回答做一点补充，即这两种方法背后的动机是（或至少是）不同的。

域分解是作为一种并行计算技术而被激发的。特别是对于单级方法，DD 在并行机器上实现是非常自然的——您将域划分为多个部分，并将每个部分分配给不同的处理器。从某种意义上说，DD 背后的动机是在处理器之间划分算术运算。

存在良好的并行多重网格实现，但并行执行通常不太自然。相反，多重网格背后的动机首先是减少算术运算。