Algorithms for the non-monic case of the sparse modular GCD algorithm
Algorithms for the non-monic case of the sparse modular GCD algorithm
复制标题
DOI：
10.1145/1073884.1073903
复制
发表时间：
2005-07
期刊：
影响因子：
--
通讯作者：
Jennifer de Kleine;M. Monagan;A. Wittkopf
中科院分区：
文献类型：
--
作者：
Jennifer de Kleine;M. Monagan;A. Wittkopf
设G =（4 y2 + 2 z）x2 +（10 y2 + 6 z）是两个多项式A，B ∈ [x，y，z]的最大公约数（Gcd）.由于G在主变量x中不是一元的，因此Richard Zippel的稀疏模块化Gcd算法不能直接应用，因为无法一致地缩放G在x中的单变量图像。我们提出了两个新的稀疏模块化Gcd算法来解决这个问题，而不需要任何因子分解。第一个是Zippel算法的修改，将比例因子视为待求解的未知数。这导致了一个结构化的耦合线性系统，其中一个有效的解决方案仍然是可能的。第二种算法使用稀疏的、一次变量的有理函数插值算法从一元图像重建一元Gcd x2 +（5 y2 + 3 z）/（2 y2 +z）。
Let G = (4y2+2z)x2 + (10y2+6z) be the greatest common divisor (Gcd) of two polynomials A, B ∈ ℤ[x,y,z]. Because G is not monic in the main variable x, the sparse modular Gcd algorithm of Richard Zippel cannot be applied directly as one is unable to scale univariate images of G in x consistently. We call this the normalization problem.We present two new sparse modular Gcd algorithms which solve this problem without requiring any factorizations. The first, a modification of Zippel's algorithm, treats the scaling factors as unknowns to be solved for. This leads to a structured coupled linear system for which an efficient solution is still possible. The second algorithm reconstructs the monic Gcd x2 + (5y2+3z)/(2y2+z) from monic univariate images using a sparse, variable at a time, rational function interpolation algorithm.