Fast computation of eigenvalues of periodic CMV matrices

Abstract

Periodic CMV matrices are unitary matrices that can be specified by $O(n)$ data. Their eigenvalues can be computed by standard methods, storing them as conventional matrices (using $O(n^2)$ data) in $O(n^3)$ time. Here a fast method that computes the eigenvalues in $O(n^2)$ time (using $O(n)$ data) is presented.