Volume 58, pp. 316-347, 2023.

Improved bisection eigenvalue method for band symmetric Toeplitz matrices

Yuli Eidelman and Iulian Haimovici

Abstract

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 Tq with bandwidth q admits the representation Tq=Aq+Hq, where the eigendata of Aq are obtained explicitly and the matrix Hq has nonzero entries only in two diagonal blocks of size (q1)×(q1). Based on this representation, one obtains an interlacing property of the eigenvalues of the matrix Tq and the known eigenvalues of the matrix Aq. 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 , DOI: 10.1553/etna_vol58s316

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