外观
ASM 预条件子入门
做 Krylov 迭代法时,真正决定求解速度的,往往不是 cg、gmres 这些迭代器本身,而是预条件子。很多线性系统如果不加预条件,残差降得很慢;一旦预条件选对了,收敛速度会快很多。ASM(Additive Schwarz Method)就是并行计算里非常常见的一类预条件子。
简单说,ASM 的想法并不复杂:既然整个大系统太难一次性处理,那就把它拆成若干个重叠的小子区域,在每个子区域上先解一个局部问题,再把这些局部修正加起来,作为原问题的预条件修正。
这个思路和分而治之有点像。原问题是一个大矩阵
Ax=b
ASM 不直接去“精确求逆” A,而是构造一个比较便宜的近似逆 M−1,让迭代法实际求解的是
M−1Ax=M−1b
如果 M−1 选得好,那么 M−1A 的谱性质会比原来的 A 好很多,Krylov 迭代就会更快收敛。
ASM 的核心公式通常写成
M−1=i∑RiTAi−1Ri
这里可以这样理解:
- Ri 是限制算子,把全局向量取到第 i 个子区域上。
- Ai 是子区域上的局部矩阵。
- Ai−1 不一定真的是精确逆,很多时候只是局部直接解或者局部不完全分解。
- RiT 把局部修正再散回全局。
所以 ASM 的过程其实就是:
- 把全局残差限制到各个子区域。
- 在每个子区域上解一个局部问题。
- 把各个局部解加回全局。
之所以叫 Additive Schwarz,就是因为这些局部修正最后是“加起来”的,而不是像乘法 Schwarz 那样一个接一个顺序更新。
ASM 最直观的优点是它天然适合并行。每个子区域的问题都可以在不同进程上同时做,因此很适合 MPI 环境。这也是它在 PETSc 里经常出现的原因。
不过 ASM 也不是没有代价。最关键的一个参数是 overlap,也就是子区域之间的重叠层数。没有重叠时,各个子问题彼此看不到太多邻居信息,预条件效果往往一般;重叠多一些,局部问题会更接近原问题,预条件通常更强,但计算和通信开销也会增加。
在实践里,overlap 常常从 0 或 1 开始试:
overlap = 0:子区域完全不重叠,成本最低,但效果可能偏弱。overlap = 1:通常是一个比较常见的折中。- 更大的 overlap:有时会继续改善收敛,但也可能得不偿失。
从结构上看,ASM 可以看成块 Jacobi 的一个推广。块 Jacobi 也是把问题拆成多个块,各块独立求解;区别是块 Jacobi 通常不重叠,而 ASM 允许子区域重叠。正是这点重叠,让 ASM 往往比纯块 Jacobi 更稳一些。
如果问题规模继续变大,还会遇到一个经典现象:一层 ASM(one-level ASM)虽然能处理局部耦合,但对全局低频误差不够敏感,于是迭代次数可能随着子区域数量增加而变差。这时常常需要引入 coarse space,也就是二层 Schwarz(two-level Schwarz)方法。直观上说,局部子问题负责消掉高频误差,coarse problem 负责处理全局慢变化误差。很多领域分解方法最后都会走到这一步。
在 PETSc 里,ASM 用起来很直接。最基本的命令行配置可以写成:
-ksp_type gmres
-pc_type asm
-pc_asm_overlap 1如果想让每个子块内部再用一个局部预条件子,比如 ILU,可以继续加:
-ksp_type gmres
-pc_type asm
-pc_asm_overlap 1
-sub_pc_type ilu如果局部问题不大,也可以直接让子块走局部 LU:
-ksp_type gmres
-pc_type asm
-pc_asm_overlap 1
-sub_pc_type lu这里的 sub_pc_type 指的是每个子区域内部怎么解局部问题。很多时候,ASM 的效果不只是由 pc_type asm 决定,还强烈依赖这些局部子求解器的选择。
如果想看 PETSc 实际把区域切成什么样、每个子块用了什么配置,可以配合:
-pc_view
-ksp_view调参数时,通常可以重点看下面几件事:
- Krylov 迭代次数有没有明显下降。
- 增大 overlap 之后,总时间是变快还是变慢。
- 局部子问题是不是太贵,比如
sub_pc_type lu虽然强,但未必划算。 - 进程数增加后,迭代次数是否明显恶化。
如果只是想先建立一个直觉,可以把 ASM 理解成这样:它不是直接解决整个大问题,而是让每个子区域先“各自帮一点忙”,再把这些局部帮助合成一个全局修正。这个修正不一定完美,但只要足够接近真逆,就能显著加快迭代法。
对很多 PDE 离散出来的大型稀疏线性系统来说,ASM 是一个很自然的起点:思想直观,和并行环境契合,在 PETSc 里也容易上手。真到性能优化阶段,再继续考虑 overlap、局部求解器、以及是否需要 two-level 方法,通常会更合适。
版权所有
版权归属:Guisong Wu