Implicit double shift QR-algorithm for companion matrices

被引：28
作者：
Van Barel, Marc [1 ]
Vandebril, Raf [1 ]
Van Dooren, Paul [2 ]
Frederix, Katrijn [1 ]
机构：
[1] Katholieke Univ Leuven, Dept Comp Sci, B-3001 Heverlee, Belgium
[2] Catholic Univ Louvain, Dept Engn Math, B-1348 Louvain, Belgium
来源：
NUMERISCHE MATHEMATIK | 2010年 / 116卷 / 02期
关键词：
EIGENVALUE ALGORITHMS;
D O I：
10.1007/s00211-010-0302-y
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper an implicit (double) shifted QR-method for computing the eigenvalues of companion and fellow matrices will be presented. Companion and fellow matrices are Hessenberg matrices, that can be decomposed into the sum of a unitary and a rank 1 matrix. The Hessenberg, the unitary as well as the rank 1 structures are preserved under a step of the QR-method. This makes these matrices suitable for the design of a fast QR-method. Several techniques already exist for performing a QR-step. The implementation of these methods is highly dependent on the representation used. Unfortunately for most of the methods compression is needed since one is not able to maintain all three, unitary, Hessenberg and rank 1 structures. In this manuscript an implicit algorithm will be designed for performing a step of the QR-method on the companion or fellow matrix based on a new representation consisting of Givens transformations. Moreover, no compression is needed as the specific representation of the involved matrices is maintained. Finally, also a double shift version of the implicit method is presented.
引用
收藏
页码：177 / 212
页数：36
相关论文
共 21 条
[1]  
BARNETT S, 1983, MONOGRAPHS TXB PURE
[2]   On computing Givens rotations reliably and efficiently [J].
Bindel, D ;
Demmel, J ;
Kahan, W ;
Marques, O .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2002, 28 (02) :206-238
[3]  
Bindel David., 2005, A fast and stable nonsymmetric eigensolver for certain structured matrices
[4]   Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices [J].
Bini, D. A. ;
Eidelman, Y. ;
Gemignani, L. ;
Gohberg, I. .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2007, 29 (02) :566-585
[5]   A fast implicit QR eigenvalue algorithm for companion matrices [J].
Bini, D. A. ;
Boito, P. ;
Eidelman, Y. ;
Gemignani, L. ;
Gohberg, I. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (08) :2006-2031
[6]  
Bini DA, 2004, ELECTRON T NUMER ANA, V18, P137
[7]   Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations [J].
Bini, DA ;
Gemignani, L ;
Pan, VY .
NUMERISCHE MATHEMATIK, 2005, 100 (03) :373-408
[8]  
Chandrasekaran S, 2008, OPER THEORY ADV APPL, V179, P111
[9]  
DELVAUX S, 2006, TW459 KATH U LEUV DE
[10]  
DELVAUX S, 2008, TW538 KATH U LEUV DE
123