Faster algorithms for computing Hong’s bound on absolute positiveness

We show how to compute Hong’s bound for the absolute positiveness of a polynomial in d variables with maximum degree δ in O(nlogdn) time, where n is the number of non-zero coefficients. For the univariate case, we give a linear time algorithm. As a consequence, the time bounds for the continued fraction algorithm for real root isolation improve by a factor of δ.