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 O(n) floating point operations instead of the standard O(n(2)) operations needed for performing a QR-step on a Hessenberg matrix. The algorithm is based on a suitable 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.
|Autori:||VANDEBRIL R; DEL CORSO G|
|Titolo:||An implicit multishift QR-algorithm for symmetric plus low rank matrices|
|Anno del prodotto:||2010|
|Digital Object Identifier (DOI):||10.1137/090754522|
|Appare nelle tipologie:||1.1 Articolo in rivista|