The Ehrhart polynomials and parametric vertices program

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

The program input is a system of equations or inequations where
the right side term is always equal to zero. They are of the form

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

or

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

In the following, these equations or inequations are called constraints.
The input must be captured in a text file according to the following
rules:

- the constraints can be given in 2 matrices: the first one composed of
constraints concerning variables x1, x2, ..., the second one composed
of constraints only concerning the parameters. Anyway, this second matrix
can be omitted and included in the first one.

- Each matrix must be preceeded by two integers giving respectively the
number of rows and the number of columns of the matrix.

- In each matrix, a row beginning with 0 (zero) is an equality constraint,
a row beginning with 1 (one) is an inequality constraint (greater or equal).

- Integer values following the value 0 or 1 in a row, have to be ordered
in order to correspond first to the variables coefficients in the constraints
(a1, ..., an, in a predefined order of the variables), then to the parameters
coefficients (b1, ..., bm, in a predefined order of the parameters), and
then to the constant coefficient (c).

- Comments must be preceeded by the character #

EXAMPLE : file `example'
******************************************************
# This is a simple example of a parametric line segment
# that is defined by
# 1 <= x <= n/2
# n <= 80
# The program input for this line segment is :

2 4                   # 2 rows and 4 columns in the matrix concerning variables

#  x  n  cst
1  1  0  -1          # for x - 1 >= 0
1 -2  1   0          # for -2x + n >= 0

1 3                   # 1 row and 3 columns in the matrix only concerning
                      # parameters

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

This example also could have been defined in one single matrix :

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

1 1 0 -1
1 -2 1 0
1 0 -1 80             # constraints only concerning parameters 

                      # can be included in the 1st matrix

0 3                   # this row is necessary to tell the program 
                      # the number of parameters (0 row in the 2nd matrix, 
                      # 1 parameter + 2 = 3)
******************************************************

Execution :

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

Vertices :
[ P/2 ]
[ 1 ]

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

The parameters are automatically called P, Q, R, S, ... by the program. The
answer for the example is :

- the validity domain is {2 <= n <= 80},
- the parametric vertices are n/2 and 1,
- the Ehrhart polynomial is EP(n) = 1/2 n + [0, -1/2]_n, where [0, -1/2]_n is
a periodic number in n, equal to 0 if n modulo 2 = 0 and -1/2 otherwise.