An O(n sup 2 log(n)) Method For Finding The Eigenvalues Of Symmetric Toeplitz And Hankel Matrices.

This paper presents the first technique for computing the eigenvalues of symmetric Toeplitz and Hankel matrices in O(n sup 2 log (n)) computations, as compared to O(n sup 3) computations, required by all the previous techniques. This is achieved by developing a fast tridiagonalization algorithm, which makes use of the relationships of the Toeplitz and Hankel matrices with the circulant Toeplitz form. Then from this symmetric tridiagonal matrix, the eigenvalues are found by applying a QL-type algorithm, which incorporates Wilkinson's shift. Using the algorithm of this paper, the asymptotic complexity of finding all the eigenvalues of symmetric Toeplitz and Hankel matrices is O(n sup (2+epsilon)) where 0