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.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2012, 47 (4), pp.410-421. 〈10.1016/j.jsc.2011.09.005〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00528634
Contributeur : Ba Thang Luu <>
Soumis le : vendredi 22 octobre 2010 - 11:09:31
Dernière modification le : lundi 4 décembre 2017 - 15:14:18

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

347