非并行优化：在增加核心之前先减少计算量 / Reducing Computation Before Adding Parallel Hardware
📅 创建时间：2026-07-20 🏷️ 标签：#算法优化 #直接法 #迭代法 #降阶 #自适应 📚 前置知识：[[11-discrete-systems-and-matrices]]
1. 为什么先考虑非并行方法
并行通常只能减少已有工作的执行时间，而算法改进可以直接减少工作量。
更好的算法 × 并行硬件优先级通常高于：
低效算法 × 更多核心2. 直接法
LU
A = LU
Ly=b
Ux=y适合：
- 中小型问题
- 多右端项
- 需要高鲁棒性
- 矩阵不是 SPD
Cholesky
对 SPD 矩阵：
A = LLᵀ计算和存储量小于通用 LU。
Fill-in
稀疏分解过程中原本为零的位置可能变成非零。重排序可以减少 Fill-in：
- AMD
- Nested Dissection
- 图分区排序
选择更好的重排序，可能比增加几个线程更有效。
3. 迭代法
迭代法从初始猜测逐步降低残差。
CG
适用于 SPD，内存需求低，核心操作容易并行。
GMRES
适用于非对称系统，鲁棒但需要存储 Krylov 基向量，重启会影响收敛。
BiCGSTAB
内存较低，但收敛过程可能不平滑。
迭代法是否高效主要取决于预条件器，而不只是主算法名称。
4. 预条件器
将：
Ax=b转化为更容易求解的系统：
M⁻¹Ax=M⁻¹bJacobi
只用对角线。高度并行，但对困难问题效果有限。
ILU/IC
近似不完全分解。收敛效果好，但三角求解并行性一般。
AMG
代数多重网格在多个尺度上消除误差，特别适合泊松、弹性和压力方程。
Domain Decomposition
把模型分成子域，各自近似求解，再处理界面。
5. 多重网格为什么快
普通迭代擅长消除高频误差，但低频误差下降慢。把问题转移到粗网格后，原来的低频误差会变得更容易处理。
细网格平滑
→ 限制到粗网格
→ 粗网格校正
→ 插值回细网格
→ 再平滑理想情况下，计算成本接近未知量数量的线性增长。
6. 多右端项复用
船舶结构可能需要计算很多载荷工况，但 K 不变：
Ku1=f1
Ku2=f2
Ku3=f3直接法可以分解一次、多次回代。迭代法可使用：
- 上一个工况解作为初值
- Block Krylov
- Recycling Krylov
7. 物理延续法
困难非线性或 CFD 问题可以逐步增加难度：
- 从低雷诺数到目标雷诺数
- 从低速度到目标速度
- 从稳态结果启动瞬态
- 从无空化到空化
- 从小载荷到完整载荷
- 从线弹性到弹塑性
这能减少发散和无效迭代。
8. 自适应网格
均匀加密会在不重要区域浪费大量未知量。自适应方法根据误差或物理指标加密：
- CFD：自由液面、涡量、压力梯度、空化界面
- FEA：应力梯度、能量误差、塑性区、裂纹尖端
若只需局部高精度，自适应通常优于全局加密。
9. 降阶模型
模态降阶
u ≈ Φq把几十万自由度投影到几十或几百个模态坐标。
适合：
- 低频动力响应
- 参数扫描
- 实时或快速预测
POD/ROM
从高保真计算快照中提取主要空间模式，用于流场和结构响应快速近似。
降阶模型需要验证适用参数范围，不能随意外推。
10. 时间尺度处理
- 使用稳定允许范围内更大的时间步
- 局部时间步加速稳态 CFD
- 自适应时间步
- 显式计算中的质量缩放需谨慎
- 降低不必要输出频率
时间步太小会增加步数，太大则损失精度或稳定性。
11. 结果和 I/O 优化
大型计算写出所有变量、所有时间步可能比求解还慢。
可以：
- 只输出所需变量
- 降低写出频率
- 在线计算平均值和积分量
- 使用二进制/HDF5/CGNS
- 分离检查点和可视化结果
12. 非并行方法选择表
| 问题 | 优先改进 |
|---|---|
| 多个静力工况 | 分解复用 |
| 低阶频响 | 模态降阶 |
| 非线性不收敛 | 延续法、增量控制、材料/接触检查 |
| CFD 迭代慢 | 初始场、预条件器、多重网格 |
| 局部区域需要精度 | 自适应网格 |
| 显式步数过多 | 消除极小单元、检查质量缩放 |
| 输出占用巨大 | 减少变量和写出频率 |
下一篇：[[13-parallel-acceleration-map]]