一类大规模稀疏矩阵特征问题求解的并行算法  

PARALLEL SOLVING LARGE-SCALE SPARSE MATRIX EIGENVALUE PROBLEM

作　　者：吴洋[1,2] 赵永华[1] 纪国良[1,2] 

机构地区：[1]中国科学院计算机网络信息中心超级计算中心 [2]中国科学院大学,北京100190

出　　处：《数值计算与计算机应用》2013年第2期136-146,共11页Journal on Numerical Methods and Computer Applications

基　　金：国家自然科学基金(60873113);国家基础研究项目(973项目:2011CB309702);863项目(2010AA012301;2102AA01A309)资助

摘　　要：本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率,设计了负载平衡的行划分方式,实现了计算和通信重叠的稀疏矩阵重排序方法,通过预处理减少计算过程中各进程间消息传递的通信量.另外,基于多核处理器高性能并行计算,实现了MPI和细粒度(线程级)OpenMP混合并行算法.在深腾7800并行计算机上对并行算法进行了测试,结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性,适合大规模稀疏特征问题的求解.This paper presents a parallel conjugate gradient method to solve the large-scale sparse matrix eigenvalue problem. Design a matrix＇s row-partition method with load balance,implement a matrix rearranging method for the overlap of computation and communication, decrease the traffic between processors through preprocess. In addition, we present a MPI and OpenMP parallel methods. We take some numerical experiments under ShenTeng7800 shows that keep constant communication time under different processors. Shows that algorithm has high Daxa]le] efl^e-i^r~e＇~r ~,~ 1＋;

关 键 词：共轭梯度法 并行算法 负载均衡 压缩格式 

分 类 号：O241.6[理学—计算数学]