---------- Forwarded message ---------- Date: Wed, 13 May 2009 12:52:33 +0100 From: Vladimir Koshelev <vedun@ispras.ru> To: P M Hill <hill@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