平滑聚合代数多重网格

形式陈述

没有现成几何粗网格时，仍能从矩阵中构造粗空间校正。平滑聚合代数多重网格先将变量分组，把候选慢方向局部拟合成粗基，再平滑这些基函数。

设 $A=A^T\succ0$ ， $D=\operatorname{diag}(A)$ 。输入除矩阵外，还包括若干应被粗空间很好表示的候选向量，组成矩阵 $B$ 。典型标量椭圆问题使用常向量作为近零候选；弹性系统可能需要平移和转动候选，这些信息未必仅凭矩阵零模式就能猜出。

基本设置过程为：

根据矩阵连接图及选定的强连接规则，把节点划为互不相交的聚合。
在每个聚合限制候选 $B$ ，构造局部基并延伸为初始延拓 $P_0$ ，同时记录粗候选 $B_c$ ，使 $P_0B_c=B$ 。
平滑延拓，例如

P=(I-\omega D^{-1}A)P_0.

核对 $P$ 的列独立性，形成 $A_c=P^TAP$ ，继续构造更粗层或结束设置。

多个候选时，在每个聚合选出一组极大线性无关的限制候选列，对这个列数不超过局部自由度数的矩阵作局部 QR 分解，取其正交列为局部基，并把所有原候选在此基下的坐标放入 $B_c$ ；局部秩为零时不增加粗列。精确算术下这给出 $P_0B_c=B$ ，浮点中若按容差舍弃近相关方向，则应报告实际再现误差。一个常量候选的最简单版本则直接用聚合指示向量；是否归一化只改变粗坐标，只要 $B_c$ 同步调整，表示的空间相同。

直觉

初始聚合基常像一块块阶梯：在某组节点上为一，出了组立刻为零。它能表示组内常量，却在聚合边界形成陡跳。平滑常把基向量的影响扩散到邻近聚合。能量降低需要参数条件：对非空正定系统，若 $0<\omega<2/\lambda_{\max}(D^{-1}A)$ ，加权 Jacobi 就在 $A$ -能量范数下收缩，所以每个非零基函数的能量降低。这样得到的粗空间有机会更贴近局部迭代难以消除的方向。

两点聚合先生成分片常量基，平滑后跨聚合出现三分之一权重，并单列边界上的常量再现缺陷 — 聚合、平滑延拓与边界缺陷

这里平滑的是延拓矩阵的列，发生在设置阶段；求解阶段仍会用独立的平滑迭代处理当前误差。两者可以采用相似公式，但输入对象和成本不同。

精确再现只对真零模自动保持

由 $P_0B_c=B$ 可直接得到

PB_c=B-\omega D^{-1}AB.

因此平滑后的候选再现缺陷恰为 $\omega D^{-1}AB$ 。如果某候选满足 $Ab=0$ ，则它被精确保持；若仅是近零方向，通常只有近似保持。对严格正定矩阵，非零真零模并不存在。

在带 Neumann 零模的半正定问题中，真零模的这条代数恒等式仍成立，但求解还须处理兼容性与零空间，不能直接调用本页的正定粗逆。Dirichlet 问题中的常量是一个候选慢方向，不应被误叫成矩阵的精确零模。

例子与边界

八节点链的完整设置

取 $A=T_8=\operatorname{tridiag}(-1,2,-1)$ ，聚合为 $\{0,1\},\{2,3\},\{4,5\},\{6,7\}$ 。初始延拓每列是对应两点的指示向量，因而 $P_0\mathbf1_4=\mathbf1_8$ 。

取 $\omega=2/3$ ，则 $P=(I-A/3)P_0$ ，逐行得到

P=\frac13\begin{pmatrix} 2&0&0&0\\2&1&0&0\\1&2&0&0\\ 0&2&1&0\\0&1&2&0\\0&0&2&1\\ 0&0&1&2\\0&0&0&2 \end{pmatrix}.

例如节点 $1$ 原属第一聚合，平滑后第一粗基权重为 $2/3$ ，第二粗基权重为 $1/3$ ；跨聚合边不再是骤然截断。其 Galerkin 粗矩阵为

A_c=\frac19\begin{pmatrix} 6&-1&-1&0\\-1&4&-1&-1\\ -1&-1&4&-1\\0&-1&-1&6 \end{pmatrix}.

