通过并行计算和多重网格提升等几何分析计算效率

摘要

等几何分析是一种新型的偏微分方程数值解法，广泛应用于工程领域。为了使等几何分析在众多工程领域中更加实用，需要研究如何提高等几何分析计算效率，实现高效的等几何分析求解器。本论文通过使用并行计算和多重网格方法来提升等几何分析的计算效率。本论文的主要工作以及创新点包括:
　　 (1)提出基于计算域分解的并行算法来加速等几何分析的线性系统的装配。将计算域均匀划分给所有处理器，在计算域上的计算完成后，使用一个快速多路归并算法构建全局刚度矩阵，完成线性系统的构建。
　　 (2)将等几何分析的并行性分成计算域层次和全局刚度矩阵层次，提出利用全局刚度矩阵分解的并行算法来构建和求解等几何分析的线性系统。利用计算域分解的方法，并行地完成计算域层次的计算。在全局刚度矩阵层次上，将全局刚度矩阵均匀地按块划分给所有处理器。利用均匀划分全局刚度矩阵的方法，实现了一个并行共轭梯度法来求解线性系统。
　　 (3)在Intel SCC上实现了一个并行等几何分析框架。使用的并行方法是全局刚度矩阵划分，计算域层次的计算是用惰性计算来完成。每个核使用一个哈希表来保存已经计算域的值。在构建线性系统时，去哈希表上查询需要的计算域，如果查询不在则计算出来并且添加到哈希表中。在全局刚度矩阵划分的基础上，针对SCC的结构实现了共轭梯度法。
　　 (4)提出两种多重网格方法来加速等几何分析的线性系统求解器的收敛。两种方法称为correction scheme和nested iteration。Correction scheme通过在粗网格上精确求解残量方程来加速细网格上的收敛。Nested iteration使用粗网格上的精确解作为细网格上的初始解。基于nested iteration，提出了基于多重网格的等几何分析数值模拟方法。
　　 实验表明，基于计算域分解的并行算法在8核系统上最高能够得到6.17的加速比。基于矩阵分解的并行算法可以得到接近线性的加速比。本论文提出的多重网格方法可以有效地加速线性系统迭代的收敛，基于多重网格的等几何分析数值模拟的效率要大大高于一般的等几何分析数值模拟方法。
　　 通过使用并行计算技术加速线性系统的构建，使用多重网格方法来加速线性系统求解，根据本论文的算法可以构建高效的等几何分析求解器。

目录

声明

摘要

表格

插图

算法

第一章 绪论

1．1 研究动机

1．2 国内外研究现状

1．2．1 使用不同几何表示来构造解空间

1．2．2 等几何分析的应用推广

1．2．3 等几何分析的理论

1．2．4 等几何分析的计算效率研究

1．3 研究内容与主要成果

1．4 本文的结构安排

第二章 背景及相关工作

2．1 偏微分方程简介

2．1．1 偏微分方程的定义

2．1．2 偏微分方程的应用举例

2．1．3 偏微分方程的解析方法

2．1．4 有限差分法

2．1．5 有限体积法

2．1．6 有限元方法

2．2 等几何分析

2．2．1 B样条和NURBS简介

2．2．2 其他几何工具

2．2．3 等几何分析解空间构造以及细化操作

2．3 有限元方法的并行算法

2．4 多核体系结构与共享存储系统

2．5 本章小结

第三章 基于计算域分解的并行等几何分析

3．1 二维泊松方程的等几何分析

3．2 基于计算域分解的并行算法

3．3 算法分析

3．3．1 时间复杂度分析

3．3．2 优点与不足

3．4 实验结果

3．4．1 有效性验证

3．4．2 性能测试

3．5 本章小结

第四章 基于矩阵分解的并行方法

4．1 基于计算域分解方法的不足

4．2 基于矩阵分解的并行算法

4．2．1 刚度矩阵的存储结构

4．2．2 计算高斯点上的值

4．2．3 装配刚度矩阵和力量向量

4．2．4 稀疏线性系统求解

4．2．5 算法分析

4．3 实验结果与分析

4．3．1 算法有效性验证

4．3．2 预条件算子的有效性验证

4．3．3 算法效率实验

4．4 本章小结

第五章 面向SCC平台的并行等几何分析框架

5．1 SCC平台的介绍

5．2 面向SCC的并行等几何分析框架

5．2．1 数据划分方法

5．2．2 面向SCC的共轭梯度法

5．2．3 并行构建线性系统

5．3 实验结果及分析

5．3．1 模拟模式

5．3．2 在SCC上的测试

5．4 本章小结

第六章 面向等几何分析的多重网格法

6．1 一些记号

6．1．1 误差分析

6．1．2 离散系统

6．2 两种多重网格方法

6．2．1 Correction Scheme方法

6．2．2 Nested Iteration方法

6．3 多重网格的数值模拟

6．4 本章小结

第七章 总结与未来工作展望

7．1 本文工作

7．1．1 基于计算域分解的并行方法

7．1．2 基于刚度矩阵分解的并行算法

7．1．3 基于SCC的高效等几何分析框架

7．1．4 面向等几何分析的多重网格方法

7．2 未来工作展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果