Articolo in rivista, 2017, ENG, 10.1137/16M1107851

Fast Hessenberg reduction of some rank structured matrices

Gemignani L.; Robol L

Dipartimento di Informatica, Università di Pisa, Pisa, Italy; CNR-ISTI, Pisa, Italy

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.

SIAM journal on matrix analysis and applications (Print) 38 (2), pp. 574–598

Keywords

Hessenberg reduction, Quasiseparable matrices, Bulge chasing, CMV matrix, Complexity

CNR authors

Robol Leonardo

CNR institutes

ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"

ID: 374248

Year: 2017

Type: Articolo in rivista

Creation: 2017-07-12 10:18:47.000

Last update: 2020-12-16 12:46:19.000

CNR authors

External IDs

CNR OAI-PMH: oai:it.cnr:prodotti:374248

DOI: 10.1137/16M1107851

Scopus: 2-s2.0-85021767753

ISI Web of Science (WOS): 000404766000015