Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleShort rational functions for toric algebra and applications
Author(s) Jesus A. de Loera, D. Haws, Raymond Hemmecke, P. Huggins, Bernd Sturmfels, R. Yoshida
TypeArticle in Journal
AbstractWe encode the binomials belonging to the toric ideal IA 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 IA, 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.
KeywordsGröbner basis, Toric ideals, Hilbert series, Short rational function, Barvinok’s algorithm, Ehrhart polynomial, Lattice points, Magic cubes and squares
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717104000252
LanguageEnglish
JournalJournal of Symbolic Computation
Volume38
Number2
Pages959 - 973
Year2004
Edition0
Translation No
Refereed No
Webmaster