nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2006-2007 Universiteit Leiden
3 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 *
5 * Use of this software is governed by the GNU LGPLv2.1 license
6 *
7 * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
8 * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
9 * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
10 * B-3001 Leuven, Belgium
11 */
12  
13 #include <stdlib.h>
14 #include <isl_ctx_private.h>
15 #include <isl_map_private.h>
16 #include <isl_options_private.h>
17 #include "isl_basis_reduction.h"
18  
19 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
20 {
21 int i;
22  
23 for (i = 0; i < n; ++i)
24 GBR_lp_get_alpha(lp, first + i, &alpha[i]);
25 }
26  
27 /* Compute a reduced basis for the set represented by the tableau "tab".
28 * tab->basis, which must be initialized by the calling function to an affine
29 * unimodular basis, is updated to reflect the reduced basis.
30 * The first tab->n_zero rows of the basis (ignoring the constant row)
31 * are assumed to correspond to equalities and are left untouched.
32 * tab->n_zero is updated to reflect any additional equalities that
33 * have been detected in the first rows of the new basis.
34 * The final tab->n_unbounded rows of the basis are assumed to correspond
35 * to unbounded directions and are also left untouched.
36 * In particular this means that the remaining rows are assumed to
37 * correspond to bounded directions.
38 *
39 * This function implements the algorithm described in
40 * "An Implementation of the Generalized Basis Reduction Algorithm
41 * for Integer Programming" of Cook el al. to compute a reduced basis.
42 * We use \epsilon = 1/4.
43 *
44 * If ctx->opt->gbr_only_first is set, the user is only interested
45 * in the first direction. In this case we stop the basis reduction when
46 * the width in the first direction becomes smaller than 2.
47 */
48 struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
49 {
50 unsigned dim;
51 struct isl_ctx *ctx;
52 struct isl_mat *B;
53 int unbounded;
54 int i;
55 GBR_LP *lp = NULL;
56 GBR_type F_old, alpha, F_new;
57 int row;
58 isl_int tmp;
59 struct isl_vec *b_tmp;
60 GBR_type *F = NULL;
61 GBR_type *alpha_buffer[2] = { NULL, NULL };
62 GBR_type *alpha_saved;
63 GBR_type F_saved;
64 int use_saved = 0;
65 isl_int mu[2];
66 GBR_type mu_F[2];
67 GBR_type two;
68 GBR_type one;
69 int empty = 0;
70 int fixed = 0;
71 int fixed_saved = 0;
72 int mu_fixed[2];
73 int n_bounded;
74 int gbr_only_first;
75  
76 if (!tab)
77 return NULL;
78  
79 if (tab->empty)
80 return tab;
81  
82 ctx = tab->mat->ctx;
83 gbr_only_first = ctx->opt->gbr_only_first;
84 dim = tab->n_var;
85 B = tab->basis;
86 if (!B)
87 return tab;
88  
89 n_bounded = dim - tab->n_unbounded;
90 if (n_bounded <= tab->n_zero + 1)
91 return tab;
92  
93 isl_int_init(tmp);
94 isl_int_init(mu[0]);
95 isl_int_init(mu[1]);
96  
97 GBR_init(alpha);
98 GBR_init(F_old);
99 GBR_init(F_new);
100 GBR_init(F_saved);
101 GBR_init(mu_F[0]);
102 GBR_init(mu_F[1]);
103 GBR_init(two);
104 GBR_init(one);
105  
106 b_tmp = isl_vec_alloc(ctx, dim);
107 if (!b_tmp)
108 goto error;
109  
110 F = isl_alloc_array(ctx, GBR_type, n_bounded);
111 alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded);
112 alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded);
113 alpha_saved = alpha_buffer[0];
114  
115 if (!F || !alpha_buffer[0] || !alpha_buffer[1])
116 goto error;
117  
118 for (i = 0; i < n_bounded; ++i) {
119 GBR_init(F[i]);
120 GBR_init(alpha_buffer[0][i]);
121 GBR_init(alpha_buffer[1][i]);
122 }
123  
124 GBR_set_ui(two, 2);
125 GBR_set_ui(one, 1);
126  
127 lp = GBR_lp_init(tab);
128 if (!lp)
129 goto error;
130  
131 i = tab->n_zero;
132  
133 GBR_lp_set_obj(lp, B->row[1+i]+1, dim);
134 ctx->stats->gbr_solved_lps++;
135 unbounded = GBR_lp_solve(lp);
136 isl_assert(ctx, !unbounded, goto error);
137 GBR_lp_get_obj_val(lp, &F[i]);
138  
139 if (GBR_lt(F[i], one)) {
140 if (!GBR_is_zero(F[i])) {
141 empty = GBR_lp_cut(lp, B->row[1+i]+1);
142 if (empty)
143 goto done;
144 GBR_set_ui(F[i], 0);
145 }
146 tab->n_zero++;
147 }
148  
149 do {
150 if (i+1 == tab->n_zero) {
151 GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
152 ctx->stats->gbr_solved_lps++;
153 unbounded = GBR_lp_solve(lp);
154 isl_assert(ctx, !unbounded, goto error);
155 GBR_lp_get_obj_val(lp, &F_new);
156 fixed = GBR_lp_is_fixed(lp);
157 GBR_set_ui(alpha, 0);
158 } else
159 if (use_saved) {
160 row = GBR_lp_next_row(lp);
161 GBR_set(F_new, F_saved);
162 fixed = fixed_saved;
163 GBR_set(alpha, alpha_saved[i]);
164 } else {
165 row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
166 GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
167 ctx->stats->gbr_solved_lps++;
168 unbounded = GBR_lp_solve(lp);
169 isl_assert(ctx, !unbounded, goto error);
170 GBR_lp_get_obj_val(lp, &F_new);
171 fixed = GBR_lp_is_fixed(lp);
172  
173 GBR_lp_get_alpha(lp, row, &alpha);
174  
175 if (i > 0)
176 save_alpha(lp, row-i, i, alpha_saved);
177  
178 if (GBR_lp_del_row(lp) < 0)
179 goto error;
180 }
181 GBR_set(F[i+1], F_new);
182  
183 GBR_floor(mu[0], alpha);
184 GBR_ceil(mu[1], alpha);
185  
186 if (isl_int_eq(mu[0], mu[1]))
187 isl_int_set(tmp, mu[0]);
188 else {
189 int j;
190  
191 for (j = 0; j <= 1; ++j) {
192 isl_int_set(tmp, mu[j]);
193 isl_seq_combine(b_tmp->el,
194 ctx->one, B->row[1+i+1]+1,
195 tmp, B->row[1+i]+1, dim);
196 GBR_lp_set_obj(lp, b_tmp->el, dim);
197 ctx->stats->gbr_solved_lps++;
198 unbounded = GBR_lp_solve(lp);
199 isl_assert(ctx, !unbounded, goto error);
200 GBR_lp_get_obj_val(lp, &mu_F[j]);
201 mu_fixed[j] = GBR_lp_is_fixed(lp);
202 if (i > 0)
203 save_alpha(lp, row-i, i, alpha_buffer[j]);
204 }
205  
206 if (GBR_lt(mu_F[0], mu_F[1]))
207 j = 0;
208 else
209 j = 1;
210  
211 isl_int_set(tmp, mu[j]);
212 GBR_set(F_new, mu_F[j]);
213 fixed = mu_fixed[j];
214 alpha_saved = alpha_buffer[j];
215 }
216 isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
217 tmp, B->row[1+i]+1, dim);
218  
219 if (i+1 == tab->n_zero && fixed) {
220 if (!GBR_is_zero(F[i+1])) {
221 empty = GBR_lp_cut(lp, B->row[1+i+1]+1);
222 if (empty)
223 goto done;
224 GBR_set_ui(F[i+1], 0);
225 }
226 tab->n_zero++;
227 }
228  
229 GBR_set(F_old, F[i]);
230  
231 use_saved = 0;
232 /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
233 GBR_set_ui(mu_F[0], 4);
234 GBR_mul(mu_F[0], mu_F[0], F_new);
235 GBR_set_ui(mu_F[1], 3);
236 GBR_mul(mu_F[1], mu_F[1], F_old);
237 if (GBR_lt(mu_F[0], mu_F[1])) {
238 B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
239 if (i > tab->n_zero) {
240 use_saved = 1;
241 GBR_set(F_saved, F_new);
242 fixed_saved = fixed;
243 if (GBR_lp_del_row(lp) < 0)
244 goto error;
245 --i;
246 } else {
247 GBR_set(F[tab->n_zero], F_new);
248 if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
249 break;
250  
251 if (fixed) {
252 if (!GBR_is_zero(F[tab->n_zero])) {
253 empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1);
254 if (empty)
255 goto done;
256 GBR_set_ui(F[tab->n_zero], 0);
257 }
258 tab->n_zero++;
259 }
260 }
261 } else {
262 GBR_lp_add_row(lp, B->row[1+i]+1, dim);
263 ++i;
264 }
265 } while (i < n_bounded - 1);
266  
267 if (0) {
268 done:
269 if (empty < 0) {
270 error:
271 isl_mat_free(B);
272 B = NULL;
273 }
274 }
275  
276 GBR_lp_delete(lp);
277  
278 if (alpha_buffer[1])
279 for (i = 0; i < n_bounded; ++i) {
280 GBR_clear(F[i]);
281 GBR_clear(alpha_buffer[0][i]);
282 GBR_clear(alpha_buffer[1][i]);
283 }
284 free(F);
285 free(alpha_buffer[0]);
286 free(alpha_buffer[1]);
287  
288 isl_vec_free(b_tmp);
289  
290 GBR_clear(alpha);
291 GBR_clear(F_old);
292 GBR_clear(F_new);
293 GBR_clear(F_saved);
294 GBR_clear(mu_F[0]);
295 GBR_clear(mu_F[1]);
296 GBR_clear(two);
297 GBR_clear(one);
298  
299 isl_int_clear(tmp);
300 isl_int_clear(mu[0]);
301 isl_int_clear(mu[1]);
302  
303 tab->basis = B;
304  
305 return tab;
306 }
307  
308 /* Compute an affine form of a reduced basis of the given basic
309 * non-parametric set, which is assumed to be bounded and not
310 * include any integer divisions.
311 * The first column and the first row correspond to the constant term.
312 *
313 * If the input contains any equalities, we first create an initial
314 * basis with the equalities first. Otherwise, we start off with
315 * the identity matrix.
316 */
317 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
318 {
319 struct isl_mat *basis;
320 struct isl_tab *tab;
321  
322 if (!bset)
323 return NULL;
324  
325 if (isl_basic_set_dim(bset, isl_dim_div) != 0)
326 isl_die(bset->ctx, isl_error_invalid,
327 "no integer division allowed", return NULL);
328 if (isl_basic_set_dim(bset, isl_dim_param) != 0)
329 isl_die(bset->ctx, isl_error_invalid,
330 "no parameters allowed", return NULL);
331  
332 tab = isl_tab_from_basic_set(bset, 0);
333 if (!tab)
334 return NULL;
335  
336 if (bset->n_eq == 0)
337 tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
338 else {
339 isl_mat *eq;
340 unsigned nvar = isl_basic_set_total_dim(bset);
341 eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
342 1, nvar);
343 eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis);
344 tab->basis = isl_mat_lin_to_aff(tab->basis);
345 tab->n_zero = bset->n_eq;
346 isl_mat_free(eq);
347 }
348 tab = isl_tab_compute_reduced_basis(tab);
349 if (!tab)
350 return NULL;
351  
352 basis = isl_mat_copy(tab->basis);
353  
354 isl_tab_free(tab);
355  
356 return basis;
357 }