Title: An implicit multishift QR-algorithm for Hermitian plus low rank matrices
Authors: Vandebril, Raf ×
Del Corso, Gianna M. #
Issue Date: Jul-2010
Publisher: Society for Industrial and Applied Mathematics
Series Title: SIAM Journal on Scientific Computing vol:32 issue:4 pages: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.
ISSN: 1064-8275
Publication status: published
KU Leuven publication type: IT
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
Vandebril_DelCorso_2010.pdfOA article Published 431KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science