An overview of parallel algorithms for the singular value and symmetric eigenvalue problems

摘要

Solving dense symmetric eigenvalue problems and computing singular value decompositions continue to be two of the most dominating tasks in numerous scientific applications. With the advent of multiprocessor computer systems, the design of efficient parallel algorithms to determine these solutions becomes of paramount importance. In this paper, we discuss two fundamental approaches for determining the eigenvalues and eigenvectors of dense symmetric matrices on machines such as the Alliant FX/8 and CRAY X-MP. One approach capitalizes upon the inherent parallelism offered by Jacobi methods, while the other relies upon an efficient reduction to tridiagonal form via Householder's transformations followed by a multisectioning technique to obtain the eigenvalues and eigenvectors of the corresponding symmetric tridiagonal matrix. For the singular value decomposition, we discuss an efficient method for rectangular matrices in which the number of rows is substantially larger or smaller than the number of columns. This scheme performs an initial orthogonal factorization using block Householder transformation, followed by a parallel one-sided Jacobi method to obtain the singular values and singular vectors of the resulting upper-triangular matrix. Exceptional performance for this SVD scheme is demonstrated for tall matrices of full or deficient rank having clustered or multiple singular values. A hybrid method that combines one- and two-sided Jacobi schemes is also discussed. Performance results for each of the above algorithms on the Alliant FX/8 and CRAY X-MP computer systems will be presented with particular emphasis given to speedups obtained over such classical EISPACK algorithms.