Roots of Polynomials: on twisted QR methods for companion matrices and pencils

Jared L. Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. Watkins

Research output: Contribution to journalArticle

115 Downloads (Pure)

Abstract

Two generalizations of the companion QR algorithm by J.L. Aurentz, T. Mach, R. Vandebril, and D.S. Watkins, SIAM Journal on Matrix Analysis and Applications, 36(3): 942--973, 2015, to compute the roots of a polynomial are presented. First, we will show how the fast and backward stable QR algorithm for companion matrices can be generalized to a QZ algorithm for companion pencils. Companion pencils admit a greater flexibility in scaling the polynomial and distributing the matrix coefficients over both matrices in the pencil. This allows for an enhanced stability for polynomials with largely varying coefficients. Second, we will generalize the pencil approach further to a twisted QZ algorithm. Whereas in the classical QZ case Krylov spaces govern the convergence, the convergence of the twisted case is determined by a rational Krylov space. A backward error analysis to map the error back to the original pencil and to the polynomial coefficients shows that in both cases the error scales quadratically with the input. An extensive set of numerical experiments supports the theoretical backward error, confirms the numerical stability and shows that the computing time depends quadratically on the problem size.
Original languageEnglish
JournalarXiv
Volume1611
Issue number02435
Publication statusPublished - Nov 8 2016

Keywords

  • polynomial rootfinding
  • companion matrix
  • companion pencil
  • eigenvalue
  • QR algorithm
  • QZ algorithm
  • rotators
  • core transformation
  • backward stability
  • Root
  • AMS subject classification: 65F15, 65H17, 15A18, 65H04

ASJC Scopus subject areas

  • Numerical Analysis

Fingerprint Dive into the research topics of 'Roots of Polynomials: on twisted QR methods for companion matrices and pencils'. Together they form a unique fingerprint.

  • KU Leuven

    Thomas Mach (Visiting researcher)

    Oct 10 2016Oct 14 2016

    Activity: Visiting typesVisiting an external research institution

Cite this