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 : jeudi 3 mai 2018 - 13:32:58

Lien texte intégral

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

397