Improving the Performance of the Continued Fractions Method Using New Bounds of Positive Roots

Abstract

In this paper we compare four implementations of the Vincent-Akritas-Strzebonski Continued Fractions (VAS-CF) real root isolation method using four different (two linear and two quadratic complexity) bounds on the values of the positive roots of polynomials. The quadratic complexity bounds were included to see if the quality of their estimates compensates for their quadratic complexity. Indeed, experimentation on various classes of special and random polynomials revealed that the VAS-CF implementation using LMQ, the Quadratic complexity variant of our Local Max bound, achieved an overall average speed-up of 40% over the original implementation using Cauchy's linear bound.