Toward an efficient parallel eigensolver for dense symmetric matrices

We describe a parallel algorithm for finding the eigenvalues and eigenvecto rs of a dense symmetric matrix, with an emphasis on the dense linear algebr a operations. We follow the traditional three-step process: reduce to tridi agonal form, solve the tridiagonal problem, then backtransform the result. Since the different steps have different algorithmic characteristics, this problem serves as a perfect vehicle for exploring some issues associated wi th parallel linear algebra calculations. In particular, we examine the effe cts of matrix distribution and blocking on the computational performance of tridiagonalization and backtransformation. Through experiments on an Intel Paragon, we demonstrate that block storage of the matrix is not necessary for a highly efficient block algorithm. The performance of our approach com pares very favorably with that of the corresponding ScaLAPACK routines.