Recursive and iterative algorithms for computing eigenvalues of Hermitian Toeplitz matrices

The numerical solution of the complete eigenspectrum for Hermitian Toeplitz matrices is presented. Trench´s algorithm (1989), which employs bisection on contiguous intervals, and the Pegasus method are used to achieve estimates of distinct eigenvalues. Several modifications of Trench´s algorithm are examined; the goals are an increase in the rate of convergence, even at some reduction in estimate accuracy, and an accommodation of eigenvalue multiplicity or clustering. A promising approach that contains three key ingredients is found. They are: a modification of Trench´s procedure to employ noncontiguous intervals, a procedure for multiplicity identification, and a replacement of the Pegasus method by the modified Rayleigh quotient iteration. The result is the basis for a novel eigenspectrum solver with a cubic convergence rate and good estimation accuracy. Simulation results for high-order Hermitian Toeplitz matrices are provided