Efficient algorithms for the evaluation of the eigenvalues of (block) banded Toeplitz matrices

Abstract:

Let A be an $n \times n$ banded block Toeplitz matrix of bandwidth k with $m \times m$ blocks having entries in a field F. We present algorithms for computing $p(\lambda ) = \det (A - \lambda I)$ as well as the ratio $p(\lambda )/p’(\lambda )$, where $p’(\lambda )$ is the first derivative of $p(\lambda )$ with respect to $\lambda$, in roughly $(3/2){k^2}\log n + O({k^3})$ block multiplications. If the field F supports FFT, then the cost is reduced to $O(({m^2}k\log k + {m^3}k)\log n + {k^3}{m^3})$ scalar multiplications. The algorithms generalize an algorithm given by W. Trench for computing $p(\lambda )$ in the case $m = 1$ in roughly $k\log n + O({k^3})$ multiplications and rely on powering a companion matrix associated with the linear recurrence relation representing the original problem.