Volume 59, pp. 60-88, 2023.

The bisection eigenvalue method for unitary Hessenberg matrices via their quasiseparable structure

Yuli Eidelman and Iulian Haimovici

Abstract

If $N_0$ is a normal matrix, then the Hermitian matrices $\frac{1}{2}(N_0+N_0^{\ast })$ and $\frac{i}{2}(N_0^{\ast }-N_0)$ have the same eigenvectors as $N_0$. Their eigenvalues are the real part and the imaginary part of the eigenvalues of $N_0$, respectively. If $N_0$ is unitary, then only the real part of each of its eigenvalues and the sign of the imaginary part is needed to completely determine the eigenvalue, since the sum of the squares of these two parts is known to be equal to $1$. Since a unitary upper Hessenberg matrix $U$ has a quasiseparable structure of order one and we express the matrix $A=\frac{1}{2}(U+U^{\ast })$ as quasiseparable matrix of order two , we can find the real part of the eigenvalues and, when needed, a corresponding eigenvector $x$, by using techniques that have been established in the paper by Eidelman and Haimovici [Oper. Theory Adv. Appl., 271 (2018), pp. 181–200].
We describe here a fast procedure, which takes only $1.7\mathrm{\%}$ of the bisection method time, to find the sign of the imaginary part. For instance, in the worst case only, we build one row of the quasiseparable matrix $U$ and multiply it by a known eigenvector of $A$, as the main part of the procedure. This case occurs for our algorithm when among the $4$ numbers $\pm \cos t\pm i\sin t$ there are exactly $2$ eigenvalues and they are opposite, so that we have to distinguish between the case $\lambda ,-\lambda$ and the case $\bar{\lambda },-\bar{\lambda }$.
The performance of the developed algorithm is illustrated by a series of numerical tests. The algorithm is more accurate and many times faster (when executed in Matlab) than for general Hermitian matrices of quasiseparable order two, because the action of the quasiseparable generators, which are small matrices in the previous cited paper, can be replaced by scalars, most of them real numbers.

Full Text (PDF) [426 KB], BibTeX , DOI: 10.1553/etna_vol59s60

Key words

quasiseparable, eigenstructure, Sturm property, bisection, unitary Hessenberg

AMS subject classifications

15A18, 15B10, 15B57, 65F15

Links to the cited ETNA articles

[8]	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
[19]	Vol. 58 (2023), pp. 316-347 Yuli Eidelman and Iulian Haimovici: Improved bisection eigenvalue method for band symmetric Toeplitz matrices