###### Options

# Near optimal subdivision algorithms for real root isolation

Publikationstyp

Conference Paper

Publikationsdatum

2015-06-24

Sprache

English

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.