Details:
Title  Approximate GCD of several univariate polynomials with small degree perturbations  Author(s)  Thomas Bayer, Mohamed Elkadi, Andre Galligo  Type  Article in Journal  Abstract  We consider the following computational problem: given a family of generic univariate polynomials f≔(f_0, … ,f_s) , construct an algorithm to find polynomial perturbations u≔(u_0, … ,u_s) with “small” degrees such that the greater common divisor of the family of polynomials 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 for the case s = 1 .  Keywords  GCD of univariate polynomials, EEA, Normal degree sequence, Approximate computation, Minimal syzygies, μ basis, Generic initial ideal, Groebner basis  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717111001404 
Language  English  Journal  Journal of Symbolic Computation  Volume  47  Number  4  Pages  410  421  Year  2012  Note  Special Issue for Joachim von zur Gathen at 60  Edition  0  Translation 
No  Refereed 
No 
