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.
Abstract In this paper, we give improved bounds for the computational complexity of computing with planar algebraic curves. More specifically, for arbitrary coprime polynomials f , g ∈ Z [ x , y ] and an arbitrary polynomial h ∈ Z [ x , y ] , each of total degree less than n and with integer coefficients of absolute value less than 2 τ , we show that each of the following problems can be solved in a deterministic way with a number of bit operations bounded by O ( n 6 + n 5 τ ) , where we ignore polylogarithmic factors in n and τ : • The computation of isolating regions in C 2 for all complex solutions of the system f = g = 0 , • the computation of a separating form for the solutions of f = g = 0 , • the computation of the sign of h at all real valued solutions of f = g = 0 , and • the computation of the topology of the planar algebraic curve C defined as the real valued vanishing set of the polynomial f . Our bound improves upon the best currently known bounds for the first three problems by a factor of n 2 or more and closes the gap to the state-of-the-art randomized complexity for the last problem. 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.  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. Abstract The subject of this paper is fast numerical algorithms for factoring univariate polynomials with complex coefficients and for computing partial fraction decompositions (PFDs) of rational functions in C ( z ). Numerically stable and computationally feasible versions of PFD are specified first for the special case of rational functions with all singularities in the unit disk (the “bounded case”) and then for rational functions with arbitrarily distributed singularities. Two major algorithms for computing PFDs are presented: The first one is an extension of the “splitting circle method” by A. Schonhage (“The Fundamental Theorem of Algebra in Terms of Computational Complexity,” Technical Report, Univ. Tubingen, 1982) for factoring polynomials in C [ z ] to an algorithm for PFD. The second algorithm is a Newton iteration for simultaneously improving the accuracy of all factors in an approximate factorization of a polynomial resp. all partial fractions of an approximate PFD of a rational function. Algorithmically useful starting value conditions for the Newton algorithm are provided. Three subalgorithms are of independent interest. They compute the product of a sequence of polynomials, the sum of a sequence of rational functions, and the modular representation of a polynomial. All algorithms are described in great detail, and numerous technical auxiliaries are provided which are also useful for the design and analysis of other algorithms in computational complex analysis. Combining the splitting circle method with simultaneous Newton iteration yields favourable time bounds (measured in bit operations) for PFD, polynomial factoring, and root calculation. In particular, the time bounds for computing high accuracy PFDs, high accuracy factorizations, and high accuracy approximations for zeros of squarefree polynomials are linear in the output size (and hence optimal) up to logarithmic factors.