A Hessenberg Reduction Algorithm for Rank Structured Matrices
Authors:
- Steven DelvauxSDSteven Delvaux
- Marc Van BarelMBMarc Van Barel
- Steven Delvaux And Marc Van BarelSBSteven Delvaux And Marc Van Barel
- L. GemignaniLGL. Gemignani
- L. RobolLRL. Robol
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 29 (3) , 895-926
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.
Keywords
This publication has 15 references indexed in Scilit:
- Structures preserved by the QR-algorithmJournal of Computational and Applied Mathematics, 2006
- Structures preserved by matrix inversionSIAM Journal on Matrix Analysis and Applications, 2006
- A fast algorithm for the inversion of general Toeplitz matricesComputers & Mathematics with Applications, 2005
- Rank structures preserved by the QR-algorithm: The singular caseJournal of Computational and Applied Mathematics, 2005
- Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form2003
- Fast and Stable Reduction of Diagonal Plus Semi-Separable Matrices to Tridiagonal and Bidiagonal FormBIT Numerical Mathematics, 2001
- Fast and stable eigendecomposition of symmetric banded plus semi-separable matricesLinear Algebra and its Applications, 2000
- The QR algorithm for unitary Hessenberg matricesJournal of Computational and Applied Mathematics, 1986
- Tridiagonalization of a symetric band matrixNumerische Mathematik, 1968
- Calculating the Singular Values and Pseudo-Inverse of a MatrixJournal of the Society for Industrial and Applied Mathematics Series B Numerical Analysis, 1965