Volume 44, pp. 342-366, 2015.

The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms

Yuli Eidelman and Iulian Haimovici

Abstract

Since we can evaluate the characteristic polynomial of an $N\times N$ order one quasiseparable Hermitian matrix $A$ in less than $10N$ arithmetical operations by sharpening results and techniques from Eidelman, Gohberg, and Olshevsky [Linear Algebra Appl., 405 (2005), pp. 1–40], we use the Sturm property with bisection to compute all or selected eigenvalues of $A$. Moreover, linear complexity algorithms are established for computing norms, in particular, the Frobenius norm $\Vert A{\Vert }_F$ and $\Vert A{\Vert }_{\mathrm{\infty }},\Vert A{\Vert }_1$, and other bounds for the initial interval to be bisected. Upper and lower bounds for eigenvalues are given by the Gershgorin Circle Theorem, and we describe an algorithm with linear complexity to compute them for quasiseparable matrices.

Full Text (PDF) [312 KB], BibTeX

Key words

quasiseparable, Hermitian, Sturm property, matrix norm, eigenvalues, bisection

AMS subject classifications

15A18, 15A15, 65F35, 15A57, 65F15

ETNA articles which cite this article

Vol. 58 (2023), pp. 316-347 Yuli Eidelman and Iulian Haimovici: Improved bisection eigenvalue method for band symmetric Toeplitz matrices

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