PARALLEL ALGORITHMS TO COMPUTE THE EIGENVALUES AND EIGENVECTORS OFSYMMETRIC TOEPLITZ MATRICES∗
Authors:
- 1 January 1998
- journal article
- research article
- Published by Taylor & Francis in Parallel Algorithms and Applications
- Vol. 13 (1) , 75-93
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
This publication has 26 references indexed in Scilit:
- Accelerated bisection techniques for tri- and quindiagonal matricesInternational Journal for Numerical Methods in Engineering, 1992
- Solution and linear estimation of 2-D nearest-neighbor modelsProceedings of the IEEE, 1990
- An efficient algorithm for computing Pisarenko's harmonic decomposition using Levinson's recursionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- Toeplitz eigensystem solverIEEE Transactions on Acoustics, Speech, and Signal Processing, 1985
- On the eigenstructure of Toeplitz matricesIEEE Transactions on Acoustics, Speech, and Signal Processing, 1984
- An accelerated bisection method for the calculation of eigenvalues of a symmetric tridiagonal matrixNumerische Mathematik, 1984
- Fast solution of toeplitz systems of equations and computation of Padé approximantsJournal of Algorithms, 1980
- A parallel organisation of the bisection algorithmThe Computer Journal, 1979
- A view of three decades of linear filtering theoryIEEE Transactions on Information Theory, 1974
- The “Pegasus” method for computing the root of an equationBIT Numerical Mathematics, 1972