Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleApproximate GCD of several univariate polynomials with small degree perturbations
Author(s) Thomas Bayer, Mohamed Elkadi, Andre Galligo
TypeArticle in Journal
AbstractWe 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 .
KeywordsGCD of univariate polynomials, EEA, Normal degree sequence, Approximate computation, Minimal syzygies, μ -basis, Generic initial ideal, Groebner basis
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717111001404
LanguageEnglish
JournalJournal of Symbolic Computation
Volume47
Number4
Pages410 - 421
Year2012
NoteSpecial Issue for Joachim von zur Gathen at 60
Edition0
Translation No
Refereed No
Webmaster