@article{df131cd8653f49deaf855a93220bd0cb,

title = "Fast and backward stable computation of roots of polynomials, Part II: Backward error analysis; companion matrix and companion pencil",

abstract = "This work is a continuation of work by [J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, J. Matrix Anal. Appl., 36 (2015), pp. 942–973]. In that paper we introduced a companion QR algorithm that finds the roots of a polynomial by computing the eigenvalues of the companion matrix in O(n2) time using O(n) memory. We proved that the method is backward stable. Here we introduce, as an alternative, a companion QZ algorithm that solves a generalized eigenvalue problem for a companion pencil. More importantly, we provide an improved backward error analysis that takes advantage of the special structure of the problem. The improvement is also due, in part, to an improvement in the accuracy (in both theory and practice) of the turnover operation, which is the key component of our algorithms. We prove that for the companion QR algorithm, the backward error on the polynomial coefficients varies linearly with the norm of the polynomial{\textquoteright}s vector of coefficients. Thus, the companion QR algorithm has a smaller backward error than the unstructured QR algorithm (used by MATLAB{\textquoteright}s roots command, for example), for which the backward error on the polynomial coefficients grows quadratically with the norm of the coefficient vector. The companion QZ algorithm has the same favorable backward error as companion QR, provided that the polynomial coefficients are properly scaled.",

keywords = "Backward stability, Companion matrix, Companion pencil, Core transformation, Eigenvalue, Francis algorithm, Polynomial, QR algorithm, QZ algorithm, Root",

author = "Aurentz, {Jared L.} and Thomas Mach and Leonardo Robol and Raf Vandebril and Watkins, {David S.}",

note = "Funding Information: ∗Received by the editors October 18, 2017; accepted for publication (in revised form) by J. L. Barlow May 25, 2018; published electronically August 14, 2018. http://www.siam.org/journals/simax/39-3/M115280.html Funding: The research was partially supported by the Research Council KU Leuven, project C14/16/056 (Inverse-Free Rational Krylov Methods: Theory and Applications), by an IN-dAM/GNCS project, and by the Spanish Ministry of Economy and Competitiveness through the Severo Ochoa Programme for Centers of Excellence in R&D (SEV-2015-0554). †Instituto de Ciencias Matem{\'a}ticas, Universidad Aut{\'o}noma de Madrid, Madrid 28049, Spain (JaredAurentz@gmail.com). ‡Department of Mathematics, School of Science and Technology, Nazarbayev University, 010000 Astana, Kazakhstan (thomas.mach@nu.edu.kz). §Istituto di Scienza e Tecnologie dell Informazione “A. Faedo” (ISTI), CNR, Pisa 56127, Italy (Leonardo.Robol@isti.cnr.it). ¶Department of Computer Science, University of Leuven, KU Leuven, Leuven B-3001, Belgium (Raf.Vandebril@cs.kuleuven.be). ‖Department of Mathematics, Washington State University, Pullman, WA 99164-3113 (watkins@math.wsu.edu). Funding Information: The research was partially supported by the Research Council KU Leuven, project C14/16/056 (Inverse-Free Rational Krylov Methods: Theory and Applications), by an IN-dAM/GNCS project, and by the Spanish Ministry of Economy and Competitiveness through the Severo Ochoa Programme for Centers of Excellence in R&D (SEV-2015-0554). Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",

year = "2018",

month = jan,

day = "1",

doi = "10.1137/17M1152802",

language = "English",

volume = "39",

pages = "1245--1269",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}