Approximate GCD of several univariate polynomials, small degree perturbations

Mohamed Elkadi 1, 2 André Galligo 1, 2 Ba Thang Luu 2, 3
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : We consider the following computational problem, posed by von zur Gathen et al. [18]: given a family of generic univariate polynomials f := (f0 , ..., fs ), construct an algorithm to find polynomial purtubbations u :=(u0 , ..., us ) with "small" degrees such that the GCD (greater common divisor) of the perturbed family f + u has a "large" degree. In this paper, we propose an algorithm which solves this problem in polynomial time under a generic condition generalizing the normal degree sequence used in [18] for the case s = 1.
Document type :
Journal articles
Liste complète des métadonnées
Contributor : Ba Thang Luu <>
Submitted on : Friday, October 22, 2010 - 11:09:31 AM
Last modification on : Thursday, May 3, 2018 - 1:32:58 PM

Links full text




Mohamed Elkadi, André Galligo, Ba Thang Luu. Approximate GCD of several univariate polynomials, small degree perturbations. Journal of Symbolic Computation, Elsevier, 2012, 47 (4), pp.410-421. ⟨10.1016/j.jsc.2011.09.005⟩. ⟨inria-00528634⟩



Record views