1 /*
2 This file is part of PolyLib.
3
4 PolyLib is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 PolyLib is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with PolyLib. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 /**
19 * $Id: matrix_addon.c,v 1.17 2007/03/18 18:49:08 skimo Exp $
20 *
21 * Polylib matrix addons
22 * Mainly, deals with polyhedra represented as a matrix (implicit form)
23 * @author Benoit Meister <meister@icps.u-strasbg.fr>
24 *
25 */
26
27 #include <stdlib.h>
28 #include<polylib/polylib.h>
29 #include <polylib/matrix_addon.h>
30
31 /** Creates a view of the constraints of a polyhedron as a Matrix * */
constraintsView(Polyhedron * P)32 Matrix * constraintsView(Polyhedron * P) {
33 Matrix * view = (Matrix *)malloc(sizeof(Matrix));
34 view->NbRows = P->NbConstraints;
35 view->NbColumns = P->Dimension+2;
36 view->p = P->Constraint;
37 return view;
38 }
39
40 /** "Frees" a view of the constraints of a polyhedron */
constraintsView_Free(Matrix * M)41 void constraintsView_Free(Matrix * M) {
42 free(M);
43 }
44
45 /**
46 * splits a matrix of constraints M into a matrix of equalities Eqs and a
47 * matrix of inequalities Ineqs allocs the new matrices.
48 * Allocates Eqs and Ineqs.
49 */
split_constraints(Matrix const * M,Matrix ** Eqs,Matrix ** Ineqs)50 void split_constraints(Matrix const * M, Matrix ** Eqs, Matrix **Ineqs) {
51 unsigned int i, j, k_eq, k_ineq, nb_eqs=0;
52
53 /* 1- count the number of equations */
54 for (i=0; i< M->NbRows; i++)
55 if (value_zero_p(M->p[i][0])) nb_eqs++;
56
57 /* 2- extract the two matrices of equations */
58 (*Eqs) = Matrix_Alloc(nb_eqs, M->NbColumns);
59 (*Ineqs) = Matrix_Alloc(M->NbRows-nb_eqs, M->NbColumns);
60
61 k_eq = k_ineq = 0;
62 for(i=0; i< M->NbRows; i++) {
63 if (value_zero_p(M->p[i][0]))
64 {
65 for(j=0; j< M->NbColumns; j++)
66 value_assign((*Eqs)->p[k_eq][j], M->p[i][j]);
67 k_eq++;
68 }
69 else
70 {
71 for(j=0; j< M->NbColumns; j++)
72 value_assign((*Ineqs)->p[k_ineq][j], M->p[i][j]);
73 k_ineq++;
74 }
75 }
76 }
77
78
79 /* returns the dim-dimensional identity matrix */
Identity_Matrix(unsigned int dim)80 Matrix * Identity_Matrix(unsigned int dim) {
81 Matrix * ret = Matrix_Alloc(dim, dim);
82 unsigned int i,j;
83 for (i=0; i< dim; i++) {
84 for (j=0; j< dim; j++) {
85 if (i==j)
86 { value_set_si(ret->p[i][j], 1); }
87 else value_set_si(ret->p[i][j], 0);
88 }
89 }
90 return ret;
91 } /* Identity_Matrix */
92
93
94 /**
95 * returns the dim-dimensional identity matrix.
96 * If I is set to NULL, allocates it first.
97 * Else, assumes an existing, allocated Matrix.
98 */
Matrix_identity(unsigned int dim,Matrix ** I)99 void Matrix_identity(unsigned int dim, Matrix ** I) {
100 int i,j;
101 if (*I==NULL) {
102 (*I) = Identity_Matrix(dim);
103 }
104 else {
105 assert((*I)->NbRows>=dim && (*I)->NbColumns>=dim);
106 for (i=0; i< dim; i++) {
107 for (j=0; j< dim; j++) {
108 if (i==j) {
109 value_set_si((*I)->p[i][j], 1);
110 }
111 else {
112 value_set_si((*I)->p[i][j], 0);
113 }
114 }
115 }
116 }
117 } /* Matrix_identity */
118
119
120 /** given a n x n integer transformation matrix transf, compute its inverse
121 M/g, where M is a nxn integer matrix. g is a common denominator for
122 elements of (transf^{-1}) */
mtransformation_inverse(Matrix * transf,Matrix ** inverse,Value * g)123 void mtransformation_inverse(Matrix * transf, Matrix ** inverse, Value * g) {
124 Value factor;
125 unsigned int i,j;
126 Matrix *tmp, *inv;
127
128 value_init(*g);
129 value_set_si(*g,1);
130
131 /* a - compute the inverse as usual (n x (n+1) matrix) */
132 tmp = Matrix_Copy(transf);
133 inv = Matrix_Alloc(transf->NbRows, transf->NbColumns+1);
134 MatInverse(tmp, inv);
135 Matrix_Free(tmp);
136
137 /* b - as it is rational, put it to the same denominator*/
138 (*inverse) = Matrix_Alloc(transf->NbRows, transf->NbRows);
139 for (i=0; i< inv->NbRows; i++)
140 value_lcm(*g, *g, inv->p[i][inv->NbColumns-1]);
141 for (i=0; i< inv->NbRows; i++) {
142 value_division(factor, *g, inv->p[i][inv->NbColumns-1]);
143 for (j=0; j< (*inverse)->NbColumns; j++)
144 value_multiply((*inverse)->p[i][j], inv->p[i][j], factor);
145 }
146
147 /* c- clean up */
148 value_clear(factor);
149 Matrix_Free(inv);
150 } /* mtransformation_inverse */
151
152
153 /** takes a transformation matrix, and expands it to a higher dimension with
154 the identity matrix regardless of it homogeneousness */
mtransformation_expand_left_to_dim(Matrix * M,int new_dim)155 Matrix * mtransformation_expand_left_to_dim(Matrix * M, int new_dim) {
156 Matrix * ret = Identity_Matrix(new_dim);
157 int offset = new_dim-M->NbRows;
158 unsigned int i,j;
159
160 assert(new_dim>=M->NbColumns);
161 assert(M->NbRows==M->NbColumns);
162
163 for (i=0; i< M->NbRows; i++)
164 for (j=0; j< M->NbRows; j++)
165 value_assign(ret->p[offset+i][offset+j], M->p[i][j]);
166 return ret;
167 } /* mtransformation_expand_left_to_dim */
168
169
170 /** simplify a matrix seen as a polyhedron, by dividing its rows by the gcd of
171 their elements. */
mpolyhedron_simplify(Matrix * polyh)172 void mpolyhedron_simplify(Matrix * polyh) {
173 int i, j;
174 Value cur_gcd;
175 value_init(cur_gcd);
176 for (i=0; i< polyh->NbRows; i++) {
177 Vector_Gcd(polyh->p[i]+1, polyh->NbColumns-1, &cur_gcd);
178 printf(" gcd[%d] = ", i);
179 value_print(stdout, VALUE_FMT, cur_gcd);printf("\n");
180 Vector_AntiScale(polyh->p[i]+1, polyh->p[i]+1, cur_gcd, polyh->NbColumns-1);
181 }
182 value_clear(cur_gcd);
183 } /* mpolyhedron_simplify */
184
185
186 /** inflates a polyhedron (represented as a matrix) P, so that the apx of its
187 Ehrhart Polynomial is an upper bound of the Ehrhart polynomial of P
188 WARNING: this inflation is supposed to be applied on full-dimensional
189 polyhedra. */
mpolyhedron_inflate(Matrix * polyh,unsigned int nb_parms)190 void mpolyhedron_inflate(Matrix * polyh, unsigned int nb_parms) {
191 unsigned int i,j;
192 unsigned nb_vars = polyh->NbColumns-nb_parms-2;
193 Value infl;
194 value_init(infl);
195 /* subtract the sum of the negative coefficients of each inequality */
196 for (i=0; i< polyh->NbRows; i++) {
197 value_set_si(infl, 0);
198 for (j=0; j< nb_vars; j++) {
199 if (value_neg_p(polyh->p[i][1+j]))
200 value_addto(infl, infl, polyh->p[i][1+j]);
201 }
202 /* here, we subtract a negative value */
203 value_subtract(polyh->p[i][polyh->NbColumns-1],
204 polyh->p[i][polyh->NbColumns-1], infl);
205 }
206 value_clear(infl);
207 } /* mpolyhedron_inflate */
208
209
210 /** deflates a polyhedron (represented as a matrix) P, so that the apx of its
211 Ehrhart Polynomial is a lower bound of the Ehrhart polynomial of P WARNING:
212 this deflation is supposed to be applied on full-dimensional polyhedra. */
mpolyhedron_deflate(Matrix * polyh,unsigned int nb_parms)213 void mpolyhedron_deflate(Matrix * polyh, unsigned int nb_parms) {
214 unsigned int i,j;
215 unsigned nb_vars = polyh->NbColumns-nb_parms-2;
216 Value defl;
217 value_init(defl);
218 /* substract the sum of the negative coefficients of each inequality */
219 for (i=0; i< polyh->NbRows; i++) {
220 value_set_si(defl, 0);
221 for (j=0; j< nb_vars; j++) {
222 if (value_pos_p(polyh->p[i][1+j]))
223 value_addto(defl, defl, polyh->p[i][1+j]);
224 }
225 /* here, we substract a negative value */
226 value_subtract(polyh->p[i][polyh->NbColumns-1],
227 polyh->p[i][polyh->NbColumns-1], defl);
228 }
229 value_clear(defl);
230 } /* mpolyhedron_deflate */
231
232
233 /** use an eliminator row to eliminate a variable in a victim row (without
234 * changing the sign of the victim row -> important if it is an inequality).
235 * @param Eliminator the matrix containing the eliminator row
236 * @param eliminator_row the index of the eliminator row in <tt>Eliminator</tt>
237 * @param Victim the matrix containing the row to be eliminated
238 * @param victim_row the row to be eliminated in <tt>Victim</tt>
239 * @param var_to_elim the variable to be eliminated.
240 */
eliminate_var_with_constr(Matrix * Eliminator,unsigned int eliminator_row,Matrix * Victim,unsigned int victim_row,unsigned int var_to_elim)241 void eliminate_var_with_constr(Matrix * Eliminator,
242 unsigned int eliminator_row, Matrix * Victim,
243 unsigned int victim_row,
244 unsigned int var_to_elim) {
245 Value cur_lcm, mul_a, mul_b;
246 Value tmp, tmp2;
247 int k;
248
249 value_init(cur_lcm);
250 value_init(mul_a);
251 value_init(mul_b);
252 value_init(tmp);
253 value_init(tmp2);
254 /* if the victim coefficient is not zero */
255 if (value_notzero_p(Victim->p[victim_row][var_to_elim+1])) {
256 value_lcm(cur_lcm, Eliminator->p[eliminator_row][var_to_elim+1],
257 Victim->p[victim_row][var_to_elim+1]);
258 /* multiplication factors */
259 value_division(mul_a, cur_lcm,
260 Eliminator->p[eliminator_row][var_to_elim+1]);
261 value_division(mul_b, cur_lcm,
262 Victim->p[victim_row][var_to_elim+1]);
263 /* the multiplicator for the vitim row has to be positive */
264 if (value_pos_p(mul_b)) {
265 value_oppose(mul_a, mul_a);
266 }
267 else {
268 value_oppose(mul_b, mul_b);
269 }
270 value_clear(cur_lcm);
271 /* now we have a.mul_a = -(b.mul_b) and mul_a > 0 */
272 for (k=1; k<Victim->NbColumns; k++) {
273 value_multiply(tmp, Eliminator->p[eliminator_row][k], mul_a);
274 value_multiply(tmp2, Victim->p[victim_row][k], mul_b);
275 value_addto(Victim->p[victim_row][k], tmp, tmp2);
276 }
277 }
278 value_clear(mul_a);
279 value_clear(mul_b);
280 value_clear(tmp);
281 value_clear(tmp2);
282 }
283 /* eliminate_var_with_constr */
284
285
286 /* STUFF WITH PARTIAL MAPPINGS (Mappings to a subset of the
287 variables/parameters) : on the first or last variables/parameters */
288
289 /** compress the last vars/pars of the polyhedron M expressed as a polylib
290 matrix
291 - adresses the full-rank compressions only
292 - modfies M */
mpolyhedron_compress_last_vars(Matrix * M,Matrix * compression)293 void mpolyhedron_compress_last_vars(Matrix * M, Matrix * compression) {
294 unsigned int i, j, k;
295 unsigned int offset = M->NbColumns - compression->NbRows;
296 /* the computations on M will begin on column "offset" */
297
298 Matrix * M_tmp = Matrix_Alloc(1, M->NbColumns);
299 assert(compression->NbRows==compression->NbColumns);
300 /* basic matrix multiplication (using a temporary row instead of a whole
301 temporary matrix), but with a column offset */
302 for(i=0; i< M->NbRows; i++) {
303 for (j=0; j< compression->NbRows; j++) {
304 value_set_si(M_tmp->p[0][j], 0);
305 for (k=0; k< compression->NbRows; k++) {
306 value_addmul(M_tmp->p[0][j], M->p[i][k+offset],compression->p[k][j]);
307 }
308 }
309 for (j=0; j< compression->NbRows; j++)
310 value_assign(M->p[i][j+offset], M_tmp->p[0][j]);
311 }
312 Matrix_Free(M_tmp);
313 } /* mpolyhedron_compress_last_vars */
314
315
316 /** use a set of m equalities Eqs to eliminate m variables in the polyhedron
317 Ineqs represented as a matrix
318 eliminates the m first variables
319 - assumes that Eqs allow to eliminate the m equalities
320 - modifies Eqs and Ineqs */
mpolyhedron_eliminate_first_variables(Matrix * Eqs,Matrix * Ineqs)321 unsigned int mpolyhedron_eliminate_first_variables(Matrix * Eqs,
322 Matrix *Ineqs) {
323 unsigned int i, j, k;
324 /* eliminate one variable (index i) after each other */
325 for (i=0; i< Eqs->NbRows; i++) {
326 /* find j, the first (non-marked) row of Eqs with a non-zero coefficient */
327 for (j=0; j<Eqs->NbRows && (Eqs->p[j][i+1]==0 ||
328 ( !value_cmp_si(Eqs->p[j][0],2) ));
329 j++);
330 /* if no row is found in Eqs that allows to eliminate variable i, return an
331 error code (0) */
332 if (j==Eqs->NbRows) return 0;
333 /* else, eliminate variable i in Eqs and Ineqs with the j^th row of Eqs
334 (and mark this row so we don't use it again for an elimination) */
335 for (k=j+1; k<Eqs->NbRows; k++)
336 eliminate_var_with_constr(Eqs, j, Eqs, k, i);
337 for (k=0; k< Ineqs->NbRows; k++)
338 eliminate_var_with_constr(Eqs, j, Ineqs, k, i);
339 /* mark the row */
340 value_set_si(Eqs->p[j][0],2);
341 }
342 /* un-mark all the rows */
343 for (i=0; i< Eqs->NbRows; i++) value_set_si(Eqs->p[i][0],0);
344 return 1;
345 } /* mpolyhedron_eliminate_first_variables */
346
347
348 /** returns a contiguous submatrix of a matrix.
349 * @param M the input matrix
350 * @param sr the index of the starting row
351 * @param sc the index of the starting column
352 * @param er the index ofthe ending row (excluded)
353 * @param ec the ined of the ending colummn (excluded)
354 * @param sub (returned), the submatrix. Allocated if set to NULL, assumed to
355 * be already allocated else.
356 */
Matrix_subMatrix(Matrix * M,unsigned int sr,unsigned int sc,unsigned int er,unsigned int ec,Matrix ** sub)357 void Matrix_subMatrix(Matrix * M, unsigned int sr, unsigned int sc,
358 unsigned int er, unsigned int ec, Matrix ** sub) {
359 int i;
360 int nbR = er-sr;
361 int nbC = ec-sc;
362 assert (er<=M->NbRows && ec<=M->NbColumns);
363 if ((*sub)==NULL) {
364 (*sub) = Matrix_Alloc(nbR, nbC);
365 }
366 if (nbR==0 || nbC==0) return;
367 for (i=0; i< nbR; i++) {
368 Vector_Copy(&(M->p[i+sr][sc]), (*sub)->p[i], nbC);
369 }
370 }/* Matrix_subMatrix */
371
372
373 /**
374 * Cloning function. Similar to Matrix_Copy() but allocates the target matrix
375 * if it is set to NULL.
376 */
Matrix_clone(Matrix * M,Matrix ** Cl)377 void Matrix_clone(Matrix * M, Matrix ** Cl) {
378 Matrix_subMatrix(M, 0,0, M->NbRows, M->NbColumns, Cl);
379 }
380
381
382 /**
383 * Copies a contiguous submatrix of M1 into M2, at the indicated position.
384 * M1 and M2 are assumed t be allocated already.
385 * @param M1 the source matrix
386 * @param sr1 the starting source row
387 * @param sc1 the starting source column
388 * @param nbR the number of rows
389 * @param nbC the number of columns
390 * @param M2 the target matrix
391 * @param sr2 the starting target row
392 * @param sc2 the starting target column
393 */
Matrix_copySubMatrix(Matrix * M1,unsigned int sr1,unsigned int sc1,unsigned int nbR,unsigned int nbC,Matrix * M2,unsigned int sr2,unsigned int sc2)394 void Matrix_copySubMatrix(Matrix *M1,
395 unsigned int sr1, unsigned int sc1,
396 unsigned int nbR, unsigned int nbC,
397 Matrix * M2,
398 unsigned int sr2, unsigned int sc2) {
399 int i;
400 for (i=0; i< nbR; i++) {
401 Vector_Copy(&(M1->p[i+sr1][sc1]), &(M2->p[i+sr2][sc2]), nbC);
402 }
403 } /* Matrix_copySubMatrix */
404
405
406 /**
407 * transforms a matrix M into -M
408 */
Matrix_oppose(Matrix * M)409 void Matrix_oppose(Matrix * M) {
410 int i,j;
411 for (i=0; i<M->NbRows; i++) {
412 for (j=0; j< M->NbColumns; j++) {
413 value_oppose(M->p[i][j], M->p[i][j]);
414 }
415 }
416 }
417