In this paper, parallel extensions of a complete symmetric eigensolver, proposed by Yau and Lu in 1993, are pre sented. First, an overview of this invariant subspace decomposition method for dense symmetric matrices is given, followed by numerical results. Then, works are exposed in progress on distributed-memory implementa tion. The algorithm's heavy reliance on matrix-matrix mul tiplication, coupled with Fast Fourier Transform (FFT), should yield a highly parallelizable algorithm. Finally, performance results for the dominant computation kernel on the Intel Paragon are presented.
Get full access to this article
View all access options for this article.
References
1.
Anderson, E., Z. Bai, C.H. Bischof, J.W. Demmel, J.J. Dongarra, J.J. DuCroz, A. Greenbaum, S.J. Hammarling, A. McKenney, S. Ostrouchov, and D.C. Sorensen.1992. LAPACK user's guidePhiladelphia: Society for Industrial and Applied Mathematics .
2.
Anderson, E., Z. Bai, C.H. Bischof, J.W. Demmel, J.J. Dongarra, J.J. DuCroz, A. Greenbaum, S.J. Hammarling, A. McKenney, S. Ostrouchov, and D.C. Sorensen.1995. LAPACK users' guide, release 2.0. 2d ed. Philadelphia: SIAM.
3.
Bischof, C., S. Huss-Lederman, X. Sun, A. Tsao, and T. Turnbull.1994. Parallel performance of a symmetric eigensolver based on the invariant subspace decomposition approach. PRISM Working Note 15, Argonne National Laboratory, Argonne, IL.
4.
Choi, J., J.J. Dongarra, D.W. Walker, and R.C. Whaley.1994. Scalapack reference manual parallel factorization routines (LU, QR, and Cholesky) and parallel reduction routines (HDR, BRD, and TRD). Technical Report ORNL/TM-12470, Oak Ridge National Laboratory, Oak Ridge, TN.
5.
Cuppen, J.J.M.1981. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math.36: 177-195.
6.
Dongarra, J., and D. Sorensen.1987. A fully parallel algorithm for the symmetric eigenvalue problem. SIAM J. Sci. Statist. Comput.8:S139-S154.
7.
Giménez, D., R. van de Geijn, V. Hernández, and A.M. Vidal.1996. Exploiting the symmetry on the Jacobi method on a mesh of processors. Paper presented at the 4th EUROMICRO Workshop on Parallel and Distributed Processing, Braga, Portugal.
8.
Ipsen, I.C.F., and E.R. Jessup.1990. Solving the symmetric tridiagonal eigenvalue problem on the hypercube. SIAM J. Sci. Stat. Comput.11 (2):203-229.
9.
Lin, C., and L. Snyder.1992. A matrix product algorithm and its comparative performance on hypercubes. In Scalable High Performance Computing Conference SHPCC92. Los Alamitos, CA: IEEE Computer Society, pp. 190-193.
10.
Rivlin, T.J.1990. Chebyshev polynomial: From approximation theory to algebraic and number theory. 2d ed. New York: John Wiley.
11.
Rojo, O., and R.L. Soto.1994. A decreasing sequence of eigenvalue localization region. Linear Alg. Appl.196:71-84.
12.
Yau, S.-T., and Lu, Y.1993. Reducing the symmetric matrix eigenvalue problem to matrix multiplications. SIAM Journal Sci. Comput.14 (1):121-136.
