A new version of Graeffe's algorithm for finding all the roots of univariat
e complex polynomials is proposed. It is obtained from the classical algori
thm by a process analogous to renormalization of dynamical systems.
This iteration is called the renormalized Graeffe iteration. It is globally
convergent, with probability 1. All quantities involved in the computation
are bounded once the initial polynomial is given (with probability 1). Thi
s implies remark-able stability properties for the new algorithm, thus over
coming known limitations of the classical Graeffe algorithm.
If we start with a degree-d polynomial. each renormalized Graeffe iteration
costs c (d(2)) arithmetic operations, with memory c(d),
A probabilistic global complexity bound is given. The case of univariate re
al polynomials is briefly discussed.
A numerical implementation of the algorithm presented herein allows us to s
olve random polynomials of degree up to 1000. (C) 2001 Academic Press.