Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

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

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


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

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

Gröbner bases, toric ideals, project & lift, Frobenius numbers
Downloads Download Wolfram CDF Player

presentation.pdf (435.6 KB) - PDF Document
Examples-final.nb (985.6 KB) - Mathematica Notebook
Hemmecke-final.nb (1.9 MB) - Mathematica Notebook