basis_reduction_templ.c

   1 #include <stdlib.h>
   2 #include "isl_basis_reduction.h"
   3
   4 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
   5 {
   6         int i;
   7
   8         for (i = 0; i < n; ++i)
   9                 GBR_lp_get_alpha(lp, first + i, &alpha[i]);
  10 }
  11
  12 /* This function implements the algorithm described in
  13  * "An Implementation of the Generalized Basis Reduction Algorithm
  14  *  for Integer Programming" of Cook el al. to compute a reduced basis.
  15  * We use \epsilon = 1/4.
  16  *
  17  * If ctx->gbr_only_first is set, the user is only interested
  18  * in the first direction.  In this case we stop the basis reduction when
  19  * the width in the first direction becomes smaller than 2.
  20  */
  21 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
  22 {
  23         unsigned dim;
  24         struct isl_mat *basis;
  25         int unbounded;
  26         int i;
  27         GBR_LP *lp = NULL;
  28         GBR_type F_old, alpha, F_new;
  29         int row;
  30         isl_int tmp;
  31         struct isl_vec *b_tmp;
  32         GBR_type *F = NULL;
  33         GBR_type *alpha_buffer[2] = { NULL, NULL };
  34         GBR_type *alpha_saved;
  35         GBR_type F_saved;
  36         int use_saved = 0;
  37         isl_int mu[2];
  38         GBR_type mu_F[2];
  39         GBR_type two;
  40         GBR_type one;
  41         int n_zero = 0;
  42         int empty = 0;
  43         int fixed = 0;
  44         int fixed_saved = 0;
  45         int mu_fixed[2];
  46
  47         if (!bset)
  48                 return NULL;
  49
  50         dim = isl_basic_set_total_dim(bset);
  51         basis = isl_mat_identity(bset->ctx, dim);
  52         if (!basis)
  53                 return NULL;
  54
  55         if (dim == 1)
  56                 return basis;
  57
  58         isl_int_init(tmp);
  59         isl_int_init(mu[0]);
  60         isl_int_init(mu[1]);
  61
  62         GBR_init(alpha);
  63         GBR_init(F_old);
  64         GBR_init(F_new);
  65         GBR_init(F_saved);
  66         GBR_init(mu_F[0]);
  67         GBR_init(mu_F[1]);
  68         GBR_init(two);
  69         GBR_init(one);
  70
  71         b_tmp = isl_vec_alloc(bset->ctx, dim);
  72         if (!b_tmp)
  73                 goto error;
  74
  75         F = isl_alloc_array(bset->ctx, GBR_type, dim);
  76         alpha_buffer[0] = isl_alloc_array(bset->ctx, GBR_type, dim);
  77         alpha_buffer[1] = isl_alloc_array(bset->ctx, GBR_type, dim);
  78         alpha_saved = alpha_buffer[0];
  79
  80         if (!F || !alpha_buffer[0] || !alpha_buffer[1])
  81                 goto error;
  82
  83         for (i = 0; i < dim; ++i) {
  84                 GBR_init(F[i]);
  85                 GBR_init(alpha_buffer[0][i]);
  86                 GBR_init(alpha_buffer[1][i]);
  87         }
  88
  89         GBR_set_ui(two, 2);
  90         GBR_set_ui(one, 1);
  91
  92         lp = GBR_lp_init(bset);
  93         if (!lp)
  94                 goto error;
  95
  96         i = 0;
  97
  98         GBR_lp_set_obj(lp, basis->row[0], dim);
  99         bset->ctx->stats->gbr_solved_lps++;
 100         unbounded = GBR_lp_solve(lp);
 101         isl_assert(bset->ctx, !unbounded, goto error);
 102         GBR_lp_get_obj_val(lp, &F[0]);
 103
 104         if (GBR_lt(F[0], one)) {
 105                 if (!GBR_is_zero(F[0])) {
 106                         empty = GBR_lp_cut(lp, basis->row[0]);
 107                         if (empty)
 108                                 goto done;
 109                         GBR_set_ui(F[0], 0);
 110                 }
 111                 n_zero++;
 112         }
 113
 114         do {
 115                 if (i+1 == n_zero) {
 116                         GBR_lp_set_obj(lp, basis->row[i+1], dim);
 117                         bset->ctx->stats->gbr_solved_lps++;
 118                         unbounded = GBR_lp_solve(lp);
 119                         isl_assert(bset->ctx, !unbounded, goto error);
 120                         GBR_lp_get_obj_val(lp, &F_new);
 121                         fixed = GBR_lp_is_fixed(lp);
 122                         GBR_set_ui(alpha, 0);
 123                 } else
 124                 if (use_saved) {
 125                         row = GBR_lp_next_row(lp);
 126                         GBR_set(F_new, F_saved);
 127                         fixed = fixed_saved;
 128                         GBR_set(alpha, alpha_saved[i]);
 129                 } else {
 130                         row = GBR_lp_add_row(lp, basis->row[i], dim);
 131                         GBR_lp_set_obj(lp, basis->row[i+1], dim);
 132                         bset->ctx->stats->gbr_solved_lps++;
 133                         unbounded = GBR_lp_solve(lp);
 134                         isl_assert(bset->ctx, !unbounded, goto error);
 135                         GBR_lp_get_obj_val(lp, &F_new);
 136                         fixed = GBR_lp_is_fixed(lp);
 137
 138                         GBR_lp_get_alpha(lp, row, &alpha);
 139
 140                         if (i > 0)
 141                                 save_alpha(lp, row-i, i, alpha_saved);
 142
 143                         GBR_lp_del_row(lp);
 144                 }
 145                 GBR_set(F[i+1], F_new);
 146
 147                 GBR_floor(mu[0], alpha);
 148                 GBR_ceil(mu[1], alpha);
 149
 150                 if (isl_int_eq(mu[0], mu[1]))
 151                         isl_int_set(tmp, mu[0]);
 152                 else {
 153                         int j;
 154
 155                         for (j = 0; j <= 1; ++j) {
 156                                 isl_int_set(tmp, mu[j]);
 157                                 isl_seq_combine(b_tmp->el,
 158                                                 bset->ctx->one, basis->row[i+1],
 159                                                 tmp, basis->row[i], dim);
 160                                 GBR_lp_set_obj(lp, b_tmp->el, dim);
 161                                 bset->ctx->stats->gbr_solved_lps++;
 162                                 unbounded = GBR_lp_solve(lp);
 163                                 isl_assert(bset->ctx, !unbounded, goto error);
 164                                 GBR_lp_get_obj_val(lp, &mu_F[j]);
 165                                 mu_fixed[j] = GBR_lp_is_fixed(lp);
 166                                 if (i > 0)
 167                                         save_alpha(lp, row-i, i, alpha_buffer[j]);
 168                         }
 169
 170                         if (GBR_lt(mu_F[0], mu_F[1]))
 171                                 j = 0;
 172                         else
 173                                 j = 1;
 174
 175                         isl_int_set(tmp, mu[j]);
 176                         GBR_set(F_new, mu_F[j]);
 177                         fixed = mu_fixed[j];
 178                         alpha_saved = alpha_buffer[j];
 179                 }
 180                 isl_seq_combine(basis->row[i+1],
 181                                 bset->ctx->one, basis->row[i+1],
 182                                 tmp, basis->row[i], dim);
 183
 184                 if (i+1 == n_zero && fixed) {
 185                         if (!GBR_is_zero(F[i+1])) {
 186                                 empty = GBR_lp_cut(lp, basis->row[i+1]);
 187                                 if (empty)
 188                                         goto done;
 189                                 GBR_set_ui(F[i+1], 0);
 190                         }
 191                         n_zero++;
 192                 }
 193
 194                 GBR_set(F_old, F[i]);
 195
 196                 use_saved = 0;
 197                 /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
 198                 GBR_set_ui(mu_F[0], 4);
 199                 GBR_mul(mu_F[0], mu_F[0], F_new);
 200                 GBR_set_ui(mu_F[1], 3);
 201                 GBR_mul(mu_F[1], mu_F[1], F_old);
 202                 if (GBR_lt(mu_F[0], mu_F[1])) {
 203                         basis = isl_mat_swap_rows(basis, i, i + 1);
 204                         if (i > 0) {
 205                                 use_saved = 1;
 206                                 GBR_set(F_saved, F_new);
 207                                 fixed_saved = fixed;
 208                                 GBR_lp_del_row(lp);
 209                                 --i;
 210                         } else {
 211                                 GBR_set(F[0], F_new);
 212                                 if (bset->ctx->gbr_only_first &&
 213                                     GBR_lt(F[0], two))
 214                                         break;
 215
 216                                 if (fixed) {
 217                                         if (!GBR_is_zero(F[0])) {
 218                                                 empty = GBR_lp_cut(lp, basis->row[0]);
 219                                                 if (empty)
 220                                                         goto done;
 221                                                 GBR_set_ui(F[0], 0);
 222                                         }
 223                                         n_zero++;
 224                                 }
 225                         }
 226                 } else {
 227                         GBR_lp_add_row(lp, basis->row[i], dim);
 228                         ++i;
 229                 }
 230         } while (i < dim-1);
 231
 232         if (0) {
 233 done:
 234                 if (empty < 0) {
 235 error:
 236                         isl_mat_free(basis);
 237                         basis = NULL;
 238                 }
 239         }
 240
 241         GBR_lp_delete(lp);
 242
 243         if (alpha_buffer[1])
 244                 for (i = 0; i < dim; ++i) {
 245                         GBR_clear(F[i]);
 246                         GBR_clear(alpha_buffer[0][i]);
 247                         GBR_clear(alpha_buffer[1][i]);
 248                 }
 249         free(F);
 250         free(alpha_buffer[0]);
 251         free(alpha_buffer[1]);
 252
 253         isl_vec_free(b_tmp);
 254
 255         GBR_clear(alpha);
 256         GBR_clear(F_old);
 257         GBR_clear(F_new);
 258         GBR_clear(F_saved);
 259         GBR_clear(mu_F[0]);
 260         GBR_clear(mu_F[1]);
 261         GBR_clear(two);
 262         GBR_clear(one);
 263
 264         isl_int_clear(tmp);
 265         isl_int_clear(mu[0]);
 266         isl_int_clear(mu[1]);
 267
 268         return basis;
 269 }