它包含跨越一个相邻聚合的连接，已经不只是三对角矩阵。 $P$ 满列秩，可由上述行方程逐个消去粗系数检验，因此 $A_c$ 正定。

四个初始粗基的能量平方均为 $2$ ；平滑后变为 $(2/3,4/9,4/9,2/3)$ 。基函数能量确实降低，但这并不表示每个给定误差的粗校正都必然变好。

边界缺陷与一个反例

本例

A\mathbf1_8=(1,0,0,0,0,0,0,1)^T,

所以

P\mathbf1_4=(2/3,1,1,1,1,1,1,2/3)^T.

常量在首尾各损失 $1/3$ ，内部仍保持一。这不是数值舍入，而是 Dirichlet 边界造成的精确代数结果。

用未平滑 $P_0$ 做精确粗校正时，常量误差位于其列空间内，可以完全消除。改用上述 $P$ 后，对常量误差的剩余量为

e_c=\frac17(1,-1,0,1,1,0,-1,1)^T, \qquad \|e_c\|_A^2=2/7.

因此“每列能量更低”不意味着“对每个向量都更精确”。SA 的效率应由平滑与粗空间共同作用、设置复杂度及一类问题上的收敛来评价，而不是把初始再现性质无条件移交给平滑后的空间。

满秩检查也不能省略

$P_0$ 满列秩不保证任意平滑参数都保住它。例如 $A=I$ 、 $\omega=1$ 时， $I-\omega D^{-1}A=0$ ，全部粗基被消成零。虽然这个平滑器单独就能精确解该特殊系统，所构造的粗矩阵却是奇异的。设置过程应检查实际秩、粗矩阵状态及是否还需要继续粗化。

推论与应用

本例细矩阵有 $22$ 个非零项， $P_0$ 有 $8$ 项，平滑后 $P$ 有 $14$ 项，粗矩阵有 $14$ 项。只含这两层时，算子复杂度为

C_A=\frac{\operatorname{nnz}A+\operatorname{nnz}A_c}{\operatorname{nnz}A} =\frac{18}{11},

网格复杂度为 $(8+4)/8=3/2$ 。前者计入稀疏算子变密，后者只数未知量，不能相互替代。更多平滑步可能扩大延拓支撑并使粗矩阵更密，设置与应用成本都要检查。

一般设置成本包括连接强度计算、聚合、候选局部拟合、稀疏乘积 $AP_0$ 与 $P^TAP$ 。若每行宽度和聚合大小有界，这些步骤可以很经济；没有相应稀疏性界时，不能自动声称线性设置成本。强各向异性、系数跳变或错误候选也可能要求改用其他聚合与插值策略。

单元任务：把每一次校正都核对到原方程

完整执行七节点 Poisson 系统的一次 V-cycle，交出每层矩阵、延拓、残差、限制右端、粗解和回程校正；最终原残差与能量误差必须同时核对。再为七乘七网格产生自然序和十字嵌套剖分的全部填充账本，并解释 IC(0) 丢弃了哪些位置。

最后重算本页的 $P_0,P,A_c$ ，报告常量再现缺陷、两层算子复杂度，并说明所用循环是否满足固定线性正定的 PCG 接口。

完整题解、标准库核验脚本、逐层精确结果提供完整状态。脚本的分数运算用于认证小例子；网格填充统计独立于数值系数，不把偶然相消算作结构节省。

参考资料

Jinchao Xu and Ludmil Zikatanov, “Algebraic Multigrid Methods”, Acta Numerica, 2017, §§13.1–13.3：作者预印本。单候选与多候选聚合、延拓平滑、真零模再现及粗矩阵变密。
Marian Brezina, Robert Falgout, Scott MacLachlan, Thomas Manteuffel, Stephen McCormick and John Ruge, “Adaptive Smoothed Aggregation (αSA) Multigrid”, SIAM Journal on Scientific Computing 25(6), 2004, §2, equations (2.7)–(2.11) and Algorithm 2：作者公开稿。标准 SA 设置、局部候选拟合、平滑延拓与 Galerkin 层级。

形式陈述 ​

精确再现只对真零模自动保持 ​

八节点链的完整设置 ​

边界缺陷与一个反例 ​

满秩检查也不能省略 ​

单元任务：把每一次校正都核对到原方程 ​

反向链接