Computing Gröbner fans |
| |
Authors: | Komei Fukuda Anders N Jensen Rekha R Thomas |
| |
Institution: | Institute for Operations Research and Institute of Theoretical Computer Science, ETH Zentrum, CH-8092 Zurich, Switzerland and Mathematics Institute / ROSO EPFL, CH-1015 Lausanne, Switzerland ; Institut for Matematiske Fag, Aarhus Universitet, DK-8000 Århus, Denmark ; Department of Mathematics, University of Washington, Seattle, Washington 98195-4350 |
| |
Abstract: | This paper presents algorithms for computing the Gröbner fan of an arbitrary polynomial ideal. The computation involves enumeration of all reduced Gröbner bases of the ideal. Our algorithms are based on a uniform definition of the Gröbner 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 Gröbner 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 Gröbner 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. |
| |
Keywords: | |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|