论文部分内容阅读
特征值求解问题在众多的科学和工程领域都有着广泛的应用,因此特征值求解的研究一直是众多专家学者研究的热点。对于实际问题所产生的大规模稀疏矩阵,一般需要投影类算法进行求解,如Lanczos算法、Amoldi算法等。计算机硬件的发展以及并行技术的兴起,大大的提高了计算机特征值求解的计算能力,同时,也出现了许多高效的特征值并行求解软件库,如PARPACK、Anasazi、BLOPEX、PRIMME等。 然而,随着矩阵规模、求解特征值数目以及处理器数目的增加,使得求解特征值的并行算法在并行效率、存储量、计算量等各方面都面临着瓶颈问题。本文所研究的特征值并行求解的谱分割方案,将矩阵特征值求解区间分割为若干个子区间,同时将处理器分组,分别对各个小区间独立的进行并行求解。通过引入一层粗粒度的并行,缓解特征值并行求解的瓶颈问题。实现谱分割的关键在于精确的估计矩阵特征值分布。而本文提出了基于矩阵盖尔圆信息来粗略估计矩阵特征值分布的方法,并给出了一个结合三次埃尔米特插值以及二分法的迭代分割区间的算法。最后,本文给出了结合谱分割和基于围道积分的近似谱投影算法,进行特征值并行求解的方案。 本文的主要工作如下: 1.研究了基于围道积分的近似谱投影算法极其理论,并结合高斯-勒让德积分方法以及MUMPS软件包实现了该并行方法,进行了测试。 2.给出了一种通过矩阵盖尔圆信息粗略估计矩阵特征值分布的方案,并提出了对特征值分布估计进行修正的方法。 3.研究了谱分割的基本理论以及方法,并提出了结合二分法的迭代方法实现区间分割,减少计算量。 4.结合谱分割、基于围道积分的近似谱投影方法、高斯-勒让德积分方法给出了特征值并行求解的方案,并进行了实验测试。 试验结果表明,采用该方案对大规模矩阵特征值求解,可以在保证求解结果准确可靠的前提下,增加并行算法的加速比、并行效率以及可扩展性。