{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T10:36:16Z","timestamp":1778754976473,"version":"3.51.4"},"reference-count":58,"publisher":"American Mathematical Society (AMS)","issue":"301","license":[{"start":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T00:00:00Z","timestamp":1478736000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["Research Grant No. 26870149"],"award-info":[{"award-number":["Research Grant No. 26870149"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["267526"],"award-info":[{"award-number":["267526"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["Research Grant No. 26870149"],"award-info":[{"award-number":["Research Grant No. 26870149"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267526"],"award-info":[{"award-number":["267526"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>A common way of computing the roots of a polynomial is to find the eigenvalues of a linearization, such as the companion (when the polynomial is expressed in the monomial basis), colleague (Chebyshev basis) or comrade matrix (general orthogonal polynomial basis). For the monomial case, many studies exist on the stability of linearization-based rootfinding algorithms. By contrast, little seems to be known for other polynomial bases. This paper studies the stability of algorithms that compute the roots via linearization in nonmonomial bases, and has three goals. First we prove normwise stability when the polynomial is properly scaled and the QZ algorithm (as opposed to the more commonly used QR algorithm) is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. Second, we extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis we suggest how to choose between QR and QZ. Finally, we focus on the special case of the Chebyshev basis and finding real roots of a general function on an interval, and discuss how to compute accurate roots. The main message is that to guarantee backward stability QZ applied to a properly scaled pencil is necessary.<\/p>","DOI":"10.1090\/mcom3049","type":"journal-article","created":{"date-parts":[[2015,3,4]],"date-time":"2015-03-04T10:56:38Z","timestamp":1425466598000},"page":"2391-2425","source":"Crossref","is-referenced-by-count":18,"title":["On the stability of computing polynomial roots via confederate linearizations"],"prefix":"10.1090","volume":"85","author":[{"given":"Yuji","family":"Nakatsukasa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vanni","family":"Noferini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,11,10]]},"reference":[{"key":"1","unstructured":"M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables, Number 55, Courier Dover Publications, 1972."},{"key":"2","series-title":"Pure and Applied Mathematics, Vol. 65","volume-title":"Sobolev spaces","author":"Adams, Robert A.","year":"1975"},{"issue":"4","key":"3","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1145\/356056.356065","article-title":"Algorithm 610. A portable FORTRAN subroutine for derivatives of the psi function","volume":"9","author":"Amos, D. E.","year":"1983","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"issue":"2","key":"4","first-page":"101","article-title":"On matrices depending on parameters","volume":"26","author":"Arnol\u2032d, V. I.","year":"1971","journal-title":"Uspehi Mat. Nauk","ISSN":"https:\/\/id.crossref.org\/issn\/0042-1316","issn-type":"print"},{"key":"5","doi-asserted-by":"crossref","unstructured":"J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, Fast and backward stable computation of roots of polynomials, preprint, 2014.","DOI":"10.1137\/140983434"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s10543-013-0449-x","article-title":"Fast computation of eigenvalues of companion, comrade, and related matrices","volume":"54","author":"Aurentz, Jared L.","year":"2014","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"7","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","isbn-type":"print","volume-title":"Polynomials and linear control systems","volume":"77","author":"Barnett, Stephen","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0824718984"},{"key":"8","doi-asserted-by":"crossref","unstructured":"R. Bevilacqua, G. M. Del Corso, and L. Gemignani, A CMV\u2013based eigensolver for companion matrices, arXiv preprint arXiv:1406.2820, 2014.","DOI":"10.1137\/140978065"},{"issue":"2-3","key":"9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1023\/A:1019199917103","article-title":"Design, analysis, and implementation of a multiprecision polynomial rootfinder","volume":"23","author":"Bini, Dario Andrea","year":"2000","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00211-005-0595-4","article-title":"Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations","volume":"100","author":"Bini, Dario A.","year":"2005","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"11","doi-asserted-by":"crossref","unstructured":"D. Bini, L. Gemignani, and V. Y. Pan, Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices, SIAM J. Matrix Anal. Appl. 29 (2007), no. 2, 556\u2013585.","DOI":"10.1137\/050627563"},{"key":"12","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.cam.2013.04.037","article-title":"Solving secular and polynomial equations: a multiprecision algorithm","volume":"272","author":"Bini, Dario A.","year":"2014","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"3-4","key":"13","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF02207694","article-title":"Numerical computation of polynomial zeros by means of Aberth\u2019s method","volume":"13","author":"Bini, Dario Andrea","year":"1996","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"key":"14","unstructured":"P. Boito, Y. Eidelman, and L. Gemignani, Implicit QR for companion-like pencils, arXiv preprint 1401.5606, 2014."},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10543-014-0478-0","article-title":"Implicit QR for rank-structured matrix pencils","volume":"54","author":"Boito, P.","year":"2014","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"issue":"8","key":"16","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1016\/j.apnum.2005.09.007","article-title":"Computing real roots of a polynomial in Chebyshev series form through subdivision","volume":"56","author":"Boyd, John P.","year":"2006","journal-title":"Appl. Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0168-9274","issn-type":"print"},{"key":"17","volume-title":"A history of mathematics","author":"Boyer, Carl B.","year":"1968"},{"key":"18","isbn-type":"print","volume-title":"Introduction to approximation theory","author":"Cheney, E. W.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0821813749"},{"key":"19","series-title":"Graduate Texts in Mathematics","isbn-type":"print","volume-title":"Using algebraic geometry","volume":"185","author":"Cox, David A.","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/0387207066","edition":"2"},{"issue":"4","key":"20","doi-asserted-by":"publisher","first-page":"2181","DOI":"10.1137\/090772927","article-title":"Fiedler companion linearizations and the recovery of minimal indices","volume":"31","author":"De Ter\u00e1n, Fernando","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"21","doi-asserted-by":"crossref","unstructured":"F. De Ter\u00e1n, F. M. Dopico, and J. P\u00e9rez, Backward stability of polynomial root-finding using fiedler companion matrices, MIMS EPrint 2014.38, 2014, preprint.","DOI":"10.1093\/imanum\/dru057"},{"issue":"210","key":"22","doi-asserted-by":"publisher","first-page":"763","DOI":"10.2307\/2153450","article-title":"Polynomial roots from companion matrix eigenvalues","volume":"64","author":"Edelman, Alan","year":"1995","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"23","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s10543-012-0381-5","article-title":"Chebyshev interpolation for nonlinear eigenvalue problems","volume":"52","author":"Effenberger, Cedric","year":"2012","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"24","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0024-3795(03)00548-2","article-title":"A note on companion matrices","volume":"372","author":"Fiedler, Miroslav","year":"2003","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"25","doi-asserted-by":"publisher","first-page":"221","DOI":"10.2307\/2004418","article-title":"Calculation of Gauss quadrature rules","volume":"23","author":"Golub, Gene H.","year":"1969","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"26","unstructured":"G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 4th edition, 2012."},{"key":"27","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1093\/qmath\/12.1.61","article-title":"The colleague matrix, a Chebyshev analogue of the companion matrix","volume":"12","author":"Good, I. J.","year":"1961","journal-title":"Quart. J. Math. Oxford Ser. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5606","issn-type":"print"},{"key":"28","unstructured":"N. Hale and A. Townsend, A fast FFT-based discrete Legendre transform, IMA J. Numer. Anal., to appear."},{"key":"29","isbn-type":"print","volume-title":"Accuracy and stability of numerical algorithms","author":"Higham, Nicholas J.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0898713552"},{"key":"30","isbn-type":"print","volume-title":"Matrix analysis","author":"Horn, Roger A.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521548236","edition":"2"},{"issue":"1-2","key":"31","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0377-0427(93)E0242-E","article-title":"Perturbation of the coefficients in the recurrence relation of a class of polynomials","volume":"57","author":"Ifantis, E. K.","year":"1995","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"32","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/BF02163334","article-title":"A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration","volume":"14","author":"Jenkins, M. A.","year":"1969","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"2","key":"33","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/S0895479899365720","article-title":"Solving polynomials with small leading coefficients","volume":"26","author":"J\u00f3nsson, Gudbj\u00f6rn F.","year":"2004","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"34","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF02162564","article-title":"Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen","volume":"8","author":"Kerner, Immo O.","year":"1966","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3","key":"35","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1137\/130904508","article-title":"Fast reduction of generalized companion matrix pairs for barycentric Lagrange interpolants","volume":"34","author":"Lawrence, Piers W.","year":"2013","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3","key":"36","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s11075-013-9770-3","article-title":"Stability of rootfinding for barycentric Lagrange interpolants","volume":"65","author":"Lawrence, Piers W.","year":"2014","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"key":"37","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21752-9","volume-title":"Introduction to smooth manifolds","volume":"218","author":"Lee, John M.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0387954953"},{"key":"38","unstructured":"D. Lemonnier and P. Van Dooren, Optimal scaling of companion pencils for the QZ algorithm, in Proceedings SIAM Applied Linear Algebra Conference, 2003."},{"issue":"1-4","key":"39","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1023\/A:1025592811765","article-title":"Perturbed recurrence relations","volume":"33","author":"Leopold, Elie","year":"2003","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"issue":"2","key":"40","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0377-0427(90)90028-X","article-title":"On orthogonal polynomials with perturbed recurrence relations","volume":"30","author":"Marcell\u00e1n, F.","year":"1990","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"41","isbn-type":"print","volume-title":"Chebyshev polynomials","author":"Mason, J. C.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0849303559"},{"key":"42","unstructured":"NAG Ltd. The NAG C Library Manual, Mark 7. The Numerical Algorithms Group, 2002. \\url{http:\/\/www.nag.co.uk\/numeric\/cl\/manual\/pdf\/G05\/g05cac.pdf} and \\url{http:\/\/www.nag.co.uk\/numeric\/fl\/manual\/pdf\/G05\/g05kaf.pdf}."},{"key":"43","unstructured":"Y. Nakatsukasa, V. Noferini, and A. Townsend, Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach, The Mathematical Institute, University of Oxford, Eprints Archive 1638, 2013."},{"issue":"1","key":"44","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00211-014-0635-z","article-title":"Computing the common zeros of two bivariate functions via B\u00e9zout resultants","volume":"129","author":"Nakatsukasa, Yuji","year":"2015","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"45","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1016\/j.laa.2015.01.015","article-title":"Duality of matrix pencils, Wong chains and linearizations","volume":"471","author":"Noferini, Vanni","year":"2015","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"2","key":"46","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/S0036144595288554","article-title":"Solving a polynomial equation: some history and recent progress","volume":"39","author":"Pan, Victor Y.","year":"1997","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"1","key":"47","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1006\/jcom.1999.0532","article-title":"Approximating complex polynomial zeros: modified Weyl\u2019s quadtree construction and improved Newton\u2019s iteration","volume":"16","author":"Pan, Victor Y.","year":"2000","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"48","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF02165404","article-title":"Handbook Series Linear Algebra: Balancing a matrix for calculation of eigenvalues and eigenvectors","volume":"13","author":"Parlett, B. N.","year":"1969","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"49","series-title":"Computer Science and Scientific Computing","isbn-type":"print","volume-title":"Matrix perturbation theory","author":"Stewart, G. W.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0126702306"},{"key":"50","unstructured":"G. Szeg\u0151. Orthogonal Polynomials, AMS Colloquium Publications, 1992."},{"issue":"1-3","key":"51","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/S0024-3795(99)00063-4","article-title":"Backward error and condition of polynomial eigenvalue problems","volume":"309","author":"Tisseur, Fran\u00e7oise","year":"2000","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"52","unstructured":"A. Townsend, Private communication, 2015."},{"key":"53","isbn-type":"print","volume-title":"Approximation theory and approximation practice","author":"Trefethen, Lloyd N.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611972399"},{"key":"54","unstructured":"L. N. Trefethen et al. Chebfun Version 5. The Chebfun Development Team, 2014. http:\/\/www.maths.ox.ac.uk\/chebfun\/."},{"key":"55","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0024-3795(83)90069-1","article-title":"The eigenstructure of an arbitrary polynomial matrix: computational aspects","volume":"50","author":"Van Dooren, Paul","year":"1983","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"1","key":"56","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/100809167","article-title":"Chasing bulges or rotations? A metamorphosis of the QR-algorithm","volume":"32","author":"Vandebril, Raf","year":"2011","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"7","key":"57","doi-asserted-by":"publisher","first-page":"485","DOI":"10.2307\/2322503","article-title":"Another note on the inclusion \ud835\udc3f^{\ud835\udc5d}(\ud835\udf07)\u2282\ud835\udc3f^{\ud835\udc5e}(\ud835\udf07)","volume":"92","author":"Villani, Alfonso","year":"1985","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"key":"58","unstructured":"H. S. Wilf, Mathematics for the Physical Sciences. Courier Dover Publications, 2013."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-301\/S0025-5718-2015-03049-X\/S0025-5718-2015-03049-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-301\/S0025-5718-2015-03049-X\/S0025-5718-2015-03049-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:53:37Z","timestamp":1776797617000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-301\/S0025-5718-2015-03049-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,10]]},"references-count":58,"journal-issue":{"issue":"301","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S0025-5718-2015-03049-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom3049","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,11,10]]}}}