Linear and Quadratic Complexity Bounds on the Values of the Positive Roots of Polynomials
Alkiviadis G. Akritas · Zenodo (CERN European Organization for Nuclear Research) · 2020
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 per-formance of the Vincent-Akritas-Strzeboński (VAS) continued fractions method for the isolation of real roots of polynomials. We first present the following four linear complex-ity bounds (two “old ” and two “new ” ones, respectively): Cauchy’s, (C), K ioustelidis’, (K), F irst-Lambda, (FL) and Local-M ax, (LM); we then state the quadratic complex-ity 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).