大型周期块三对角线性方程组的并行算法

论文摘要

充分发挥并行计算机的潜在性能,寻求大型稀疏线性代数方程组的高效并行解法,是当前大规模科学计算中急待解决的问题,也是研究的热点问题,并行算法设计与并行程序实现的关键:依据不同并行计算机的结构特征,减少整体通讯并尽量使各处理机之间负载平衡。 本文基于分布式存储环境,着重研究系数矩阵为大型周期块三对角的线性方程组的并行求解问题,提出一些相应的高效分布式并行算法。 主要完成了如下工作: （1） 基于对系数矩阵的分解,根据分治思想提出了一种近似直接并行解法,使算法只在相邻处理机间有两次通信,有效地减少了通信次数。从理论上,给出了该算法成立的一个充分条件。并在HP rx2600集群上进行了数值计算,验证了该算法的有效性和可行性。 （2） 在方法（1）的基础上导出了一种并行求解周期块三对角线性方程组的迭代解法,通过对系数矩阵进行适当的分裂,使算法在不满足方法（1）的条件下,也能够计算,即扩大了方法的使用范围。从理论上,讨论了误差,给出了系数矩阵为Hermite正定矩阵和M-矩阵时算法的收敛性条件,最后在HP rx2600集群上进行了数值计算验证。 （3） 为加快方法（2）的收敛速度,引入松弛因子ω,得到一种松弛迭代并行算法,虽然理论分析收敛性条件尚不完善,有待进一步研究和探讨,但数值算例结果表明,该方法具有很高的并行效率,且迭代次数大大减小,收敛速度大幅度加快。 （4） 提出了一种求解周期块三对角线性方程组的迭代并行算法,并给出了相关的理论和数值算例。 （5） 基于Galerkin原理,提出了一种求解块三对角线性方程组的Amoldi并行算法,通过选取适当的子空间,使算法只在相邻处理机间有通信,因而具有很好的并行性,而且证明了该算法的收敛性。在HP rx2600集群上进行数值计算,结果表明,加速比呈线性增加,并行效率达到90%以上。

论文目录

• 摘要
• Abstract
• 第一章 预备知识
• §1.1 引言
• §1.2 基本概念及理论准备
• 第二章 周期块三对角线性方程组的一种直接解法
• §2.1 算法推导
• §2.2 并行实现
• §2.3 误差分析
• §2.4 数值算例
• 第三章 周期块三对角线性方程组的一种迭代算法
• §3.1 并行迭代格式推导
• §3.2 并行实现
• §3.3 收敛性分析
• §3.4 数值算例及结果比较
• 第四章 周期块三对角线性方程组的一种并行算法
• §4.1 算法推导
• §4.2 并行实现
• §4.3 收敛性分析
• §4.4 数值算例
• §4.5 几种方法算例结果比较
• 第五章 基于Galerkin原理的一种Arnoldi并行算法
• §5.1 问题的提出
• §5.2 Galerkin原理
• §5.3 改进的循环型Arnoldi算法
• §5.4 算法推导
• §5.5 并行实现
• §5.6 收敛性分析
• §5.7 数值算例
• 结束语
• 参考文献
• 硕士阶段研究成果
• 致谢
• 西北工业大学业 学位论文知识产权声明书
• 西北工业大学 学位论文原创性声明