Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing Gröbner fans

Authors: Komei Fukuda, Anders N. Jensen and Rekha R. Thomas
Journal: Math. Comp. 76 (2007), 2189-2212
MSC (2000): Primary 13P10, 52B20, 14Q99
Published electronically: May 3, 2007
MathSciNet review: 2336291
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 13P10, 52B20, 14Q99

Retrieve articles in all journals with MSC (2000): 13P10, 52B20, 14Q99

Additional Information

Komei Fukuda
Affiliation: 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

Anders N. Jensen
Affiliation: Institut for Matematiske Fag, Aarhus Universitet, DK-8000 Århus, Denmark

Rekha R. Thomas
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195-4350

Received by editor(s): September 23, 2005
Received by editor(s) in revised form: March 30, 2006
Published electronically: May 3, 2007
Additional Notes: The research of the first author was supported by the Swiss National Science Foundation Project 200021-105202,“Polytopes, Matroids and Polynomial Systems”.
The research of the second author was partially supported by the Faculty of Science, University of Aarhus, Danish Research Training Council (Forskeruddannelsesrådet, FUR), Institute for Operations Research ETH, the Swiss National Science Foundation Project 200021-105202, grants DMS 0222452 and DMS 0100141 of the U.S. National Science Foundation and the American Institute of Mathematics.
The research of the third author was supported by grant DMS 0401047 of the U.S. National Science Foundation.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.