A New Parallel Approach to the Toeplitz Inverse Eigenproblem Using Newton-like Methods

摘要

In this work we describe several portable sequential and parallel algorithms for solving the inverse eigenproblem for Real Symmetric Toeplitz matrices. The algorithms are based on Newton's method (and some variations), for solving nonlinear systems. We exploit the structure and some properties of Toeplitz matrices to reduce the cost, and use Finite Difference techniques to approximate the Jacobian matrix. With this approach, the storage cost is considerably reduced, compared with parallel algorithms proposed by other authors. Furthermore, all the algorithms are efficient in computational cost terms. We have implemented the parallel algorithms using the parallel numerical linear algebra library SCALAPACK based on the MPI environment. Experimental results have been obtained using two different architectures: a shared memory multiprocessor, the SGI PowerChallenge, and a cluster of Pentium II PC's connected through a Myrinet network. The algorithms obtained show a good scalability in most cases.