[PPL-devel] PPL Library capabilities (fwd)

[P M Hill]

---------- 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.
>
> Dear Vladimir,
>
> 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
> addition of equality constraints using add_constraint() and
> 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);
> ph.add_constraint(new Constraint(lhs1,
> Relation_Symbol.EQUAL,
> le_0));
> ph.add_constraint(new Constraint(lhs2,
> 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
version of Java interface doesn't give access to low level Linear
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