PARALLEL ALGORITHMS TO COMPUTE THE EIGENVALUES AND EIGENVECTORS OFSYMMETRIC TOEPLITZ MATRICES∗

∗This paper was partially supported by the CICYT project TIC96-1062-C03: “Parallel Algorithms for the computation of the eigenvalues of sparse and structured malrices”

Abstract

In this paper we present two parallel versions of bisection method to compute the spectrum of symmetric Toeplitz matrices. Both parallel algorithms have been implemented and analysed on a virtual shared memory multiprocessor using a portable message-passing environment. The algorithms very efficiently parallelize the sequential method, and the application of a dynamic strategy to distribute the computations produces better results than the use of a static method. We also improve the performance of the original sequential algorithm by applying Newton's method for the final approximation of the eigenvalues. However, the bad results of the sequential algorithm produce low speedups when we compare the parallel methods with the best available sequential algorithm.

Keywords:

• Toeplitz matrices eigenstructure
• Parallel algorithms
• Dynamic load balance

Notes

∗This paper was partially supported by the CICYT project TIC96-1062-C03: “Parallel Algorithms for the computation of the eigenvalues of sparse and structured malrices”