The ZPolyhedralSets subpackage of the PolyhedralSets package is a collection of commands for computing with Z-polyhedral sets.

A Z-polyhedral set is the intersection of a polyhedral set with an integer lattice. (A Z-polytope is the intersection of a polytope with an integer lattice; a polytope is a bounded polyhedral set.)

The functionalities of this package offer tools to construct, visualize and study Z-polyhedral sets.

The commands Lattice and ZPolyhedralSet build integer lattices and Z-polyhedral sets.

The command IsContained is an inclusion-test for sets of Z-polyhedral sets.

The command IsEmpty checks whether a Z-Polyhedral set is empty.

The command IsIntegerPointOf checks whether a given integer point belongs to a given a Z-Polyhedral set.

The command SamplePoint returns one point of a non-empty Z-Polyhedral set.

The command EnumerateIntegerPoints enumerates the points of a bounded Z-Polyhedral set.

The command PlotIntegerPoints3d plots the points of a bounded three-dimensional Z-Polyhedral set.

The command IntegerPointDecomposition is at the core of this package: it decomposes a given Z-polyhedral set into Z-polyhedral sets with additional properties (such as consistency and good specialization).

The examples below are advanced problems taken from the literature (see the fourth reference below). They illustrate the kind of applications that this package can support.

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

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

$\mathrm{vars}≔\left[i\,j\,k\,\mathrm{i1}\,\mathrm{j1}\,n\right]$

$\mathrm{vars}≔\left[i\,j\,k\,\mathrm{i1}\,\mathrm{j1}\,n\right]$

$\mathrm{ineqs}≔\left[j\=\mathrm{j1}\,k\=\mathrm{i1}\,0\le i\,i\le n\,i\+1\le j\,j\le n\,1\le k\,k\le i-1\,0\le \mathrm{i1}\,\mathrm{i1}\le n\,\mathrm{i1}\+1\le \mathrm{j1}\,\mathrm{j1}\le n\,i\le \mathrm{i1}-1\right]$

$\mathrm{ineqs}≔\left[j=\mathrm{j1}\,k=\mathrm{i1}\,0\le i\,i\le n\,i+1\le j\,j\le n\,1\le k\,k\le i-1\,0\le \mathrm{i1}\,\mathrm{i1}\le n\,\mathrm{i1}+1\le \mathrm{j1}\,\mathrm{j1}\le n\,i\le \mathrm{i1}-1\right]$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\mathrm{vars}\right)$

$\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$

$\mathrm{ineqs}≔\left[x\=i\+\mathrm{di}\,y\=j\+\mathrm{dj}\,2\le i\,i\le N-1\,2\le j\,j\le N-1\,-1\le \mathrm{di}\+\mathrm{dj}\,\mathrm{di}-\mathrm{dj}\le 1\,\mathrm{di}\+\mathrm{dj}\le 1\,-1\le \mathrm{di}-\mathrm{dj}\right]$

$\mathrm{ineqs}≔\left[x=i+\mathrm{di}\,y=j+\mathrm{dj}\,2\le i\,i\le N-1\,2\le j\,j\le N-1\,\mathrm{-1}\le \mathrm{di}+\mathrm{dj}\,\mathrm{di}-\mathrm{dj}\le 1\,\mathrm{di}+\mathrm{dj}\le 1\,\mathrm{-1}\le \mathrm{di}-\mathrm{dj}\right]$

$\mathrm{vars}≔\left[\mathrm{di}\,\mathrm{dj}\,i\,j\,x\,y\,N\right]$

$\mathrm{vars}≔\left[\mathrm{di}\,\mathrm{dj}\,i\,j\,x\,y\,N\right]$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\mathrm{vars}\right)$

$\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$

