对称矩阵三对角化的有效并行块算法设计  

AN EFFICIENT PARALLEL BLOCKING ALGORITHM DESIGN FOR REDUCING A SYMMETRIC MATRIX TO TRIDIAGONAL FORM

作　　者：赵永华[1] 迟学斌[1] 程强[1] 陈江[1] 赵涛[1] 

机构地区：[1]中国科学院计算机网络信息中心超级计算中心

出　　处：《数值计算与计算机应用》2006年第2期123-132,共10页Journal on Numerical Methods and Computer Applications

基　　金：中国科学院知识创新工程信息化建设专项(INF05-SCE)国家"863"项目(863;2002AA104540)国家自然科学基金"当代并行机的并行算法应用基础研究"(2005LB321702)

摘　　要：在矩阵数值计算中,块算法通常比非块算法更有效,但这也增加了并行算法设计和实现的难度．在广义稠密对称矩阵特征问题并行求解器中,并行块算法的构造可应用到正定对称矩阵的Choleski分解、对称矩阵的三对角化和回代转化(back-transiation)操作中．本文将并行块算法的讨论集中在具有代表性的对称矩阵三对角化上,给出在非块存储方式下对称矩阵三对角化的并行块算法设计方法．分析块算法大小同矩阵规模和处理器数量的关系．在深腾6800上的试验表明,我们的算法具有很好的性能,并得到了比ScaLAPACK更高的性能．In numerical computation of matrices, blocking algorithm is more efficient than non-blocking algorithm, but it makes the design and implementation of the parallel algorithms more difficult. In the parallel solvers of generalized dense symmentric eigenproblems, construction of parallel blocking algorithm can be applied to the Choleski Decomposition of a positive definite matrix, reducing a symmetric matrix to tridiagonal form and back-translation operation of a symmetric matrix. In this paper, we focus on the parallel blocking algorithm of reducing a symmetric matrix to tridiagonal form, give out the implementation in non-blocking storage scheme, and analyse the relationship between the block size in blocking algorithm and matrix size and number of processors. According to the comparison on DeepComp 6800, our algorithm has better performance and better speedup than ScaLAPACK.

关 键 词：对称矩阵 并行块算法 三对角矩阵 特征值 加速比 

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