A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center