# [PPL-devel] PPL Library capabilities (fwd)

P M Hill hill at comp.leeds.ac.uk
Thu May 14 10:15:32 CEST 2009

```
---------- Forwarded message ----------
Date: Wed, 13 May 2009 12:52:33 +0100
From: Vladimir Koshelev <vedun at ispras.ru>
To: P M Hill <hill at comp.leeds.ac.uk>
Subject: Re: [PPL-devel] PPL Library capabilities

P M Hill пишет:
> On Tue, 5 May 2009, Vladimir Koshelev wrote:
>
>> Hello.
>>
>> We have polyhedral representation in our research work and use your
>> library(PPL) through Java interface. We have the following problem:
>>
>>
>>
>> We have matrix *A(n, m)* with *rank(A)* < *min(n, m).*
>>
>> Also we have system of equations *Ax = 0*.
>>
>> We need to find *x = Uy*, where *U* is integer upper triangular matrix,
>> *x* is an integer solution of previous system and* y* is a vector of
>> arbitrary integer constants.
>>
>>
>>
>> Can we solve this problem, using your library(Java interface)? We need
>> only integer solutions.
>
>
> Since you indicate here that you only use equalities and only require
> integer solutions, the Grid domain provides almost what you want.
> This domain captures any regular lattice of points that can be defined
> by a set of linear congruence relations. In particular, equalities are
> represented as congruences whose modulus is 0 and non-relational
> congruences with modulus 1 can represent the condition that the
> variables are integral.
>
> The congruence representation can be converted to the a (grid)
> generator representation which, in the case you describe above where
> the initial equalities are homogeneous, will contain the origin point
> and a set of parameters whose coefficients are in a triangular form.
>
> The interface for Grids (for all the supported languages including
> Java) is very similar to that for Polyhedra and allows for the
> add_constraints(). To specify that the variables only take integer
> values, you have to add a congruence "X = 0 modulo 1" for each
> variable X.
>
> To obtain the matrix "U", after building the grid, use
> minimized_grid_generators() to obtain the grid generator system that
> represents this grid where the coefficients of the parameters will
> already be in triangular form.
>
> I include below a simple Java test that builds a grid as indicated
> above from equality constraints and integer congruences and then
> prints the grid generators. The point is the origin while the
> coefficients of the parameters will form the matrix U.
>
> public static void test00() {
> Variable W = new Variable(0);
> Variable X = new Variable(1);
> Variable Y = new Variable(2);
> Variable Z = new Variable(3);
> Linear_Expression le_0
> = new Linear_Expression_Coefficient(new Coefficient(0));
> Linear_Expression le_W = new Linear_Expression_Variable(W);
> Linear_Expression le_X = new Linear_Expression_Variable(X);
> Linear_Expression le_Y = new Linear_Expression_Variable(Y);
> Linear_Expression le_Z = new Linear_Expression_Variable(Z);
> Linear_Expression lhs1
> = le_W.times(new Coefficient(2)).sum(le_X).subtract(le_Z);
> Linear_Expression lhs2
> = le_X.sum(le_Y).subtract(le_Z.times(new Coefficient(5)));
> Grid ph = new Grid(4, Degenerate_Element.UNIVERSE);
> Relation_Symbol.EQUAL,
> le_0));
> Relation_Symbol.EQUAL,
> le_0));
> ph.add_congruence(new Congruence(le_W, le_0, new Coefficient(1)));
> ph.add_congruence(new Congruence(le_X, le_0, new Coefficient(1)));
> ph.add_congruence(new Congruence(le_Y, le_0, new Coefficient(1)));
> ph.add_congruence(new Congruence(le_Z, le_0, new Coefficient(1)));
> System.out.println(ph.congruences().toString());
> System.out.println(ph.minimized_grid_generators().toString());
> }
>
> This will print
>
> 2*A + B - D = 0, B + C - 5*D = 0, A = 0 (mod 1), B = 0 (mod 1), C = 0
> (mod 1), D = 0 (mod 1)
> p(0), q(A + 10*C + 2*D), q(B + 4*C + D)
>
> where p(0) is the origin
> and q(...) are the parameters
>
> Therefore the matrix of coefficients of the parameters in this case is:
> 1, 10, 0, 2
> 0, 1, 4, 1
> 0, 0, 0, 0
> 0, 0, 0, 0
>
> I guess this is not quite the format you want but if the variables
> were read in reverse order, it would be upper triangular. Otherwise a
> further matrix operation would be needed to convert it to the right
> format.
>
> This solution uses the grids. If you also need to represent
> inequalities, then the grids cannot be used and the above proposal
> will not help.
>
> All the best,
> Pat
Dear Pat,

We need to transform matrix returned by minimized_grid_generators() to
another form. To do this we want to get matrix coefficients, but current
Expression representaion. It's will be very useful to get direct access
to Linear_Expression coefficients include setting and removing.
Example :
If we have Linear_Expression 4 * A + 5 * B - C - 6, we want to get {4,
5, -1, -6} ( As vector or getter method or another form.)

Method which can express one variable in constraint throw others will be
useful too.
Example :
4 * A + 6 * B - 7 * C = 0 => 4 * A = -6 * B + 7 * C

```