From approximate factorization to root isolation
Kurt Mehlhorn, Michael Sagraloff, Pengming Wang · International Symposium on Symbolic and Algebraic Computation · 2013
We present an algorithm for isolating all roots of an arbitrary complex polynomial p which also works in the presence of multiple roots provided that arbitrary good approximations of the coefficients of p and the number of distinct roots are given. Its output consists of pairwise disjoint disks each containing one of the distinct roots of p, and its multiplicity. The algorithm uses approximate factorization as a subroutine. For the case, where Pan's algorithm [16] 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 Õ(d3+d2τ+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.
Cited by 11 works. doi:10.1145/2465506.2465523
Authors
References
- Modern computer algebra
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- On Nearest-Neighbor Graphs
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding
- Cylindrical Algebraic Decomposition using validated numerics
- An efficient method for analyzing the topology of plane real algebraic curves
- Fast and exact geometric analysis of real algebraic plane curves
- An Improved Upper Complexity Bound for the Topology Computation of a Real Algebraic Plane Curve
- A simple but exact and efficient algorithm for complex root isolation