数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  在线办公 | 
数值计算与计算机应用  2015, Vol. 36 Issue (2): 132-146    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
基于谱分割的稀疏矩阵特征值问题并行求解
曾玮, 赵永华
中国科学院计算机网络信息中心超级计算中心, 北京 100190
PARALLEL EIGENVALUE CALCULATION BASED ON SPECTRUM DIVISION METHOD FOR SPARSE MATRIX
Zeng Wei, Zhao Yonghua
Supercomputing Center, Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China
 全文: PDF (954 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文给出了一个基于谱分割并行求解稀疏矩阵特征值的方案,将矩阵的特征值求解区间划分为多个独立的子区间,分别对各个子区间内的特征值进行独立的并行求解. 在该方案中,提出了一种通过盖尔圆信息估计矩阵特征值分布的方法,并结合二分法以及插值方法修正特征值的分布,提高估计的准确性,进行谱区间分割. 本文还结合谱分割和基于围道积分的近似谱投影算法设计出一个特征值问题多级并行算法,并在“深腾7000” 和 “元”超级计算机上验证了本文提出谱分割方案的有效性、均衡性以及特征值并行求解的高效性. 同通用求解方法相比,基于谱区间分割的并行算法在1024核上性能提高了5倍以上,并行求解的可扩展性显著提升.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词谱分割   特征值   并行求解     
Abstract: In this paper, an e ective scheme is given, which can solve eigenvalue for large sparse matrixes based on spectrum division method. In this scheme, we divide the spectrum into several intervals and extract eigenvalues from each subinterval independently. To estimate the eigenvalue distribution, the Gerschgorin Circle Theorem is used. In addition, an inter- polation method, aimed to find the subintervals, is applied to reduce calculation amount. In this paper, a multistage parallel algorithm, combined with spectral projection method and approximate spectral projection method based on contour integral, is given. The validity, balance, and e ciency of this algorithm are veried in supercomputer "shenteng7000" and "yuan". Working on 1024 processors, the performance of this parallel algorithm improves five times compared with the general algorithm.
Key wordsSpectrum Division Method   Eigenvalue Calculation   Parallel Computing   
收稿日期: 2015-01-14;
基金资助:

国家自然科学基金重大研究计划项目(91430214)、国家”九七三“重点基础研究发展计划基金项目(2011CB309702)、国家”八六三“高技术研究发展计划基金项目(2012AA01A309)、数学工程与先进计算国家重点实验室开放基金项目(2014A03).

引用本文:   
. 基于谱分割的稀疏矩阵特征值问题并行求解[J]. 数值计算与计算机应用, 2015, 36(2): 132-146.
. PARALLEL EIGENVALUE CALCULATION BASED ON SPECTRUM DIVISION METHOD FOR SPARSE MATRIX[J]. Journal of Numerical Methods and Computer Applicat, 2015, 36(2): 132-146.
 
[1] Galgon M, Kramer L, and Lang B. the FEAST algorithm for large eigenvalue problems[J]. Proceedings of Applied Mathematics and Mechanics, 2011, 11(1): 747-748.
[2] Polizzi E. A Density Matrix-based Algorithm for Solving Eigenvalue Problems[J]. Physical Review B, 2009, 79(11): 112-115.
[3] Tang P T, Polizzi E. FEAST as a Subspace Iteration EigenSolver Accelerated by Approximate Spectral Projection[J]. SIAM Journal on Matrix Analysis and Applications, 2014, 35(2): 354-390.
[4] Polizzi E. A High-Performance Numerical Library for Solving Eigenvalue Problems: FEAST Solver User's Guide v2.1[J]. arXiv preprint, 2013, arXiv:1203.4031v2.
[5] FEAST solver, http://www.ecs.umass.edu/polizzi/fesat, 2009-2014.
[6] MUItifrontal Massively Parallel Sparse direct Solver, http://www.mumos.enseeiht.fr/, 1999-2011.
[7] Napoli E Di, Polizzi E, Saad Y. Efficient Estimation of Eigenvalue Counts in an Interval[J]. arXiv preprint, 2014, arXiv:1308.4275v2.
[8] Aktulga H M, Lin L, Haine C, Ng E G, Yang C. Parallel eigenvalue calculation based on multiple shift-invert Lanczos and contour integral based spectral projection method[J]. Parallel Computing, 2014, 40(7): 195-212.
[9] Lin L, Saad Y, Yang C. Approximating spectral densities of large matrices[J]. arXiv preprint, 2014, arXiv:1308.5467v2.
[10] 李庆扬, 王能超, 易大义. 数值分析(第5版)[M]. 清华大学出版社 2008, 22-50.
[11] 程云鹏, 张凯院, 徐忠. 矩阵论(第3版)[M]. 西北工业大学出版社 2009, 235-290.
[12] 张林波, 迟学斌, 莫则荛. 并行计算导论[M]. 清华大学出版社 2006, 175-220.
[13] Chen W Y, Song Y Q, Bai H J. Parallel Spectral Clustering in Distributed Systems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3): 568-586.
[1] 单炜琨, 李会元. 任意三角形Laplace特征值问题谱方法的数值对比研究[J]. 数值计算与计算机应用, 2015, 36(2): 113-131.
[2] 刘冬冬, 陈艳美, 黎稳. 关于正规矩阵对广义特征值新的扰动界限[J]. 数值计算与计算机应用, 2015, 37(2): 113-122.
[3] 黄娜, 马昌凤, 谢亚君. 一类Hermitian鞍点矩阵的特征值估计[J]. 数值计算与计算机应用, 2015, 37(1): 92-102.
[4] 林府标, 张千宏. 三维Poisson方程的三种有限元解及特征值下界[J]. 数值计算与计算机应用, 2015, 36(1): 69-80.
[5] 潘春平 . 关于PageRank的广义二级分裂迭代方法[J]. 数值计算与计算机应用, 2014, 36(4): 427-436.
[6] 汪超, 陈小山. 逆特征值问题的光滑LU分解算法[J]. 数值计算与计算机应用, 2014, 35(4): 289-296.
[7] 曹阳, 戴华. 非线性特征值问题的二次近似方法[J]. 数值计算与计算机应用, 2014, 36(4): 381-392.
[8] 张慧荣, 曹建文, 孙家昶. 不等距网格上求解ODE特征值问题若干高精度格式的计算与分析[J]. 数值计算与计算机应用, 2014, 35(2): 131-152.
[9] 张磊, 曹礼群. 复合材料特征值的高阶多尺度Rayleigh商校正[J]. 数值计算与计算机应用, 2013, 35(4): 431-448.
[10] 任志茹. 三阶线性常微分方程Sinc方程组的结构预处理方法[J]. 数值计算与计算机应用, 2013, 35(3): 305-322.
[11] 曹阳, 谈为伟, 蒋美群. 广义鞍点问题的松弛维数分解预条件子[J]. 数值计算与计算机应用, 2012, 34(4): 351-360.
[12] 秦佩华. 非光滑区域上椭圆型特征值问题的间断有限元方法应用[J]. 数值计算与计算机应用, 2012, 33(4): 293-300.
[13] 冯金华, 杨一都. 方程-Δu=λρu的Han元特征值渐近展开[J]. 数值计算与计算机应用, 2012, 33(2): 81-91.
[14] 孙家昶. 特征值问题的预变换方法 (Ⅱ):任意三角形域Laplace特征值的计算分析[J]. 数值计算与计算机应用, 2012, 34(1): 1-24.
[15] 秦晓伟, 刘新国, 赵娜. 关于解极大相关问题问题P-SOR算法的收敛性[J]. 数值计算与计算机应用, 2011, 33(4): 345-356.
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10