Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schoenhage in 1982. The main drawbacks of Pan's method are that it is quite involved and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted ANEWDSC, which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. ANEWDSC can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task.
Root refinement is the process of computing better approximations once the roots are isolated. @cite_3 @cite_35 @cite_13 @cite_26 @cite_16 , algorithms have been proposed which scale like @math for large @math . The former two algorithms are based on the splitting circle approach and compute approximations of all complex roots. The latter two solutions are dedicated to approximate only the real roots. They combine a fast convergence method (i.e., the secant method and Newton iteration, respectively) with approximate arithmetic and efficient multipoint evaluation; however, there are details missing in @cite_16 when using multipoint evaluation. In order to achieve complexity bounds comparable to the one stated in Theorem , the methods from @cite_3 @cite_16 need as input isolating intervals whose size is comparable to the separation of the corresponding root, that is, the roots must be "well isolated". This is typically achieved by using a fast method, such as Pan's method, for complex root isolation first. Our algorithm does not need such a preprocessing step.
@cite_35 @cite_26 @cite_3 @cite_16 @cite_13
1997509004 1664198596 2144619406 203551860
We introduce a novel algorithm denoted NewDsc to isolate the real roots of a univariate square-free polynomial f with integer coefficients. The algorithm iteratively subdivides an initial interval which is known to contain all real roots of f and performs exact (rational) operations on the coefficients of f in each step. For the subdivision strategy, we combine Descartes' Rule of Signs and Newton iteration. More precisely, instead of using a fixed subdivision strategy such as bisection in each iteration, a Newton step based on the number of sign variations for an actual interval is considered, and, only if the Newton step fails, we fall back to bisection. Following this approach, quadratic convergence towards the real roots is achieved in most iterations. In terms of complexity, our method induces a recursion tree of almost optimal size O(n·log(nτ)), where n denotes the degree of the polynomial and τ the bitsize of its coefficients. The latter bound constitutes an improvement by a factor of τ upon all existing subdivision methods for the task of isolating the real roots. We further provide a detailed complexity analysis which shows that NewDsc needs only O(n3τ) bit operations to isolate all real roots of f. In comparison to existing asymptotically fast numerical algorithms (e.g. the algorithms by V. Pan and A. Schonhage), NewDsc is much easier to access and, due to its similarities to the classical Descartes method, it seems to be well suited for an efficient implementation. We introduce a new approach to isolate the real roots of a square-free polynomial @math with real coefficients. It is assumed that each coefficient of @math can be approximated to any specified error bound. The presented method is exact, complete and deterministic. Due to its similarities to the Descartes method, we also consider it practical and easy to implement. Compared to previous approaches, our new method achieves a significantly better bit complexity. It is further shown that the hardness of isolating the real roots of @math is exclusively determined by the geometry of the roots and not by the complexity or the size of the coefficients. For the special case where @math has integer coefficients of maximal bitsize @math , our bound on the bit complexity writes as @math which improves the best bounds known for existing practical algorithms by a factor of @math . The crucial idea underlying the new approach is to run an approximate version of the Descartes method, where, in each subdivision step, we only consider approximations of the intermediate results to a certain precision. We give an upper bound on the maximal precision that is needed for isolating the roots of @math . For integer polynomials, this bound is by a factor @math lower than that of the precision needed when using exact arithmetic explaining the improved bound on the bit complexity. To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the nth degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus, Recursive combination of the two algorithms leads to computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. The new root-finder incorporates the earlier techniques of Schonhage, Neff Reif, and Kirrinnis and our old and new techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the computational complexity of both complete factorization and root-finding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of n for complete factorization and also for the approximation of well-conditioned (well isolated) roots, whereas the same algorithm is also optimal (under both arithmetic and Boolean models of computing) for the worst case input polynomial, whose roots can be ill-conditioned, forming clusters. (The worst case complexity bounds for root-finding are supported by our previous algorithms as well.) All algorithms allow processor efficient acceleration to achieve solution in polylogarithmic parallel time. Let f be a univariate polynomial with real coefficients, f ∈ R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of f in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation. Such methods have adaptive complexity, are local, and are also applicable when f is transcendental. The complexity analysis of adaptive algorithms is a new challenge for computer science. In this paper, we introduce a form of continuous amortization for adaptive complexity. Our analysis is applied to an evaluation-based root isolation algorithm called EVAL. EVAL is based on an algorithm of Mitchell and can also be seen as a 1-dimensional analogue of algorithms by Plantinga and Vegter for meshing curves and surfaces. The algorithm itself is simple, but its complexity analysis is not. Our main result is an O(d3(log d+L)) bound on the subdivision-tree size of EVAL for the benchmark problem of isolating all real roots of a square-free integer polynomial f of degree d and logarithmic height L. Our proof introduces several novel techniques: First, we provide an adaptive upper bound on the complexity of EVAL using an integral, analogous to integral bounds provided by Ruppert in a different context. Such integrals can be viewed as a form of continuous amortization. In addition, we use two algebraic amortization techniques: one is based on the standard Mahler-Davenport root bounds, but the other, based on evaluation bounds, is new.