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 19static 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 */ 48struct 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) { 268done: 269 if (empty < 0) { 270error: 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 */ 317struct 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} 358