Computing Gröbner fans
Computing Gröbner fans
复制标题
格罗布纳计算迷
DOI：
10.1090/s0025-5718-07-01986-2
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Rekha R. Thomas
中科院分区：
文献类型：
--
作者：
K. Fukuda;A. Jensen;Rekha R. Thomas
本文提出了计算任意多项式理想的Grobner扇的算法。计算涉及枚举理想的所有约化Grobner基。我们的算法是基于一个统一的定义，适用于均匀和非均匀的理想和证明，这个对象是一个多面体复杂的Grobner风扇。我们表明，细胞的Grobner风扇可以很容易地被定向为非周期性和一个独特的水槽，让他们的枚举的无记忆的反向搜索过程。这一点的重要性来自于这样一个事实，即Grobner风扇并不总是多面体的正常风扇，在这种情况下，反向搜索自动应用。计算结果使用我们的软件包Gfan中的这些算法的实现包括在内。
This paper presents algorithms for computing the Grobner fan of an arbitrary polynomial ideal. The computation involves enumeration of all reduced Grobner bases of the ideal. Our algorithms are based on a uniform definition of the Grobner fan that applies to both homogeneous and non-homogeneous ideals and a proof that this object is a polyhedral complex. We show that the cells of a Grobner fan can easily be oriented acyclically and with a unique sink, allowing their enumeration by the memory-less reverse search procedure. The significance of this follows from the fact that Grobner fans are not always normal fans of polyhedra, in which case reverse search applies automatically. Computational results using our implementation of these algorithms in the software package Gfan are included.