Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Implicit QR for companion-like pencils

Authors: P. Boito, Y. Eidelman and L. Gemignani
Journal: Math. Comp. 85 (2016), 1753-1774
MSC (2010): Primary 65F15, 65H17
Published electronically: August 31, 2015
MathSciNet review: 3471106
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A fast implicit QR algorithm for eigenvalue computation of low rank corrections of unitary matrices is adjusted to work with matrix pencils arising from polynomial zero-finding problems. The modified QZ algorithm computes the generalized eigenvalues of certain $ N\times N$ rank structured matrix pencils using $ O(N^2)$ flops and $ O(N)$ memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.

References [Enhancements On Off] (What's this?)

  • [1] V. I. Arnold, Matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101-114 (Russian). MR 0301242 (46 #400)
  • [2] David Day and Louis Romero, Roots of polynomials expressed in terms of orthogonal polynomials, SIAM J. Numer. Anal. 43 (2005), no. 5, 1969-1987 (electronic). MR 2192327 (2006h:65070),
  • [3] C. de Boor, An empty exercise, in ACM SIGNUM Newsletter, vol. 25 (4), Oct. 1990, pp. 2-6.
  • [4] Alan Edelman, Erik Elmroth, and Bo Kågström, A geometric approach to perturbation theory of matrices and matrix pencils. I. Versal deformations, SIAM J. Matrix Anal. Appl. 18 (1997), no. 3, 653-692. MR 1453545 (99e:58021),
  • [5] Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763-776. MR 1262279 (95f:65075),
  • [6] Yuli Eidelman, Israel Gohberg, and Luca Gemignani, On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms, Linear Algebra Appl. 420 (2007), no. 1, 86-101. MR 2277631 (2007j:15011),
  • [7] Yuli Eidelman, Luca Gemignani, and Israel Gohberg, Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations, Numer. Algorithms 47 (2008), no. 3, 253-273. MR 2385737 (2009a:65090),
  • [8] Y. Eidelman and I. Gohberg, On a new class of structured matrices, Integral Equations Operator Theory 34 (1999), no. 3, 293-324. MR 1689391 (2000e:15020),
  • [9] Yuli Eidelman, Israel Gohberg, and Iulian Haimovici, Separable Type Representations of Matrices and Fast Algorithms. Vol. 1: Basics. Completion Problems. Multiplication and Inversion Algorithms, Operator Theory: Advances and Applications, vol. 234, Birkhäuser/Springer, Basel, 2014. MR 3137083
  • [10] Yuli Eidelman, Israel Gohberg, and Iulian Haimovici, Separable Type Representations of Matrices and Fast Algorithms. Vol. 2: Eigenvalue Method, Operator Theory: Advances and Applications, vol. 235, Birkhäuser/Springer Basel AG, Basel, 2014. MR 3136431
  • [11] Miroslav Fiedler and Thomas L. Markham, Completing a matrix when certain entries of its inverse are specified, Linear Algebra Appl. 74 (1986), 225-237. MR 822149 (87g:15005),
  • [12] Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
  • [13] Gudbjörn F. Jónsson and Stephen Vavasis, Solving polynomials with small leading coefficients, SIAM J. Matrix Anal. Appl. 26 (2004/05), no. 2, 400-414. MR 2124155 (2005k:12010),
  • [14] D. Lemonnier, P. Van Dooren, Optimal Scaling of Companion Pencils for the QZ-Algorithm, SIAM Conference on Applied Linear Algebra, Williamsburg, VA. 2003.
  • [15] Damien Lemonnier and Paul Van Dooren, Balancing regular matrix pencils, SIAM J. Matrix Anal. Appl. 28 (2006), no. 1, 253-263. MR 2218952 (2007a:15014),
  • [16] B. G. Mertzios, Leverrier's algorithm for singular systems, IEEE Trans. Automat. Control 29 (1984), no. 7, 652-653. MR 748757,
  • [17] M. Sebek, H. Kwakernaak, D. Henrion and S. Pejchova, Recent progress in polynomial methods and Polynomial Toolbox for Matlab version 2.0, Proc. of the 37th IEEE Conference on Decision and Control, 1998, vol. 4, pp. 3661-3668.
  • [18] Kim-Chuan Toh and Lloyd N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), no. 3, 403-425. MR 1313152 (95m:65085),
  • [19] Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545-579. MR 699575 (84j:15009),
  • [20] David S. Watkins, Fundamentals of Matrix Computations, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2002. Second editon. MR 1899577 (2003a:65002)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F15, 65H17

Retrieve articles in all journals with MSC (2010): 65F15, 65H17

Additional Information

P. Boito
Affiliation: XLIM–DMI, UMR CNRS 7252, Faculté des Sciences et Techniques, 123 av. A. Thomas, 87060 Limoges, France

Y. Eidelman
Affiliation: School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel-Aviv University, Ramat-Aviv, 69978, Israel

L. Gemignani
Affiliation: Dipartimento di Informatica, Università di Pisa, Largo Bruno Pontecorvo 3, 56127 Pisa, Italy

Received by editor(s): January 29, 2014
Received by editor(s) in revised form: October 8, 2014, and December 6, 2014
Published electronically: August 31, 2015
Additional Notes: This work was partially supported by MIUR, grant number 20083KLJEZ
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society