A Hessenberg Reduction Algorithm for Rank Structured Matrices

Authors:
  • SDSteven Delvaux
    Steven Delvaux
  • MBMarc Van Barel
    Marc Van Barel
  • SBSteven Delvaux And Marc Van Barel
    Steven Delvaux And Marc Van Barel
  • LGL. Gemignani
    L. Gemignani
  • LRL. Robol
    L. Robol

Abstract
In this paper, we show how to perform the Hessenberg reduction of a rank structured matrix under unitary similarity operations in an efficient way, using the Givens-weight representation. This reduction can be used as a first step for eigenvalue computation. We also show how the algorithm can be modified to compute the bidiagonal reduction of a rank structured matrix, this latter method being a preprocessing step for computing the singular values of the matrix. For the main cases of interest, the algorithms we describe in this paper are of complexity $O((ar+bs)n^2)$, where n is the matrix size, r is some measure for the average rank index of the rank structure, s is some measure for the bandwidth of the unstructured matrix part around the main diagonal, and $a,b\in\mathbb{R}$ are certain weighting parameters. Numerical experiments demonstrate the stability of this approach.

This publication has 15 references indexed in Scilit: