A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations

被引:32
作者
Bientinesi, P [1 ]
Dhillon, IS [1 ]
Van de Geijn, RA [1 ]
机构
[1] Univ Texas, Dept Comp Sci, Austin, TX 78712 USA
关键词
parallel computing; symmetric matrix; eigenvalues; eigenvectors; relatively robust representations;
D O I
10.1137/030601107
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We present a new parallel algorithm for the dense symmetric eigenvalue/eigenvector problem that is based upon the tridiagonal eigensolver, Algorithm MR3, recently developed by Dhillon and Parlett. Algorithm MR3 has a complexity of O(n(2)) operations for computing all eigenvalues and eigenvectors of a symmetric tridiagonal problem. Moreover the algorithm requires only O(n) extra workspace and can be adapted to compute any subset of k eigenpairs in O(nk) time. In contrast, all earlier stable parallel algorithms for the tridiagonal eigenproblem require O(n(3)) operations in the worst case, while some implementations, such as divide and conquer, have an extra O(n(2)) memory requirement. The proposed parallel algorithm balances the workload equally among the processors by traversing a matrix-dependent representation tree which captures the sequence of computations performed by Algorithm MR3. The resulting implementation allows problems of very large size to be solved efficiently-the largest dense eigenproblem solved in-core on a 256 processor machine with 2 GBytes of memory per processor is for a matrix of size 128,000 x 128,000, which required about 8 hours of CPU time. We present comparisons with other eigensolvers and results on matrices that arise in the applications of computational quantum chemistry and finite element modeling of automobile bodies.
引用
收藏
页码:43 / 66
页数:24
相关论文
共 46 条
[11]  
CUPPEN JJM, 1981, NUMER MATH, V36, P177, DOI 10.1007/BF01396757
[12]  
Dekker T. J., 1969, Constructive aspects of the fundamental theorem of algebra, P37
[13]   JACOBIS METHOD IS MORE ACCURATE THAN QR [J].
DEMMEL, J ;
VESELIC, K .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1992, 13 (04) :1204-1245
[14]  
DHILLON I, 1997, P 8 SIAM C PAR PROC
[15]  
Dhillon I. S., 1997, THESIS U CALIFORNIA
[16]   Current inverse iteration software can fail [J].
Dhillon, IS .
BIT, 1998, 38 (04) :685-704
[17]   Orthogonal eigenvectors and relative gaps [J].
Dhillon, IS ;
Parlett, BN .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2003, 25 (03) :858-899
[18]   Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices [J].
Dhillon, IS ;
Parlett, BN .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2004, 387 :1-28
[19]   Inner deflation for symmetric tridiagonal matrices [J].
Dhillon, IS ;
Malyshev, AN .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 358 :139-144
[20]  
DHILLON IS, UCBCSD97971