$\left[\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}\mathrm{di}=x-i\\ \mathrm{dj}=y-j\\ -N\le \mathrm{-3}\\ -i\le \mathrm{-2}\\ -j\le \mathrm{-2}\\ -x\le \mathrm{-1}\\ -y\le \mathrm{-1}\\ i-N\le \mathrm{-1}\\ j-N\le \mathrm{-1}\\ -x-y\le \mathrm{-3}\\ x-N\le 0\\ -y+j\le 1\\ y-N\le 0\\ y-j\le 1\\ -x-y+j\le \mathrm{-1}\\ -x+y-N\le \mathrm{-2}\\ -x+y-j\le \mathrm{-1}\\ x-y-N\le \mathrm{-2}\\ x+y-2N\le \mathrm{-1}\\ -x+i-y+j\le 1\\ -x+i+y-j\le 1\\ x-i-y+j\le 1\\ x-i+y-j\le 1\\ x-y+j-N\le 0\\ x+y-j-N\le 0\end{array}\right.\\ \text{Variables}& \:& \left[\mathrm{di}\,\mathrm{dj}\,i\,j\,x\,y\,N\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{ccccc}\mathrm{-1}& 0& 1& 0& 0\\ 0& \mathrm{-1}& 0& 1& 0\\ 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\end{array}\right]\,\,\,\left[\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right]\right)\end{array}\right.\right]$

$\mathrm{ineqs}≔\left[y\=j\+\mathrm{dj}\,0\le \frac{i\+\mathrm{di}-1}{16}-x\,\frac{i\+\mathrm{di}-1}{16}-x\le 0\,2\le i\,j\le N-1\,i\le N-1\,2\le j\,-1\le \mathrm{di}\+\mathrm{dj}\,\mathrm{di}\+\mathrm{dj}\le 1\,-1\le \mathrm{di}-\mathrm{dj}\,\mathrm{di}-\mathrm{dj}\le 1\right]$

$\mathrm{ineqs}≔\left[y=j+\mathrm{dj}\,0\le \frac{i}{16}+\frac{\mathrm{di}}{16}-\frac{1}{16}-x\,\frac{i}{16}+\frac{\mathrm{di}}{16}-x\le \frac{1}{16}\,2\le i\,j\le N-1\,i\le N-1\,2\le j\,\mathrm{-1}\le \mathrm{di}+\mathrm{dj}\,\mathrm{di}+\mathrm{dj}\le 1\,\mathrm{-1}\le \mathrm{di}-\mathrm{dj}\,\mathrm{di}-\mathrm{dj}\le 1\right]$

$\mathrm{vars}≔\left[\mathrm{di}\,\mathrm{dj}\,i\,j\,y\,x\,N\right]$

$\mathrm{vars}≔\left[\mathrm{di}\,\mathrm{dj}\,i\,j\,y\,x\,N\right]$

$\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs}\,\mathrm{vars}\right)$

$\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$

$\left[\left\{\begin{array}{lll}\text{Relations}& \:& \left\{\begin{array}{:}\mathrm{di}=1-i+16x\\ \mathrm{dj}=y-j\\ -N\le \mathrm{-3}\\ -i\le \mathrm{-2}\\ -j\le \mathrm{-2}\\ -x\le 0\\ -y\le \mathrm{-1}\\ i-N\le \mathrm{-1}\\ j-N\le \mathrm{-1}\\ -16x-y\le \mathrm{-2}\\ 16x-N\le \mathrm{-1}\\ -y+j\le 1\\ y-N\le 0\\ y-j\le 1\\ -16x-y+j\le 0\\ -16x+y-N\le \mathrm{-1}\\ -16x+y-j\le 0\\ 16x-y-N\le \mathrm{-3}\\ 16x+y-2N\le \mathrm{-2}\\ -i+16x-y+j\le 0\\ -i+16x+y-j\le 0\\ i-16x-y+j\le 2\\ i-16x+y-j\le 2\\ 16x-y+j-N\le \mathrm{-1}\\ 16x+y-j-N\le \mathrm{-1}\end{array}\right.\\ \text{Variables}& \:& \left[\mathrm{di}\,\mathrm{dj}\,i\,j\,y\,x\,N\right]\\ \text{Parameters}& \:& \left[\right]\\ \text{ParameterConstraints}& \:& \left\{\begin{array}{}\end{array}\right.\\ \text{Lattice}& \:& \text{ZSpan}\left(\left[\begin{array}{ccccc}\mathrm{-1}& 0& 0& 16& 0\\ 0& \mathrm{-1}& 1& 0& 0\\ 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\end{array}\right]\,\,\,\left[\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right]\right)\end{array}\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 package was introduced in Maple 2023.

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