Title

Project-and-Lift algorithm for Toric Gröbner Bases
Author

 Stephan Ritscher
 Organization: Technische Universität München
 Department: Institut für Informatik
Revision date

2010-04-13
Description

Gröbner bases are special bases of polynomial ideals which are very important in computer algebra.

Gröbner bases of toric ideals can be used to perform integer linear programming. The project-and-lift algorithm by Hemmecke and Malkin [1] is a very efficient way to compute those Grobner bases.

Basically, the problem is to compute a Gröbner basis of I(B) = < x^a - x^b : (a - b) in ker(B)> for a given B. The monomial ordering will be specified as matrix.

The notebooks implements the project-and-lift algorithm completely in Mathematica code. The main function is HemmeckeToricGroebnerBasis. It takes exactly three arguments:

"HemmeckToricGroebnerBasis[B, variables, monomialOrder]"
• "B" is the matrix whose kernel defines the ideal.
• "variables" is a list of symbols that will be used for the output of the polynomials. Their order is important. The k-th symbol corresponds to the k-th column of the matrix. The number of symbols must therefore match the number of columns of "B".
• "monomialOrder" is a matrix which represents the monomial ordering. Basically, the order is the lexicographic comparison of the product of "monomialOrder" and the exponent vectors of the monomials.
Both notebooks contain some examples. The second one provides a framework for creating statistics from random matrices and the Frobenius number problem [2].

[1] http://arxiv.org/pdf/math.CO/0508359
[2] http://arxiv.org/pdf/math/0702040
Subjects

 Applied Mathematics > Computer Science Applied Mathematics > Optimization Mathematics > Algebra > Polynomials
Keywords

Gröbner bases, toric ideals, project & lift, Frobenius numbers