Barvinok's Rational Functions: Algorithms and Applications to Optimization, Statistics, and Algebra

Details Barvinok's Rational Functions: Algorithms and Applications to Optimization, Statistics, and Algebra Barvinok's Rational Functions: Algorithms and Applications to Optimization, Statistics, and Algebra

2004-06-15

arxiv.org/abs/math/0406284v1

Mathematics

Combinatorics

Thesis

Scientific paper

The main theme of this dissertation is the study of the lattice points in a rational convex polyhedron and their encoding in terms of Barvinok's short rational functions. The first part of this thesis looks into theoretical applications of these rational functions to Optimization, Statistics, and Computational Algebra. The main theorem on Chapter 2 concerns the computation of the \emph{toric ideal} $I_A$ of an integral $n \times d$ matrix $A$. We encode the binomials belonging to the toric ideal $I_A$ associated with $A$ using Barvinok's rational functions. If we fix $d$ and $n$, this representation allows us to compute a universal Gr\"obner basis and the reduced Gr\"obner basis of the ideal $I_A$, with respect to any term order, in polynomial time. We derive a polynomial time algorithm for normal form computations which replaces in this new encoding the usual reductions of the division algorithm. Chapter 3 presents three ways to use Barvinok's rational functions to solve Integer Programs. The second part of the thesis is experimental and consists mainly of the software package {\tt LattE}, the first implementation of Barvinok's algorithm. We report on experiments with families of well-known rational polytopes: multiway contingency tables, knapsack type problems, and rational polygons. We also developed a new algorithm, {\em the homogenized Barvinok's algorithm} to compute the generating function for a rational polytope. We showed that it runs in polynomial time in fixed dimension. With the homogenized Barvinok's algorithm, we obtained new combinatorial formulas: the generating function for the number of $5\times 5$ magic squares and the generating function for the number of $3\times 3 \times 3 \times 3$ magic cubes as rational functions.

Affiliated with

Also associated with

No associations

Rating

Barvinok's Rational Functions: Algorithms and Applications to Optimization, Statistics, and Algebra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Barvinok's Rational Functions: Algorithms and Applications to Optimization, Statistics, and Algebra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Barvinok's Rational Functions: Algorithms and Applications to Optimization, Statistics, and Algebra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-347235