Householder Symposium edition:17 location:Zeuthen, Germany date:1-6 June 2008
In this talk we propose a new iterative method based on a structured rank factorization for computing eigenvalues of semiseparable and semiseparable plus diagonal matrices. Also
the case of higher order semiseparability ranks is included. More precisely, instead of the traditional QR-iteration, a QH-iteration will be used with Q an orthogonal matrix and H a Hessenberg-like matrix (often called lower semiseparable matrix) having the lower triangular part of semiseparable form, i.e., all submatrices that one can take out of the lower triangular part of the matrix have maximum rank p.
It will be shown that this iteration is very effective for computing the eigenvalues of structured rank matrices. Whereas the traditional QR-method applied onto semiseparable
(plus diagonal) and Hessenberg-like matrices uses similarity transformations involving 2p(n − 1) Givens transformations (when p denotes the semiseparability rank), this iteration only needs p(n − 1) iterations, which is comparable to the tridiagonal and Hessenberg situation when p equals one. It will also be 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.
Based on convergence results for a generalized QR-type iteration, it follows that this iteration inherits also an extra type of convergence behavior w.r.t. the traditional QR-method.
We indicate how the algorithm can be implemented in an implicit way, based on the Givens weight representation of the involved structured rank matrices. Numerical experiments will show the viability of the approach. It will be shown that the new approach needs less iteration steps and also gives rise to more accurate results. Moreover, the traditional QR-method for semiseparable (plus diagonal) matrices is 50% more expensive than this new iteration.