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.

Download this report (PDF)

Return to tech report index