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

Two approaches for solving dense symmetric eigensystems on a multiprocessor are presented. One method is based upon Jacobi diagonalization. Two- and one-sided Jacobi schemes are discussed. The latter is motivated by the singular value decomposition (SVD) of rectangular matrices. The second approach couples an efficient reduction to tridiagonal form via Householder transformation with a multisectioning strategy to determine the eigenvalues and eigenvectors of the corresponding tridiagonal matrix. A multiprocessor scheme is presented to determine the SVD of a matrix. Possible hybrid SVD algorithm may be derived. The performance of the algorithms is compared with that of the classical algorithms implemented in EISPACK on the Alliant FX/8 and CRAY X-MP.