USAGE: toric_ideal [options] matrix_file DESCRIPTION: toric_ideal is a program for computing the toric ideal of a matrix A. This ideal is always given by the reduced Groebner basis with respect to a given term ordering which is computed via Buchberger´s algorithm. For this purpose, we can use six different algorithms: The algorithm of Conti/Traverso (ct) computes the toric ideal of an extended matrix. This ideal can be used later for solving integer programming problems for given right hand vectors. By eliminating auxiliary variables, we can get the toric ideal of the original matrix from it. The same is true for the "positive" variant of the Conti-Traverso-algorithm (pct) which can only be applied if A has nonnegative entries, but should be faster in that case (it computes the toric ideal of a smaller extended matrix). All other algorithms compute the toric ideal of A itself. Except from the elimination version of the Conti-Traverso algorithm (ect), they should be more efficient than the algorithm mentionned before. These are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano (blr), Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two seem to be the fastest in the actual implementation. FILE FORMAT: The input file has to be a MATRIX file. toric_ideal produces a GROEBNER file named like the MATRIX file with extensions replaced by .GB. where GB stands for GROEBNER and is the abbreviation for the used algorithm as above. A MATRIX file should look as follows: MATRIX columns: cost vector: rows: matrix: positive row space vector: The last two lines are only needed when toric_ideal is called with the algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the options -alg hs or -alg blr The other algorithms ignore these lines. Example: MATRIX columns: 3 cost vector: 1 1 1 rows: 2 matrix: 1 2 3 4 5 6 positive row space vector: 1 2 3 A GROEBNER file looks as follows: GROEBNER computed with algorithm: (* abbreviations as above *) from file(s): (* the following four lines are optional *) computation time: term ordering: elimination block variables >0 *) weighted block should always be >0 *) size: Groebner basis: (* optional *) The Groebner basis consists always of binomials of the form x^a - x^b where x^a and x^b are relatively prime. Such a binomial can be represented by the vector a-b. The basis elements in the GROEBNER file are given by the coefficients of this vector representation. The settings for Buchberger´s algorithm and the compiler flags are produced when the GROEBNER file is generated by a call of toric_ideal with the verbose output option -v, --verbose Example (not belonging to the example above): GROEBNER computed with algorithm: du term ordering: elimination block: 0 weighted block: 3 W_LEX 1 2 3 size: 1 Groebner basis: 2 3 -2 (* x^2 * y^3 - z^2 *) OPTIONS: -alg , --algorithm algorithm to use for computing the toric ideal; may be ct for Conti/Traverso, pct for the positive Conti/Traverso, ect for Conti/Traverso with elimination, pt for Pottier, hs for Hosten/Sturmfels, du for Di Biase/Urbanke, blr for Bigatti-LaScal-Robbiano. -p percentage of new generators to cause an autoreduction during Buchberger´s algorithm; may be an arbitrary float, a negative value allows no intermediate autoreductions default is -p 12.0 -S [RP] [M] [B] [M] [2] criteria to use in Buchberger´s algorithm for discarding unneccessary S-pairs RP relatively prime leading terms M Gebauer-Moeller criterion M F Gebauer-Moeller criterion F B Gebauer-Moeller criterion B 2 Buchberger´s second criterion default is -S RP M B -v, --verbose verbose output mode; writes the settings for Buchberger´s algorithm and the compiler flags into the output GROEBNER file -V , --version version of Buchberger´s algorithm to use; may be 1, 1a, 2 or 3 default is -V 1