Improved bisection eigenvalue method for band symmetric Toeplitz matrices
Yuli Eidelman, Iulian Haimovici · ETNA - Electronic Transactions on Numerical Analysis · 2023
We apply a general bisection eigenvalue algorithm, developed forHermitian matrices with quasiseparable representations, to the particular caseof real band symmetric Toeplitz matrices. We show that every band symmetricToeplitz matrix $T_q$ with bandwidth $q$ admits the representation$T_q=A_q+H_q$, where the eigendata of $A_q$ are obtained explicitly andthe matrix $H_q$ has nonzero entries only in two diagonal blocksof size $(q-1)\times (q-1)$. Based on this representation, one obtainsan interlacing property of the eigenvalues of the matrix $T_q$ and the knowneigenvalues of the matrix $A_q$. This allows us to essentially improve the performance of thebisection eigenvalue algorithm. We also present an algorithm tocompute the corresponding eigenvectors.