An implicit multishift QR-algorithm for Hermitian plus low rank matrices

Hermitian plus possibly unhermitian 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 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.