Options
Near optimal subdivision algorithms for real root isolation
Publikationstyp
Conference Paper
Date Issued
2015-06-24
Sprache
English
Author(s)
Institut
TORE-URI
Volume
2015
Start Page
331
End Page
338
Citation
Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC (2015): 331-338 (2015-06-24)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
ACM
Isolating real roots of a square-free polynomial in a given interval is a fundamental problem. Subdivision based algorithms are a standard approach to solve this problem. E.g., Sturm's method, or various algorithms based on the Descartes's rule of signs. For isolating all the real roots of a degree n polynomial with root separation σ, the subdivision tree size of most of these algorithms is bounded by O(log 1/σ) (assume σ < 1). Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2013) have developed algorithms that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O(n(log(n log 1/σ))). Their algorithms and analysis crucially depend on the terminating predicates. We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on the Descartes's rule of signs is bounded by O(n log 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 hence the analysis extends to other predicates; and second, we use the geometry of clusters of roots instead of root bounds.
Subjects
Continuous amortization
Integral analysis
Newton diagram
Real root isolation
Subdivision algorithms
DDC Class
004: Informatik
510: Mathematik