Overview - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Overview of the ZPolyhedralSets Subpackage

 Calling Sequence ZPolyhedralSets:-command(arguments) command(arguments)

Description

 • 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.

Examples

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

This first problem considers dependence anaysis in Cholesky's LU algorithm. See the image below, taken from William Pugh's paper on Presburger arithmetic. One objective of this problem is to decide whether the studied code can be parallelized. This is achieved by checking whether the same memory location is accessed by two statements (or more), at least once while writing.

For example, is there an an array slot read by Line 5 at some iteration $\left(i,j,k\right)$ before being written in Line 6 at some iteration $\left(i\prime ,j\prime ,k\prime \right)$. Answering this particular question is done by solving for the integer solutions of a system of linear equations and inequalities. Three cases need to be distinguished: (1) $i, (2) $i=i\prime$ and $j, and (3) $i=i\prime$ and $j=j\prime$.

The system below corresponds to the first case. The other two cases are treated similarly.

 > $\mathrm{vars}≔\left[i,j,k,\mathrm{i1},\mathrm{j1},n\right]$
 ${\mathrm{vars}}{≔}\left[{i}{,}{j}{,}{k}{,}{\mathrm{i1}}{,}{\mathrm{j1}}{,}{n}\right]$ (1)
 > $\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]$ (2)
 > $\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs},\mathrm{vars}\right)$

We apply IntegerPointDecomposition. Since no integer points are found, we deduce that there are no dependencies.

 > $\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$
 $\left[\right]$ (3)

The second problem considers memory accesses by a for-loop nest. See the image below, taken from William Pugh's paper on Presburger arithmetic.

One objective of this problem is to describe analytically the set of accessed memory locations as a function of the loop bound $N$. Describing this set is done by setting up a system of linear equations and inequalities and eliminating the intermediate (and unnecessary) variables.  In the system below those intermediate variables (to be eliminated) are $i,j,\mathrm{di},\mathrm{dj}$, whereas $x,y,N$ are seen as parameters.

 > $\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}{,}{-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]$ (4)
 > $\mathrm{vars}≔\left[\mathrm{di},\mathrm{dj},i,j\right];$$\mathrm{params}≔\left[x,y,N\right]$
 ${\mathrm{vars}}{≔}\left[{\mathrm{di}}{,}{\mathrm{dj}}{,}{i}{,}{j}\right]$
 ${\mathrm{params}}{≔}\left[{x}{,}{y}{,}{N}\right]$ (5)
 > $\mathrm{pzp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs},\mathrm{vars},':-\mathrm{parameters}'=\mathrm{params}\right)$

Applying IntegerPointDecomposition  we obtain necessary and sufficient constraints for the system to have integer solutions.

 > $\mathrm{ipd}≔\mathrm{IntegerPointDecomposition}\left(\mathrm{pzp}\right)$
 ${\mathrm{ipd}}{≔}\left[\left\{\begin{array}{lll}{\text{Relations}}& {:}& \left\{\begin{array}{:}{\mathrm{di}}{=}{x}{-}{i}\\ {\mathrm{dj}}{=}{y}{-}{j}\\ {-}{i}{\le }{-2}\\ {-}{j}{\le }{-2}\\ {i}{-}{N}{\le }{-1}\\ {j}{-}{N}{\le }{-1}\\ {-}{y}{+}{j}{\le }{1}\\ {y}{-}{j}{\le }{1}\\ {-}{x}{-}{y}{+}{j}{\le }{-1}\\ {-}{x}{+}{y}{-}{j}{\le }{-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}\right]\\ {\text{Parameters}}& {:}& \left[{x}{,}{y}{,}{N}\right]\\ {\text{ParameterConstraints}}& {:}& \left\{\begin{array}{:}{-}{N}{\le }{-3}\\ {-}{x}{\le }{-1}\\ {-}{y}{\le }{-1}\\ {-}{x}{-}{y}{\le }{-3}\\ {x}{-}{N}{\le }{0}\\ {y}{-}{N}{\le }{0}\\ {-}{x}{+}{y}{-}{N}{\le }{-2}\\ {x}{-}{y}{-}{N}{\le }{-2}\\ {x}{+}{y}{-}{2}{}{N}{\le }{-1}\end{array}\right\\\ {\text{Lattice}}& {:}& {\text{ZSpan}}\left(\left[\begin{array}{ccccc}{-1}& {0}& {1}& {0}& {0}\\ {0}& {-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]$ (6)

Those constraints form the desired answer. We note that they define a Z-polyhedral set, which is two-dimensional in the variables $x$ and $y$, as well as parametric in $N$.

 > $\mathrm{GetParametersConstraints}\left(\mathrm{ipd}\left[1\right]\right)$
 $\left[{-}{N}{\le }{-3}{,}{-}{x}{\le }{-1}{,}{-}{y}{\le }{-1}{,}{-}{x}{-}{y}{\le }{-3}{,}{x}{-}{N}{\le }{0}{,}{y}{-}{N}{\le }{0}{,}{-}{x}{+}{y}{-}{N}{\le }{-2}{,}{x}{-}{y}{-}{N}{\le }{-2}{,}{x}{+}{y}{-}{2}{}{N}{\le }{-1}\right]$ (7)

References

 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.

Compatibility

 • The PolyhedralSets:-ZPolyhedralSets package was introduced in Maple 2023.
 • For more information on Maple 2023 changes, see Updates in Maple 2023.