Tangent Graeffe iteration (Q5952132)

The authors present a version of renormalized Graeffe's algorithm, also considered in their previous paper [J. Complexity 17, No. 3, 541-573 (2001; reviewed above)], for solving real and complex univariate polynomials. Recall that Graeffe iteration maps a degree \(d\) polynomial \(f(x)\) into the degree \(d\) polynomial \[ Gf(x)=(-1)^d f(\sqrt{x}) f(-\sqrt{x}). \] and that, if \(\zeta_1,\zeta_2,\ldots,\zeta_d\) are the roots of \(f\), then the roots of \(Gf\) are \(\zeta_1^2,\zeta_2^2,\ldots,\zeta_d^2.\)