Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications
Provides a faster method for a specific matrix structure, benefiting computational linear algebra applications.
The paper presents an O(n^2k) algorithm for Hessenberg reduction of real diagonal plus low-rank matrices, with applications to polynomial eigenvalue problems, and reports numerical experiments analyzing stability.
We present a novel algorithm to perform the Hessenberg reduction of an $n\times n$ matrix $A$ of the form $A = D + UV^*$ where $D$ is diagonal with real entries and $U$ and $V$ are $n\times k$ matrices with $k\le n$. The algorithm has a cost of $O(n^2k)$ 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