Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?
HTML articles powered by AMS MathViewer

by Vanni Noferini and Javier Pérez PDF
Math. Comp. 86 (2017), 1741-1767 Request permission


Computing the roots of a scalar polynomial, or the eigenvalues of a matrix polynomial, expressed in the Chebyshev basis $\{ T_k(x)\}$ is a fundamental problem that arises in many applications. In this work, we analyze the backward stability of the polynomial rootfinding problem solved with colleague matrices. In other words, given a scalar polynomial $p(x)$ or a matrix polynomial $P(x)$ expressed in the Chebyshev basis, the question is to determine whether or not the whole set of computed eigenvalues of the colleague matrix, obtained with a backward stable algorithm, like the QR algorithm, are the set of roots of a nearby polynomial. In order to do so, we derive a first order backward error analysis of the polynomial rootfinding algorithm using colleague matrices adapting the geometric arguments in [A. Edelman and H. Murakami, Polynomial roots for companion matrix eigenvalues, Math. Comp. 210, 763–776, 1995] to the Chebyshev basis. We show that, if the absolute value of the coefficients of $p(x)$ (respectively, the norm of the coefficients of $P(x)$) are bounded by a moderate number, computing the roots of $p(x)$ (respectively, the eigenvalues of $P(x)$) via the eigenvalues of its colleague matrix using a backward stable eigenvalue algorithm is backward stable. This backward error analysis also expands on the very recent work [Y. Nakatsukasa and V. Noferini, On the stability of computing polynomial roots via confederate linearizations, Math. Comp. 85 (2016), no. 301, 2391–2425] that already showed that this algorithm is not backward normwise stable if the coefficients of the polynomial $p(x)$ do not have moderate norms.
Similar Articles
Additional Information
  • Vanni Noferini
  • Affiliation: School of Mathematics, The University of Manchester, Manchester, England, M13 9PL
  • Address at time of publication: Department of Mathematical Sciences, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, United Kingdom
  • MR Author ID: 936379
  • Email:
  • Javier Pérez
  • Affiliation: School of Mathematics, The University of Manchester, Manchester, England, M13 9PL
  • Address at time of publication: Department of Rehabilitation Sciences, Biomedical Sciences Group, KU Leuven – University, Tervuursevest 101 – box 1500, 3001 Leuven, Belgium
  • Email:
  • Received by editor(s): April 5, 2015
  • Received by editor(s) in revised form: January 13, 2016, and February 9, 2016
  • Published electronically: December 7, 2016
  • Additional Notes: The work of the first-named author was supported by European Research Council Advanced Grant MATFUN (267526)
    The work of the second-named author was supported by Engineering and Physical Sciences Research Council grant EP/I005293.
  • © Copyright 2016 American Mathematical Society
  • Journal: Math. Comp. 86 (2017), 1741-1767
  • MSC (2010): Primary 65H04, 65H17, 65F15, 65G50
  • DOI:
  • MathSciNet review: 3626535