Near optimal subdivision algorithms for real root isolation

摘要

Isolating real roots of a square-free polynomial in a given interval is a fundamental problem in computational algebra. Subdivision based algorithms are a standard approach to solve this problem. For instance, Sturm's method, or various algorithms based on the Descartes's rule of signs. For the benchmark problem of isolating all the real roots of a polynomial of degree n and root separation a, the size of the subdivision tree of most of these algorithms is bounded by O (log 1/sigma) (assume sigma < 1). Moreover, it is known that this is optimal for subdivision algorithms that perform uniform subdivision, i.e., the width of the interval decreases by some constant. Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2016) have developed algorithms for real root isolation that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O (n(log(n log 1/sigma))).