2023/10/20 by D. Gribanov, D. S. Malyshev, Gribanov, D. +4 · 2 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2310.13788
In this paper, we consider the counting function EP(y) = |Py ∩ Znx| for a parametric polyhedron Py = \x ∈ Rnx \colon A x ≤ b + B y\, where y ∈ Rny. We give a new representation of EP(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 EP(y) in certain scenarios. The most important cases are the following: 1) We show that, for the parametric polyhedron Py defined by a standard-form system A x = y, x ≥ 0 with a fixed number of equalities, the function EP(y) can be represented by a polynomial-time computable function. In turn, such a representation of EP(y) can be constructed by an 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 EP 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.