Implicit QR for companion-like pencils

Boito, P.; Eidelman, Y.; Gemignani, L.

doi:10.1090/mcom/3020

Implicit QR for companion-like pencils
HTML articles powered by AMS MathViewer

by P. Boito, Y. Eidelman and L. Gemignani;

Math. Comp. 85 (2016), 1753-1774

DOI: https://doi.org/10.1090/mcom/3020

Published electronically: August 31, 2015

PDF | Request permission

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

V. I. Arnol′d, On matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101–114 (Russian). MR 301242
David Day and Louis Romero, Roots of polynomials expressed in terms of orthogonal polynomials, SIAM J. Numer. Anal. 43 (2005), no. 5, 1969–1987. MR 2192327, DOI 10.1137/040609847
C. de Boor, An empty exercise, in ACM SIGNUM Newsletter, vol. 25 (4), Oct. 1990, pp. 2–6.
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, DOI 10.1137/S0895479895284634
Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763–776. MR 1262279, DOI 10.1090/S0025-5718-1995-1262279-2
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, DOI 10.1016/j.laa.2006.06.028
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, DOI 10.1007/s11075-008-9172-0
Y. Eidelman and I. Gohberg, On a new class of structured matrices, Integral Equations Operator Theory 34 (1999), no. 3, 293–324. MR 1689391, DOI 10.1007/BF01300581
Yuli Eidelman, Israel Gohberg, and Iulian Haimovici, Separable type representations of matrices and fast algorithms. Vol. 1, Operator Theory: Advances and Applications, vol. 234, Birkhäuser/Springer, Basel, 2014. Basics. Completion problems. Multiplication and inversion algorithms. MR 3137083
Yuli Eidelman, Israel Gohberg, and Iulian Haimovici, Separable type representations of matrices and fast algorithms. Vol. 2, Operator Theory: Advances and Applications, vol. 235, Birkhäuser/Springer Basel AG, Basel, 2014. Eigenvalue method. MR 3136431
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, DOI 10.1016/0024-3795(86)90125-4
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
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, DOI 10.1137/S0895479899365720
D. Lemonnier, P. Van Dooren, Optimal Scaling of Companion Pencils for the QZ-Algorithm, SIAM Conference on Applied Linear Algebra, Williamsburg, VA. 2003.
Damien Lemonnier and Paul Van Dooren, Balancing regular matrix pencils, SIAM J. Matrix Anal. Appl. 28 (2006), no. 1, 253–263. MR 2218952, DOI 10.1137/S0895479804440931
B. G. Mertzios, Leverrier’s algorithm for singular systems, IEEE Trans. Automat. Control 29 (1984), no. 7, 652–653. MR 748757, DOI 10.1109/TAC.1984.1103602
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.
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, DOI 10.1007/s002110050069
Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545–579. MR 699575, DOI 10.1016/0024-3795(83)90069-1
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, DOI 10.1002/0471249718