Probabilistic Algorithms for Computing Resultants

M. Monagan


Let A and B be two polynomials in Z[x,y] and let R = res_x(A,B) in Z[y] be the resultant of A and B taken wrt x. The most efficient general purpose method for computing R is the modular resultant algorithm of Collins. We modify Collin's algorithm to make it output sensitive. Our algorithm is necessarily probabilistic. The advantage of our algorithm is that it will be faster, potentially much faster, when the bounds needed for the coefficients in R and degree of R for Collin's algorithm are inaccurate.

Our second contribution is an output sensitive modular algorithm for computing the monic resultant in Q[y]. It is also probabilistic. The advantage of this algorithm is that it is faster still when the resultant has a large integer content. The paper includes a number of resultant problems from real applications that motivate the need to consider such algorithms.

We have implemented both algorithms in Maple. We give timing comparisons of our algorithms comparing them with Collin's algorithm and the subresultant algorithm on various problems. The timings demonstrate that our algorithms do yield a big speedup.