Qd-type methods for quasiseparable matrices

In the last few years many numerical techniques for computing eigenvalues of structured rank matrices have been proposed. Most of them arebased on $QR$ iterations since, in the symmetric case, the rank structure is preserved and high accuracy is guaranteed. In the unsymmetriccase, however, the $QR$ algorithm destroys the rank structure, which is instead preserved if $LR$ iterations are used. We consider a wideclass of quasiseparable matrices which can be represented in terms of the same parameters involved in their Neville factorization. Thisclass, if assumptions are made to prevent possible breakdowns, is closed under $LR$ steps. Moreover, we propose an implicit shifted $LR$method with a linear cost per step, which resembles the qd method for tridiagonal matrices. We show that for totally nonnegativequasiseparable matrices the algorithm is stable and breakdowns cannot occur, if the Laguerre shift, or other shift strategy preservingnonnegativity, is used. Computational evidence shows that good accuracy is obtained also when applied to symmetric positive definitematrices.