Short rational functions for toric algebra and applications

DOI10.1016/J.JSC.2004.02.001zbMATH Open1137.13316arXivmath/0307350OpenAlexW1972231647MaRDI QIDQ2643547FDOQ2643547

Authors: Raymond Hemmecke, Bernd Sturmfels, Ruriko Yoshida, Jesús A. De Loera, David C. Haws, Peter Huggins 

Publication date: 24 August 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We encode the binomials belonging to the toric ideal $I_A$ associated with an integral $dimesn$ matrix $A$ using a short sum of rational functions as introduced by Barvinok cite{bar,newbar}. Under the assumption that $d,n$ are fixed, this representation allows us to compute the Graver basis and the reduced Gr"obner 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 computation 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 further connections to integer programming and statistics.

Full work available at URL: https://arxiv.org/abs/math/0307350

Recommendations

• Rational approximations on toric varieties
• The short toric polynomial
• The short toric polynomial
• On the algebraic tori over some function fields
• Approximating rational points on toric varieties
• Hypergeometric functions and toric varieties
• Stably rational algebraic tori
• Function fields of algebraic tori revisited
• Torsors and rational points

zbMATH Keywords

lattice points[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go Gr��bner basis]Hilbert seriesEhrhart polynomialBarvinok's algorithmtoric idealsmagic cubes and squaresshort rational function

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• Effective lattice point counting in rational convex polytopes
• Title not available (Why is that?)
• Combinatorics and commutative algebra.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• The Gröbner fan of an ideal
• Short rational generating functions for lattice point problems
• Integer programming, Barvinok's counting algorithm and Gomory relaxations.
• Title not available (Why is that?)

Cited In (19)

• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• Effective lattice point counting in rational convex polytopes
• A new complexity result on multiobjective linear integer programming using short rational generating functions
• Two-stage quadratic integer programs with stochastic right-hand sides
• A mathematical programming approach to the computation of the omega invariant of a numerical semigroup
• Presburger arithmetic, rational generating functions, and quasi-polynomials
• Normal toric ideals of low codimension
• Counting numerical semigroups with short generating functions.
• Minimal invariant Markov basis for sampling contingency tables with fixed marginals
• The many aspects of counting lattice points in polytopes
• A computational study of integer programming algorithms based on Barvinok's rational functions
• Hypergraph encodings of arbitrary toric ideals
• Short rational generating functions for solving some families of fuzzy integer programming problems
• Polyhedral omega: a new algorithm for solving linear Diophantine systems
• Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach
• Generalized reduction to compute toric ideals
• Learning a performance metric of Buchberger's algorithm
• Ehrhart polynomials of matroid polytopes and polymatroids
• The short toric polynomial

Uses Software

• LattE

This page was built for publication: Short rational functions for toric algebra and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643547)