Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4945898 | Journal of Symbolic Computation | 2017 | 32 Pages |
Abstract
We describe a subroutine that reduces the size of the subdivision tree of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on either the Descartes's rule of signs or Sturm sequences is bounded by O(nlogâ¡n), which is close to the optimal value of O(n). The corresponding bound for the algorithm EVAL, which uses certain interval-arithmetic based predicates, is O(n2logâ¡n). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and extend it to handle non-uniform subdivisions; second, we use the geometry of clusters of roots instead of root bounds. The latter aspect enables us to derive a bound on the subdivision tree that is independent of the root separation Ï. The number of Newton iterations is bounded by O(nlogâ¡logâ¡(1/Ï)).
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Prashant Batra, Vikram Sharma,