Volume 33, pp. 126-150, 2008-2009.

A new iteration for computing the eigenvalues of semiseparable (plus diagonal) matrices

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi

Abstract

This paper proposes a new type of iteration for computing eigenvalues of semiseparable (plus diagonal) matrices based on a structured-rank factorization. Remarks on higher order semiseparability ranks are also made. More precisely, instead of the traditional $QR$ iteration, a $QH$ iteration is used. The $QH$ factorization is characterized by a unitary matrix $Q$ and a Hessenberg-like matrix $H$ in which the lower triangular part is semiseparable (often called a lower semiseparable matrix). The $Q$ factor of this factorization determines the similarity transformation of the $QH$ method. It is shown that this iteration is extremely useful for computing the eigenvalues of structured-rank matrices. Whereas the traditional $QR$ method applied to semiseparable (plus diagonal) and Hessenberg-like matrices uses similarity transformations involving $2p(n-1)$ Givens transformations (where $p$ denotes the semiseparability rank), the $QH$ iteration only needs $p(n-1)$ Givens transformations, which is comparable to the generalized Hessenberg (symmetric band) situation having $p$ subdiagonals. It is also shown that this method can in some sense be interpreted as an extension of the traditional $QR$ method for Hessenberg matrices, i.e., the traditional case also fits into this framework. It is also shown that this iteration exhibits an extra type of convergence behavior compared to the traditional $QR$ method. The algorithm is implemented in an implicit way, based on the Givens-weight representation of the structured rank matrices. Numerical experiments show the viability of this approach. The new approach yields better complexity and more accurate results than the traditional $QR$ method.

Full Text (PDF) [289 KB], BibTeX

Key words

$QH$ algorithm, structured rank matrices, implicit computations, eigenvalue, $QR$ algorithm, rational $QR$ iteration

AMS subject classifications

65F05

Links to the cited ETNA articles

[4]	Vol. 18 (2004), pp. 137-152 Dario A. Bini, Francesco Daddi, and Luca Gemignani: On the shifted QR iteration applied to companion matrices