PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
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


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional