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

Coefficients 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

- 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.

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.

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

This document was generated on