Fast Hessenberg reduction of some rank structured matrices

par Luca Gemignani (Dipartimento di Informatica, Università di Pisa)

vendredi 4 mars 2016, 09:30 → 10:30 Europe/Paris

Salle XR203 (Bâtiment XLIM)

We develop two fast algorithms for Hessenberg reduction of a structured matrix $A = D + UV^H$ where $D$ is a real or unitary $n \times n$ diagonal matrix and $U, V \in \mathbb{C}^{n \times k}$. The proposed algorithm for the real case exploits a two--stage approach by first reducing the matrix to a generalized $k$-Hessenberg form and then completing the reduction by annihilation of the $k-1$ unwanted sub diagonals. It is shown that the novel method requires $O(n^2k)$ arithmetic operations and it is significantly faster than other reduction algorithms for rank structured matrices. The method is then extended to the unitary plus low rank case by simultaneously working on $A$ and the real part $\Re(D)$. We show that the preservation of the structure on $\Re(D)$ induces a structured reduction on $A$ in a block CMV--type format and we show how to generalize the subdiagonal elimination to this case, while still being able to provide a condensed representation for the reduced matrix. In this way the complexity still remains linear in $k$ and, moreover, the resulting algorithm can be adapted to deal efficiently with block companion matrices. This is a joint work with L. Robol.