Representation of constraints, generators and affine expressions

Coefficients
Format of vectors

Coefficients

Normally we shoud use rational numbers for coefficients of vectors and matrices. avis98b observed experimentally in a very similar context that using a common denominator for all coefficients of a vector or of a matrix row is more efficient, probably because vector combination is easier. wilde93 uses also the same technique.

To avoid overflow problem, multi-precision integers are needed; their drawback is obviously the loss of speed. As a consequence, we have defined a generic interface for integers and the compile-time option allows to deal with either

• multi-precision integers; we use for that the GNU Multi Precision library (GMP), which reveals very efficient according to K. Fukuda's home page;
• normal machine integers (32 or 64 bits long int's), with at this time no overflow check;
• and long long int's, introduced by the new ANSI C 99 standard and allowed by gcc and some others compilers.

The type pkint_t is supposed to provide conversion operators from machine int to type pkint_t. You should look at file `gint.nw' for details.

Format of frames, generators and affine expressions

As in wilde93 we reserve a particular treatment for equality constraints, instead of considering them as two opposed inequalities, because more efficient methods are available for example to minimize them (gauss pivot). Dually, we distinguish for generators bidirectionnal lines from normal rays.

The format of objects depends if the library has been opened with the strict option or not. We note d the dimension of affine polyhedra, i.e., the number of dimensions different of \xi and \epsilon.

If the strict option is unset (no strict inequalities):

• [0,b,a_0,...,a_{d-1}] represents the equality constraint
  a_0 x_0 + ... + a_{d-1} x_{d-1} + b = 0;
• [1,b,a_0,...,a_{d-1}] represents the inequality constraint
  a_0 x_0 + ... + a_{d-1} x_{d-1} + b >= 0;
• [0,0,a_0,...,a_{d-1}] represents the line of direction (a_0,...,a_{d-1});
• [1,0,a_0,...,a_{d-1}] represents the ray of direction (a_0,...,a_{d-1});
• [1,b,a_0,...,a_{d-1}] represents the vertex (a_0/b,...,a_{d-1}/b);
• [d,b,a_0,...,a_{d-1}] represents the affine expression
  x ==> a_0/d x_0 + ... + a_{d-1}/d x_{d-1} + b/d;

If the strict option is set (strict inequalities), an additionnal dimension is introduced at index 2 to put \epsilon-coefficients:

• [0,b,0,a_0,...,a_{d-1}] represents the equality constraint
  a_0 x_0 + ... + a_{d-1} x_{d-1} + b = 0;
• [1,b,0,a_0,...,a_{d-1}] represents the inequality constraint
  a_0 x_0 + ... + a_{d-1} x_{d-1} + b >= 0;
• [1,b,-s,a_0,...,a_{d-1}] where s>0 represents the inequality constraint
  a_0 x_0 + ... + a_{d-1} x_{d-1} + b > 0;
• [0,0,0,a_0,...,a_{d-1}] represents the line of direction (a_0,...,a_{d-1});
• [1,0,0,a_0,...,a_{d-1}] represents the ray of direction (a_0,...,a_{d-1});
• [1,b,s,a_0,...,a_{d-1}] where s>=0 represents the vertex
  (s/b)|(a_0/b,...,a_{d-1}/b);
• [den,b,0,a_0,...,a_{d-1}] represents the affine expression
  x ==> a_0/den x_0 + ... + a_{d-1}/den x_{d-1} + b/den;

If a vector is given without matching a suitable format, depending on its nature, the results are unpredictable. That's come from the fact that the library uses the assumption \xi >= 0 and possibly \epsilon >= 0 to decide wether a polyhedron is empty or not.

The constraint \xi >= 0 (\xi >= \epsilon wit strict option) is called the positivity constraint, and the constraint \epsilon >= 0 the strictness constraint.

To make more easy a certain form of genericity, the library offers variables bool polka_strict and int polka_dec that memorized respectively the operation mode (strict or non strict) and the index of the first "normal" coefficient (2 or 3). The index of the constant coefficient is in any case 1.