Algebraic Algorithms for Computing the Complex Zeros of Gaussian Polynomials

Let G be a univariate Gaussian rational polynomial (a polynomial with Gaussian rational coefficients) having m distinct zeros. Algebraic algorithms are designed and implemented which, given G and a positive rational error bound E, use Sturm's Theorem, the Routh-Hurwitz Theorems, and infinite precision integer arithmetic or modular arithmetic to compute m disjoint squares in the complex plane, each containing one zero of G and having width less than E. Also included are algorithms for the following operations: associating with each square the multiplicity of the unique zero of G contained in the square; determining the number of zeros of G in regions of the complex plane such as circles and rectangles; refining selected individual zeros of G, that is, given G, a square S containing a single zero of G, and a positive rational error bound E, computing a subsquare of S which contains the zero and has width less than E. The theoretical computing times of the algorithms are analyzed and presented along with empirical computing times