2018-08-30 | 编辑：文/先进制造部

最大公因子或公因式是数学中的一个非常基本的概念。计算整数最大公因子(GCD)的欧几里得算法可以说是最重要的数学算法。该算法也可直接应用于单变元多项式最大公因式(GCD)的计算。GCD的计算也是符号计算领域一个非常基本的问题。到目前为止，已有很多很成熟的计算多项式GCD的高效算法。但计算含参数的多项式GCD的算法却寥寥无几。究其原因，是因为参数多项式的GCD需要考虑所有可能的参数取值，不同的参数取值对应着不同的GCD, 从而使得该问题变得异常复杂。对于含参数的单变元多项式， Abramov和Kvashenko提出了运用子结式链理论来计算GCD。参数Groebner系统也可直接用于含参数的单变元多项式GCD的计算。对于多变元的情形，参数多项式GCD的计算则要困难得多，只有Nagasaka在ISSAC 2017上提出了两种计算方法。他的方法都要求参数多项式在参数赋值之后关于主变元是本原多项式。可是，针对所有可能的不同赋值，计算参数多项式的本原部分非常繁琐和困难。他的这种处理方式会耗费大量的计算时间和内存，导致该方法效率低下。因此，提出一个参数多变元多项式GCD的高效算法非常必要。

先进制造部的科研人员王定康和合作者们在这一问题上取得了重要进展。他们通过计算一个参数多项式商理想的参数Groebner系统，从而可以得到参数多项式的GCD。该方法已在著名的计算机代数系统Singular上实现，对于随机生成的一些参数多变元多项式，下表列出了不同方法的计算时间。其中New表示该新算法，NGT和NSS则表示Nagasaka提出的两种已有算法。

表格：计算时间

 

上面的实验数据表明新算法比Nagasaka提出的两种算法更高效。该方法的关键点在于将最大公因式和参数多项式理想联系起来。研究的创新点在于利用参数Groebner系统来计算参数理想的商理想，无须考虑参数多项式是否为本原多项式，从而节约了计算时间，大大地提高了算法效率。该研究工作被ISSAC2018接受并已正式发表。

参考文献

[1].D. Cox, J. Little, and D. O’shea. 1992. Ideals, varieties, and algorithms. Springer, third edition.

[2].D. Kapur, Y. Sun, and D.K. Wang. 2013. An efficient algorithm for computing a comprehensive Groebner system of a parametric polynomial system. Journal of Symbolic Computation 49 (2013), 27–44.

[3].K. Nagasaka. 2017. Parametric greatest common divisors using comprehensive Groebner systems. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation. 341–348.