                    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  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 .

 http://arxiv.org/pdf/math.CO/0508359
 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   Downloads     presentation.pdf (435.6 KB) - PDF Document Examples-final.nb (985.6 KB) - Mathematica Notebook Hemmecke-final.nb (1.9 MB) - Mathematica Notebook       