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.
Very recent work @cite_25 on isolating the real roots of a sparse integer polynomial @math makes crucial use of a slight modification of the subroutine Newton-Test as proposed in . There, it is used to refine an isolating interval @math for a root of @math in a number of arithmetic operations that is nearly linear in the number of roots that are close to @math and polynomial in @math , where @math and @math denotes the number of non-vanishing coefficients of @math . This eventually yields the first real root isolation algorithm that needs only a number of arithmetic operations over the rationals that is polynomial in the input size of the sparse representation of @math . Furthermore, for very sparse polynomials (i.e. @math with @math a constant), the algorithm from @cite_25 uses only @math bit operations to isolate all real roots of @math and is thus near-optimal.
@cite_25
2950326154
Let @math be an arbitrary polynomial of degree @math with @math non-zero integer coefficients of absolute value less than @math . In this paper, we answer the open question whether the real roots of @math can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of @math . More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of @math with @math many exact arithmetic operations over the rational numbers. When using approximate but certified arithmetic, the bit complexity of our algorithm is bounded by @math , where @math means that we ignore logarithmic. Hence, for sufficiently sparse polynomials (i.e. @math for a positive constant @math ), the bit complexity is @math . We also prove that the latter bound is optimal up to logarithmic factors.