Utilisation du programme de calcul des polynômes d'Ehrhart
 des sommets paramétriques et de leurs domaines de validité

Philippe Clauss, Vincent Loechner et Doran Wilde
********************************************************************

L'entrée du programme est un système d'équations ou d'inéquations
où le membre de droite est toujours nul de la forme

a1 x1 + a2 x2 + ... + an xn + b1 n1 + b2 n2 + ... + bm nm + c = 0

ou

a1 x1 + a2 x2 + ... + an xn + b1 n1 + b2 n2 + ... + bm nm + c >= 0


Dans la suite, nous appelons ces équations ou inéquations des contraintes. Cette 
entrée doit être saisie dans un fichier de type texte selon le format suivant :

- Les contraintes peuvent être données en 2 matrices : la première constituée 
des contraintes portant sur les variables x1, x2, ..., la deuxième constituée 
des contraintes portant uniquement sur les paramètres. Toutefois, cette
deuxième matrice peut être omise et inclue dans la première.

- Chaque matrice doit être précédée de deux entiers indiquant respectivement
le nombre de lignes et le nombre de colonnes de la matrice.

- Dans chaque matrice, une ligne commençant par 0 (zéro) indique une
contrainte d'égalité, une ligne commençant par 1 (un) indique une contrainte 
d'inégalité dans le sens supérieur ou égal (>=).

- Les valeurs entières sur une ligne qui suivent la valeur 0 ou 1 doivent être
ordonnées pour correspondre d'abord aux coefficients des variables dans les 
contraintes (a1, ..., an, dans un ordre prédéfini des variables), puis aux 
coefficients des paramètres dans les contraintes (b1, ..., bm, dans un ordre 
prédéfini des paramètres), puis au coefficient constant (c).

- Les commentaires doivent être précédés du caractère #

EXEMPLE : Fichier `exemple'
******************************************************
# Ceci est un exemple simple d'un segment de droite
# paramétrique pouvant être défini par
# 1 <= x <= n/2
# n <= 80
# L'entrée du programme pour ce segment de droite est :

2 4                   # 2 lignes et 4 colonnes dans la matrice portant sur les variables

#  x  n  cste
1  1  0   -1          # pour x - 1 >= 0
1 -2  1    0          # pour -2x + n >= 0

1 3                   # 1 ligne et 3 colonnes dans la matrice portant uniquement
                      # sur les paramètres

1 -1 80               # pour -n + 80 >= 0
******************************************************

Cet exemple aurait également pu être défini en une seule matrice :

******************************************************
3 4

1 1 0 -1
1 -2 1 0
1 0 -1 80             # les contraintes portant uniquement sur les paramètres 

                      # peuvent être inclues dans la 1ère matrice

0 3                   # cette ligne est indispensable pour indiquer au programme 
                      # le nombre de paramètres (0 ligne dans la 2ème matrice, 
                      # 1 paramètre + 2 = 3)
******************************************************

Exécution :

******************************************************
% Ehrhart < exemple
---------------------------------------
Domain :
         P  -2 >= 0
         - P + 80 >= 0

Vertices :
[ P/2 ]
[ 1 ]

Ehrhart Polynomial:
( 1/2 * P + [ 0, -1/2 ]_P )
******************************************************

Les paramètres sont automatiquement nommés P, Q, R, S, ... par le programme. La 
réponse du programme pour l'exemple est donc :

- le domaine de validité est {2 <= n <= 80},
- les sommets paramétriques sont n/2 et 1,
- le polynôme d'Ehrhart est EP(n) = 1/2 n + [0, -1/2]_n, où [0, -1/2]_n est un
nombre périodique en n, égal à 0 si n modulo 2 = 0 et -1/2 sinon.