数字模拟导论-讲座21 边界值问题-三维有限微分问题的求解 Jacob White 感谢Deepak Ramaswamy, Michal Rewienski, and Karen Veroy 大纲 ?回顾FEM和F－D 一维实例 ?一二三维的有限差分矩阵 高斯消元的代价 ?Krylov法 通讯下限 基于改善通讯的预条件器 SMA-HPC ?2003 MIT 热流动 一维实例 正则化一维方程 正则化泊松方程 SMA-HPC ?2003 MIT 数值解 有限差分 离散化 将区间（0，1）分为n＋1个相等的子区间 SMA-HPC ?2003 MIT 数值解 有限差分 近似 例如： SMA-HPC ?2003 MIT FD矩阵的特性 一维泊松方程 有限差分 SMA-HPC ?2003 MIT 应用基本函数 残差方程 偏差分方程形式 基本函数表述 将基本函数表示代入方程 SMA-HPC ?2003 MIT 应用基本函数 基本权值 Galerkin模式 使残差对基本函数正交 产生n个方程n个未知量 SMA-HPC ?2003 MIT 应用基本函数 基本权值 具有部分积分的 Galerkin模式 基本函数的一阶求导 SMA-HPC ?2003 MIT 汽车结构分析 ?方程 ——机械部件（板、梁、壳）的力位移关系 及合力为零 ——连续体动力学的偏差分方程 SMA-HPC ?2003 MIT 飞机阻力分析 ?方程 ——Navier-Stokes偏差分方程 SMA-HPC ?2003 MIT 发动机热分析 ?方程 ——泊松偏差分方程 SMA-HPC ?2003 MIT FD矩阵特性 SMA-HPC ?2003 MIT 二维离散问题 离散化泊松方程 FD矩阵特性 二维离散问题 非零矩阵5×5实例 SMA-HPC ?2003 MIT FD矩阵特性 三维离散问题 离散化泊松方程 SMA-HPC ?2003 MIT FD矩阵特性 二维离散 非零矩阵m＝4实例 SMA-HPC ?2003 MIT FD矩阵特性 总结 数值特性 对角占优矩阵 每一行严格对角占优或连接每一个严格对角占优行的路径 矩阵对称正定 假定均匀离散化，对角为： SMA-HPC ?2003 MIT FD矩阵特性 总结 结构特性 三维矩阵很大 矩阵是稀疏的 每一行非零元是： 矩阵是带宽的 SMA-HPC ?2003 MIT GE基础 三角化 图 SMA-HPC ?2003 MIT GE基础 三角化 算法 SMA-HPC ?2003 MIT GE的复杂性 对于二维和三维问题需要一个快速求解法！ SMA-HPC ?2003 MIT 带宽GE 三角化 算法 SMA-HPC ?2003 MIT 带宽GE的复杂性 对于三维问题需要一个快速求解方法！ SMA-HPC ?2003 MIT 满足Krylov的世界 预条件 从Ax =b开始形成PAx = P b 确定Krylov空间 从Krylov空间选择解 GCR取最小残差 SMA-HPC ?2003 MIT Krylov法 预条件 对角预条件器 ?对角阵的逆很容易求 ?通常改善收敛性 SMA-HPC ?2003 MIT Krylov法 收敛性分析 多GCR的最优性 GCR最优性性能 多项式使 因此 任何满足限制的多项式可 用来得到上限 SMA-HPC ?2003 MIT 热传导杆矩阵的多残差图 无传导到空气的损失（n＝10） 使尽可能小 如果特征值聚类则较容易 SMA-HPC ?2003 MIT 满足Krylov的世界 对角的Krylov向量 预条件A SMA-HPC ?2003 MIT 满足Krylov的世界 通讯下限 对角的Krylov向量 预条件A 对于m网格点的通讯下限 SMA-HPC ?2003 MIT 满足Krylov的世界 二维情形 对角的Krylov向量 预条件A 对一个m×m网格 SMA-HPC ?2003 MIT 满足Krylov的世界 GCR的收敛性 特征向量分析 回顾D －1A 的特征值 SMA-HPC ?2003 MIT 满足Krylov的世界 GCR的收敛性 特征向量分析 GCR迭代得到收敛性 SMA-HPC ?2003 MIT 满足Krylov的世界 带宽高斯消元过程 松弛和GCR 在二维和三维GCR比高斯消元快 只有m 3 非零的三维矩阵较快 可以消除通讯下限 SMA-HPC ?2003 MIT 满足Krylov的世界 怎么快收敛的 GCR 预条件是唯一希望 对于对角预条件AGCR已经获得通讯下限 预条件器必须加速通讯 通过1个以上网格点乘以PA使值移动 SMA-HPC ?2003 MIT 预条件法 高斯赛德尔预条件 具体视图 每一次高斯赛德尔松弛迭代使数据通过网格点 一维离散化PDE SMA-HPC ?2003 MIT 预条件法 高斯赛德尔预条件 Krylov向量 高斯赛德尔在唯一分析通讯加快 SMA-HPC ?2003 MIT 预条件法 高斯赛德尔预条件 对称的高斯赛德尔 这个对称的高斯赛德尔预条件器在两个方向通讯 SMA-HPC ?2003 MIT 预条件法 高斯赛德尔预条件 对称的高斯赛德尔 SGS迭代方程的起源 前向扫动（半步） 后向扫动（半步） SMA-HPC ?2003 MIT 预条件法 块对角预条件器 线模式 矩阵 网格 三对角阵加快 SMA-HPC ?2003 MIT 预条件法 块对角预条件器 线模式 预条件器线在唯 一方向通讯 现在预条件器是两个三对角解，在两者之间变量排序 问题： 解： 线首先在X方 向，然后y方向 网格 SMA-HPC ?2003 MIT 预条件法 域分解 块对角预条件器 将域分为小块， 每一个具有相同 的网格点编号 方法： 折中：快少意味着收敛 快，但迭代代价 大 SMA-HPC ?2003 MIT 预条件法 域分解 块对角预条件器 m点 块编号 点 块代价：l×l网格因子 稀疏GE GCR迭代 通讯界给出 迭代 对于l建议非敏感性：算法是 对于每一个GCR迭代重取因子？ SMA-HPC ?2003 MIT 预条件法 赛德尔化块对角 预条件器 线模式 SMA-HPC ?2003 MIT 网格 矩阵 预条件法 重叠域预条件器 基于线模式 求解较大的系统，但对于困难问题收敛较快（不只是泊松问题） 网格 矩阵 SMA-HPC ?2003 MIT 预条件法 不完备因子模式 大纲 回顾高斯消元法 计算步骤 填入稀疏阵 大大增加了因子代价 填入二维网格 不完备因子的思想 SMA-HPC ?2003 MIT 稀疏阵 填入 实例 非零结构矩阵一个GE步骤后的矩阵 填入 SMA-HPC ?2003 MIT 稀疏阵 填入 第二个实例 填入的传播 从第一步填入产生第二步填入 SMA-HPC ?2003 MIT 稀疏阵 填入 在矩阵的填入模式 SMA-HPC ?2003 MIT 非常稀疏 致密 非常稀疏 稀疏阵 填入 非因子随机矩阵 SMA-HPC ?2003 MIT 稀疏阵 填入 因子随机矩阵 SMA-HPC ?2003 MIT 二维有限差分矩阵的因子 产生的填入使因子代价高昂 SMA-HPC ?2003 MIT FD矩阵的特性 3维离散化 非零矩阵m＝4的实例 SMA-HPC ?2003 MIT 预条件法 不完备因子模式 主要思想 抛弃填入 抛弃所有填入 抛弃其它填入产生的填入 抛弃其它填入的填入产生的填入等 SMA-HPC ?2003 MIT 总结 ?三维BVP实例 ——航空动力学，连续机械学，热流动 ?一、二、三维有限差分方程 ——高斯消元代价 ?Krylov法 ——通讯下限 ——基于预条件器的通讯改善 SMA-HPC ?2003 MIT