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