A Bisection Eigenvalue Algorithm for Symmetric Quasiseparable Matrices

In this paper we design a fast bisection algorithm for computing a prescribed eigenvalue of a symmetric quasiseparable matrix represented by its Cholesky-like factorization A0=L0Ω0L0T, where L0 is a lower triangular quasiseparable matrix and Ω0 is a signature matrix. The workhorse of the algorithm is an efficient linear-time scheme for updating the factorization under shifting. Numerical experiments illustrate the effectiveness and the robustness of the proposed method.