Theoretical background

Intuitively, ${{\cal Z}}$-polyhedra are sparse polyhedra. They are used, for instance, to model iteration domains of loops with non unit stride.

Definition 4   (${{\cal Z}}$-polyhedron) A ${{\cal Z}}$-polyhedron is the intersection of a polyhedron and an affine integral full dimensional lattice.

A ${{\cal Z}}$-polyhedron can be defined as the image of a polyhedron by an invertible, integral function. Consider, for instance, the lattice $L_1 = \{2i+1, 3j+5\ \vert\ i,j \in {\cal Z}\}$ and the polyhedron $Q_1= \{i,j\ \vert\ 0 \leq i \leq 5 ,0 \leq 3j \leq 20 \}$. Then $Z_1 = L_1 \cap Q_1$ is a ${{\cal Z}}$-polyhedron (see figure ). $Z_1$ can also be expressed as:

$$Z_1 = \{2i+1, 3j+5 ~\vert~ -1\leq 2i \leq 4, -15 \leq 9j \leq 5 \}\quad,$$

which is the image of polyhedron $Q_2=\{i,j\vert -1\leq 2i \leq 4,-15 \leq 9j \leq 5 \}$ by the function $(i,j\rightarrow 2i+1, 3j+5)$. $Q_2$ is obtained by taking the preimage of $Q_1$ by the function defining the lattice: $(i,j\rightarrow 2i+1, 3j+5)$.

Figure: example of polyhedron $Q_1= \{i,j\ \vert\ 0 \leq i \leq 5 ,0 \leq 3j \leq 20 \}$, lattice $L_1 = \{2i+1, 3j+5\ \vert\ i,j \in {\cal Z}\}$ and ${{\cal Z}}$-polyhedron $Z_1=Q_1\cap L_1$ (the dotted line represent the shape of the original rational polyhedron).

As Polylib operates on domains made out of unions of polyhedra, it is natural to define a similar object for ${{\cal Z}}$-polyhedra. A ${{\cal Z}}$-domain is a finite union of intersections between a domain and a full dimensionnal integral affine lattice. The set of ${{\cal Z}}$-domains is closed under union, intersection, difference, and image by integral invertible function.

The image and pre-image by rational functions is also implemented in Polylib, but the result of the image (or pre-image) is always intersected with the canonical lattice (${\cal Z}^n$). See [NRi00] for further detail on this subject.

From the implementation point of view, a ${{\cal Z}}$-polyhedron is represented internally as the image of a polyhedron by an affine, invertible mapping. Hence, storing a ${{\cal Z}}$-polyhedron amounts to storing a domain and a matrix.