Short rational functions for toric algebra and applications

DOI10.1016/J.JSC.2004.02.001MaRDI QIDQ2643547zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

lattice pointsHilbert seriesEhrhart polynomialBarvinok's algorithmtoric idealsmagic cubes and squaresshort rational functionGröbner basis

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)

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.

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

Cites work

• scientific article; zbMATH DE number 108068 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1565322 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• scientific article; zbMATH DE number 2209709 (Why is no real title available?)
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Combinatorics and commutative algebra.
• Effective lattice point counting in rational convex polytopes
• Integer programming, Barvinok's counting algorithm and Gomory relaxations.
• Short rational generating functions for lattice point problems
• The Gröbner fan of an ideal

Cited in

(18)

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

Describes a project that uses

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)