论文标题
一种用于计算单变量矢量的$μ$基础的新算法
A new algorithm for computing $μ$-bases of the univariate polynomial vector
论文作者
论文摘要
在本文中，我们表征了格罗布纳碱基与U-Bases之间的关系：N单变量多项式相对于术语跨度单序的n单变量多项式的Syzygy模块的任何最小值基础都是其U-BASIS。此外，根据GCD计算，我们通过递归方式构建了Syzygy模块的自由基础。根据这种关系和构造的自由基础，提出了一种用于计算Syzygy模块U基本的新算法。在合理的假设下，算法的理论复杂性为O（n^3d^2），其中d是输入n多项式的最大程度。我们已经在Maple中实现了该算法（MingB）。实验数据和性能与Song and Goldman（2009）（SG算法）和Hong等人开发的现有算法进行了比较。 （2017）（HHK算法）表明，当N和D足够大时，MingB算法比SG算法更有效，而MingB算法和HHK算法都具有自己的优势。
In this paper, we characterized the relationship between Groebner bases and u-bases: any minimal Groebner basis of the syzygy module for n univariate polynomials with respect to the term-over-position monomial order is its u-basis. Moreover, based on the gcd computation, we construct a free basis of the syzygy module by the recursive way. According to this relationship and the constructed free basis, a new algorithm for computing u-bases of the syzygy module is presented. The theoretical complexity of the algorithm is O(n^3d^2) under a reasonable assumption, where d is the maximum degree of the input n polynomials. We have implemented this algorithm (MinGb) in Maple. Experimental data and performance comparison with the existing algorithms developed by Song and Goldman (2009) (SG algorithm) and Hong et al. (2017) (HHK algorithm) show that MinGb algorithm is more efficient than SG algorithm when n and d are sufficiently large, while MinGb algorithm and HHK algorithm both have their own advantages.
