Articolo in rivista, 2017, ENG, 10.1137/16M1107851
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
Hessenberg reduction, Quasiseparable matrices, Bulge chasing, CMV matrix, Complexity
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