Comparison of algorithms for calculation of g.c.d. of polynomials
- 1 March 1973
- journal article
- research article
- Published by Taylor & Francis in International Journal of Systems Science
- Vol. 4 (2) , 211-226
- https://doi.org/10.1080/00207727308920007
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.Keywords
This publication has 7 references indexed in Scilit:
- A note on the automatic pretreatment of polynomialsThe Computer Journal, 1970
- Greatest common divisor of two polynomialsLinear Algebra and its Applications, 1970
- Another Theorem Relating Sylvester's Matrix and the Greatest Common DivisorMathematics Magazine, 1969
- A new method for solving polynomial equationsThe Computer Journal, 1968
- A New Version of the Euclidean AlgorithThe American Mathematical Monthly, 1963
- Greatest Common Divisor of Several Integers and an Associated Linear Diophantine EquationThe American Mathematical Monthly, 1960
- Applications of Routh's Algorithm to Network-Theory ProblemsIRE Transactions on Circuit Theory, 1959