From approximate factorization to root isolation with application to cylindrical algebraic decomposition. (January 2015)

• Record Type: Journal Article
• Authors: Mehlhorn, Kurt; Sagraloff, Michael; Wang, Pengming
• Is Part Of: Journal of symbolic computation. Volume 66(2015)
• Page Start: 34
• Page End: 69
• Publication Date: 2015-01
• Subjects: Root isolation -- Root refinement -- Root finding -- Curve analysis -- Topology computation -- Bivariate polynomial system -- Complexity analysis -- Cylindrical algebraic decomposition; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2014.02.001
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 τ, we show that O ˜ ( d 3 + d 2 τ + d κ ) bit operations are sufficient to compute isolating disks of size less than 2 − κ for all roots of p, where κ 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 τ, we improve the currently best running time from O ˜ ( n 9 τ + n 8 τ 2 ) (deterministic) to O ˜ ( n 6 + n 5 τ ) (randomized) for topology computation and from O ˜ ( n 8 + n 7 τ ) (deterministic) to O ˜ ( n 6 + n 5 τ ) (randomized) for solving bivariate systems.