Complexity of Algorithms for Computing Greatest Common Divisors of Parametric Univariate Polynomials
Ali Ayad · 2010
This paper presents a comparison between the complexity bounds of different algorithms for computing greatest common divisor of a finite set of parametric univariate polynomials. Each algorithm decomposes the parameters space into a finite number of constructible sets such that a greatest common divisor of the parametric univariate polynomials is given uniformly in each constructible set. The first one is a parametrization of the well-known euclidean algorithm, this is the worst case study: its complexity is exponential in the number k of the polynomials and the upper bound d on the degrees of the polynomials. The second algorithm comes from a paper of Grigoryev in 1989. The third algorithm is based on a parametrization of the well-known Gaussian elimination procedure for solving linear systems. The complexity of these two last algorithms is polynomial in k and d and exponential in the number r of the parameters. These algorithms are used to solve parametric univariate polynomial systems and to compute the multiplicities of roots of parametric univariate polynomials.