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
DOI: https://doi.org/10.1090/S0025-5718-07-01986-2
Published electronically: May 3, 2007
MathSciNet review: 2336291
Full-text PDF

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?)

  • 1. Beatrice Amrhein, Oliver Gloor, and Wolfgang Küchlin, Walking faster, Proceedings DISCO '96 (Berlin), LNCS 1128, Springer, 1996, pp. 150-161.
  • 2. David Avis and Komei Fukuda, Reverse search for enumeration, Discrete Applied Mathematics 65 (1996), 21-46. MR 1380066 (98a:05080)
  • 3. David Bayer and Ian Morrison, Standard bases and geometric invariant theory I. Initial ideals and state polytopes., J. Symb. Comput. 6 (1988), no. 2/3, 209-217. MR 988413 (90e:13001)
  • 4. Göran Björck and Ralf Fröberg, A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic $ n$-roots, J. Symb. Comput. 12 (1991), no. 3/4, 329-336. MR 1128248 (92g:68067)
  • 5. Tristram Bogart, Anders Jensen, Rekha Thomas, David Speyer, and Bernd Sturmfels, Computing tropical varieties., J. Symb. Comput. 42 (2007), no. 1-2, 54-73. MR 2284285
  • 6. Stéphane Collart, Michael Kalkbrener, and Daniel Mall, Converting bases with the Gröbner walk., J. Symb. Comput. 24 (1997), no. 3/4, 465-469. MR 1484492
  • 7. David Cox, John Little, and Donal O'Shea, Ideals, varieties, and algorithms, second edition, Springer, 1997.
  • 8. Jean-Charles Faugere, Patrizia Gianni, Daniel Lazard, and Teo Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput. 16 (1993), 329-344. MR 1263871 (94k:68095)
  • 9. Komei Fukuda, cddlib reference manual, cddlib version 094b, Swiss Federal Institute of Technology, Lausanne and Zürich, Switzerland, 2005, http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html.
  • 10. Komei Fukuda, Anders Jensen, Niels Lauritzen, and Rekha Thomas, The generic Gröbner walk., J. Symb. Comput. 42 (2007), no. 3, 298-312.
  • 11. William Fulton, Introduction to toric varieties, Princeton University Press, 1993. MR 1234037 (94g:14028)
  • 12. Torbjörn Granlund et al., GNU multiple precision arithmetic library 4.1.2, December 2002, http://swox.com/gmp/.
  • 13. Birkett Huber and Rekha R. Thomas, Computing Gröbner fans of toric ideals., Experimental Mathematics 9 (2000), no. 3/4, 321-331. MR 1795304 (2001h:13039)
  • 14. Anders N. Jensen, Gfan, a software system for Gröbner fans, Available at http://home.imf.au.dk/ajensen/software/gfan/gfan.html.
  • 15. Anders N. Jensen, A non-regular Gröbner fan, Discrete and Computational Geometry 37 (2007), no. 3, 443-453.
  • 16. Michael Kalkbrener, On the complexity of Gröbner bases conversion, J. Symb. Comput. 28 (1999), 265-273. MR 1709906 (2000g:13020)
  • 17. Niels Lauritzen, Truncated Gröbner fans and lattice ideals,(2005).
  • 18. Daniel Mall, Gröbner fans and projective schemes, Progress in Computer Science and Applied Logic 15 (1998), 181-191. MR 1624580 (99d:13033)
  • 19. Teo Mora and Lorenzo Robbiano, The Gröbner fan of an ideal., J. Symb. Comput. 6 (1988), no. 2/3, 183-208. MR 988412 (90d:13004)
  • 20. Jörg Rambau, TOPCOM: Triangulations of point configurations and oriented matroids, ZIB report 02-17 (2002).
  • 21. Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8, American Mathematical Society, 1996. MR 1363949 (97b:13034)
  • 22. Carlo Traverso, Hilbert functions and the Buchberger algorithm, J. Symb. Comput. 22 (1996), 355-376. MR 1428831 (98i:13054)

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
Email: fukuda@ifor.math.ethz.ch

Anders N. Jensen
Affiliation: Institut for Matematiske Fag, Aarhus Universitet, DK-8000 Århus, Denmark
Email: ajensen@imf.au.dk

Rekha R. Thomas
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195-4350
Email: thomas@math.washington.edu

DOI: https://doi.org/10.1090/S0025-5718-07-01986-2
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.

American Mathematical Society