Go to the previous, next section.

`i = ~A`

- Check if there does not exist an integer solution to the given system of
inequalities.
`i`is set to TRUE if NO SOLUTION and returns FALSE if a solution exists to the system of inequalities. `i = (A == B)`

`i`is set to TRUE if both systems of inequalities represent the same set of integer points.`i = (A >> B)`

- This is the subset or
*"is contained?"*operator. It checks if all the integer points given by the set of inequalities of`B`are also included in the polyhedron defined by the system of inequalities`A`. `i = col_lcm(j);`

- Find the least common multiplier of all the numbers in the
`j`-th column. `i = col_gcd(j);`

- Find the greatest common divider of all the numbers in the
`j`-th column. `normalize();`

- Normalize the inequalities by dividing each inequality by the gcd. In
`normalize(TRUE)`

the constant term of each inequality is adjusted to make the bounds tight without changing the integer solution. `del_zeros();`

- Remove the rows that have all zero values. If the coefficient values and the
constant of a constraint are all zeros, it represents
`0 >= 0`, thus void of any information. `del_unused_var();`

- Each column (other than the first) represents coefficients of a variable. If no non-zero coefficient exists for a variable (the column is all zeros) remove that variable from the system. Since no inequality uses this variable, getting rid of that variable does not change the problem.
`del_repetition();`

- If the same inequality is repeated multiple times, get rid of all the copies but one.
`del_loose();`

- If two inequalities have similar coefficients but have different constant terms, eliminate the slacker inequality.
`min_constant();`

- ...
`max_rank();`

- Position of the rightmost column that has a non-zero element.
`A = B.filter(a, i, j);`

`A = B.filter_thru(a, i);`

`A = B.filter_away(a, i);`

``Filter'`functions are used to filter a subset of inequalities from a given set of inequalities. The filter kernel`a`has an entry for each column of`B`. If`a[x]`is 0 the column`x`does not affect the results while a 1 makes that column active. The variable`i`is the sign of the participating coefficients. If`i`is 0, all active columns with non-zero coefficients participate; if`i`is 1, only the active columns with positive coefficients participate;`i`is -1, only the active columns with negative coefficient participate. Finally the variable`j`in the function`filter`

determines the filter operation. If`j`is 1 the operation is`filter_thru`

and when`j`is -1 the operation is`filter_away`

.Let's look at an example loop nest.

for i1 = 0 to N do for i2 = 0 to MIN(i1, N) do for i3 = 1 to MIN(i2, N-1) do for i4 = 0 to 100 do ...

The set of inequalities representing this loop nest is:

// N i1 i2 i3 i4 [ 0 0 1 0 0 0 ] [ 0 1 -1 0 0 0 ] [ 0 0 0 1 0 0 ] A = [ 0 0 1 -1 0 0 ] [ 0 1 0 -1 0 0 ] [ -1 0 0 0 1 0 ] [ 0 0 0 1 -1 0 ] [ 1 1 0 0 -1 0 ] [ 0 0 0 0 0 1 ] [ 100 0 0 0 0 -1 ]

Let's see how to extract the lower and upper bounds of the loop

`i2`from the system of inequalities`A`.constraint c(6); // First remove all the inequalities representing // the bounds of inner loops (

`i3`and`i4`). This step // will remove the 7th inequality where`i2`is in // the bounds of`i3`. c = 0; c[4] = 1 c[5] = 1 // c =[ 0 0 0 0 1 1 ] B = A.filter_away(c, 0); // [ 0 0 1 0 0 0 ] // [ 0 1 -1 0 0 0 ] // B = [ 0 0 0 1 0 0 ] // [ 0 0 1 -1 0 0 ] // [ 0 1 0 -1 0 0 ] // Now get the inequalities that represent the bounds // of`i2`. After the previous step, all the inequalities // with a non-zero coefficient for`i2`represents a // bound for the`i2`loop. c = 0; c[3] = 1 // c = [ 0 0 0 1 0 0 ] LB = B.filter_thru(c, 1); // The lower bound of the loop i2 is: // LB = [ 0 0 0 1 0 0 ] UB = B.filter_thru(c, -1); // The upper bound of the loop i2 is: // UB = [ 0 0 1 -1 0 0 ] // [ 0 1 0 -1 0 0 ]

Go to the previous, next section.