文档介绍：国防科学技术大学
博士学位论文
大型稀疏线性方程组并行求解及预处理技术研究
姓名:仲妍
申请学位级别:博士
专业:计算机科学与技术
指导教师:骆志刚
2010-10
国防科学技术大学研究生院博士学位论文
摘要
大型稀疏线性方程组的高效并行求解是科学与工程计算中众多数值模拟问题
的核心。其求解方法通常分为直接法和迭代法两类,直接法计算过程稳定且计算
量可测、计算精度高,迭代法则存储和计算开销小。在实际应用中,针对直接法
存储开销大和迭代法存在不收敛风险等问题,发展出旨在改进系数矩阵质量的预
处理技术:通过变换或重排序系数矩阵,使变化后的矩阵具有谱分布更集中、填
充元个数更少或分块形式等特点,从而有利于提高算法稳定性,减少存储量或开
发并行性。因此,线性方程组的并行求解方法以及预处理技术得以共同发展。
本文主要完成了如下工作:
1、在典型结构线性方程组并行求解方面,基于一类具有内在并行特性的消去
过程——PIE(parallel implicit elimination)消去过程(WZ 分解)框架,通过研究
对称三对角矩阵的 WZ 分解式,推广得到一般三对角矩阵和 p-对称三对角矩阵的
WZ 分解式。前者去除了对称性的限制,后者将三条对角线的带宽推广到任意正整
数 p。继而,基于分而治之原则,运用通信与计算重叠技术和系数矩阵分割技术,
进一步提出并实现了一般三对角矩阵线性方程组和 p-对称三对角线性方程组的并
行求解算法,分别称为 PTri 算法和 PpSTri 算法。理论分析和数值实验表明,与现
有同类算法相比,本文构造的并行算法能有效平衡各处理机间的负载,并降低相
互等待的时间开销。其中,PTri 算法相对于 LUO 算法[22]的效率提高程度大于 22%;
当 p=1 时,PpSTri 算法较 RAO 算法[35]的效率改进率大于 %。
2、在一般结构线性方程组的并行求解方面,传统 Kryolv 子空间方法受同步开
销影响难以提升并行求解效率。基于 BiCR 算法,通过对现有 s-step 方法的研究,
构造出旨在减少并行求解中同步通信次数和访存次数的 s-BiCR 算法;进而结合分
布式矩阵向量乘积算子,实现了 s-BiCR 算法的并行求解。理论分析和统计实验表
明,s-BiCR 算法具有良好的并行特性和数据本地性。在并行求解过程中,数值实
验表明并行 s-BiCR 算法在计算速度和精度上均高于同类算法 s-BiCG[2]。
3、在线性方程组高效求解的预处理方面,对旨在减少非对称矩阵消去过程中
填充元的最小度排序算法进行了研究。针对传统排序算法应用于非对称矩阵时,
不能真实反映填充元变化的问题,基于原始矩阵二部图,利用消去集、可达集、
路径的条件 Q、消去关键边路径和消去元路径等概念,提出非对称矩阵消去过程
中非零元在二部图上的等价表示方法,进而研究了矩阵非零元结构的变化特征。
在此基础上,提出非对称矩阵可达集的计算方法,并证明该方法的搜索路径长度
不超过 3;提出未消去点具有相同邻接点集的判定方法以及未消去点的合并方法;
通过对消去点之间关系的分类,讨论了消去点的合并方法。在上述理论研究的基
第 i 页
国防科学技术大学研究生院博士学位论文
础上,设计了适合于非对称矩阵的近似最小度排序算法(NonAMD 算法)。实验
结果显示,与同类算法相比,NonAMD 算法使预处理后的矩阵在分解中非零元增
长比例最小,表明直接针对非对称矩阵研究最小度排序算法在减少填充元个数方
面的有效性。
关键词:WZ 分解;三对角矩阵;p-对称三对角矩阵;Krylov 子空间方法;s
步方法;二部图;最小度排序;并行计算
第 ii 页
国防科学技术大学研究生院博士学位论文
Abstract
Solving large sparse linear systems fast lies in the heart of many numerical
simulation problems in scientific and puting. Direct methods and
iterative methods are the two main solving methods. The former have stable calculation
process, putation and high precision, while the later need less storage
and time. In practical applications, precondition