Structured backward errors in linearizations

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorNoferini, Vanni
dc.contributor.authorRobol, Leonardo
dc.contributor.authorVandebril, Raf
dc.contributor.departmentStatistics and Mathematical Data Science
dc.contributor.departmentUniversity of Pisa
dc.contributor.departmentKU Leuven
dc.contributor.departmentDepartment of Mathematics and Systems Analysisen
dc.date.accessioned2021-08-04T06:41:14Z
dc.date.available2021-08-04T06:41:14Z
dc.date.issued2020
dc.descriptionFunding Information: ∗Received December 19, 2019. Accepted April 15, 2021. Published online on June 7, 2021. Recommended by Qiang Ye. The work of Vanni Noferini was supported by an Academy of Finland grant (Suomen Akatemian päätös 331240); the work of Leonardo Robol was supported by an INdAM/GNCS research grant “Metodi low-rank per problemi di algebra lineare con struttura data-sparse”. †Department of Mathematics and Systems Analysis, Aalto University, PL 11000, 00076 Aalto, Finland (vanni.noferini@aalto.fi). ‡Department of Mathematics, University of Pisa, Largo Bruno Pontecorvo 5, 56127 Pisa, Italy (leonardo.robol@unipi.it). The author is a member of the INdAM research group GNCS. §Institute of Information Science and Technologies “A. Faedo”, ISTI-CNR, Pisa, Italy (leonardo.robol@isti.cnr.it). ¶Department of Computer Science, KU Leuven, Celestijnenlaan 200A, 3001 Heverlee, Belgium (raf.vandebril@cs.kuleuven.be). Publisher Copyright: Copyright © 2021, Kent State University.
dc.description.abstractA 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 non-structure-exploiting 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. 942-973] it was shown that a structure-exploiting 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 structure-exploiting 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).en
dc.description.versionPeer revieweden
dc.format.extent23
dc.format.extent420-442
dc.format.mimetypeapplication/pdf
dc.identifier.citationNoferini , V , Robol , L & Vandebril , R 2020 , ' Structured backward errors in linearizations ' , Electronic Transactions on Numerical Analysis , vol. 54 , pp. 420-442 . https://doi.org/10.1553/ETNA_VOL54S420en
dc.identifier.doi10.1553/ETNA_VOL54S420
dc.identifier.issn1068-9613
dc.identifier.issn1097-4067
dc.identifier.otherPURE UUID: 61b903aa-2b19-44b2-bcfd-8bf8d3687a03
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/61b903aa-2b19-44b2-bcfd-8bf8d3687a03
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85108594916&partnerID=8YFLogxK
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/65515241/Structured_backward_errors_in_linearizations.pp420_442.pdf
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/108883
dc.identifier.urnURN:NBN:fi:aalto-202108048127
dc.language.isoenen
dc.publisherKent State University
dc.relation.ispartofseriesElectronic Transactions on Numerical Analysisen
dc.relation.ispartofseriesVolume 54en
dc.rightsopenAccessen
dc.subject.keywordBackward error
dc.subject.keywordColleague matrix
dc.subject.keywordCompanion matrix
dc.subject.keywordComrade matrix
dc.subject.keywordLinearization
dc.subject.keywordStructured QR
dc.titleStructured backward errors in linearizationsen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionpublishedVersion
Files