Projects per year
Abstract
A standard approach to calculate the roots of a univariate polynomial is to compute the eigenvalues of an associated confederate matrix instead, such as, for instance, the companion or comrade matrix. The eigenvalues of the confederate matrix can be computed by Francis's QR algorithm. Unfortunately, even though the QR algorithm is provably backward stable, mapping the errors back to the original polynomial coefficients can still lead to huge errors. However, the latter statement assumes the use of a nonstructureexploiting QR algorithm. In [J. L. Aurentz et al., Fast and backward stable computation of roots of polynomials, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 942973] it was shown that a structureexploiting QR algorithm for companion matrices leads to a structured backward error in the companion matrix. The proof relied on decomposing the error into two parts: a part related to the recurrence coefficients of the basis (a monomial basis in that case) and a part linked to the coefficients of the original polynomial. In this article we prove that the analysis can be extended to other classes of comrade matrices. We first provide an alternative backward stability proof in the monomial basis using structured QR algorithms; our new point of view shows more explicitly how a structured, decoupled error in the confederate matrix gets mapped to the associated polynomial coefficients. This insight reveals which properties have to be preserved by a structureexploiting QR algorithm to end up with a backward stable algorithm. We will show that the previously formulated companion analysis fits into this framework, and we analyze in more detail Jacobi polynomials (comrade matrices) and Chebyshev polynomials (colleague matrices).
Original language  English 

Pages (fromto)  420442 
Number of pages  23 
Journal  Electronic Transactions on Numerical Analysis 
Volume  54 
DOIs  
Publication status  Published  2020 
MoE publication type  A1 Journal articlerefereed 
Keywords
 Backward error
 Colleague matrix
 Companion matrix
 Comrade matrix
 Linearization
 Structured QR
Fingerprint
Dive into the research topics of 'Structured backward errors in linearizations'. Together they form a unique fingerprint.Projects
 1 Active

Nonbacktracking centrality measures and beyond
Noferini, V., Barbarino, G., Wood, R. & Quintana Ponce, M.
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding