4ti2 -- Computation of Hilbert bases, Graver bases, toric Groebner bases, and more

groebner

This code computes a generating set and then a Gröbner basis

of the toric ideal of a matrix A or
of the lattice ideal of a lattice L

with respect to the term ordering specified in 'fileName.cost'. If 'fileName.cost' is not present, a default term ordering is used. Note that you may specify any term ording with this new version by simply putting a matrix into 'fileName.cost' that encodes this term ordering. There are no short cuts like '--lexicographic' coded into 'groebner' at the moment.

See

A.M. Bigatti and R. LaScala and L. Robbiano. Computing toric ideals. Journal of Symbolic Computation 27 (1999), 351--365.
R. Gebauer and H. M. Möller. On an installation of Buchberger's algorithm. Journal of Symbolic Computation 6 (1988), 275--286.
R. Hemmecke and P. Malkin. Computing generating sets of lattice ideals. e-print arXiv:math.CO/0508359, 2005.
S. Hosten and B. Sturmfels. GRIN: An implementation of Gröbner bases for integer program- ming. In: "Integer programming and combinatorial optimisation", E. Balas and J. Clausen, eds., LNCS 920, Springer-Verlag, 1995, 267--276.

for more details on the algorithms implemented.

Usage

./groebner [--options] fileName

Examples

./groebner fileName
./groebner --quiet fileName

Default behavior

If 'fileName.cost' is not present, a default term ordering is used.
If existent, the Gröbner basis is computed from an ideal generating set given in 'fileName.mar' or in 'fileName.gro'.

Comments

There are two major algorithms implemented to find a generating set for the lattice ideal:
- Saturation algorithm
- Project-amd-Lift algorithm (default)
Both use a completion procedure whose critical-pair selection strategy can be driven by:
- the simplest and straight-forward FIFO strategy (default)
- a selection by increasing weights, where a weights matrix should be specified in 'fileName.weights'.
- the Gebauer-and-Möller criteria to eliminate many critical pairs. It seems to be most effective, when 4ti2 is not having a generating set available, as it is the case in the Saturation algorithm. Therefore, this option is set as default if the Saturation algorithm is chosen.
  Moreover, this strategy is a useful alternative to the 'normal' strategy if this one is performing badly.
Auto-reduction is turned on by default to avoid unnecessarily huge intermediate sets. You may turn it off completely by setting the option 'auto-reduce-freq=-1'.
The default settings worked pretty well in our experiments. But, if you have 3 processors to spare, it is probably best to start 3 computations in parallel each with different algorithms.

Option
(not on SUN) Short-hand
(also on SUN) Effect

--quiet -q no output is written to the screen

--force -f forces full computation from scratch regardless of existing files like 'fileName.gro'

--saturation -s Use the Saturation algorithm of Hosten & Sturmfels.

--project-and-lift -p Use the Project-and-Lift algorithm. (default)

--normal -n Use the straight-forward completion procedure. (default)
Critical pairs are queued and chosen by FIFO.

--weighted -w Use the weighted completion procedure.
Critical pairs are chosen by increasing weight.

--gebauer-moeller -g Use the Gebauer and Moeller criteria.

--auto-reduce-freq=n -an Set the frequency of auto reduction to 'n' iterations. (n=20,000 default)
Set 'auto-reduce-freq=-1' to switch off auto-reduction.

Option (not on SUN)	Short-hand (also on SUN)	Effect
--quiet	-q	no output is written to the screen
--force	-f	forces full computation from scratch regardless of existing files like 'fileName.gro'
--saturation	-s	Use the Saturation algorithm of Hosten & Sturmfels.
--project-and-lift	-p	Use the Project-and-Lift algorithm. (default)
--normal	-n	Use the straight-forward completion procedure. (default) Critical pairs are queued and chosen by FIFO.
--weighted	-w	Use the weighted completion procedure. Critical pairs are chosen by increasing weight.
--gebauer-moeller	-g	Use the Gebauer and Moeller criteria.
--auto-reduce-freq=n	-an	Set the frequency of auto reduction to 'n' iterations. (n=20,000 default) Set 'auto-reduce-freq=-1' to switch off auto-reduction.

Output file Content

fileName.gro list of Gröbner basis elements