并行算法在大规模线性方程组求解中的应用与研究

论文摘要

在计算数学与计算机科学领域中,Ax=b形式的线性方程组求解是问题的关键。为解决这一问题,在单处理器系统下对于各种不同种类的线性方程组很多可靠高质量和高效数值方法已经研究出来了。随着超大规模集成电路和和网络技术的最新进展,已经激起了人们对通过多处理机系统来解决许多实际问题兴趣。许多计算密集型的应用(比如:有限元分析计算)最终都会化简成为求解大规模线性方程组的问题。因此,在广泛的应用中,许多求解大规模线性方程组的并行算法扮演着非常重要的作用。在这些并行算法被正式投入使用之前,首先必须解决其中与实现相关的问题。本文主要针对求解线性方程组典型的并行算法的研究及其在IBM x3500上的实现(比如:Gauss消元法,Jordan消元法,LU分解,Cramer法则,Jacobi迭代法,SOR超松弛迭代法等)。对于线性方程组有许多分类方法,一种分类方法是简单的将其划分成稠密线性方程组和稀疏线程方程组,稠密线性方程组一般采取直接法求解,而稀疏线性方程组一般采取迭代法求解,特别是大规模稀疏线程方程组的求解在实际应用中尤其重要。本文主要做以下几方面的工作:(1)并行计算体系结构和基于消息传递的MPI编程介绍,以及MPI编程基础。(2)研究线性方程组的直接解法。对Gauss和Jordan消元法的并行算法进行了综述,并且分析这两个算法各自的计算时间代价和通信时间代价。最终这两个算法在基于MPI编程环境的多处理机上进行了实验及对比分析。(3)研究线性方程组的迭代解法。对Jacobi迭代,Seidel迭代和SOR超松弛迭代同样进行了综述。并且在多处理机上实现了Jacobi迭代和Seidel并行算法。(4)为了体现了大规模稀疏线性方程组求解的应用价值,研究了基于离散法求解二维Poisson方程,给出了其求解过程的MPI实现,并且从多个方面对该MPI程序进行了讨论与改进。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 问题的提出研究的意义
• 1.2 本文研究的目的和研究的内容
• 2 并行计算
• 2.1 并行体系结构
• 2.1.1 Flynn 分类法
• 2.1.2 MIMD 的进一步分类
• 2.2 并行编程环境MPI
• 2.2.1 消息传递编程MPI 的介绍
• 2.3 MPI 并行程序的两种基本模式
• 2.3.1 对等模式的MPI 程序设计
• 2.3.2 主从模式的MPI 程序设计
• 2.4 MPI 并行程序的设计的通信模式
• 2.4.1 标准通信模式
• 2.4.2 缓存通信模式
• 2.4.3 同步通信模式
• 2.4.4 就绪通信模式
• 2.5 非阻塞通信MPI 程序设计
• 2.5.1 非阻塞通信简介
• 2.5.2 非阻塞标准发送和接收
• 2.6 并行程序的度量
• 2.7 通信问题
• 2.8 并行计算数学工具PETSc
• 3 求解线性方程组的直接法
• 3.1 直接消元法基础
• 3.2 Gauss 消元法
• 3.2.1 Gauss 消元法介绍
• 3.2.2 Gauss 串行算法
• 3.2.3 Gauss 消元法并行算法
• 3.3 Jordan 消元法介绍
• 3.4 Gauss 消元法与Jordan 消元法的实验对比分析
• 3.5 一个新的Gauss 消元法（连续Gauss 消元法）
• 3.5.1 连续Gauss 消元法介绍
• 3.5.2 连续高斯消元法的并行算法
• 3.5.3 连续Gauss 消元算法的内存需求
• 3.5.4 并行任务的调度
• 3.5.5 总结
• 3.6 三角方程组的并行解法
• 3.6.1 三对角方程组的串行解法
• 3.6.2 三对角方程组的并行解法
• 4 求解线性方程组的迭代法
• 4.1 基本迭代法介绍
• 4.2 Jacobi 迭代（同步迭代）
• 4.3 Seidel 迭代（异步迭代）
• 4.4 SOR 超松弛迭代
• 4.5 异步并行迭代法
• 4.5.1 异步并行迭代法基础
• 4.5.2 线性迭代的一般收敛性结果
• 4.6 应用实例
• 4.6.1 求解Poisson 方程问题的提出与基础
• 4.6.2 并行算法设计与分析
• 4.6.3 MPI 并行程序设计
• 4.6.4 并行效率分析
• 4.6.5 MPI 并行程序的改进
• 4.6.6 实验结果分析
• 5 结论与展望
• 5.1 主要结论
• 5.2 后续研究工作的展望
• 致谢
• 参考文献
• 附录
• A. 作者在攻读学位期间发表的论文目录