Computation of toric Gröbner bases, Gröbner bases of lattices and and integer points of polytopes

Loc Pottier

Institut National de Recherche en Informatique et Automatique,
Projet S.A.F.I.R.,
2004 route des Lucioles, Sophia Antipolis,
06565 Valbonne CEDEX, FRANCE.
Email :

The directory Bastat-Sun available by anonymous ftp on machine by decompressing file 9510-LP-bastat.tar.Z under directory safir contains two C programs working on Sun machines.

These programs are based on computation of Gröbner bases of saturated binomial ideals. Such ideals, for example toric ideals (which define toric varieties, parametrized by monomials) have applications in combinatorics and integer linear programming.

Mathematical bases of these programs can be found in [1], [5], [3], [4].

Basic algorithm for computation of toric Gröbner bases
Let  be a variety parametrized by monomials (with exponents possibly negative) :

Let  be the kernel of the morphism from  in  sending to .

Let  be the matrix with  as columns, and  be its kernel, which is a sub-lattice of . Let  be a basis of .

The ideal  is the trace on  of 

Program bastat computes the reduced Gröbner basis of  for a given order (in fact a Gröbner basis of , intersected with), and the dimension of .

One can give  in two ways : by the matrix , or by a basis of a lattice.

If the parameters of  are homogeneous (monomials  have the same degree), it asks if it must compute the degree of , what is done if one type any word but 0 (it can take a long time).

We describe now the main features of the implementation:

Outlines of the algorithm
: we use a Buchberger/Knuth-Bendix like completion algorithm, keeping the family of binomials reduced.
Implementation of polynomials
: All polynomials in the computation are in fact differences of monomials. Moreover, the two monomials have no variable in commun, then we represente them as a vector of exponents : to the binomial corresponds the vector . We call this vector "the vector of the binomial".
: the vector of the S-polynomial of two binomials is simply the difference of vectors of the binomials.
: to reduce a binomial to a normal form by a family of binomials, we can reduce first the head, and then the tail. Then a lemma says that the the head and the tail of the result have no variable in common.
Unnecessary S-polynomial
: we eliminate unnecessary S-polynomials by a criterion on their vectors derived from classical criterion of Buchberger, etc.



Input and output
The program bastat ask for the following inputs:
the monomial order and the way the ideal is given:
lexicographic order, the ideal is given by the matrix .
reverse lexicographic order, the ideal is given by the matrix .
lexicographic order, the ideal is given by a matrix whose rows are a basis of the lattice.
reverse lexicographic order, the ideal is given by a matrix whose rows are a basis of the lattice.



a matrix  of integers.



The binomials of the Gröbner basis of  are printed as vector of dimension , positive coordinates corresponding to exponents of leading monomial, negative to tail monomial.

During the computation are printed pairs of numbers: first is the current number of binomials in the basis, second is the current number of S-polynomials to be reduced.

Limits: the program is limited by the number of elements in the Gröbner bases (10000), the number of S-polynomials to be reduced (1000000), and the size of integers (32 bits). Overcrossing these bounds will cause the program to wildly end, or to give wrong results.

Comparing with macaulay
In each session, the program creates a file input-macaulay containing a macaulay script computing a reverse lexicographic Gröbner basis for (again by a Gröbner basis of  and elimination).

To make this computaion, type macaulay<input-macaulay. The trace of the macaulay session is recorded in the file output-macaulay.

Comparizon of execution times beetwen bastat and macaulay is very favourable to bastat, particulary in the cases when degrees or number of variables exceed bounds of macaulay.

When we give as input the variety by monomials of parameters, a second file input-mat-macaulay is created, where the ideal  becomes

The Gröbner basis of  is then obtained by a Gröbner basis of  and by eliminination of variables . This method can allow macaulay to achieve its computation when degrees a too big in the first definition of .

This example is due to M.Morales et P.Gimenez (Institut Fourier, Grenoble, France).

Executions times are those of Sun SPARC10/51 machine.

macaulay computes it in 0.48 second (with input-macaulay, it fails with too big degrees with input-mat-macaulay).

The method of Morales [2], effective in codimension 2, computes it immediately.

bastat computes it in 0.32 second (this time contains an uncompressible part of memory allocation, which becomes non significant with bigger examples).

The curve is parametrized with:

Run bastat:

$ bastat

Loi(tre(accent aigu)ma)c Pottier                                              

Projet SAFIR (Systemes Algebriques Formels pour l'Industrie et la Recherche)
INRIA Sophia Antipolis 
2004 route des Lucioles
06565 Valbonne Cedex FRANCE
Tel: 93 65 78 19
Fax: 93 65 77 66
Courrier electronique:

                         avril 1994                       

Ordre sur les monomes:1
Matrice des monomes (= colonnes) definissant la variete:
Nombre de colonnes: 4
Nombre de lignes: 2
Donnez les coefficients de la matrice ligne par ligne:
281 1   781 0
500 780 0   781
-39  25  14   0 
 14 -29  -5  20 
Base standard de l'ideal 
[-1 281 0 -280]
[2 219 -1 -220]
[5 157 -2 -160]
[8 95 -3 -100]
[-3 62 1 -60]
[11 33 -4 -40]
[39 -25 -14 0]
[-14 29 5 -20]
[25 4 -9 -20]
Temps: 0.32s
Nombre de binomes dans la base standard: 9
Dimension de la variete: 2
L'ideal est homogene.
Calcul du degre de la variete?(repondre par 0 ou 1):1
Degre 781
Temps: 0.00s
With macaulay:
$ macaulay<input-macaulay     
        A computer algebra system for algebraic geometry

    This program, Macaulay, may be freely copied for others.  We
request that you write us to join a mailing list of Macaulay users,
so that we can keep you informed of updates to Macaulay.

    Dave Bayer                   Mike Stillman
    Department of Mathematics    Department of Mathematics
    Barnard College              Cornell University
    New York, NY 10027           Ithaca, NY 14853
    (212)854-2643, 864-4235      (607)255-7240, 277-1835

Macaulay version 3.0, created 8/14/89

% ring R
! characteristic (if not 31991)       ? 
! number of variables                 ? 5
!   5 variables, please               ? x[0]x[1]x[2]x[3]x[4]
! variable weights (if not all 1)     ? 
! monomial order (if not rev. lex.)   ? 1 4
;   largest degree of a monomial        : 512 512 

ideal I
! number of generators ? 3
! (1,1) ? x[0]1x[1]1x[2]1x[3]1x[4]1-1
! (1,2) ? x[2]29x[3]5-x[1]14x[4]20
! (1,3) ? x[1]39-x[2]25x[3]14

% <inhomog_std I J

% elim J H

% putstd H
; 1
; 9
; x[2]29x[3]5-x[1]14x[4]20
; x[2]62x[3]-x[1]3x[4]60
; x[2]281-x[1]x[4]280
; x[1]2x[2]219-x[3]x[4]220
; x[1]5x[2]157-x[3]2x[4]160
; x[1]8x[2]95-x[3]3x[4]100
; x[1]11x[2]33-x[3]4x[4]40
; x[1]25x[2]4-x[3]9x[4]20
; x[1]39-x[2]25x[3]14

% end of file ($) received, exiting Macaulay


Fri Oct 6 13:21:34 MET 1995