The computation of roots of a univariate polynomial is the most classical task in computational algebra. Since this problem arises in very many applications, plenty of techniques for its solution have been proposed. In this paper, Sagraloff and Mehlhorn extend the set of known methods by discussing an algorithm for a certain special variant of this problem: Under the assumption that the polynomial has real coefficients and only simple zeros, their goal is to provide a set of disjoint intervals on the real line such that (1) each interval contains exactly one root of the polynomial and (2) all real roots are contained in the union of the intervals. Algorithms for this special case have been introduced before; however, in all cases where a complete analysis of these known methods exists, they typically have a rather high complexity.

The new algorithm that Sagraloff and Mehlhorn construct is called the approximate arithmetic Newton-Descartes algorithm, or ANewDsc for short. As the name indicates, it is based on the classical Descartes method for the isolation of real roots in suitable subintervals. The main shortcomings of this approach in its original form are the necessity to use exact arithmetic and its inefficiency in the case of clustered roots. A modification of the basic idea is now presented that alleviates both of these problems simultaneously. This feature contrasts with previously known variants of the Descartes method that could not handle more than one of the undesired properties. The underlying idea behind this modification is based on an analysis of the recursion tree of the Descartes algorithm. It turns out that long chains in the tree correspond to clustered roots, and based on this knowledge, one can see that these chains can be more efficiently traversed when the Descartes method is combined with Newton’s algorithm and a specific subdivision strategy.

The complexity analysis for the case that the polynomial has only integer coefficients reveals that ANewDsc requires O(n² (k+τ) log^j (n (k + τ))) bit operations for some j > 0 where n is the degree of the polynomial, k is the number of non-zero coefficients, and 2^τ is an upper bound on the absolute value of the coefficients. A similar result is also provided for the case of a polynomial with arbitrary real coefficients that are assumed to be known up to a certain accuracy. In either case, this complexity is the same as or just marginally worse than the complexity of the best currently known methods. Unlike many other algorithms, ANewDsc can also be applied (at a lower computational cost) if one does not seek all real roots of the polynomial but only those real roots that are located within a given interval.

The paper presents a very detailed description of the algorithm from which its correctness is evident and a thorough complexity analysis. Some possible refinements are indicated as well. In my opinion, it is not only of interest for researchers who are active in the area of polynomial root finding and for users from other fields who need such algorithms for their work, but it is also very instructive for novices in the area of polynomial root finding because it provides plenty of insight into the fundamental difficulties that arise in this context and into possible ways to overcome them.