An efficient algorithm for infallible polynomial complex root isolation
George Ernest Collins, Werner Krandick · 1992
Applying the principle of the argument to rectangles provides an efficient algorithm for polynomial complex root isolation. For example, the roots of a real integral polynomial of degree 10 (with 10-bit coefficients) can be isolated in about 1 second. Furthermore, although the algorithm is not designed for efficient refinement of isolating rectangles, it does nevertheless refine all of these rectangles to width 10 \\Gamma50 in less than 4 minutes. 1 Introduction Let A(z) be a non-zero squarefree univariate polynomial with Gaussian integer coefficients. This paper presents an algorithm which produces disjoint isolating rectangles for all the roots of A(z) in the complex plane, i.e. each such rectangle will contain exactly one root of A, and each root of A will be contained in one of the rectangles. The sides of the rectangles will be parallel to the axes. Given any rational number e ? 0, the algorithm will deliver isolating rectangles with sidelengths ! e. Unlike numerical methods t...