# An algorithm for the Hessenberg reduction of rank structured matrices

## Steven Delvaux

We call a matrix rank structured if the ranks of certain submatrices starting from the lower-left matrix corner, as well as the ranks of certain submatrices starting from the upper-right matrix corner, are small compared to the matrix size. The class of rank structured matrices contains as special cases the classes of semiseparable matrices, unitary Hessenberg matrices, quasiseparable matrices and so on.

In order to specify algorithms for the class of rank structured matrices, we will first need an efficient representation. To this end we will use the Givensweight representation: this is a generalization of the Givens-vector representation for semiseparable matrices [1], which we generalize to the case of an arbitrary rank structure.

In this talk we describe how, using
the Givens-weight representation, we can devise an efficient algorithm to
transform a rank structured matrix into a Hessenberg matrix by the use of
unitary similarity transformations. The algorithm is particularly important
since the Hessenberg reduction process is commonly used as a first step to
determine the eigenvalue spectrum of a matrix. We also show how the algorithm
can be modified to transform the given matrix to bidiagonal form, by means of
possibly different unitary row and column operations, i.e. by a reduction of the
form *A -> U AV* . This reduction is also important, since it can be used as a first
step to compute the singular value decomposition of a matrix.

### References

- R. Vandebril, M. Van Barel, and N. Mastronardi. A note on the representation and definition of semiseparable matrices. Numer. Linear Algebra Appl., 12:839 858, June 2005.