Roots of Polynomials: on twisted QR methods for companion matrices and pencils
Loading...
Date
2016-11-08
Authors
Aurentz, Jared L.
Mach, Thomas
Robol, Leonardo
Vandebril, Raf
Watkins, David S.
Journal Title
Journal ISSN
Volume Title
Publisher
arXiv
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.
Description
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
Citation
Aurentz, J. L., Mach, T., Robol, L., Vandebril, R., & Watkins, D. S. (2016). Roots of Polynomials: on twisted QR methods for companion matrices and pencils. arXiv, 1611(02435).