The function RootBound computes an estimate for the absolute
value of the largest complex root of a univariate polynomial, or
equivalently the radius of a disc centred on the origin of the
complex plane which contains all complex roots.
The intention is to obtain a reasonably good estimate quickly. An optional second argument says how many iterations of Graeffe's transformation to use to obtain a better bound; by default a heuristic is used to decide how many iterations. More iterations give a better bound, but they become increasingly expensive.
RootBound(f) return an upper bound for absolute value of every complex root of f
RootBound(f,niters) return an upper bound for absolute value of every complex root of f,
using niters iterations of Graeffe's transformation. Need 0 <= niters <= 25
RootBoundTransform(f) returns a_d*x^d - sum(a_k*x^k, k=0,..,d-1) where a_k is abs value of coeff of x^k in f
This is still an early version (so there is a lot of cruft).
I shall probably keep the "logarithmic version". To limit the amount
of potentially costly arithmetic with big integers, I have used a
(dense) logarithmic representation of the univariate polynomial:
a vector<double> whose k-th entry contains log(a_k)
where a_k means the coeff of x^k in the monic polynomial.
I have used a "large negative" constant to represent log(0).
The implementation follows what I wrote in (the "big factor" paper): J. Abbott: Bounds on Factors in ZZ[x], JSC vol.50, 2013, pp. 532-563
I have added a "preprocess" function which makes the coeffs "primitive"
(coprime integers), and removes any powers of x which divide the
poly, and also rewrites the poly in terms of x^k where k is
chosen largest possible (usually it is just 1, of course).
The case of a linear polynomial is handled separately since we can compute the root directly.
Still lots of cruft!
Continues to apply Graeffe transformations even when this cannot
produce any improvement (i.e. if poly is of form x^d - rest
where rest has all coeffs non-negative.
2017