README

Toric

A program for solving integer programs using Groebner bases.

Installing the software
1. Before you install, you will need to have the NTL library installed. Visit http://www.shoup.net/ntl/ to download NTL.
  1. Unpack the tarball:
    
    tar xzvf Toric.tar.gz
  2. Enter the directory 'Toric' and type the command
    
    make all
    
    This assumes that the NTL library (libntl.a) lives in /usr/local/lib, and that the NTL header files live in /usr/local/include/NTL. If you have installed the NTL library elsewhere, you can redefine NTLLINK and NTLINCLUDE using the appropriate directories, either by editing the Makefile or by giving make additional commandline arguments:
    
    make NTLLINK="/path/to/ntllib" NTLINCLUDE="/path/to/headers" all
  3. You should now have 5 executables: toric, weightGB, kernel, elim, and reduce.
Running the program
1. The Hosten-Sturmfels algorithm
  1. Create a file with the matrix for the integer program. The expected format of the file is
```
		#rows #columns
		a11 ... a1n
		a21 ... a2n
		 .	 .
		 .	 .
		am1 ... amn
```
    For example:
```
		3 6
		1 5 10 6 4 3
		2 4 6 8 11 5 
		9 7 5 4 3 10 
```
  2. Run kernel to compute a lattice basis for the integer kernel of the matrix. The syntax is
    kernel [inputfile] [outputfile]
  3. There are several options for computing generators for a toric ideal (and a grevlex Groebner basis):
    1. The basic method for computing a grevlex Groebner basis is to enter the command
      
      toric [inputfile] [outputfile]
      
      where inputfile is either the output from kernel or any file in the same format. Using this method, toric will automatically select which variables to use for saturation.
    2. To select the variables used for saturation in a similar manner; add a line before the list of vectors of the form
```
		S 1 0 1 1 0 ... 1 0
```
      where a 1 in the i-th place instructs toric to saturate the i-th variable.
    3. The output of this calculation will be of the same format as the input file.
  4. Performing Groebner base calculation with a specific weight vector:
    1. To specify a weight vector to calculate the Groebner base with respect to a certain set of generators for a toric ideal, add:
```
                 W w_1 w_2 ... w_n
```
      to the second line of the file specifying the set of generators for the toric ideal. So, the file format for a set of generators and weight vector which we will be calculating a Groebner base with respect to is:
```
            n
            W w_1 w_2 ... w_n
            [list of generators]
```
      If no weight vector is specified, then a standard grevlex Groebner basis for the list of generators passed is generated.
    2. To truncate based on A-degree or to place bounds on the maximum size of the variables create a new file. The format of the file is:
```
		b_1 b_2 ... b_m
		u_1 u_2 ... u_n
```
      where the first line is the upper bound for the A-degree (see the section "Implementation" for information) and u_i is the upper bound on the degree of the i-th variable. The second line can be omitted if you only want to truncate using A-degree. Any entry that is negative will be ignored for the purposes of truncating. The correct syntax is then
```
		weightGB [inputfile] [outputfile] [matrixfile] [boundfile]
```
2. The Conti-Traverso Algorithm
  1. Performing the Conti-Traverso Algorithm is just a special weightGB calculation. The correct input file format is:
```
                m+n
                W 0 0 0 ... 0 1 1 ... 1
                [1 0 0 ... 0 -a_11 ... -a_m1]
                [0 1 0 ... 0 -a_12 ... -a_m2]
                        .       .
                        .       .
                        .       .
                [0 0 0 ... 1 -a_1n ... -a_mn]
```
    where m is the number of rows and n the number of columns of A, and a_ij is the ij-th entry of A. The output of this computation is an elimination Groebner basis of the input toric ideal.
  2. A Groebner basis can be calculated two different ways:
    1. Use the command
```
                weightGB [inputfile] [outputfile]
```
      using the file created in 1. as the input.
    2. Truncate using a bound on A-degree and/or bounds on the variables -- this is set up exactly as in the Hosten-Sturmfels algorithm. If you use this method, you must also create a file with the matrix [A | I] -- the matrix A with an m by m identity matrix adjoined. The syntax is then exactly as in H-S:
```
                weightGB [inputfile] [outputfile] [matrixfile] [boundfile]
```
3. Eliminating a set of variables. To eliminate a set of variables from a generating set or Groebner basis, use:
4. Reduction to normal form
  1. Once a Groebner basis has been computed, create a file with the vector that is to be reduced to its normal form. The format for this file is exactly the same as the format of the input file for toric:
```
		n
		[a_1 ... a_n]
```
  2. The vector can be reduced with the command
```
		reduce [GBfile] [vectorfile] [outputfile]
```
Implementation
1. Truncation
  1. A "loose" form of truncation is implemented in weightGB when truncating with respect to A-degree. If b is the bound on A-degree, then the algorithm functions as follows: during the Buchberger algorithm, if an S-polynomial (vector) v appears whose positive part v+ satisfies A(v+)>b (with the comparison made component-wise), then v is discarded.
  2. Truncating with respect to A-degree during Conti-Traverso will result in the same output as computing a full Groebner basis and then truncating it with respect to A-degree. The same does not necessarily hold when truncating in the Hosten-Sturmfels algorithm.
Peter Couperus
Davis Doherty
University of Washington
Department of Mathematics