Computation of the GCD of polynomials using gaussian transformations and shifting

Abstract

A new numerical method for the computation of the greatest common divisor (GCD) of an m-set of polynomials of R [s], P_m,d of maximal degree d, is presented. This method is based on a recently developed theoretical algorithm (Karcanias 1987) that uses elementary transformations and shifting operations; the present algorithm takes into account the non-generic nature of GCD and thus uses steps, which minimize the introduction of additional errors and defines the GCD in an approximate sense. For a given set P_m,d with a basis matrix P_m, the method defines first, the most orthogonal uncorrupted base P_r from the rows of P_m, where r = rank(P_m) ≤ m. By applying successively gaussian transformations and shifting, on the basis matrix P_r ε R^r×(d+1) we produce each time a new basis matrix P_z with z = rank(P_z) < r. The method terminates when the rank of P_z is approximately equal to 1; the coefficient vector of the GCD is then defined as a row of the unit rank matrix P_z. The method defines the exact degree of the GCD, successfully evaluates an approximate solution and works satisfactorily with large numbers of polynomials of any fixed degree.