Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation

作为在更多的一般范围的计算机代数学和符号的计算的最重要的任务之一，自从开始，计算 multivariate 多项式的最大的普通除数(GCD ) 的问题广泛地被学习了有计算机科学的数学学科交差。为象数字图象恢复和改进那样的许多真实应用程序，非线性的系统的柔韧的控制理论， L 1-norm 在察觉到技术压缩的凸的优化，以及芦苇贤明之人和 BCH 的代数学的译码编码，稀少的 GCD 的概念起仅仅的一个核心作用最大的普通除数与很，少数比原来的多项式由于问题或数据结构的性质具有兴趣的称为。这份报纸经由分别地基于 Zippels 方法和 Ben-Or/Tiwari 算法的变化的 multivariate 多项式插值论述二个方法。为了减少计算复杂性，概率的技术和随机化，被采用处理 univariate GCD 计算和 univariate 多项式插值。作者在例子的重要身体上表明我们的算法的实际表演。实现的实验说明那我们的算法为输入的一个相当宽的范围是有效的。

The problem of computing the greatest common divisor（GCD） of multivariate polynomials, as one of the most important tasks of computer algebra and symbolic computation in more general scope, has been studied extensively since the beginning of the interdisciplinary of mathematics with computer science. For many real applications such as digital image restoration and enhancement,robust control theory of nonlinear systems, L1-norm convex optimization in compressed sensing techniques, as well as algebraic decoding of Reed-Solomon and BCH codes, the concept of sparse GCD plays a core role where only the greatest common divisors with much fewer terms than the original polynomials are of interest due to the nature of problems or data structures. This paper presents two methods via multivariate polynomial interpolation which are based on the variation of Zippel＇s method and Ben-Or/Tiwari algorithm, respectively. To reduce computational complexity, probabilistic techniques and randomization are employed to deal with univariate GCD computation and univariate polynomial interpolation. The authors demonstrate the practical performance of our algorithms on a significant body of examples. The implemented experiment illustrates that our algorithms are efficient for a quite wide range of input.