Preprint A59/2001
On the Geometry of Graeffe Iteration

Jorge P. Zubelli | Malajovich, Gregorio

**Keywords: **
graeffe method | geometric computational mathematics | root-finding

A new version of the Graeffe's algorithms for finding all
the roots of univariate complex polynomials is proposed.
It is obtained from the classical algorithm by a process
analogous to renormalization of dynamical systems.
This iteration is called 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). This implies
remarkable stability properties for the new algorithm,
thus overcoming known limitations of the classical
Graeffe algorithm.
If we start with a degree-$d$ polynomial, each renormalized
Graeffe iteration costs O(d^2) arithmetic operations, with
memory O(d).
A probabilistic global complexity bound is given. The case
of univariate real polynomials is briefly discussed.
A numerical implementation of the algorithm presented herein
allowed us to solve random polynomials of degree up to 1000.