An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system
An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system
复制标题
DOI：
10.1016/j.jsc.2011.12.015
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
D. Kapur;Yao Sun;Dingkang Wang
中科院分区：
文献类型：
--
作者：
D. Kapur;Yao Sun;Dingkang Wang
提出了一种新的有效算法，用于计算 k[U][X] 上理想参数多项式的综合 Gröbner 系统。与先前提出的算法（包括 Suzuki 和 Sato 的算法以及 Nabeshima 的算法）相比，该算法生成的分支（段）更少。因此，该算法能够计算由应用程序产生的参数多项式理想的综合 Gröbner 系统，这是其他众所周知的算法无法企及的。新算法的起点是 Weispfenning 的算法，该算法具有 Suzuki 和 Sato 的关键见解，他们提出在执行基于参数约束的任何分支之前，首先计算 k[U,X] 上理想的 Gröbnerbasis。该算法利用了这样的结果：沿着对应于综合Gröbner系统的树中的任何分支，对于k(U)[X]中的每个不可整除的主幂乘积只需要考虑一个多项式，并且条件是它们的主系数的乘积不为0；其他分支对应于该乘积为0的情况。此外，为了处理不等式参数约束，采用概率检查来对理想参数约束进行激进隶属度检验。这与基于 Rabinovitch 技巧的一般昂贵检查形成对比，该技巧使用 Nabeshima 算法中的新变量。所提出的算法已在 Magma 和 Singular 中实现，并用来自不同应用程序的多个示例进行了实验。其性能（分支数量和执行时间）已与其他几种现有算法进行了比较。 Magma 实现中融入了许多启发式方法和高效检查，特别是在理想参数约束为 0 维的情况下。该算法已成功用于解决计算机视觉中著名的 P3P 问题的特殊情况。
A new efficient algorithm for computing a comprehensive Gröbnersystem of a parametric polynomial ideal over k[U][X] is presented. This algorithm generates fewer branches (segments) compared to previously proposed algorithms including Suzuki and Sato’s algorithm as well as Nabeshima’s algorithm. As a result, the algorithm is able to compute comprehensive Gröbnersystems of parametric polynomial ideals arising from applications which have been beyond the reach of other well known algorithms. The starting point of the new algorithm is Weispfenning’s algorithm with a key insight by Suzuki and Sato who proposed computing first a Gröbnerbasis of an ideal over k[U,X] before performing any branches based on parametric constraints. The proposed algorithm exploits the result that along any branch in a tree corresponding to a comprehensive Gröbnersystem, it is only necessary to consider one polynomial for each nondivisible leading power product in k(U)[X] with the condition that the product of their leading coefficients is not 0; other branches correspond to the cases where this product is 0. In addition, for dealing with a disequality parametric constraint, a probabilistic check is employed for radical membership test of an ideal of parametric constraints. This is in contrast to a general expensive check based on Rabinovitch’s trick using a new variable as in Nabeshima’s algorithm. The proposed algorithm has been implemented in Magma and Singular, and experimented with a number of examples from different applications. Its performance (the number of branches and execution time) has been compared with several other existing algorithms. A number of heuristics and efficient checks have been incorporated into the Magma implementation, especially in the case when the ideal of parametric constraints is 0-dimensional. The algorithm has been successfully used to solve a special case of the famous P3P problem from computer vision.