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) V 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 L, 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 ∫IO 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). |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2442829.2442875 | ISSAC |
Keywords | Field | DocType |
recursion tree,practical exact numerical algorithm,r root,certain numerical predicate c0,burr-krahmer proof,simple real root isolation,recent bound,fundamental problem,optimal tree size bound,bisects i0,range l,interval i0 | Integer,Discrete mathematics,Combinatorics,Real roots,Polynomial,Root isolation,Absolute value,Algorithm,Subdivision algorithms,Recursion,Mathematics | Conference |
Citations | PageRank | References |
8 | 0.54 | 22 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vikram Sharma | 1 | 229 | 20.35 |
Chee-Keng Yap | 2 | 1996 | 395.32 |