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 options->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  * or
  21  *      - we have moved forward all the way to the last direction
  22  *        and then back again all the way to the first direction.
  23  */
  24 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
  25 {
  26         unsigned dim;
  27         struct isl_mat *basis;
  28         int unbounded;
  29         int i;
  30         GBR_LP *lp = NULL;
  31         GBR_type F_old, alpha, F_new;
  32         int row;
  33         isl_int tmp;
  34         struct isl_vec *b_tmp;
  35         GBR_type *F = NULL;
  36         GBR_type *alpha_buffer[2] = { NULL, NULL };
  37         GBR_type *alpha_saved;
  38         GBR_type F_saved;
  39         int use_saved = 0;
  40         isl_int mu[2];
  41         GBR_type mu_F[2];
  42         GBR_type two;
  43
  44         if (!bset)
  45                 return NULL;
  46
  47         dim = isl_basic_set_total_dim(bset);
  48         basis = isl_mat_identity(bset->ctx, dim);
  49         if (!basis)
  50                 return NULL;
  51
  52         if (dim == 1)
  53                 return basis;
  54
  55         isl_int_init(tmp);
  56         isl_int_init(mu[0]);
  57         isl_int_init(mu[1]);
  58
  59         GBR_init(alpha);
  60         GBR_init(F_old);
  61         GBR_init(F_new);
  62         GBR_init(F_saved);
  63         GBR_init(mu_F[0]);
  64         GBR_init(mu_F[1]);
  65         GBR_init(two);
  66
  67         b_tmp = isl_vec_alloc(bset->ctx, dim);
  68         if (!b_tmp)
  69                 goto error;
  70
  71         F = isl_alloc_array(bset->ctx, GBR_type, dim);
  72         alpha_buffer[0] = isl_alloc_array(bset->ctx, GBR_type, dim);
  73         alpha_buffer[1] = isl_alloc_array(bset->ctx, GBR_type, dim);
  74         alpha_saved = alpha_buffer[0];
  75
  76         if (!F || !alpha_buffer[0] || !alpha_buffer[1])
  77                 goto error;
  78
  79         for (i = 0; i < dim; ++i) {
  80                 GBR_init(F[i]);
  81                 GBR_init(alpha_buffer[0][i]);
  82                 GBR_init(alpha_buffer[1][i]);
  83         }
  84
  85         GBR_set_ui(two, 2);
  86
  87         lp = GBR_lp_init(bset);
  88         if (!lp)
  89                 goto error;
  90
  91         i = 0;
  92
  93         GBR_lp_set_obj(lp, basis->row[0], dim);
  94         bset->ctx->stats->gbr_solved_lps++;
  95         unbounded = GBR_lp_solve(lp);
  96         isl_assert(bset->ctx, !unbounded, goto error);
  97         GBR_lp_get_obj_val(lp, &F[0]);
  98
  99         do {
 100                 if (use_saved) {
 101                         row = GBR_lp_next_row(lp);
 102                         GBR_set(F_new, F_saved);
 103                         GBR_set(alpha, alpha_saved[i]);
 104                 } else {
 105                         row = GBR_lp_add_row(lp, basis->row[i], dim);
 106                         GBR_lp_set_obj(lp, basis->row[i+1], dim);
 107                         bset->ctx->stats->gbr_solved_lps++;
 108                         unbounded = GBR_lp_solve(lp);
 109                         isl_assert(bset->ctx, !unbounded, goto error);
 110                         GBR_lp_get_obj_val(lp, &F_new);
 111
 112                         GBR_lp_get_alpha(lp, row, &alpha);
 113
 114                         if (i > 0)
 115                                 save_alpha(lp, row-i, i, alpha_saved);
 116
 117                         GBR_lp_del_row(lp);
 118                 }
 119                 GBR_set(F[i+1], F_new);
 120
 121                 GBR_floor(mu[0], alpha);
 122                 GBR_ceil(mu[1], alpha);
 123
 124                 if (isl_int_eq(mu[0], mu[1]))
 125                         isl_int_set(tmp, mu[0]);
 126                 else {
 127                         int j;
 128
 129                         for (j = 0; j <= 1; ++j) {
 130                                 isl_int_set(tmp, mu[j]);
 131                                 isl_seq_combine(b_tmp->el,
 132                                                 bset->ctx->one, basis->row[i+1],
 133                                                 tmp, basis->row[i], dim);
 134                                 GBR_lp_set_obj(lp, b_tmp->el, dim);
 135                                 bset->ctx->stats->gbr_solved_lps++;
 136                                 unbounded = GBR_lp_solve(lp);
 137                                 isl_assert(bset->ctx, !unbounded, goto error);
 138                                 GBR_lp_get_obj_val(lp, &mu_F[j]);
 139                                 if (i > 0)
 140                                         save_alpha(lp, row-i, i, alpha_buffer[j]);
 141                         }
 142
 143                         if (GBR_lt(mu_F[0], mu_F[1]))
 144                                 j = 0;
 145                         else
 146                                 j = 1;
 147
 148                         isl_int_set(tmp, mu[j]);
 149                         GBR_set(F_new, mu_F[j]);
 150                         alpha_saved = alpha_buffer[j];
 151                 }
 152                 isl_seq_combine(basis->row[i+1],
 153                                 bset->ctx->one, basis->row[i+1],
 154                                 tmp, basis->row[i], dim);
 155
 156                 GBR_set(F_old, F[i]);
 157
 158                 use_saved = 0;
 159                 /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
 160                 GBR_set_ui(mu_F[0], 4);
 161                 GBR_mul(mu_F[0], mu_F[0], F_new);
 162                 GBR_set_ui(mu_F[1], 3);
 163                 GBR_mul(mu_F[1], mu_F[1], F_old);
 164                 if (GBR_lt(mu_F[0], mu_F[1])) {
 165                         basis = isl_mat_swap_rows(basis, i, i + 1);
 166                         if (i > 0) {
 167                                 use_saved = 1;
 168                                 GBR_set(F_saved, F_new);
 169                                 GBR_lp_del_row(lp);
 170                                 --i;
 171                         } else {
 172                                 GBR_set(F[0], F_new);
 173                                 if (bset->ctx->gbr_only_first &&
 174                                     GBR_lt(F[0], two))
 175                                         break;
 176                         }
 177                 } else {
 178                         GBR_lp_add_row(lp, basis->row[i], dim);
 179                         ++i;
 180                 }
 181         } while (i < dim-1);
 182
 183         if (0) {
 184 error:
 185             isl_mat_free(basis);
 186             basis = NULL;
 187         }
 188
 189         GBR_lp_delete(lp);
 190
 191         if (alpha_buffer[1])
 192                 for (i = 0; i < dim; ++i) {
 193                         GBR_clear(F[i]);
 194                         GBR_clear(alpha_buffer[0][i]);
 195                         GBR_clear(alpha_buffer[1][i]);
 196                 }
 197         free(F);
 198         free(alpha_buffer[0]);
 199         free(alpha_buffer[1]);
 200
 201         isl_vec_free(b_tmp);
 202
 203         GBR_clear(alpha);
 204         GBR_clear(F_old);
 205         GBR_clear(F_new);
 206         GBR_clear(F_saved);
 207         GBR_clear(mu_F[0]);
 208         GBR_clear(mu_F[1]);
 209         GBR_clear(two);
 210
 211         isl_int_clear(tmp);
 212         isl_int_clear(mu[0]);
 213         isl_int_clear(mu[1]);
 214
 215         return basis;
 216 }