A presentation of the Gfan software package
Anders Nedergaard Jensen ∗Department of Mathematical Sciences, University of Aarhus andInstitute for Operations Research, ETH Zürich

8th April 2005

Abstract
Gfan is a new software package for computing Gröbner fans of polynomial ideals in Q[x1 , . . . , xn ]. We give a short description of this package.
Some technical details are given to give the reader an idea of what thesoftware can do.

1Background

Introduction Gfan is a software package for computing the Gröbner fan ([9])
of a given polynomial ideal. It is an implementation of the ideas appearing
in [4] which is joint work with Komei Fukuda and Rekha Thomas. For
toric and lattice ideals such programs already exist: TiGERS [6] andCaTS [7]. Gfan works on any ideal in Q[x 1 , . . . , xn ]. Besides Buchberger’salgorithm, the local basis change procedure [2] and the simplex method,
the reverse search technique [1] and algorithms for exploiting symmetry
are used. This allows enumeration of fans with millions of cones. Gfan
has been used for studying the structure of the Gröbner fan. Among thenew results is an example of a Gröbner fan which is not the normal fanof a polyhedron [8].
The Gröbner fan of an ideal The Gröbner fan of an ideal I ⊂ k[x 1 , . . . , xn ]is a polyhedral complex consisting of cones in R n . The monomial initial
ideals (with respect to term orders) of I are in bijection with the marked
reduced Gröbner bases of I and with the full dimensional cones in theGröbner fan of I. Knowing a marked reduced Gröbner basis its initial
ideal and equations defining its Gröbner cone are easily read off. Thus
a useful way to present the Gröbner fan of an ideal is by the set of its
reduced Gröbner bases.
Partially supported by the Faculty of Science, University of Aarhus, Danish ResearchTraining Council (Forskeruddannelsesrådet, FUR) , Institute for Operations Research ETH,
grants DMS 0222452 and DMS 0100141 of the U.S. National Science Foundation and theAmerican Institute of Mathematics.
∗12

Demonstration of the software

Computing all reduced Gröbner bases Computing all reduced Gröbner
bases of a polynomial ideal is the primary purpose of the software. Thiscan be done using the program gfan. For example, runninggfan
on the input{a^2+b*c, b^2+a*c, c^2+a*b}
produces a list of the 9 reduced Gröbner bases of the ideal generated by
the input:{{c^4, b*c^2, b^2*c, b^3-c^3, a*c+b^2, a*b+c^2, a^2+b*c},{c^3-b^3, b*c^2, b^2*c, b^4, a*c+b^2, a*b+c^2, a^2+b*c},{c^2+a*b, b^2*c, b^4, a*c+b^2, a*b^2, a^2+b*c},{c^2+a*b, b*c+a^2, b^4, a*c+b^2, a*b^2, a^2*b, a^3-b^3},{c^2+a*b, b*c+a^2, b^3-a^3, a*c+b^2, a*b^2, a^2*b, a^4},{c^4, b*c^2, b^2+a*c, a*c^2, a*b+c^2, a^2+b*c},{c^4, b*c+a^2, b^2+a*c, a*c^2, a*b+c^2, a^2*c, a^3-c^3},{c^3-a^3, b*c+a^2, b^2+a*c, a*c^2, a*b+c^2, a^2*c, a^4},{c^2+a*b, b*c+a^2, b^2+a*c, a^2*c, a^2*b, a^4}}
Combining programs on the command line Since Gfan is not part of abig algebra program we are limited to doing manipulations supported by
the UNIX shell. The Gfan package contains other programs than gfan.
For example we may combine gfan and gfan polynomialsetunion using
the pipe operation to compute a universal Gröbner basis:
gfan | gfan_polynomialsetunion
With the same input as before the output will be{c^4, b*c^2, b^2*c, b^3-c^3, a*c+b^2, a*b+c^2,a^2+b*c, c^3-b^3, b^4, a*b^2, a^2*b, a^3-b^3,b^3-a^3, a^4, a*c^2, a^2*c, a^3-c^3, c^3-a^3}Another possibility is to visualize the Gröbner fan.
gfan | gfan_render > picture1.fig
will produce the first xfig file shown in Figure 1 while the following willrender the staircase diagrams:
gfan | gfan_renderstaircase -m > picture2.fig

2Figure 1: The Gröbner fan of the ideal intersected with the standard simplex,
staircase diagrams visualising the various monomial initial ideals and a Gröbner
fan of a different ideal.

3

Advanced features

Symmetry Our examples are rarely random. They often possess a lot ofsymmetry. In our example, the ideal is invariant under any permutationof the three variables. In many cases it would be sufficient to know only
the essentially different Gröbner bases. Gfan can do its computations up
to symmetry.
Interactive mode The program gfan interactive is useful for investigating
the local structure of the fan. It allows the user to interactively walk fromcone to cone along an arbitrary path in the Gröbner fan.

4

Final remarks

Performance The software has been used to compute big examples. Here isan example of its performance: The ideal generated by the 4 × 4 minors of
4 × 5 matrix has 3000 reduced Gröbner bases. They can be computed in
5 hours using reverse search. Exploiting the symmetry of the ideal they
can be computed in 12 seconds.
Future improvements A natural extension of the software is a program forchecking if a set of polynomials is a Gröbner basis with respect to some(unknown) term order. Another could be a universal Gröbner basis test
- is a given set of polynomials a Gröbner basis with respect to any termorder?
Supported platforms and required libraries The following platforms aresupported: Linux, Mac OS X and other UNIX variants. It is likely thatthe program will also run on Microsoft Windows systems through Cygwin.
The program is written in C++ and can be compiled with gcc 3.3.3. The
following libraries are required: gmp [5] (arithmetics) and cddlib [3] (LPsolving).

3

References[1] David Avis and Komei Fukuda. A basis enumeration algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete
Computational Geometry, 8:295–313, 1992.
[2] Stéphane Collart, Michael Kalkbrener, and Daniel Mall. Converting baseswith the Gröbner walk. J. Symb. Comput., 24(3/4):465–469, 1997.
[3] Komei Fukuda. cddlib reference manual, cddlib Version 093b. Swiss
Federal Institute of Technology, Lausanne and Zürich, Switzerland, 2003.
http://www.ifor.math.ethz.ch/˜fukuda/cdd home/cdd.html.
[4] Komei Fukuda, Anders Jensen, and Rekha Thomas. Computing Gröbnerfans. In preparation.
[5] Torbjörn Granlund et al. GNU multiple precision arithmetic library 4.1.2,December 2002. http://swox.com/gmp/.
[6] Birkett Huber and Rekha R. Thomas. Computing Gröbner fans of toricideals. Experimental Mathematics, 9(3/4):321–331, 2000.
[7] Anders Jensen. CaTS, a software system for toric state polytopes. Available
at http://www.soopadoopa.dk/anders/cats/cats.html.
[8] Anders Jensen. A non-regular Gröbner fan. 2005. math.CO/0501352.
[9] Teo Mora and Lorenzo Robbiano. The Gröbner fan of an ideal. J. Symb.
Comput., 6(2/3):183–208, 1988.

4