Computation of the GCD of polynomials using gaussian transformations and shifting

Publisher Website
Google Scholar
Abstract
A new numerical method for the computation of the greatest common divisor (GCD) of an m-set of polynomials of R [s], Pm,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 Pm,d with a basis matrix Pm, the method defines first, the most orthogonal uncorrupted base Pr from the rows of Pm, where r = rank(Pm) ≤ m. By applying successively gaussian transformations and shifting, on the basis matrix Pr ε Rr×(d+1) we produce each time a new basis matrix Pz with z = rank(Pz) < r. The method terminates when the rank of Pz is approximately equal to 1; the coefficient vector of the GCD is then defined as a row of the unit rank matrix Pz. 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.

This publication has 9 references indexed in Scilit: