Numerical solution of the eigenvalue problem for Hermitian Toeplitz-like matrices

Abstract

An iterative method based on displacement structure is proposed for computing eigenvalues and eigenvectors of a class of Hermitian Toeplitz-like matrices which includes matrices of the form T*T where T is arbitrary Toeplitz matrix, Toeplitz-block matrices and block-Toeplitz matrices. The method obtains a specific individual eigenvalue (i.e., the i-th smallest, where i is a specified integer in [1, 2,...,n]) of an n x n matrix at a computational cost of O(n2) operations. An associated eigenvector is obtained as a byproduct. The method is more efficient than general purpose methods such as the QR algorithm for obtaining a small number (compared to n) of eigenvalues. Moreover, since the computation of each eigenvalue is independent of the computation of all other eigenvalues, the method is highly parallelizable. Numerical results illustrate the effectiveness of the method.