International Journal of Control, Vol.79, No.11, 1447-1461, 2006
Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance
The computation of the greatest common divisor (GCD) of several polynomials is a problem that emerges in many fields of applications. The GCD computation has a non-generic nature and thus its numerical computation is a hard problem. In this paper we examine the family of matrix pencil methods for GCD computation and investigate their performance as far as their complexity, error analysis and their effectiveness for evaluating approximate solutions. The relative merits of the various variants of such methods are examined for the different cases of sets of polynomials with varying number of elements and degree. The developed algorithms combine symbolical and numerical programming and this is what we de. ne here as hybrid computations. The combination of numerical operations with symbolical programming can improve the nature of the methods and guarantees the stability of the algorithm. Furthermore, it emphasizes the significance of hybrid computations in complex problems such as the computation of GCD. All methods are tested thoroughly for several sets of polynomials and the results are presented in tables.