Approximate GCD of several univariate polynomials with small degree perturbations

作者：Elkadi Mohamed^*; Galligo Andre; Ba Thang Luu

来源：Journal of Symbolic Computation, 2012, 47(4): 410-421.

DOI：10.1016/j.jsc.2011.09.005

• GCD of univariate polynomials
• EEA
• Normal degree sequence
• Approximate computation
• Minimal syzygies
• mu-basis
• Generic initial ideal
• Groebner basis

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(5)) with %26quot;small%26quot; degrees such that the greater common divisor of the family of polynomials f + u has a %26quot;large%26quot; degree. %26lt;br%26gt;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.

• 出版日期2012-4