A PARALLEL INERTIA METHOD FOR FINDING EIGENVALUES ON VECTOR AND SIMD ARCHITECTURES

A new variant of bisection for the parallel and vector computation of the eigenvalues of a symmetric tridiagonal matrix T is proposed. Bisec tion is based on the computation of the inertia of(T - sigma I) to det ermine the number of eigenvalues of T less than a given origin shift s caler sigma. In order to introduce parallelism, the proposed algorithm uses parallel matrix factorization techniques to compute the inertia using the diagonal D of the LDL(t) decomposition of P(T - sigma I)P-t, where P is a suitable permutation matrix chosen to partially decouple the factorization. This approach yields up to O(n) parallelism for co mputing a single eigenvalue. The resulting parallel algorithm has a se quential computational complexity approximately 9/4 more expensive tha n the serial inertia computation; however speedups of 5 to 6 over seri al bisection and of 3.8 to 4.6 over multisection, due to the vectoriza tion, have been measured on the Cray 2 and YMP for a matrix of size 30 00. For larger problems, YMP and Connection Machine 2 (CM-2) implement ations are compared and shown to be competitive.