Approximate GCD of several univariate polynomials, small degree perturbations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Symbolic Computation Année : 2012

Approximate GCD of several univariate polynomials, small degree perturbations

Résumé

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.

Dates et versions

inria-00528634 , version 1 (22-10-2010)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More