Next: Main functions of Zpolyhedron.c Up: Z-Polyhedra Previous: Z-Polyhedra   Contents

# Theoretical background

Intuitively, -polyhedra are sparse polyhedra. They are used, for instance, to model iteration domains of loops with non unit stride.

Definition 4   (-polyhedron) A -polyhedron is the intersection of a polyhedron and an affine integral full dimensional lattice.

A -polyhedron can be defined as the image of a polyhedron by an invertible, integral function. Consider, for instance, the lattice and the polyhedron . Then is a -polyhedron (see figure ). can also be expressed as:

which is the image of polyhedron by the function . is obtained by taking the preimage of by the function defining the lattice: .

As Polylib operates on domains made out of unions of polyhedra, it is natural to define a similar object for -polyhedra. A -domain is a finite union of intersections between a domain and a full dimensionnal integral affine lattice. The set of -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 (). See [NRi00] for further detail on this subject.

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

Next: Main functions of Zpolyhedron.c Up: Z-Polyhedra Previous: Z-Polyhedra   Contents
Sorin Olaru 2002-04-24