Near optimal tree size bounds on a simple real root isolation algorithm

Vikram Sharma, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of isolating all real roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) ⊆ C1(I) holds on each I. We prove that the size of the recursion tree is O(d(L + r + log d)) where f has degree d, its coefficients have absolute values < 2L, and I0 contains r roots of f. In the range L ≥ d, our bound is the sharpest known, and provably optimal. Our results are closely paralleled by recent bounds on EVAL by Sagraloff-Yap (ISSAC 2011) and Burr-Krahmer (2012). In the range L ≤ d, our bound is incomparable with those of Sagraloff-Yap or Burr-Krahmer. Similar to the Burr-Krahmer proof, we exploit the technique of "continuous amortization" from Burr-Krahmer-Yap (2009), namely to bound the tree size by an integral I0 G(x)dx over a suitable "charging function" G(x). We give an application of this feature to the problem of ray-shooting (i.e., finding smallest root in a given interval).

Original languageEnglish (US)
Title of host publicationISSAC 2012 - Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation
Pages319-326
Number of pages8
DOIs
StatePublished - 2012
Event37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012 - Grenoble, France
Duration: Jul 22 2012Jul 25 2012

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Other

Other37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012
Country/TerritoryFrance
CityGrenoble
Period7/22/127/25/12

Keywords

  • Continuous amortization
  • Integral analysis
  • Real root isolation
  • Subdivision algorithm

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Near optimal tree size bounds on a simple real root isolation algorithm'. Together they form a unique fingerprint.

Cite this