一、AMG基本思想

1.1 基本概述

AMG是一种不依赖于网格几何信息的多重网格法，完全基于矩阵 A的代数结构来构造粗网格、限制算子、延拓算子等。

主要步骤：

  • 光滑（Smooth）：在细网格上用简单迭代法（如 Gauss-Seidel）消去高频误差
  • 粗网格校正（Coarse Correction)：将残差限制到粗网格上，在粗网格上求解误差方程，再插值回细网格修正解。
  • 循环迭代：常见为W-cycle、V-cycle、F-cycle
img

1.2 补充说明

当使用有限差分法、有限元法等数值方法时，控制方程（如热传导方程、波动方程）会被离散化，最终转化为一个大规模的线性方程组 A x = b

矩阵A包含了网格点的连接关系以及物理方程的信息

矩阵中每一行对应一个网格点上的离散方程（可以理解为一个点或Cell）

非零元素表示该点与其相邻点之间的耦合关系

1.3 例子

\[ A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}, \quad b = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}. \]

第一步：光滑化

初始猜测\(x^{(0)} = [0,0,0]^T\)

用一次 GaussSeidel 迭代（光滑） \[ x_i^{(new)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j<i} a_{ij} x_j^{(new)} - \sum_{j>i} a_{ij} x_j^{(old)} \right) \]

  • \(i = 1:x_1=(1-0)/2=0.5\)
  • \(i=2:x_2=(2-(-1)*0.5-0)/2=1.25\)
  • \(i=3:x_3=(3-(-1)*1.25-0)/2=2.125\)

所以一次光滑后： \[ x^{(1)} = [0.5, 1.25, 2.125]^T \] 计算残差\(r = b - A x^{(1)}\)： \[ A x^{(1)} = \begin{bmatrix} 2\cdot 0.5 - 1\cdot 1.25 + 0 \\ -1\cdot 0.5 + 2\cdot 1.25 - 1\cdot 2.125 \\ 0 - 1\cdot 1.25 + 2\cdot 2.125 \end{bmatrix} = \begin{bmatrix} 1.0 - 1.25 \\ -0.5 + 2.5 - 2.125 \\ -1.25 + 4.25 \end{bmatrix} = \begin{bmatrix} -0.25 \\ -0.125 \\ 3.0 \end{bmatrix} \\ r = b - A x^{(1)} = \begin{bmatrix} 1 - (-0.25) \\ 2 - (-0.125) \\ 3 - 3 \end{bmatrix} = \begin{bmatrix} 1.25 \\ 2.125 \\ 0 \end{bmatrix} \] 第二步：粗网格选取

选点1,3作为粗网格点（C点），点2作为细网格点（F点）

即粗网格是 {1,3}，细网格是 {2}。

第三步：构造插值算子P

AMG 中，插值公式（直接插值简化版）：

对 F 点 i，其值由相邻 C 点插值。这里 F 点 i=2，相邻 C 点是 1 和 3。 \[ w_{2 \to 1} = \frac{a_{21} }{ a_{21} + a_{23} } = \frac{1}{1+1} = 0.5 \\ w_{2 \to 3} = 0.5 \] （更精确的公式要考虑强连接，这里简单用对称等权）

所以插值矩阵 P（细→粗编号映射：粗点 1→粗网格索引 1，粗点 3→粗网格索引 2，F 点 2 对应一行插值公式）： \[ P = \begin{bmatrix} 1 & 0 \\ 0.5 & 0.5 \\ 0 & 1 \end{bmatrix} \] 含义：粗网格函数 \(u_c = [u_{c1}, u_{c2}]^T\) 延拓到细网格： \[ u_1 = u_{c1},u_2 = 0.5 u_{c1} + 0.5 u_{c2},u_3 = u_{c2} \] 第四步：限制算子R

常用 \(R = P^T\)（Galerkin 粗化）： \[ R = P^T = \begin{bmatrix} 1 & 0.5 & 0 \\ 0 & 0.5 & 1 \end{bmatrix} \] 第五步：构建粗网格

先算\(AP\)： \[ A P = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0.5 & 0.5 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1.5 & -0.5 \\ 0 & 0 \\ -0.5 & 1.5 \end{bmatrix} \]

再乘 \(R = P^T\)： \[ A_c = R (A P) = \begin{bmatrix} 1 & 0.5 & 0 \\ 0 & 0.5 & 1 \end{bmatrix} \begin{bmatrix} 1.5 & -0.5 \\ 0 & 0 \\ -0.5 & 1.5 \end{bmatrix} = \begin{bmatrix} 1.5 & -0.5 \\ -0.5 & 1.5 \end{bmatrix} \] 第六步：粗网格计算

