IntegerPointDecomposition(zpoly) decomposes zpoly into pairwise disjoint Z-Polyhedral sets with additional algebraic properties that an arbitrary Z-polyhedron is unlikely to have. Those algebraic properties are specified in Definition 2 of the first reference listed below. They imply that such a Z-polyhedron, say zp, is consistent (that is, has at least one point) and is specializable. This latter property means that if x is the variable of lowest rank in zp and v is a possible value for x (that is, there exists at least one point of zp with v as x-coordinate) then all the points of zp with v as x-coordinate are given by specializing at x=v the system of linear inequalities defining zp.

The output option selects the return format. It can be given as:

output=latticeformat (the default). With this option, the Z-polyhedral sets constructed can use arbitrary lattices.

output=omegatestformat. With this option, Maple replaces the use of a lattice in each Z-polyhedron by using auxiliary variables, as in the Omega Test method of William Pugh; see the fourth reference below.

The algorithm behind IntegerPointDecomposition is described in the first two papers listed below and is inspired by the other three references.

Advanced problems can be found in the help page of ZPolyhedralSets. Those problems are taken from the literature (the fifth reference below) and illustrate the kind of applications that the command IntegerPointDecomposition can support. More elementary examples are shown below as well as in the help page of ZPolyhedralSet.

$\mathrm{with}\left(\mathrm{PolyhedralSets}\right)\:$

$\mathrm{with}\left(\mathrm{ZPolyhedralSets}\right)\:$

$\mathrm{ineqs}≔\left[0\le -16+2y+z\,0\le -72+4x+4y+3z\,0\le 2y-z\,0\le -24+4x+4y-3z\,0\le -4x+4y+3z\,0\le 48-4x+4y-3z\,0\le 48-4x-4y+3z\,0\le 8-2y+z\,0\le -24+4x-4y+3z\,0\le 24-2y-z\,0\le 24+4x-4y-3z\,0\le 96-4x-4y-3z\right]$

$\mathrm{ineqs}≔\left[0\le -16+2y+z\,0\le -72+4x+4y+3z\,0\le 2y-z\,0\le -24+4x+4y-3z\,0\le -4x+4y+3z\,0\le 48-4x+4y-3z\,0\le 48-4x-4y+3z\,0\le 8-2y+z\,0\le -24+4x-4y+3z\,0\le 24-2y-z\,0\le 24+4x-4y-3z\,0\le 96-4x-4y-3z\right]$

$L≔\mathrm{Lattice}\left(\mathrm{Matrix}\left(\left[\left[1\,0\,2\right]\,\left[0\,-1\,1\right]\,\left[0\,0\,2\right]\right]\right)\,\mathrm{Vector}\left(\left[0\,0\,1\right]\right)\right)$

$L≔\mathrm{Lattice}\left(\left[\begin{array}{ccc}1& 0& 2\\ 0& \mathrm{-1}& 1\\ 0& 0& 2\end{array}\right]\,\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]\right)$

$\mathrm{vars}≔\left[x\,y\,z\right]$

$\mathrm{vars}≔\left[x\,y\,z\right]$

$\mathrm{zps}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\mathrm{vars}\,':-\mathrm{lattice}'=L\right)$

$\mathrm{zps}≔\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}0\le 2y-z\\ 0\le -16+2y+z\\ 0\le 8-2y+z\\ 0\le 24-2y-z\\ 0\le -4x+4y+3z\\ 0\le -72+4x+4y+3z\\ 0\le -24+4x-4y+3z\\ 0\le -24+4x+4y-3z\\ 0\le 24+4x-4y-3z\\ 0\le 48-4x-4y+3z\\ 0\le 48-4x+4y-3z\\ 0\le 96-4x-4y-3z\end{array}\right.\\ \text{Variables}& \:& \left[x\,y\,z\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{ccc}1& 0& 2\\ 0& \mathrm{-1}& 1\\ 0& 0& 2\end{array}\right]\,\,\,\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]\right)\end{array}\right.$

$\mathrm{res}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{zps}\right)$

