Computing Gröbner fans
HTML articles powered by AMS MathViewer
- by Komei Fukuda, Anders N. Jensen and Rekha R. Thomas PDF
- Math. Comp. 76 (2007), 2189-2212 Request permission
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
- Beatrice Amrhein, Oliver Gloor, and Wolfgang Küchlin, Walking faster, Proceedings DISCO ’96 (Berlin), LNCS 1128, Springer, 1996, pp. 150–161.
- David Avis and Komei Fukuda, Reverse search for enumeration, Discrete Appl. Math. 65 (1996), no. 1-3, 21–46. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). MR 1380066, DOI 10.1016/0166-218X(95)00026-N
- David Bayer and Ian Morrison, Standard bases and geometric invariant theory. I. Initial ideals and state polytopes, J. Symbolic Comput. 6 (1988), no. 2-3, 209–217. Computational aspects of commutative algebra. MR 988413, DOI 10.1016/S0747-7171(88)80043-9
- 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. Symbolic Comput. 12 (1991), no. 3, 329–336. MR 1128248, DOI 10.1016/S0747-7171(08)80153-8
- T. Bogart, A. N. Jensen, D. Speyer, B. Sturmfels, and R. R. Thomas, Computing tropical varieties, J. Symbolic Comput. 42 (2007), no. 1-2, 54–73. MR 2284285, DOI 10.1016/j.jsc.2006.02.004
- S. Collart, M. Kalkbrener, and D. Mall, Converting bases with the Gröbner walk, J. Symbolic Comput. 24 (1997), no. 3-4, 465–469. Computational algebra and number theory (London, 1993). MR 1484492, DOI 10.1006/jsco.1996.0145
- David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, second edition, Springer, 1997.
- J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (1993), no. 4, 329–344. MR 1263871, DOI 10.1006/jsco.1993.1051
- 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.
- Komei Fukuda, Anders Jensen, Niels Lauritzen, and Rekha Thomas, The generic Gröbner walk., J. Symb. Comput. 42 (2007), no. 3, 298–312.
- William Fulton, Introduction to toric varieties, Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993. The William H. Roever Lectures in Geometry. MR 1234037, DOI 10.1515/9781400882526
- Torbjörn Granlund et al., GNU multiple precision arithmetic library 4.1.2, December 2002, http://swox.com/gmp/.
- Birkett Huber and Rekha R. Thomas, Computing Gröbner fans of toric ideals, Experiment. Math. 9 (2000), no. 3, 321–331. MR 1795304
- Anders N. Jensen, Gfan, a software system for Gröbner fans, Available at http://home.imf.au.dk/ajensen/software/gfan/gfan.html.
- Anders N. Jensen, A non-regular Gröbner fan, Discrete and Computational Geometry 37 (2007), no. 3, 443–453.
- Michael Kalkbrener, On the complexity of Gröbner bases conversion, J. Symbolic Comput. 28 (1999), no. 1-2, 265–273. Polynomial elimination—algorithms and applications. MR 1709906, DOI 10.1006/jsco.1998.0276
- Niels Lauritzen, Truncated Gröbner fans and lattice ideals,(2005).
- Daniel Mall, Gröbner fans and projective schemes, Symbolic rewriting techniques (Ascona, 1995) Progr. Comput. Sci. Appl. Logic, vol. 15, Birkhäuser, Basel, 1998, pp. 181–191. MR 1624580
- Teo Mora and Lorenzo Robbiano, The Gröbner fan of an ideal, J. Symbolic Comput. 6 (1988), no. 2-3, 183–208. Computational aspects of commutative algebra. MR 988412, DOI 10.1016/S0747-7171(88)80042-7
- Jörg Rambau, TOPCOM: Triangulations of point configurations and oriented matroids, ZIB report 02-17 (2002).
- Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR 1363949, DOI 10.1090/ulect/008
- Carlo Traverso, Hilbert functions and the Buchberger algorithm, J. Symbolic Comput. 22 (1996), no. 4, 355–376. MR 1428831, DOI 10.1006/jsco.1996.0056
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
- 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. - © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 76 (2007), 2189-2212
- MSC (2000): Primary 13P10, 52B20, 14Q99
- DOI: https://doi.org/10.1090/S0025-5718-07-01986-2
- MathSciNet review: 2336291