A new and faster representation for counting integer points in parametric polyhedra

In this paper, we consider the counting function $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y) = |{{\,\mathrm{\mathcal {P}}\,}}_{y} \cap {{\,\mathrm{\mathbb {Z}}\,}}^{n_x}|$$ E P ( y ) = | P y ∩ Z n x | for a parametric polyhedron $${{\,\mathrm{\mathcal {P}}\,}}_{y} = \{ x \in {{\,\mathrm{\mathbb {R}}\,}}^{n_x} :A x \le b + B y\}$$ P y = { x ∈ R n x : A x ≤ b + B y } , where $$y \in {{\,\mathrm{\mathbb {R}}\,}}^{n_y}$$ y ∈ R n y . We give a new representation of $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) , called a piece-wise step-polynomial with periodic coefficients, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart’s quasi-polynomials. It gives the fastest way to calculate $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) in certain scenarios. The most important cases are the following: 1) We show that, for the parametric polyhedron $${{\,\mathrm{\mathcal {P}}\,}}_y$$ P y defined by a standard-form system $$A x = y,\, x \ge 0$$ A x = y , x ≥ 0 with a fixed number of equalities, the function $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) can be represented by a polynomial-time computable function. In turn, such a representation of $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$ E P ( y ) can be constructed by an $${{\,\textrm{poly}\,}}\bigl (n, \Vert A\Vert _{\infty }\bigr )$$ poly ( n , ‖ A ‖ ∞ ) -time algorithm; 2) Assuming again that the number of equalities is fixed, we show that integer/rational Ehrhart’s quasi-polynomials of a polytope can be computed by FPT-algorithms, parameterized by sub-determinants of A or its elements; 3) Our representation of $${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}$$ E P is more efficient than other known approaches, if A has bounded elements, especially if it is sparse in addition; Additionally, we provide a discussion about possible applications in the area of compiler optimization. In some “natural” assumptions on a program code, our approach has the fastest complexity bounds.