基于谱分割的特征值并行求解算法研究

来源 :中国科学院大学 | 被引量 : 0次 | 上传用户:ligc66
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
特征值求解问题在众多的科学和工程领域都有着广泛的应用,因此特征值求解的研究一直是众多专家学者研究的热点。对于实际问题所产生的大规模稀疏矩阵,一般需要投影类算法进行求解,如Lanczos算法、Amoldi算法等。计算机硬件的发展以及并行技术的兴起,大大的提高了计算机特征值求解的计算能力,同时,也出现了许多高效的特征值并行求解软件库,如PARPACK、Anasazi、BLOPEX、PRIMME等。  然而,随着矩阵规模、求解特征值数目以及处理器数目的增加,使得求解特征值的并行算法在并行效率、存储量、计算量等各方面都面临着瓶颈问题。本文所研究的特征值并行求解的谱分割方案,将矩阵特征值求解区间分割为若干个子区间,同时将处理器分组,分别对各个小区间独立的进行并行求解。通过引入一层粗粒度的并行,缓解特征值并行求解的瓶颈问题。实现谱分割的关键在于精确的估计矩阵特征值分布。而本文提出了基于矩阵盖尔圆信息来粗略估计矩阵特征值分布的方法,并给出了一个结合三次埃尔米特插值以及二分法的迭代分割区间的算法。最后,本文给出了结合谱分割和基于围道积分的近似谱投影算法,进行特征值并行求解的方案。  本文的主要工作如下:  1.研究了基于围道积分的近似谱投影算法极其理论,并结合高斯-勒让德积分方法以及MUMPS软件包实现了该并行方法,进行了测试。  2.给出了一种通过矩阵盖尔圆信息粗略估计矩阵特征值分布的方案,并提出了对特征值分布估计进行修正的方法。  3.研究了谱分割的基本理论以及方法,并提出了结合二分法的迭代方法实现区间分割,减少计算量。  4.结合谱分割、基于围道积分的近似谱投影方法、高斯-勒让德积分方法给出了特征值并行求解的方案,并进行了实验测试。  试验结果表明,采用该方案对大规模矩阵特征值求解,可以在保证求解结果准确可靠的前提下,增加并行算法的加速比、并行效率以及可扩展性。
其他文献
在对类似于专利战略分析系统这种复杂系统的研究中,一个非常棘手的问题就是高维数据的降维问题。决定现实世界演化的背景机制通常是非线性的,传统的线性降维方法(如主成分分析
新闻背景为了抢救保存各地的方言和少数民族语言,今年10月,中国语言资源有声数据库启动。对此,一位网友说:“我感觉我家乡的方言,是世界上最动听的语言。有效保护,将使她永远
当前世界已经进入知识经济时代,越来越多的国家开始重点关注知识产权的保护,并将发展知识产权作为国家经济发展战略的重大内容。专利文档作为保存现代科技成果的重要方式,几乎包
视频监控系统是现代数字视频技术的一个新的应用,是视频技术和互联网技术不断发展过程中经过融合而成的信息系统。随着社会发展,视频监控系统的应用逐步深入各行各业,在交通、公
随着社会的发展与进步,重视继电保护系统中的信息管理技术具有重要的意义.本文主要介绍信息管理技术在继电保护系统中的运用的有关内容.
目前我国石油开采过程中,对井场施工工程参数实施实时监测的设备大多是极难维护的进口配套设备或功能简单过时的改制产品,针对这一情况和实际需要,本文对井场施工参数的实时监测
随着时代步伐的加快,我们的社会步入了全球化的知识经济时代,此时人们对信息的依赖越来越强。信息的管理和利用成为这个时代的一大研究课题,而专利信息又是所有信息中的精华部分
伴随着互联网的大规模发展和计算机处理能力的提高,越来越多的现今网络应用所需要占用的网络资源也随之增加,这些复杂应用的存在,导致网络的数据传送能力相对不足。 本文在进
指令级并行自理是目前国际上比较热门的一个研究方向.而VLIW体系结构则是一种高并行度的指令级并行处理的体系结构.该文讨论了VLIW体系机构下的优化编译器的设计和实现中的一
随着数字学术资源数量的迅速增长,学生和研究者们越来越难以在浩如烟海的学术资源库中找到自己期望的资源。推荐系统是个性化搜索引擎外另一种有效的资源过滤手段。推荐系统根