Fast and backward stable computation of roots of polynomials. Part II: backward error analysis; companion matrix and companion pencil
Aurentz J. L., Mach T., Robol L., Vandebril R., Watkins D. S.
Polynomial Backward stability QZ algorithm Root QR algorithm FOS: Mathematics Eigenvalue 15A18 Mathematics - Numerical Analysis Core transformation Analysis Francis algorithm 65F15 Numerical Analysis (math.NA) Companion matrix Companion pencil 65H17 65H04
This work is a continuation of work by J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, J. Matrix Anal. Appl., 36 (2015), pp. 942--973. In that paper we introduced a companion QR algorithm that finds the roots of a polynomial by computing the eigenvalues of the companion matrix in O(n^2) time using O(n) memory. We proved that the method is backward stable. Here we introduce, as an alternative, a companion QZ algorithm that solves a generalized eigenvalue problem for a companion pencil. More importantly, we provide an improved backward error analysis that takes advantage of the special structure of the problem. The improvement is also due, in part, to an improvement in the accuracy (in both theory and practice) of the turnover operation, which is the key component of our algorithms. We prove that for the companion QR algorithm, the backward error on the polynomial coefficients varies linearly with the norm of the polynomial's vector of coefficients. Thus, the companion QR lgorithm has a smaller backward error than the unstructured QR algorithm (used by MATLAB's roots command, for example), for which the backward error on the polynomial coefficients grows quadratically with the norm of the coefficient vector. The companion QZ algorithm has the same favorable backward error as companion QR, provided that the polynomial coefficients are properly scaled.
Source: SIAM journal on matrix analysis and applications (Print) 39 (2018): 1245–1269. doi:10.1137/17M1152802
Publisher: Society for Industrial and Applied Mathematics ,, Philadelphia, Pa. , Stati Uniti d'America
[2] J. Aurentz, R. Vandebril, and D. S. Watkins, Fast computation of the zeros of a polynomial via factorization of the companion matrix, SIAM Journal on Scienti c Computing, 35 (2013), pp. A255{A269.
[3] , Fast computation of eigenvalues of companion, comrade, and related matrices, BIT, 54 (2014), pp. 7{30.
[4] J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, Fast and backward stable computation of roots of polynomials, SIAM Journal on Matrix Analysis and Applications, 36 (2015), pp. 942{973.
[5] , Fast and stable unitary QR algorithm, Electronic Transactions on Numerical Analysis, 44 (2015), pp. 327{341. Submitted for publication.
[6] J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, A note on companion pencils, Contemporary Mathematics, 658 (2016), pp. 91{101.
[7] R. Bevilacqua, G. M. Del Corso, and L. Gemignani, A CMV{based eigensolver for companion matrices, SIAM Journal on Matrix Analysis and Applications, 36 (2015), pp. 1046{ 1068.
[8] D. A. Bini, Numerical computation of polynomial zeros by means of Aberth's algorithm, Numerical Algorithms, 13 (1996), pp. 179{200.
[9] D. A. Bini, P. Boito, Y. Eidelman, L. Gemignani, and I. Gohberg, A fast implicit QR eigenvalue algorithm for companion matrices, Linear Algebra and its Applications, 432 (2010), pp. 2006{2031.
[10] D. A. Bini, F. Daddi, and L. Gemignani, On the shifted QR iteration applied to companion matrices, Electronic Transactions on Numerical Analysis, 18 (2004), pp. 137{152.
[11] D. A. Bini, Y. Eidelman, L. Gemignani, and I. Gohberg, Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices, SIAM Journal on Matrix Analysis and Applications, 29 (2007), pp. 566{585.
[12] D. A. Bini and G. Fiorentino, Design, analysis, and implementation of a multiprecision polynomial root nder, Numerical Algorithms, 23 (2000), pp. 127{173.
[13] D. A. Bini, G. Fiorentino, L. Gemignani, and B. Meini, E ective fast algorithms for polynomial spectral factorization, Numerical Algorithms, 34 (2003), pp. 217{227.
[14] P. Boito, Y. Eidelman, and L. Gemignani, Implicit QR for companion-like pencils, Mathematics of Computation, 85 (2016), pp. 1753{1774.
[15] P. Boito, Y. Eidelman, and L. Gemignani, A real qz algorithm for structured companion pencils. https://arxiv.org/abs/1608.05395, 2016.
[16] P. Boito, Y. Eidelman, L. Gemignani, and I. Gohberg, Implicit QR with compression, Indagationes Mathematicae, 23 (2012), pp. 733{761.
[17] A. Bottcher and M. Halwass, Wiener{Hopf and spectral factorization of real polynomials by Newton's method, Linear Algebra and its Applications, 438 (2013), pp. 4760{4805.
[18] S. Chandrasekaran, M. Gu, J. Xia, and J. Zhu, A fast QR algorithm for companion matrices, Operator Theory: Advances and Applications, 179 (2007), pp. 111{143.
[19] F. de Teran, F. M. Dopico, J. Perez, and a. a. check, Backward stability of polynomial root- nding using edler companion matrices, IMA Journal of Numerical Analysis, (2014).
[20] S. Delvaux, K. Frederix, and M. Van Barel, An algorithm for computing the eigenvalues of block companion matrices, Numerical Algorithms, 62 (2012), pp. 261{287.
[21] B. Eastman, I.-J. Kim, B. Shader, and K. Vander Meulen, Companion matrix patterns, Linear Algebra and its Applications, 463 (2014), pp. 255{272.
[22] A. Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Mathematics of Computation, 64 (1995), pp. 763{776.
[23] Y. Eidelman, I. C. Gohberg, and I. Haimovici, Separable Type Representations of Matrices and Fast Algorithms { Volume 2: Eigenvalue Method, no. 235 in Operator Theory: Advances and Applications, Springer Basel, 2013.
[24] M. Fiedler, A note on companion matrices, Linear Algebra and its Applications, 372 (2003), pp. 325{331.
[25] M. A. Jenkins and J. F. Traub, Principles for testing polynomial zero nding programs, ACM Transactions on Mathematical Software, 1 (1975), pp. 26{34.
[26] G. F. Jonsson and S. Vavasis, Solving polynomials with small leading coe cients, SIAM Journal on Matrix Analysis and Applications, 26 (2004), pp. 400{414.
[27] D. Kressner, Numerical methods for general and structured eigenvalue problems, vol. 46 of LNCSE, Springer, 2005.
[28] T. Mach and R. Vandebril, On de ations in extended QR algorithms, SIAM Journal on Matrix Analysis and Applications, 35 (2014), pp. 559{579.
[29] D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, Vector spaces of linearizations for matrix polynomials, SIAM Journal on Matrix Analysis and Applications, 28 (2006), pp. 971{1004.
[30] J. M. McNamee, A bibliography on roots of polynomials, Journal of Computational and Applied Mathematics, 47 (1993), pp. 391{394.
[31] C. B. Moler, Cleve's corner: Roots - of polynomials, that is, The Mathworks Newsletter, 5 (1991), pp. 8{9.
[32] C. B. Moler and G. W. Stewart, An algorithm for generalized matrix eigenvalue problems, SIAM Journal on Numerical Analysis, 10 (1973), pp. 241{256.
[33] MPFUN - multiprecision software. http://www.netlib.org/mpfun/, 2005.
[34] G. W. Stewart, On the adjugate matrix, Linear Algebra and its Applications, 283 (1998), pp. 151{164.
[35] M. Van Barel, R. Vandebril, P. Van Dooren, and K. Frederix, Implicit double shift QR-algorithm for companion matrices, Numerische Mathematik, 116 (2010), pp. 177{212.
[36] P. Van Dooren and P. Dewilde, The eigenstructure of an arbitrary polynomial matrix: Computational aspects, Linear Algebra and its Applications, 50 (1983), pp. 545{579.
[37] R. Vandebril, Chasing bulges or rotations? A metamorphosis of the QR-algorithm, SIAM Journal on Matrix Analysis and Applications, 32 (2011), pp. 217{247.
[38] R. Vandebril and D. S. Watkins, An extension of the QZ algorithm beyond the Hessenbergupper triangular pencil, Electronic Transactions on Numerical Analysis, 40 (2012), pp. 17{ 35.
[39] , A generalization of the multishift QR algorithm, SIAM Journal on Matrix Analysis and Applications, 33 (2012), pp. 759{779.
[40] D. S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM, Philadelphia, USA, 2007.
[41] , Fundamentals of Matrix Computations, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, third ed., 2010.
[42] P. Zhlobich, Di erential qd algorithm with shifts for rank-structured matrices, SIAM Journal on Matrix Analysis and Applications, 33 (2012).
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:390115,
title = {Fast and backward stable computation of roots of polynomials. Part II: backward error analysis; companion matrix and companion pencil},
author = {Aurentz J. L. and Mach T. and Robol L. and Vandebril R. and Watkins D. S.},
publisher = {Society for Industrial and Applied Mathematics ,, Philadelphia, Pa. , Stati Uniti d'America},
doi = {10.1137/17m1152802 and 10.48550/arxiv.1611.02435},
journal = {SIAM journal on matrix analysis and applications (Print)},
volume = {39},
pages = {1245–1269},
year = {2018}
}
0000-0002-6545-1748ISTI Repository
DOI
10.1137/17m1152802
10.48550/arxiv.1611.02435
arXiv.org e-Print Archive
SIAM Journal on Matrix Analysis and Applications
epubs.siam.org