A New Constructive Root Bound for Algebraic Expressions

Li C., Yap C.

Computing effective root bounds for constant algebraic expressions is a critical problem in the Exact Geometric Computation approach to robust geometric programs. Classical root bounds are often non-constructive. Recently, various authors have proposed bounding methods which might be called constructive root bounds. For the important class of radical expressions, Burnikel et al (BFMS) have provided a constructive root bound which, in the division-free case, is an improvement over previously known bounds and is essentially tight. In the presence of division, their bound requires a quadratic blowup in root bit-bound compared to the division-free case. We present a new constructive root bound that avoids this quadratic blowup and which is applicable to a more general class of algebraic expressions. This leads to dramatically better performance in some computations. We also give an improved version of the degree-measure bound from Mignotte and BFMS. We describe our implementation in the context of the Core Library, and report on some experimental results.