Parallel Jacobi algorithms for the algebraic eigenvalue problem

The standard method for computing the eigenvalues of a general dense matrix on a traditional sequential computer is the QR algorithm. With the advent of parallel computers, a variety of parallel eigenvalue algorithms have been proposed. One approach has been to recognize the inherent parallelism in the Jacobi method, which was the standard algorithm for the problem before the invention of the QR algorithm. This thesis investigates some Jacobi-like algorithms for solving eigenvalue problems on parallel computers. First considered is the (easier) case of Hermitian matrices. The issue of convergence of the cyclic Jacobi method for the Hermitian eigenvalue problem has never been conclusively settled. New theoretical results are developed that prove global convergence of a large class of parallel Jacobi algorithms for the Hermitian eigen-problem. Next the eigenvalue problem for general matrices is considered. A new parallel Jacobi-like algorithm for general matrices developed which promises to be very competitive on massively parallel computers. It is proven that this new algorithm converges quadratically. Experimental results are presented that indicate that the algorithm can be expected to take $O(n{\rm log}\sp2 n)$ time using $O(n\sp2)$ processors. Finally an implementation of this algorithm on the massively parallel Connection Machine is described and performance results are presented.