Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications

We present a novel algorithm to perform the Hessenberg reduction of an $n imes n$ matrix $A$ of the form $A = D +U V$ where $D$ is diagonal with real entries and $U$ and $V$ are $n imes k$ matrices with $k le n$. The algorithm has a cost of $O(n^2 k)$ arithmetic operations and is based on the quasiseparable matrix technology. Applications are shown to solving polynomial eigenvalue problems and some numerical experiments are reported in order to analyze the stability of the approach.