User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Implicit double shift QR-algorithm for companion matrices

Primary tabs

Van Barel, Marc Vandebril, Raf Van Dooren, Paul [UCL] Frederix, Katrijn

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2010
Language Anglais
Journal information "Numerische Mathematik" - Vol. 116, no. 2, p. 177-212 (2010)
Peer reviewed yes
Publisher Springer (New York)
issn 0029-599X
e-issn 0945-3245
Publication status Publié
Affiliation UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Links
  1. Barnett, S.: Polynomials and linear control systems. Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York (1983)
  2. Bindel, D., Chandrasekaran, S., Demmel, J.W., Garmire, D., Gu, M.: A fast and stable nonsymmetric eigensolver for certain structured matrices. Technical report, Department of Computer Science, University of California, Berkeley, California, USA, May (2005)
  3. Bindel D., Demmel J.W., Kahan W., Marques O.A.: On computing Givens rotations reliably and efficiently. ACM Trans. Math. Softw. 28(2), 206–238 (2002)
  4. Bini, D.A., Boito, P., Eidelman, Y., Gemignani, L., Gohberg, I.C.: A fast QR eigenvalue method for a class of structured matrices. Linear Algebra Appl. (2009, accepted). doi: 10.1016/j.laa.2009.08.003
  5. Bini D.A., Daddi F., Gemignani L.: On the shifted QR iteration applied to companion matrices. Electron. Trans. Numer. Anal. 18, 137–152 (2004)
  6. Bini D.A., Eidelman Y., Gemignani L., Gohberg I.C.: Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices. SIAM J. Matrix Anal. Appl. 29(2), 566–585 (2007)
  7. Bini D.A., Gemignani L., Pan V.Y.: Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations. Numer. Math. 100(3), 373–408 (2005)
  8. Chandrasekaran S., Gu M., Xia J., Zhu J.: A fast QR algorithm for companion matrices. Oper. Theory Adv. Appl. 179, 111–143 (2007)
  9. Delvaux, S., Frederix, K., Van Barel, M.: An algorithm for computing the eigenvalues of block companion matrices. Technical Report TW538, Department of Computer Science, Katholieke Universiteit Leuven, April (2008)
  10. Delvaux, S., Van Barel, M.: The explicit QR-algorithm for rank structured matrices. Technical Report TW459, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3000 Leuven (Heverlee), Belgium, May (2006)
  11. Delvaux S., Van Barel M.: A QR-based solver for rank structured matrices. SIAM J. Matrix Anal. Appl. 30(2), 464–490 (2008)
  12. Edelman Alan, Murakami H., Polynomial roots from companion matrix eigenvalues, 10.1090/s0025-5718-1995-1262279-2
  13. Eidelman Y., Gohberg I.C.: On a new class of structured matrices. Integral Equ. Oper. Theory 34, 293–324 (1999)
  14. Eidelman Y., Gohberg I.C., Olshevsky V.: The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order. Linear Algebra Appl. 404, 305–324 (2005)
  15. Fiedler M., Markham T.L.: Completing a matrix when certain entries of its inverse are specified. Linear Algebra Appl. 74, 225–237 (1986)
  16. Golub G.H., Van Loan C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
  17. Vandebril R., Van Barel M., Golub G.H., Mastronardi N.: A bibliography on semiseparable matrices. Calcolo 42(3–4), 249–270 (2005)
  18. Vandebril R., Van Barel M., Mastronardi N.: An implicit QR-algorithm for symmetric semiseparable matrices. Numer. Linear Algebra Appl. 12(7), 625–658 (2005)
  19. Vandebril R., Van Barel M., Mastronardi N.: A note on the representation and definition of semiseparable matrices. Numer. Linear Algebra Appl. 12(8), 839–858 (2005)
  20. Vandebril R., Van Barel M., Mastronardi N.: Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods, vol. II. Johns Hopkins University Press, Baltimore (2008)
  21. Vandebril R., Van Barel M., Mastronardi N.: A parallel QR-factorization/solver of structured rank matrices. Electron. Trans. Numer. Anal. 30, 144–167 (2008)
Bibliographic reference Van Barel, Marc ; Vandebril, Raf ; Van Dooren, Paul ; Frederix, Katrijn. Implicit double shift QR-algorithm for companion matrices. In: Numerische Mathematik, Vol. 116, no. 2, p. 177-212 (2010)
Permanent URL http://hdl.handle.net/2078.1/33663