我正在尝试解决一个稀疏但缺乏任何带状结构的线性方程组。我听说有一种方法可以将隐式有限差分方案的多重网格求解器的原理扩展到一般线性问题（如果我没记错的话，它被称为代数多重网格求解器）。在阅读了一些关于它的文献之后，我仍然对如何在粗网格和细网格之间进行插值（即延长和限制）而不利用像有限差分方案那样的带状矩阵的良好结构感到非常困惑。有一些启发式的吗？谁能举个例子？
如何为代数多重网格求解器构造延长和限制算子？
计算科学
线性代数
多重网格
2021-12-18 04:57:36
3个回答
首先，如果你有一个结构化网格，你可能想要使用几何而不是代数多重网格，因为它具有一些理论和效率优势（例如，重新离散化而不是使用 Galerkin 粗网格算子的能力）。代数多重网格方法通常分为两类。
经典代数多重网格
该方法由 Brandt、McCormick 和 Ruge 在 1982 年提出，具有很强的理论-矩阵。Brandt (1986)有标准的收敛理论。请参阅Hypre 包中的BoomerAMG ，了解流行且高度可扩展的并行实现。一种更强大、更通用的变体称为 Bootstrap AMG，请参阅Brandt、Brannick、Kahl 和 Livshits 最近发表的这篇论文。
平滑聚合
Vaněk、Mandel 和 Brezina (1996)的平滑聚合是一种较新的方法，已被证明对弹性等向量问题很有用。一般的方法是从表征算子的近零空间的向量开始（例如弹性中的刚体模式），使用矩阵的连通性构造聚合（通常通过找到最大独立集)，并“平滑”聚合（使用运算符）以创建较低能量的粗略基函数。流行的并行实现有Trilinos的ML、Mark Adams的Prometheus（2004 年 Gordon Bell 奖）、PETSc的PCGAMG（也来自 Mark Adams，主要是 Prometheus 的完全替代品），以及基于 CUDA 的 GPU 代码CUSP的平滑聚合组件。
请注意，上述所有软件都可以通过使用PETSc的通用界面进行访问。
Trottenberg 等人的“Multigrid”是一本很棒的书，看起来大部分都可以在 Google 书籍中找到。它有一个关于 AMG 的附录，你可能需要从本书的其余部分了解一些 MG 的背景知识。《A Multigrid tutorial》也是一本好书。
我建议 WL Briggs、VE Henson 和 SF McCormick 撰写的“A Multigrid Tutorial”（2Ed）的第 8 章。它给出了一些重要概念的一般概念，如代数平滑度和强相关性。它还解释了如何定义插值算子（也是粗网格算子）以及如何选择粗网格。