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.
Isolating the roots of a polynomial is a fundamental and well-studied problem. One is either interested in isolating all roots, or all real roots, or all roots in a certain subset of the complex plane. A related problem is the approximate factorization of a polynomial, that is, to find @math to @math such that @math is small. Given the number of distinct complex roots of a polynomial @math , one can derive isolating disks for all roots from a sufficiently good approximate factorization of @math ; see @cite_26 . In particular, this approach applies to polynomials that are known to be square-free.
@cite_26
2134534233
We present an algorithm for isolating all roots of an arbitrary complex polynomial p that also works in the presence of multiple roots provided that (1) the number of distinct roots is given as part of the input and (2) the algorithm can ask for arbitrarily good approximations of the coefficients of p. The algorithm outputs pairwise disjoint disks each containing one of the distinct roots of p and the multiplicity of the root contained in the disk. The algorithm uses approximate factorization as a subroutine. For the case where Pan's algorithm (Pan, 2002) is used for the factorization, we derive complexity bounds for the problems of isolating and refining all roots, which are stated in terms of the geometric locations of the roots only. Specializing the latter bounds to a polynomial of degree d and with integer coefficients of bitsize less than @t, we show that [email protected]?(d^3+d^[email protected][email protected]) bit operations are sufficient to compute isolating disks of size less than 2^-^@k for all roots of p, where @k is an arbitrary positive integer. In addition, we apply our root isolation algorithm to a recent algorithm for computing the topology of a real planar algebraic curve specified as the zero set of a bivariate integer polynomial and for isolating the real solutions of a bivariate polynomial system. For polynomials of degree n and bitsize @t, we improve the currently best running time from [email protected]?(n^[email protected]+n^[email protected]^2) (deterministic) to [email protected]?(n^6+n^[email protected]) (randomized) for topology computation and from [email protected]?(n^8+n^[email protected]) (deterministic) to [email protected]?(n^6+n^[email protected]) (randomized) for solving bivariate systems.