Linear and Quadratic Complexity Bounds on the Values of the Positive Roots of Polynomials

Abstract

In this paper we review the existing linear and quadratic complexity (upper) bounds on the values of the positive roots of polynomials and their impact on the performance of the Vincent-Akritas-Strzebonski (VAS) continued fractions method for the isolation of real roots of polynomials. We first present the following four linear complexity bounds (two "old" and two "new" ones, respectively): Cauchy's, (C), Kioustelidis', (K), First-Lambda, (FL) and Local-Max, (LM); we then state the quadratic complexity extensions of these four bounds, namely: CQ, KQ, FLQ, and LMQ - the second, (KQ), having being presented by Hong back in 1998. All eight bounds are derived from Theorem 5 below. The estimates computed by the quadratic complexity bounds are less than or equal to those computed by their linear complexity counterparts. Moreover, it turns out that VAS(lmq) - the VAS method implementing LMQ - is 40% faster than the original version VAS(cauchy).