[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Representation of constraints, generators and affine expressions

Format of vectors  


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

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):

The nature of a vector: constraint, generator, or affine expression, is inferred by the context. As you can guess, index 0 is used either to distinguish bidirectional or unidirectional vectors (0 or 1), either to put a denominator; index 1 is the \xi-coefficient, used for constants.

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

Don't ask me the intuitive meaning of s >= 0 in vertices !

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.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

This document was generated on October, 27 2006 using texi2html