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^*)$ and $\frac{i}{2}(N_0^*-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^*)$ 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\%$ 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 $\overline\lambda,-\overline\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 |