Algorithms for exact polynomial root calculation

ABSTRACT

This thesis discusses two sets of fully specified algorithms which, given a univariate polynomial with integer coefficients (with possible multiple roots) and a positive rational error bound, uses infinite-precision arithmetic and Sturm's Theorem to compute intervals containing the real roots of the polynomial and whose lengths are less than the given error bound, The algorithms also provide a simple means of determining the number of real roots in any interval.The first set of algorithms uses infinite-precision integer arithmetic to compute the sequence of polynomials required by Sturm's Theorem and also to do all the required polynomial evaluations. The second set uses congruence arithmetic to compute the images of the sequence of polynomials over the finite fields GF(pi) for several primes pi and then uses the natural homomorphisms from the integers onto the finite fields GF(pi) and the Chinese Remainder Theorem to do the evaluations. The primary advantage of the use of congruence arithmetic in the second set of algorithms is that the computing time to multiply any two elements of GF(pi) is a constant whereas the time to multiply any two integers is proportional to the square of their lengths.The computing times of both sets of algorithms are analyzed in detail using the techniques of computing time analysis developed in the past few years by G. E. Collins and D. Knuth. It is shown that if P is a primitive, positive, univariate polynomial over the integers of positive degree, m, whose coefficients are bounded in magnitude by d, and which has L real roots, and ε is some positive rational number, 0 < ε ≤ 1, then the computing time to approximate the roots of P to within is:[EQUATION]using either set of algorithms.The empirical results of applying the two sets of algorithms to random polynomials and the first ten Legendre and Chebyshev polynomials are reported. Neither set of algorithms proved to be faster for all the polynomials tested.