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.


  • 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.