Exact Algorithms for the Matrix-Triangularization Subresultant PRS Method

In [2] a new method is presented for the computation of a greatest common divisor (gcd) of two polynomials, along with their polynomial remainder sequence (prs). This method is based on our generalization of a theorem by Van Vleck (1899)[12] and uniformly treats both normal and abnormal prs’s, making use of Bareiss’s (1968)[4] integer-preserving transformation algorithm for Gaussian elimination; moreover, for the polynomials of the prs’s, this method provides the smallest coefficients that can be expected without coefficient gcd computations. In this paper we present efficient, exact algorithms for the implementation of this new method, along with an example where bubble pivot is needed.