Polyhedral Process Networks - Signal Processing Systems - page 1323

$ isl_pip --format=affine
[N]->{:}
-1
[N] -> { S1[i] : exists a : 0 <= i < N and i = 3 a }
Maximize
The first line invokes isl pip . The remaining lines represent the input. The first
line of the input is the parameter domain. The second line is always -1 and is only
present for compatibility with the original pip application. The third line is the
actual input set and the last line specifies that we want to compute the lexicographic
maximum. (By default, isl pip will compute the lexicographic minimum.) The
output is as follows.

[N] -> { S1[(-3 + 3 * [(2 + N)/3])] : N >= 1 }
no solution: [N] -> { : N <= 0 }
Note that the · operation is represented using square brackets.

Note that Operation 1 can be used to compute an explicit representation of the
existentially quantified variables. As an alternative to Operation 1 , the lexicographic
maximum can be computed using Omega [ 12 ] , 4 by expressing the lexicographic
order in ( 9 ) using linear constraints, as in ( 5 ) . However, the result will not
necessarily satisfy the two conditions of Operation 1 .

4.2 Emptiness Check

A very basic and frequently used operation is that of checking whether a given
polyhedral set or relation contains any elements for any value of the parameters.

Operation 2 (Emptiness Check).
Input: a polyhedral relation R :

→ Σ × Z

d 1 → Σ × Z d 2 → B n

Z

n : R

Output: true if 0 and false otherwise

Operation 2 can be performed by applying Operation 1 (Partial Lexicographic
Maximum) on each of the basic polyhedral sets in a polyhedral set S

∀ s ∈ Z ( s )=

d 2
with the same description as R , but where all parameters and input variables are
treated as set variables. The relation R is empty iff S is empty iff in turn none of the
basic polyhedral sets has a lexicographically maximal element. Since S is (a union
of) integer linear programming (ILP) problem(s), any other algorithm for testing the
feasibility of an ILP problem will work as well. For example, isl uses generalized
basis reduction [ 4 ] .

n + d 1 +

∈ Z

4 http://www.chunchen.info/omega/