Algorithms for polynomial GCD computation over algebraic function fields
Algorithms for polynomial GCD computation over algebraic function fields
复制标题
DOI：
10.1145/1005285.1005328
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
M. V. Hoeij;M. Monagan
中科院分区：
文献类型：
--
作者：
M. V. Hoeij;M. Monagan
设L是一个代数函数域，其中k ≥ 0个参数t;1;，.，t;k;.设f;1;，f;2;是L[x]中的非零多项式。我们给出了两个算法来计算它们的gcd。第一个是模块化GCD算法，是Brown的模块化GCD算法的扩展，用于Z[x;1;，.，x;n;]和Encarnacion对于Q（α）[x]到函数域.它是利用有理数和有理数函数的重构和试除法。第二，分数自由算法，是一个修改的Moreno Maza和Rioboo算法计算gcds的三角集。该修改将L中的系数增长降低为线性。我们展示了如何扩展模块化GCD算法的工作时，L的最小多项式是不可约的。我们给出了一个实证比较这两种算法在Maple中的实现。
Let L be an algebraic function field in k ≥ 0 parameters t;1;, ..., t;k;. Let f;1;, f;2; be non-zero polynomials in L[x]. We give two algorithms for computing their gcd. The first, a modular GCD algorithm, is an extension of the modular GCD algorithm of Brown for Z[x;1;,...,x;n;] and Encarnacion for Q(α)[x] to function fields. It is uses rational number and rational function reconstruction and trial division. The second, a fraction-free algorithm, is a modification of the Moreno Maza and Rioboo algorithm for computing gcds over triangular sets. The modification reduces coefficient growth in L to be linear. We show how to extend the modular GCD algorithm to work when the minimal polynomial for L is not irreducible. We give an empirical comparison of the two algorithms using implementations in Maple.