An efficient algorithm for computing a comprehensive Gr?bner system of a parametric polynomial system

详细信息    查看全文

• 作者：Deepak Kapur^a ; ^{kapur@cs.unm.edu} ; Yao Sun^b ; ¹ ; ^{sunyao@amss.ac.cn} ; Dingkang Wang^b ; ^{dwang@mmrc.iss.ac.cn}
• 关键词：Grö ; bner basis ; Comprehensive Grö ; bner system ; Radical ideal membership ; Probabilistic check
• 刊名：Journal of Symbolic Computation
• 出版年：2013
• 出版时间：February, 2013
• 年：2013
• 卷：49
• 期：Complete
• 页码：27-44
• 全文大小：346 K

文摘

A new efficient algorithm for computing a comprehensive Gr?bner system of a parametric polynomial ideal over 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?bner systems 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?bner basis of an ideal over 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?bner system, it is only necessary to consider one polynomial for each nondivisible leading power product in with the condition that the product of their leading coefficients is not ; other branches correspond to the cases where this product is . 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 -dimensional. The algorithm has been successfully used to solve a special case of the famous P3P problem from computer vision.