add packaging
[platform/upstream/isl.git] / basis_reduction_templ.c
1 /*
2  * Copyright 2006-2007 Universiteit Leiden
3  * Copyright 2008-2009 Katholieke Universiteit Leuven
4  *
5  * Use of this software is governed by the MIT 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 }