Gemignani L., Robol L. Fast Hessenberg reduction of some rank structured matrices. In: Siam Journal on Matrix Analysis and Applications, vol. 38 (2) pp. 574 - 598. SIAM, 2017. |

Abstract (English) |
We develop two fast algorithms for Hessenberg reduction of a structured matrix $A = D + UV^H$, where $D$ is a real or unitary n x 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 Hessenberg form and then completing the reduction by annihilation of the unwanted subdiagonals. It is shown that the novel method requires O(n^2 k) arithmetic operations and is significantly faster than other reduction algorithms for rank structured matrices. The method is then extended to the unitary plus low rank case by using a block analogue of the CMV form of unitary matrices. It is shown that a block Lanczos-type procedure for the block tridiagonalization of Re(D) induces a structured reduction on A in a block staircase CMV-type shape. Then, we present a numerically stable method for performing this reduction using unitary transformations and show how to generalize the subdiagonal elimination to this shape, 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. | |

URL: | http://epubs.siam.org/doi/abs/10.1137/16M1107851 | |

DOI: | 10.1137/16M1107851 | |

Subject | Hessenberg reduction Quasiseparable matrices Bulge chasing CMV matrix Complexity G.1.3 NUMERICAL ANALYSIS. Numerical Linear Algebra 65F15 Eigenvalues, eigenvectors |

1) Download Document PDF |

Open access Restricted Private