$\mathrm{res}≔\left[\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}z\le 9\\ -z\le \mathrm{-7}\\ -2y-z\le \mathrm{-16}\\ -2y+z\le 0\\ 2y-z\le 8\\ 2y+z\le 24\\ -4x-4y-3z\le \mathrm{-72}\\ -4x-4y+3z\le \mathrm{-24}\\ -4x+4y-3z\le \mathrm{-24}\\ -4x+4y+3z\le 24\\ 4x-4y-3z\le 0\\ 4x-4y+3z\le 48\\ 4x+4y-3z\le 48\\ 4x+4y+3z\le 96\end{array}\right.\\ \text{Variables}& \:& \left[x\,y\,z\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 2\end{array}\right]\,\,\,\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]\right)\end{array}\right.\,\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}x=9\\ y=6\\ z=11\end{array}\right.\\ \text{Variables}& \:& \left[x\,y\,z\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{cc}0& 0\\ 1& 0\\ 0& 2\end{array}\right]\,\,\,\left[\begin{array}{c}9\\ 0\\ 1\end{array}\right]\right)\end{array}\right.\,\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}x=9\\ y=6\\ z=5\end{array}\right.\\ \text{Variables}& \:& \left[x\,y\,z\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{cc}0& 0\\ 1& 0\\ 0& 2\end{array}\right]\,\,\,\left[\begin{array}{c}9\\ 0\\ 1\end{array}\right]\right)\end{array}\right.\right]$

$\mathrm{tt}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{res}\left[1\right]\,\mathrm{output}=\mathrm{omegatestformat}\right)$

$\mathrm{tt}≔\left[\left[\left[z=2\mathrm{\_Z3}+1\,2\mathrm{\_Z3}\le 8\,-2\mathrm{\_Z3}\le \mathrm{-6}\,-2y-2\mathrm{\_Z3}\le \mathrm{-15}\,-2y+2\mathrm{\_Z3}\le \mathrm{-1}\,2y-2\mathrm{\_Z3}\le 9\,2y+2\mathrm{\_Z3}\le 23\,-4x-4y-6\mathrm{\_Z3}\le \mathrm{-69}\,-4x-4y+6\mathrm{\_Z3}\le \mathrm{-27}\,-4x+4y-6\mathrm{\_Z3}\le \mathrm{-21}\,-4x+4y+6\mathrm{\_Z3}\le 21\,4x-4y-6\mathrm{\_Z3}\le 3\,4x-4y+6\mathrm{\_Z3}\le 45\,4x+4y-6\mathrm{\_Z3}\le 51\,4x+4y+6\mathrm{\_Z3}\le 93\right]\,\left[z\right]\,\left[\mathrm{\_Z3}\,x\,y\right]\right]\right]$

$\mathrm{res\_omegatestformat}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{zps}\,\mathrm{output}=\mathrm{omegatestformat}\right)$

$\mathrm{res\_omegatestformat}≔\left[\left[\left[z=2\mathrm{\_Z3}+1\,2\mathrm{\_Z3}\le 8\,-2\mathrm{\_Z3}\le \mathrm{-6}\,-2y-2\mathrm{\_Z3}\le \mathrm{-15}\,-2y+2\mathrm{\_Z3}\le \mathrm{-1}\,2y-2\mathrm{\_Z3}\le 9\,2y+2\mathrm{\_Z3}\le 23\,-4x-4y-6\mathrm{\_Z3}\le \mathrm{-69}\,-4x-4y+6\mathrm{\_Z3}\le \mathrm{-27}\,-4x+4y-6\mathrm{\_Z3}\le \mathrm{-21}\,-4x+4y+6\mathrm{\_Z3}\le 21\,4x-4y-6\mathrm{\_Z3}\le 3\,4x-4y+6\mathrm{\_Z3}\le 45\,4x+4y-6\mathrm{\_Z3}\le 51\,4x+4y+6\mathrm{\_Z3}\le 93\right]\,\left[z\right]\,\left[\mathrm{\_Z3}\,x\,y\right]\right]\,\left[\left[y=6\,x=9\,z=5\right]\,\left[y\,x\,z\right]\,\left[\right]\right]\,\left[\left[y=6\,x=9\,z=11\right]\,\left[y\,x\,z\right]\,\left[\right]\right]\right]$

Rui-Juan Jing and Marc Moreno Maza. "Computing the Integer Points of a Polyhedron, I: Algorithm." Proceedings of CASC 2017: 225-241, Springer.

Rui-Juan Jing and Marc Moreno Maza. "Computing the Integer Points of a Polyhedron, II: Complexity Estimates." Proceedings of CASC 2017: 242-256, Springer.

Rachid Seghir, Vincent Loechner, and Benoı̂t Meister. "Integer affine transformations of parametric Z-polytopes and applications to loop nest optimization." Proceedings of TACO, Vol. 9(2):8:1–8:27, 2012.

William Pugh. "The omega test: a fast and practical integer programming algorithm for dependence analysis." Proceedings Supercomputing ’91, pp 4–13. ACM, 1991.

William Pugh. "Counting solutions to presburger formulas: How and why." Proceedings of PLDI, pp 121–134. ACM, 1994.

The PolyhedralSets:-ZPolyhedralSets:-IntegerPointDecomposition command was introduced in Maple 2023.

For more information on Maple 2023 changes, see Updates in Maple 2023.