粗网格方程：\(A_c e_c = r_c\)，其中$ r_c = Rr $ \[ r_c = Rr = \begin{bmatrix} 1 & 0.5 & 0 \\ 0 & 0.5 & 1 \end{bmatrix} \begin{bmatrix} 1.25 \\ 2.125 \\ 0 \end{bmatrix} = \begin{bmatrix} 1.25 + 0.5\cdot 2.125 \\ 0.5\cdot 2.125 + 0 \end{bmatrix} = \begin{bmatrix} 1.25 + 1.0625 \\ 1.0625 \end{bmatrix} = \begin{bmatrix} 2.3125 \\ 1.0625 \end{bmatrix} \] 求解\(A_c e_c = r_c\): \[ 1.5 e_1 - 0.5 e_2 = 2.3125 \\ -0.5 e_1 + 1.5 e_2 = 1.0625 \] 所以粗网格修正 \(e_c = [2, 1.375]^T\)。

第七步：插值到细网格

细网格误差 \(e = P e_c\)： \[ e = \begin{bmatrix} 1 & 0 \\ 0.5 & 0.5 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 1.375 \end{bmatrix} = \begin{bmatrix} 2 \\ 1.6875 \\ 1.375 \end{bmatrix} \] 第八步：修正解 \[ x^{(2)} = x^{(1)} + e = [0.5+2, \ 1.25+1.6875, \ 2.125+1.375]^T = [2.5, 2.9375, 3.5]^T \] 第二个分量还有误差，但第一个和第三个已经精确。我们的粗网格选取和光滑组合还需要多次 V-cycle。

二、粗网格选择

2.1 Ruge-Stuben算法

这是经典AMG的核心算法，用强弱连接性来自动选择C/F点。

2.1.1 强连接定义

点 i和点 j是强连接的，如果： \[ a_{ij} \geq \theta \cdot \max_{k \neq i} a_{ik} \] 其中 \(θ\) 为强度阈值(自定义)，通常取0.25~0.5

对于矩阵： \[ A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix} \] 每行的非对角元绝对值：行1: {1}, 行2: {1,1}, 行3: {1}。

取 θ=0.3：

  • 点1的强连接：1≥0.3×1→ 点2是强连接
  • 点2的强连接：1≥0.3×1→ 点1和点3都是强连接
  • 点3的强连接：点2是强连接

强连接图：1—2—3

2.2.2 算法步骤

  1. 初始化：
    • 所有点标记为“未定义”
    • 计算每个点的权重$_i = $强连接数
    • 所以权重：\(\lambda_1 = 1, \lambda_2 = 2, \lambda_3 = 1\)
  2. 选择C点
    • 选择权重最大的点作为第一个C点（点2）
    • 将点2的强连接邻居（点1,3）标记为F点

2.2 PMIS 算法

待续...

三、插值算子

对于细网格点（F点）： \[ u_2 = -\frac{\sum_{j \in C_2} a_{ij} u_j + \sum_{k \in F_2^s} a_{ik} \left( -\frac{\sum_{m \in C_k} a_{km} u_m}{a_{kk}} \right)}{a_{ii} + \sum_{k \in F_2^w} a_{ik}} \] 其中\(F_2^s\)是点2的强连接F点，\(F_2^w\) 是弱连接F点，（弱连接的相关计算可选可不选，选上能够使插值更精确）。

看起来复杂，但思想是：F点k对点i的影响，用k的C点邻居来近似表示。

对于粗网格点（C点）：插值规则非常简单：

每个C点直接对应粗网格中的一个点，权重为1，其他粗网格点权重为0。

3.1 例子

C点 = {1, 3}，F点 = {2}

  • 点1：C点，\(u_1 = 1*u_{c1}+0 * u_{c2}\)

  • 点3：C点，\(u_3 = 0 \cdot u_{c1} + 1 \cdot u_{c2}\)

  • 点2：F点， \[ u_2 = -\frac{\sum_{j \in C_2} a_{2j} u_j}{a_{22}}= -\frac{a_{21} u_1 + a_{23} u_3}{2} = -\frac{(-1) u_1 + (-1) u_3}{2} = \frac{u_1 + u_3}{2} = 0.5 u_1 + 0.5 u_3 \]