Complex Root Isolation.

      Аннотация: Complex root isolation of univariate Gaussian integer polynomial A(z) can be done by reducing the problem to find an algorithm to determine the number of roots of A(z) in any given closed rectangle R in the complex plane. If there are no zeros of A(z) on the boundary of R, then the number of roots in R can be obtained by using the argument principle. However, the argument principle fails when there is a root on the boundary of R. In this book a mathematical proof is given to solve the problem although there are roots on the boundary. We have also presented an algorithm based on the above result that isolate all complex zeros of A. Furthermore we have shown that the time complexity of the algorithm has a good upper bound. Finally, the algorithm is implemented in SacLib2.1 and we have provided empirical evidence that our algorithm is efficient in practice.

Ключевые слова: Polynomials, Real root isolation. Complex root isolation.