论文部分内容阅读
大规模对称矩阵特征问题存在于许多科学计算领域与工程设计中，而且在许多科学应用的软件代码中也包含着对称特征问题的求解。然而随着求解问题规模的不断增大，存储空间和计算时间正在制约着这些计算问题的求解。因此对这些代码的并行化已成为必然。而对已有的许多并行代码，如计算量子化学的并行代码和电子结构并行代码MP_Quest，稠密对称特征问题求解占据着整个运行时间的极大部分。因此对称特征问题并行算法和实现技术的研究是非常必要和迫切的。
在过去的十几年，广义稠密特征问题的研究和发展主要集中在分布存储并行计算机的并行算法研究和实现上，而不是在数值分析方面。这些研究包括使用三级矩阵.矩阵操作的块算法方法和有效的并行分布方式，另外针对线性代数问题并行策略的研究也已变得非常重要。
本文工作主要围绕着广义对称特征问题有效并行算法设计和实现技术，研究了与这一问题有关的理论、并行算法设计方法和具体的实现。并行算法的研究充分考虑了处理器网格结构、数据在处理器的分布以及块算法技术等对算法性能的影响，主要目的是降低并行算法存在的通信开销、改善负载平衡，并尽量开拓算法的并行性。另外，针对现代并行机的多级体系结构，探讨了在这种计算平台上的编程模型和有效的并行算法设计方法。所取得成果包括：
1.本文给出了将广义对称特征问题转化为标准特征问题的并行算法。从降低已有并行算法的通信开销和增加算法并行性考虑，该并行算法将Cholesky分解结合到广义对称特征问题标准化转换中。新算法可显著改善已有并行算法的性能和可扩展性。另外本文给出了一个有效求解具有多个右端项的三角矩阵方程AX=B的并行算法。
2.在使用块算法技术设计并行算法时，普遍采用的方法是将块算法和块存储结合在一起。这在LU分解和广义对称特征问题标准化等问题的并行计算中确能带来益处。而对于对称矩阵三对角化并行，算法块和数据块的分离可改善已有并行块算法中的负载平衡和可扩展性。基于这一研究，本文给出了不依赖于存储块的对称矩阵三对角化并行块算法和回转换(backtransformatiom)求解标准特征问题特征向量的并行块算法。并提出了存在于回转换算法中的数据重分配策略。
3.基于秩-2修正+laguerre迭代法求解三对角特征问题的分而治之方法，本文给出了一个并行算法。该方法明显快于基于二分法的并行求解方法，并具有二分法的求解精度。且使用了比Cuppen分而治之算法更少的存储空间。
4.针对SMP集群系统讨论了MPI/OpenMP混合并行编程模型及其实现方法，并探讨了SMP集群上的并行算法设计方法。基于该系统所具有通信多级性和并行多级性，本文提出了集群级和节点级两级并行算法设计观点。并且基于前面对称特征问题并行算法的研究，给出了在SMP集群上三对角化转换和三对角特征问题求解的混合并行算法。
(1)矩阵三对角化的混合并行算法采用了数据在SMP节点间和节点内的动态和静态两种分布方式。节点内线程间并行采用了粗粒度并行模式，这使得节点内线程并行达到了完全的负载平衡。
(2)三对角特征问题的混合并行算法采用了细粒度+粗粒度多粒度模式和任务分配的动态调用方法，改善了原MPI算法中的负载平衡问题、降低了通信开销。
5.基于本文给出的并行算法，开发了对称特征问题并行求解器PSEPS。PSEPS的运行环境是支持MPI消息传递的多种类型体系结构的并行计算机，包括共享存储多处理机、分布存储并行计算机和SMP集群系统。PSEPS的运行要求BLAS库和LAPACK库。该求解器使用了二维块-循环数据分布。
另外，基于MPI/OpenMP混合并行，在深腾6800系统开发了一个试验版的对称矩阵特征问题并行求解器。