 Overview - Maple Help

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):$

Dependence analysis in Cholesky's LU algorithm from William Pugh's paper on Presburger arithmetic. We consider below one of the three cases that the Author distinguishes. 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 and deduce that there are no dependencies.

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

Example from Section 5.1 of William Pugh's paper on Presburger arithmetic.

 > $\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,x,y,N\right]$
 ${\mathrm{vars}}{≔}\left[{\mathrm{di}}{,}{\mathrm{dj}}{,}{i}{,}{j}{,}{x}{,}{y}{,}{N}\right]$ (5)
 > $\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs},\mathrm{vars}\right)$ Apply IntegerPointDecomposition and deduce the implied relations.

 > $\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 }{-3}\\ {-}{i}{\le }{-2}\\ {-}{j}{\le }{-2}\\ {-}{x}{\le }{-1}\\ {-}{y}{\le }{-1}\\ {i}{-}{N}{\le }{-1}\\ {j}{-}{N}{\le }{-1}\\ {-}{x}{-}{y}{\le }{-3}\\ {x}{-}{N}{\le }{0}\\ {-}{y}{+}{j}{\le }{1}\\ {y}{-}{N}{\le }{0}\\ {y}{-}{j}{\le }{1}\\ {-}{x}{-}{y}{+}{j}{\le }{-1}\\ {-}{x}{+}{y}{-}{N}{\le }{-2}\\ {-}{x}{+}{y}{-}{j}{\le }{-1}\\ {x}{-}{y}{-}{N}{\le }{-2}\\ {x}{+}{y}{-}{2}{}{N}{\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}{,}{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}{-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)

Calculation of cache access from William Pugh's paper on Presburger arithmetic.

 > $\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}{,}{-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]$ (7)
 > $\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]$ (8)
 > $\mathrm{zp}≔\mathrm{ZPolyhedralSet}\left(\mathrm{ineqs},\mathrm{vars}\right)$ Apply IntegerPointDecomposition and deduce the cache access patterns.

 > $\mathrm{IntegerPointDecomposition}\left(\mathrm{zp}\right)$
 $\left[\left\{\begin{array}{lll}{\text{Relations}}& {:}& \left\{\begin{array}{:}{\mathrm{di}}{=}{1}{-}{i}{+}{16}{}{x}\\ {\mathrm{dj}}{=}{y}{-}{j}\\ {-}{N}{\le }{-3}\\ {-}{i}{\le }{-2}\\ {-}{j}{\le }{-2}\\ {-}{x}{\le }{0}\\ {-}{y}{\le }{-1}\\ {i}{-}{N}{\le }{-1}\\ {j}{-}{N}{\le }{-1}\\ {-}{16}{}{x}{-}{y}{\le }{-2}\\ {16}{}{x}{-}{N}{\le }{-1}\\ {-}{y}{+}{j}{\le }{1}\\ {y}{-}{N}{\le }{0}\\ {y}{-}{j}{\le }{1}\\ {-}{16}{}{x}{-}{y}{+}{j}{\le }{0}\\ {-}{16}{}{x}{+}{y}{-}{N}{\le }{-1}\\ {-}{16}{}{x}{+}{y}{-}{j}{\le }{0}\\ {16}{}{x}{-}{y}{-}{N}{\le }{-3}\\ {16}{}{x}{+}{y}{-}{2}{}{N}{\le }{-2}\\ {-}{i}{+}{16}{}{x}{-}{y}{+}{j}{\le }{0}\\ {-}{i}{+}{16}{}{x}{+}{y}{-}{j}{\le }{0}\\ {i}{-}{16}{}{x}{-}{y}{+}{j}{\le }{2}\\ {i}{-}{16}{}{x}{+}{y}{-}{j}{\le }{2}\\ {16}{}{x}{-}{y}{+}{j}{-}{N}{\le }{-1}\\ {16}{}{x}{+}{y}{-}{j}{-}{N}{\le }{-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}{-1}& {0}& {0}& {16}& {0}\\ {0}& {-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]$ (9) 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.