BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2008 >
Volume 2 Number 2 >

Please use this identifier to cite or link to this item:

Title: FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials
Authors: Akritas, Alkiviadis
Argyris, Andreas
Strzeboński, Adam
Keywords: Vincent’s Theorem
Real Root Isolation Methods
Linear and Quadratic Complexity Bounds on the Values of the Positive Roots
Issue Date: 2008
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 2, No 2, (2008), 145p-162p
Abstract: 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.
ISSN: 1312-6555
Appears in Collections:Volume 2 Number 2

Files in This Item:

File Description SizeFormat
sjc055-vol2-num2-2008.pdf270.02 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License