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 : pottier@sophia.inria.fr
Introduction
The directory Bastat-Sun available by anonymous ftp on machine
zenon.inria.fr 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].
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:
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
.
Example
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 CALCUL DE BASES STANDARD D'IDEAUX TORIQUES ------------------------------------------------------------------------------- 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: pottier@sophia.inria.fr ------------------------------------------------------------------------------- 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 Matrice: -39 25 14 0 14 -29 -5 20 [3,3][4,4][5,4][6,3][7,7][8,9][9,15][10,12][11,7][12,6][13,9][14,7][15,11] [16,8][17,13][18,14] 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.00sWith macaulay:
$ macaulay<input-macaulay 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 dab@math.columbia.edu mike@mssun7.msi.cornell.edu 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