An Implicit Multishift $QR$-Algorithm for Hermitian Plus Low Rank Matrices
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 32 (4) , 2190-2212
Abstract
Hermitian plus possibly non-Hermitian low rank matrices can be efficiently reduced into Hessenberg form. The resulting Hessenberg matrix can still be written as the sum of a Hermitian plus low rank matrix. In this paper we develop a new implicit multishift $QR$-algorithm for Hessenberg matrices, which are the sum of a Hermitian plus a possibly non-Hermitian low rank correction. The proposed algorithm exploits both the symmetry and low rank structure to obtain a $QR$-step involving only $\mathcal{O}(n)$ floating point operations instead of the standard $\mathcal{O}(n^2)$ operations needed for performing a $QR$-step on a Hessenberg matrix. The algorithm is based on a suitable $\mathcal{O}(n)$ representation of the Hessenberg matrix. The low rank parts present in both the Hermitian and low rank part of the sum are compactly stored by a sequence of Givens transformations and a few vectors. Due to the new representation, we cannot apply classical deflation techniques for Hessenberg matrices. A new, efficient technique is developed to overcome this problem. Some numerical experiments based on matrices arising in applications are performed. The experiments illustrate effectiveness and accuracy of both the $QR$-algorithm and the newly developed deflation technique.
Keywords
This publication has 15 references indexed in Scilit:
- Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbationsNumerical Algorithms, 2008
- A Givens-Weight Representation for Rank Structured MatricesSIAM Journal on Matrix Analysis and Applications, 2008
- A Hessenberg Reduction Algorithm for Rank Structured MatricesSIAM Journal on Matrix Analysis and Applications, 2007
- On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal formsLinear Algebra and its Applications, 2007
- Structures preserved by the QR-algorithmJournal of Computational and Applied Mathematics, 2006
- Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equationsNumerische Mathematik, 2005
- 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 Transformation--Part 2The Computer Journal, 1962
- The QR Transformation A Unitary Analogue to the LR Transformation--Part 1The Computer Journal, 1961