Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

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

Abstract:

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.
References
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: vnofer@essex.ac.uk
  • 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: javier.perezalvaro@kuleuven.be
  • 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: https://doi.org/10.1090/mcom/3149
  • MathSciNet review: 3626535