Abstract
A stable algorithm to compute the roots of polynomials is presented. The roots are found by computing the eigenvalues of the associated companion matrix by Francis's implicitly shifted QR algorithm. A companion matrix is an upper Hessenberg matrix that is unitaryplusrankone, that is, it is the sum of a unitary matrix and a rankone matrix. These properties are preserved by iterations of Francis's algorithm, and it is these properties that are exploited here. The matrix is represented as a product of 3n  1 Givens rotators plus the rankone part, so only O(n) storage space is required. In fact, the information about the rankone part is also encoded in the rotators, so it is not necessary to store the rankone part explicitly. Francis's algorithm implemented on this representation requires only O(n) flops per iteration and thus O(n^{2}) flops overall. The algorithm is described, normwise backward stability is proved, and an extensive set of numerical experiments is presented. The algorithm is shown to be about as accurate as the (slow) Francis QR algorithm applied to the companion matrix without exploiting the structure. It is faster than other fast methods that have been proposed, and its accuracy is comparable or better.
Original language  English 

Pages (fromto)  942973 
Number of pages  32 
Journal  SIAM Journal on Matrix Analysis and Applications 
Volume  36 
Issue number  3 
DOIs  
Publication status  Published  2015 
Externally published  Yes 
Keywords
 Companion matrix
 Eigenvalue
 Polynomial
 QR algorithm
 Root
 Rootfinding
 Rotators
ASJC Scopus subject areas
 Analysis
Fingerprint Dive into the research topics of 'Fast and backward stable computation of roots of polynomials'. Together they form a unique fingerprint.
Prizes

SIAM Outstanding Paper Prize 2017
Jared L. Aurentz (Recipient), Thomas Mach (Recipient), Raf Vandebril (Recipient) & David S. Watkins (Recipient), Jul 10 2017
Prize