Name
Abstract | ||
|---|---|---|
We develop two fast algorithms for Hessenberg reduction of a structured matrix A = D + UVH, where D is a real or unitary n x n diagonal matrix and U, V is an element of C-n x (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 R(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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/16M1107851 | SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS |
Keywords | Field | DocType |
Hessenberg reduction,quasi-separable matrices,bulge chasing,CMV matrix,complexity | Hessenberg matrix,Discrete mathematics,Combinatorics,Matrix (mathematics),Unitary matrix,Unitary state,Diagonal matrix,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 2 | 0895-4798 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Gemignani | 1 | 193 | 27.01 |
| Leonardo Robol | 2 | 30 | 7.04 |