Three new algorithms for multivariate polynomial GCD

AbstractThree new algorithms for multivariate polynomial GCD (greatest common divisor) are given. The first is to calculate a Gröbner basis with a certain term ordering. The second is to calculate the subresultant by treating the coefficients w.r.t. the main variable as truncated power series. The third is to calculate a PRS (polynomial remainder sequence) by treating the coefficients as truncated power series. The first algorithm is not important practically, but the second and third ones are efficient and seem to be useful practically. The third algorithm has been implemented naively and compared with the trial-division PRS algorithm and the EZGCD algorithm. Although it is too early to derive a definite conclusion, the PRS method with power series coefficients is very efficient for calculating low degree GCD of high degree non-sparse polynomials