Geodesic
FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials
Serdica Journal of Computing, Tome 2 (2008) no. 2, pp. 145-162 Cet article a éte moissonné depuis la source Bulgarian Digital Mathematics Library

Voir la notice de l'article

In this paper we present F LQ, a quadratic complexity bound on the values of the positive roots of polynomials. This bound is an extension of FirstLambda, the corresponding linear complexity bound and, consequently, it is derived from Theorem 3 below. We have implemented FLQ in the Vincent-Akritas-Strzeboński Continued Fractions method (VAS-CF) for the isolation of real roots of polynomials and compared its behavior with that of the theoretically proven best bound, LM Q. Experimental results indicate that whereas F LQ runs on average faster (or quite faster) than LM Q, nonetheless the quality of the bounds computed by both is about the same; moreover, it was revealed that when VAS-CF is run on our benchmark polynomials using F LQ, LM Q and min(F LQ, LM Q) all three versions run equally well and, hence, it is inconclusive which one should be used in the VAS-CF method.
Keywords: Vincent’s Theorem, Real Root Isolation Methods, Linear and Quadratic Complexity Bounds on the Values of the Positive Roots 
@article{SJC_2008_2_2_a3,
     author = {Akritas, Alkiviadis and Argyris, Andreas and Strzebo\'nski, Adam},
     title = {FLQ, the {Fastest} {Quadratic} {Complexity} {Bound} on the {Values} of {Positive} {Roots} of {Polynomials}},
     journal = {Serdica Journal of Computing},
     pages = {145--162},
     year = {2008},
     volume = {2},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2008_2_2_a3/}
}
TY  - JOUR
AU  - Akritas, Alkiviadis
AU  - Argyris, Andreas
AU  - Strzeboński, Adam
TI  - FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials
JO  - Serdica Journal of Computing
PY  - 2008
SP  - 145
EP  - 162
VL  - 2
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SJC_2008_2_2_a3/
LA  - en
ID  - SJC_2008_2_2_a3
ER  - 
%0 Journal Article
%A Akritas, Alkiviadis
%A Argyris, Andreas
%A Strzeboński, Adam
%T FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials
%J Serdica Journal of Computing
%D 2008
%P 145-162
%V 2
%N 2
%U http://geodesic.mathdoc.fr/item/SJC_2008_2_2_a3/
%G en
%F SJC_2008_2_2_a3
Akritas, Alkiviadis; Argyris, Andreas; Strzeboński, Adam. FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials. Serdica Journal of Computing, Tome 2 (2008) no. 2, pp. 145-162. http://geodesic.mathdoc.fr/item/SJC_2008_2_2_a3/