Volume 58, pp. 316-347, 2023.

Improved bisection eigenvalue method for band symmetric Toeplitz matrices

Yuli Eidelman and Iulian Haimovici


We apply a general bisection eigenvalue algorithm, developed for Hermitian matrices with quasiseparable representations, to the particular case of real band symmetric Toeplitz matrices. We show that every band symmetric Toeplitz matrix $T_q$ with bandwidth $q$ admits the representation $T_q=A_q+H_q$, where the eigendata of $A_q$ are obtained explicitly and the matrix $H_q$ has nonzero entries only in two diagonal blocks of size $(q-1)\times (q-1)$. Based on this representation, one obtains an interlacing property of the eigenvalues of the matrix $T_q$ and the known eigenvalues of the matrix $A_q$. This allows us to essentially improve the performance of the bisection eigenvalue algorithm. We also present an algorithm to compute the corresponding eigenvectors.

Full Text (PDF) [426 KB], BibTeX

Key words

Toeplitz, quasiseparable, banded matrices, eigenstructure, inequalities, Sturm with bisection

AMS subject classifications

15A18, 65F15, 65F50, 15A42, 65N25

Links to the cited ETNA articles

[10]Vol. 44 (2015), pp. 342-366 Yuli Eidelman and Iulian Haimovici: The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms

ETNA articles which cite this article

Vol. 59 (2023), pp. 60-88 Yuli Eidelman and Iulian Haimovici: The bisection eigenvalue method for unitary Hessenberg matrices via their quasiseparable structure

< Back