Geodesic
The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms
Electronic transactions on numerical analysis, Tome 44 (2015), pp. 342-366
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 $\|A\|_F$ and $\|A\|_{\infty},\|A\|_{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.
Classification : 15A18, 15A15, 65F35, 15A57, 65F15
Keywords: quasiseparable, Hermitian, Sturm property, matrix norm, eigenvalues, bisection 
@article{ETNA_2015__44__a12,
     author = {Eidelman,  Yuli and Haimovici,  Iulian},
     title = {The fast bisection eigenvalue method for {Hermitian} order one quasiseparable matrices and computations of norms},
     journal = {Electronic transactions on numerical analysis},
     pages = {342--366},
     year = {2015},
     volume = {44},
     zbl = {1332.65049},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2015__44__a12/}
}
TY  - JOUR
AU  - Eidelman,  Yuli
AU  - Haimovici,  Iulian
TI  - The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms
JO  - Electronic transactions on numerical analysis
PY  - 2015
SP  - 342
EP  - 366
VL  - 44
UR  - http://geodesic.mathdoc.fr/item/ETNA_2015__44__a12/
LA  - en
ID  - ETNA_2015__44__a12
ER  - 
%0 Journal Article
%A Eidelman,  Yuli
%A Haimovici,  Iulian
%T The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms
%J Electronic transactions on numerical analysis
%D 2015
%P 342-366
%V 44
%U http://geodesic.mathdoc.fr/item/ETNA_2015__44__a12/
%G en
%F ETNA_2015__44__a12
Eidelman,  Yuli; Haimovici,  Iulian. The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms. Electronic transactions on numerical analysis, Tome 44 (2015), pp. 342-366. http://geodesic.mathdoc.fr/item/ETNA_2015__44__a12/