A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations
A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations
复制标题
DOI：
10.1137/030601107
复制
发表时间：
2005-01-01
影响因子：
3.1
通讯作者：
Van de Geijn, RA
中科院分区：
文献类型：
--
作者：
Bientinesi, P;Dhillon, IS;Van de Geijn, RA
我们提出了一个新的并行算法的密集对称特征值/特征向量问题，是基于三对角特征值求解器，算法MR 3，最近开发的Dhillon和Parlett。算法MR 3计算对称三对角问题的所有特征值和特征向量的复杂度为O（n（2））。该算法只需要O（n）的额外工作空间，并且可以在O（nk）的时间内计算任意k个特征对的子集。相比之下，所有三对角特征值问题的早期稳定并行算法在最坏情况下需要O（n（3））操作，而一些实现，如分治，需要额外的O（n（2））内存。所提出的并行算法平衡的工作量之间的处理器，通过遍历矩阵相关的表示树，捕获算法MR 3执行的计算序列。由此产生的实现允许非常大的尺寸的问题被有效地解决-最大的密集特征问题解决的核心上的256处理器的机器与2千兆字节的内存每个处理器是一个矩阵的大小为128，000 x 128，000，这需要约8小时的CPU时间。我们目前的比较与其他特征值求解器和结果的矩阵中出现的计算量子化学和有限元建模的汽车车身的应用。
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.