JSJXTYY计算机系统应用Computer Systems and Applications1003-3254计算机系统应用编辑部北京36-7078f72f6c945674734689e217a30fc1ca9acc0bb9db3e9b08ea130b7e128003b1d710.15888/j.cnki.csa.007078研究开发Research and Development基于分治法求解对称三对角矩阵特征问题的混合并行实现Hybrid Parallel Algorithm Using MPI/Cilk for Symmetric Tridiagonal Eigenproblems朱京乔ZHUJing-Qiao12赵永华ZHAOYong-Huayhzhao@sccas.cn*1中国科学院 计算机网络信息中心, 北京 100190Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China中国科学院大学, 北京 100049University of Chinese Academy of Sciences, Beijing 100049, China赵永华, E-mail:
yhzhao@sccas.cn920195920192892462505320191042019242019
Divide and conquer algorithm is widely used for tridiagonal matrix eigenproblems while computing efficiency and storage limitation are always bottlenecks for large scale problems. In this study, the proposed eigenproblem algorithm based on hybrid parallel paradigm with MPI/Cilk optimizes the divide and conquer algorithm both at data and task levels. The introduced task-based parallelization mechanism inside computing nodes solves the problem in data dependence and thread starvation by directed acyclic graph model. By coarse-grained partition of tasks the overhead of data communication among MPI nodes is also optimized, which helps to improve load balance. The numerical test is carried out and the result is compared with the pure MPI and MPI/openMP parallel algorithm, which shows the performance and efficiency of the algorithm.
并行计算对称特征问题分治算法Cilkparallel computingsymmetric eigenproblemDC methodCilk国家重点研发计划(2017YFB0202202, 2016YFB0201302); 中国科学院“十三五”信息化建设专项(XXH13506-405)National Key Research and Development Program of China (2017YFB0202202, 2016YFB0201302); CAS Special Fund for Informatization Construction in 13th Five-Year Plan (XXH13506-405)
ReferencesCuppen JJMA divide and conquer method for the symmetric tridiagonal eigenproblem198036217719510.1007/BF01396757
Cuppen JJM. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numerische Mathematik, 1980, 36(2): 177–195.
Gu M, Eisenstat SCA stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem19941541266127610.1137/S089547989223924X
Gu M, Eisenstat SC. A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem. SIAM Journal on Matrix Analysis and Applications, 1994, 15(4): 1266–1276.
Tisseur F, Dongarra JA parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures199820622232236
Tisseur F, Dongarra J. A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures. SIAM Journal on Scientific Computing, 1998, 20(6): 2223–2236.
Ammar GS, Reichel L, Sorensen DCAn implementation of a divide and conquer algorithm for the unitary eigen problem199218329230710.1145/131766.131770
Ammar GS, Reichel L, Sorensen DC. An implementation of a divide and conquer algorithm for the unitary eigen problem. ACM Transactions on Mathematical Software, 1992, 18(3): 292–307.
https://www.cilkplus.org/cilk-plus-tutoriall.]]>
Melman ANumerical solution of a secular equation199569448349310.1007/s002110050104
Melman A. Numerical solution of a secular equation. Numerische Mathematik, 1995, 69(4): 483–493.
Dhillon IS, Parlett BNOrthogonal eigenvectors and relative gaps200325385889910.1137/S0895479800370111
Dhillon IS, Parlett BN. Orthogonal eigenvectors and relative gaps. SIAM Journal on Matrix Analysis and Applications, 2003, 25(3): 858–899.
Dhillon IS, Parlett BNMultiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices200438712810.1016/j.laa.2003.12.028
Dhillon IS, Parlett BN. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. Linear Algebra and its Applications, 2004, 387: 1–28.