A Parallel Eigensolver for Dense Symmetric Matrices Based on Multiple Relatively Robust Representations
Paolo Bientinesi, Inderjit S. Dhillon, Robert A. Geijn · SIAM Journal on Scientific Computing · 2005
We present a new parallel algorithm for the dense symmetric eigenvalue/eigenvector problem that is based upon the tridiagonal eigensolver, Algorithm $\mbox{\sf MR}^3$, recently developed by Dhillon and Parlett. Algorithm $\mbox{\sf MR}^3$ 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 $\mbox{\sf MR}^3$. 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 $\times$ 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.