论文部分内容阅读
大型稀疏线性方程组的高效并行求解是科学与工程计算中众多数值模拟问题的核心。其求解方法通常分为直接法和迭代法两类,直接法计算过程稳定且计算量可测、计算精度高,迭代法则存储和计算开销小。在实际应用中,针对直接法存储开销大和迭代法存在不收敛风险等问题,发展出旨在改进系数矩阵质量的预处理技术:通过变换或重排序系数矩阵,使变化后的矩阵具有谱分布更集中、填充元个数更少或分块形式等特点,从而有利于提高算法稳定性,减少存储量或开发并行性。因此,线性方程组的并行求解方法以及预处理技术得以共同发展。本文主要完成了如下工作:1、在典型结构线性方程组并行求解方面,基于一类具有内在并行特性的消去过程——PIE(parallel implicit elimination)消去过程(WZ分解)框架,通过研究对称三对角矩阵的WZ分解式,推广得到一般三对角矩阵和p-对称三对角矩阵的WZ分解式。前者去除了对称性的限制,后者将三条对角线的带宽推广到任意正整数p。继而,基于分而治之原则,运用通信与计算重叠技术和系数矩阵分割技术,进一步提出并实现了一般三对角矩阵线性方程组和p-对称三对角线性方程组的并行求解算法,分别称为PTri算法和PpSTri算法。理论分析和数值实验表明,与现有同类算法相比,本文构造的并行算法能有效平衡各处理机间的负载,并降低相互等待的时间开销。其中,PTri算法相对于LUO算法[22]的效率提高程度大于22%;当p=1时,PpSTri算法较RAO算法[35]的效率改进率大于7.8%。2、在一般结构线性方程组的并行求解方面,传统Kryolv子空间方法受同步开销影响难以提升并行求解效率。基于BiCR算法,通过对现有s-step方法的研究,构造出旨在减少并行求解中同步通信次数和访存次数的s-BiCR算法;进而结合分布式矩阵向量乘积算子,实现了s-BiCR算法的并行求解。理论分析和统计实验表明,s-BiCR算法具有良好的并行特性和数据本地性。在并行求解过程中,数值实验表明并行s-BiCR算法在计算速度和精度上均高于同类算法s-BiCG[2]。3、在线性方程组高效求解的预处理方面,对旨在减少非对称矩阵消去过程中填充元的最小度排序算法进行了研究。针对传统排序算法应用于非对称矩阵时,不能真实反映填充元变化的问题,基于原始矩阵二部图,利用消去集、可达集、路径的条件Q、消去关键边路径和消去元路径等概念,提出非对称矩阵消去过程中非零元在二部图上的等价表示方法,进而研究了矩阵非零元结构的变化特征。在此基础上,提出非对称矩阵可达集的计算方法,并证明该方法的搜索路径长度不超过3;提出未消去点具有相同邻接点集的判定方法以及未消去点的合并方法;通过对消去点之间关系的分类,讨论了消去点的合并方法。在上述理论研究的基础上,设计了适合于非对称矩阵的近似最小度排序算法(NonAMD算法)。实验结果显示,与同类算法相比,NonAMD算法使预处理后的矩阵在分解中非零元增长比例最小,表明直接针对非对称矩阵研究最小度排序算法在减少填充元个数方面的有效性。