SMA-HPC ?2003 MIT 数值模拟导论－讲座23 积分方程的快速算法 Jacob White 感谢Deepak Ramaswamy, Michal Rewienski和Karen Veroy 大纲 SMA-HPC ?2003 MIT 离散化积分方程的求解 应用Krylov子空间法 快速矩阵向量积 多极点算法 多极点表示 基本层次 算法改善 局部展开 自适应算法 计算结果 SMA-HPC ?2003 MIT 静电学的外部问题 电势 外部 是在表面给定的 Dirichelet问题 首先应该找到积分方程 电势 格林函数 电量密 度 微型谐振器的阻力 SMA-HPC ?2003 MIT 谐振器 离散结构 计算力 俯视图 计算力 上视图 三维拉普拉斯方程 SMA-HPC ?2003 MIT 基本函数法 分段常基 积分方程 将平面离 散为小的片 表示 基函数 片 如果X在片j上 如果X不在片j上 三位拉普拉斯法 SMA-HPC ?2003 MIT 基函数法 质心配置 在面片质 心配置点 配置点 三位拉普拉斯法 SMA-HPC ?2003 MIT 基函数法 计算矩阵单元 配置点 片 片的面积 一点的 二次近似 四点的 二次近似 三维拉普拉斯法 SMA-HPC ?2003 MIT 基函数法 分段常基Galerkin 配置点 片 一点的 二次近似 是单值可积的 三位拉普拉斯法 SMA-HPC ?2003 MIT 基本函数法 “同一项”的计算 变换窍门 配置点 片 半径为R的 圆盘的配置点 在两段积分 圆盘其他面 圆盘积分单值 但有解析公式 圆盘 三维拉普拉斯法 SMA-HPC ?2003 MIT 基本函数法 “同一项”的计算窍门 配置点 片 1）如果面片是平面多边形，解析公式存在 2）曲面片能用投影处理 三位拉普拉斯法 SMA-HPC ?2003 MIT 基本函数法 Galerkin（测试＝基） 对于分段常基 三维拉普拉斯法 SMA-HPC ?2003 MIT 基本函数法 稠密矩阵 积分方程法产生大型稠密矩阵 高斯消元法太慢了！ 离散积分方程的求解 SMA-HPC ?2003 MIT 广义共轭残差算法 GCR第k步 计算Apk，对于离散 积分方程，A是密度 在第k步搜索方 向确定最优步长 更新解和残差 计算新的正交搜索方向 计算Apk 离散化积分方程的求解 SMA-HPC ?2003 MIT 广义共轭残差算法 GCR的复杂性 密度矩阵向量 乘积代价O（n2） 向量内积 向量加法，O（n） O（k）内积， 总代价O（nk） 即使迭代次数较小，积分方程算法代价为O（n2） 离散化积分方程的求解 SMA-HPC ?2003 MIT 广义共轭残差算法 快速矩阵向量求积 精确计算Apk 密度矩阵向量乘积代价O(n2) 近似计算Apk 矩阵乘积代价降为O(n) 或O(nlogn) 快速求解器 SMA-HPC ?2003 MIT 计算代价 高斯消元时间 存储空间 具有直接M－V的GCR 时间 存储空间 快速方法时间 存储空间 基本多极点的概念 SMA-HPC ?2003 MIT 多极点表示 直接电势估计 d估计点 面片 在i点的电势： 完全估计d点花费d2次操作 基本多极点的概念 SMA-HPC ?2003 MIT 多极点表示 直接电势估计 d估计点 面片 i点的近似电势 基本多极点的概念 SMA-HPC ?2003 MIT 多极点表示 直接电势估计 ?面片电量的多极点系数函数 ?计算多极点展开花费d数量级的操作 ?每一近似电势估计花费1数量级的操作 ?由于d面片d数量级的操作，d电势估计 基本多极点的概念 SMA-HPC ?2003 MIT 多极点表示 误差度量的不变性 估计点 估计点 基本多极点概念 SMA-HPC ?2003 MIT 多极点表示 多极点算法层次 层次保证： ?边界误差 阶数＝2产生的精度为1％ 多极点的优化 SMA-HPC ?2003 MIT 局部展开 代价的降低 构造一个局部展开表示远距离电荷的电势 ?每一估计点用一简单局部展开估 计，而不是多极点展开 ?构造一个局部展开表示远距 离电荷的电势 多极点的优化 SMA-HPC ?2003 MIT 局部展开 分簇估计 d估计点 面片 对于估计点簇局部展开总结了远距离电荷的影响 多极点的优化 SMA-HPC ?2003 MIT 局部展开 分簇估计 ?当过多极点展开结合电荷合并时，电势估计是O（n） ?i点的电势估计近似为 多极点的展开 SMA-HPC ?2003 MIT 局部展开 操作总结 立方1 立方2 局部展开 多极点展开 多极点优化 SMA-HPC ?2003 MIT 局部展开 操作总结 ?多极点和局部展开是应用互补层次建立的 ?完成计算包括： 1）建立多极点（前向通道） 2）建立局部（后向通道） 3）估计局部展开和附近电荷电势（估计通道） 多极点优化 SMA-HPC ?2003 MIT 局部展开 层次的构造 ?首先通过孩子向父母前 向移动建立多极点展开 ?然后通过父母向孩子 后向移动建立局部展开 ?计算树结构 多极点的优化 SMA-HPC ?2003 MIT 局部展开 构造细节 ?将多极点展开转换为局部展开 ?一个孩子的局部展开是其父母的局 部展开加上孩子交互作用范围的多 极点展开的转换 多极点优化 SMA-HPC ?2003 MIT 自适用算法 多极点的低效率 直接估计 多极点优化 SMA-HPC ?2003 MIT 自适用算法 多极点的低效率 多极点估计 应用多极点比直接法的代价昂贵 多极点优化 SMA-HPC ?2003 MIT 自适用多极点算法 简单的自适应模式 果多极点系数比面片少，则直接计算面片的影响 ?类似，如果局部展开比估计点少，则不用局部展开 ?对于非均匀面片分布维持O（mn）的复杂性 计算实例 SMA-HPC ?2003 MIT 球的翻译 电势分布 电势为： 电荷为： 计算实例 SMA-HPC ?2003 MIT 球的翻译 离散化的收敛性 1/(# panels)面片之一 计算实例 SMA-HPC ?2003 MIT 球的翻译 离散化的收敛性 ?误差应该如1/n衰减 ?多极点近似最终干涉 ?高阶多极点展开需要高阶精度 计算实例 SMA-HPC ?2003 MIT 两个球的翻译 电视分布 ?在每一球电势分布： ?与一个简单的具体问题是否对应？ 计算实例 SMA-HPC ?2003 MIT 两个球的翻译 计算矩阵向量乘积的代价 计算实例 SMA-HPC ?2003 MIT 两个球的翻译 计算矩阵向量乘积的代价 ?直接矩阵向量乘积代价如n2增加 ?多极点矩阵向量乘积代价如n增加 ?多极点算法的应用范围取决于精度 ?对于阶数为2的展开，中断点n＝400 复杂性总结 SMA-HPC ?2003 MIT 离散化为n个面片的积分方程 ?高斯消元法：O（n3） GCR，直接M－V法：O（n2） ?多极点加速GCR：O（mn） 选择FFT网格来平衡代价 SMA-HPC ?2003 MIT 选择FFT网格来平衡代价 SMA-HPC ?2003 MIT ?选择网格使直接法代价等于FFT代价 ?问题的细化通常使网格更细化 非均匀问题 SMA-HPC ?2003 MIT ?非均匀－空网格导致FFT效率低 细化立方分布－非均匀性恶化 总结 SMA-HPC ?2003 MIT 离散化积分方程的求解 应用Krylov子空间法 快速矩阵向量积 多极点算法 多极点表示 基本层次 算法改善 局部展开 自适应算法 计算结果 预修正FFT算法