## Abstract

We encode the binomials belonging to the toric ideal I_{A} associated with an integral d×n matrix A using a short sum of rational functions as introduced by Barvinok (Math. Operations Research 19 (1994) 769) and Barvinok and Woods (J. Amer. Math. Soc. 16 (2003) 957). Under the assumption that d and n are fixed, this representation allows us to compute a universal Gröbner basis and the reduced Gröbner basis of the ideal I_{A}, with respect to any term order, in time polynomial in the size of the input. We also derive a polynomial time algorithm for normal form computations which replaces in this new encoding the usual reductions typical of the division algorithm. We describe other applications, such as the computation of Hilbert series of normal semigroup rings, and we indicate applications to enumerative combinatorics, integer programming, and statistics.

Original language | English |
---|---|

Pages (from-to) | 959-973 |

Number of pages | 15 |

Journal | Journal of Symbolic Computation |

Volume | 38 |

Issue number | 2 |

DOIs | |

State | Published - Aug 2004 |

Externally published | Yes |

## Keywords

- Barvinok's algorithm
- Ehrhart polynomial
- Gröbner basis
- Hilbert series
- Lattice points
- Magic cubes and squares
- Short rational function
- Toric ideals