 |
|
|
|
|
 |
 |
|
Project-and-Lift algorithm for Toric Gröbner Bases
|
|
|
|
|
|
| Organization: | Technische Universität München |
| Department: | Institut für Informatik |
|
|
|
|
|
|
2010-04-13
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
Gröbner bases, toric ideals, project & lift, Frobenius numbers
|
|
|
 |
|
|
| presentation.pdf (435.6 KB) - PDF Document | | Examples-final.nb (985.6 KB) - Mathematica Notebook | | Hemmecke-final.nb (1.9 MB) - Mathematica Notebook |
|
|
For the newest resources, visit Wolfram Repositories and Archives »
