Efficient diagonalization of oversized matrices on a distributed-memory multiprocessor

On parallel architectures, Jacobi methods for computing the singular value decomposition (SVD) and the symmetric eigenvalue decomposition (EVD) have been established as one of the most popular algorithms due to their excellent parallelism. Most of the Jacobi algorithms for distributed-memory architectures have been developed under the assumption that matrices can be distributed over the processors by square blocks of an even order or column blocks with an even number of columns. Obviously, there is a limit on the number of processors while we need to deal with problems of various sizes. We propose algorithms to diagonalize oversized matrices on a given distributed-memory multiprocessor with good load balancing and minimal message passing. Performances of the proposed algorithms vary greatly, depending on the relation between the problem size and the number of available processors. We give theoretical performance analyses which suggest the faster algorithm for a given problem size on a given distributed-memory multiprocessor. Finally, we present a new implementation for the convergence test of the algorithms on a distributed-memory multiprocessor and the implementation results of the algorithms on the NCUBE/seven hypercube architecture.This work was supported by National Science Foundation grant CCR-8813493. This work was partly done during the author's visit to the Mathematical Science Section, Engineering Physics and Mathematics Division, Oak Ridge National Laboratory, while participating in the Special Year on Numerical Linear Algebra, 1988, sponsored by the UTK Departments of Computer Science and Mathematics, and the ORNL Algebra sponsored by the UTK Departments of Computer Science and Mathematics, and the ORNL Mathematical Sciences Section, Engineering Physics and Mathematics Division.