Comparison of algorithms for calculation of g.c.d. of polynomials

Abstract
A study is made of several algorithms for computing the greatest common divisor g(λ) of two or mora polynomials a1(λ) with real coefficients. Brief descriptions are given of methods including the Routh array form of Euclid's algorithm, a recent approach using the companion matrix of one of the polynomials, another matrix method due to Blankinship and an iterative scheme of Weinstock. The problem of finding multipliers, polynomials x1(λ)such that Σa1x1=g1 also discussed. Estimates are given of the numbers of operations which each method involves when calculating the g.c.d. Numerical results obtained when testing a variety of examples are also presented. By virtue of these considerations it is concluded that for the general problem of finding g(λ)and the multipliers Blankinship's method is the best, both for reasons of accuracy (i.e. ability to distinguish between nearly identical factors) and of computing time and storage requirements. For the case when it is only required to find the g.c.d. of two polynomials the Kouth array scheme is a slightly faster alternative.

This publication has 7 references indexed in Scilit: