X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=basis_reduction_templ.c;h=7f4b28f06c9fc95557fc06e1e27d8ef4d2aa01e6;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=ecb191fcbf13362838f34a4fea14f2e84a89510c;hpb=61eefa8fe09982393c83beb48b487509c4135b13;p=platform%2Fupstream%2Fisl.git diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c index ecb191f..7f4b28f 100644 --- a/basis_reduction_templ.c +++ b/basis_reduction_templ.c @@ -1,4 +1,19 @@ +/* + * Copyright 2006-2007 Universiteit Leiden + * Copyright 2008-2009 Katholieke Universiteit Leuven + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science, + * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands + * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A, + * B-3001 Leuven, Belgium + */ + #include +#include +#include +#include #include "isl_basis_reduction.h" static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha) @@ -9,22 +24,32 @@ static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha) GBR_lp_get_alpha(lp, first + i, &alpha[i]); } -/* This function implements the algorithm described in +/* Compute a reduced basis for the set represented by the tableau "tab". + * tab->basis, which must be initialized by the calling function to an affine + * unimodular basis, is updated to reflect the reduced basis. + * The first tab->n_zero rows of the basis (ignoring the constant row) + * are assumed to correspond to equalities and are left untouched. + * tab->n_zero is updated to reflect any additional equalities that + * have been detected in the first rows of the new basis. + * The final tab->n_unbounded rows of the basis are assumed to correspond + * to unbounded directions and are also left untouched. + * In particular this means that the remaining rows are assumed to + * correspond to bounded directions. + * + * This function implements the algorithm described in * "An Implementation of the Generalized Basis Reduction Algorithm * for Integer Programming" of Cook el al. to compute a reduced basis. * We use \epsilon = 1/4. * - * If options->gbr_only_first is set, the user is only interested + * If ctx->opt->gbr_only_first is set, the user is only interested * in the first direction. In this case we stop the basis reduction when - * - the width in the first direction becomes smaller than 2 - * or - * - we have moved forward all the way to the last direction - * and then back again all the way to the first direction. + * the width in the first direction becomes smaller than 2. */ -struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) +struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) { unsigned dim; - struct isl_mat *basis; + struct isl_ctx *ctx; + struct isl_mat *B; int unbounded; int i; GBR_LP *lp = NULL; @@ -40,17 +65,30 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) isl_int mu[2]; GBR_type mu_F[2]; GBR_type two; - - if (!bset) + GBR_type one; + int empty = 0; + int fixed = 0; + int fixed_saved = 0; + int mu_fixed[2]; + int n_bounded; + int gbr_only_first; + + if (!tab) return NULL; - dim = isl_basic_set_total_dim(bset); - basis = isl_mat_identity(bset->ctx, dim); - if (!basis) - return NULL; + if (tab->empty) + return tab; - if (dim == 1) - return basis; + ctx = tab->mat->ctx; + gbr_only_first = ctx->opt->gbr_only_first; + dim = tab->n_var; + B = tab->basis; + if (!B) + return tab; + + n_bounded = dim - tab->n_unbounded; + if (n_bounded <= tab->n_zero + 1) + return tab; isl_int_init(tmp); isl_int_init(mu[0]); @@ -63,58 +101,82 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) GBR_init(mu_F[0]); GBR_init(mu_F[1]); GBR_init(two); + GBR_init(one); - b_tmp = isl_vec_alloc(bset->ctx, dim); + b_tmp = isl_vec_alloc(ctx, dim); if (!b_tmp) goto error; - F = isl_alloc_array(bset->ctx, GBR_type, dim); - alpha_buffer[0] = isl_alloc_array(bset->ctx, GBR_type, dim); - alpha_buffer[1] = isl_alloc_array(bset->ctx, GBR_type, dim); + F = isl_alloc_array(ctx, GBR_type, n_bounded); + alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded); + alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded); alpha_saved = alpha_buffer[0]; if (!F || !alpha_buffer[0] || !alpha_buffer[1]) goto error; - for (i = 0; i < dim; ++i) { + for (i = 0; i < n_bounded; ++i) { GBR_init(F[i]); GBR_init(alpha_buffer[0][i]); GBR_init(alpha_buffer[1][i]); } GBR_set_ui(two, 2); + GBR_set_ui(one, 1); - lp = GBR_lp_init(bset); + lp = GBR_lp_init(tab); if (!lp) goto error; - i = 0; + i = tab->n_zero; - GBR_lp_set_obj(lp, basis->row[0], dim); - bset->ctx->stats->gbr_solved_lps++; + GBR_lp_set_obj(lp, B->row[1+i]+1, dim); + ctx->stats->gbr_solved_lps++; unbounded = GBR_lp_solve(lp); - isl_assert(bset->ctx, !unbounded, goto error); - GBR_lp_get_obj_val(lp, &F[0]); + isl_assert(ctx, !unbounded, goto error); + GBR_lp_get_obj_val(lp, &F[i]); + + if (GBR_lt(F[i], one)) { + if (!GBR_is_zero(F[i])) { + empty = GBR_lp_cut(lp, B->row[1+i]+1); + if (empty) + goto done; + GBR_set_ui(F[i], 0); + } + tab->n_zero++; + } do { + if (i+1 == tab->n_zero) { + GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim); + ctx->stats->gbr_solved_lps++; + unbounded = GBR_lp_solve(lp); + isl_assert(ctx, !unbounded, goto error); + GBR_lp_get_obj_val(lp, &F_new); + fixed = GBR_lp_is_fixed(lp); + GBR_set_ui(alpha, 0); + } else if (use_saved) { row = GBR_lp_next_row(lp); GBR_set(F_new, F_saved); + fixed = fixed_saved; GBR_set(alpha, alpha_saved[i]); } else { - row = GBR_lp_add_row(lp, basis->row[i], dim); - GBR_lp_set_obj(lp, basis->row[i+1], dim); - bset->ctx->stats->gbr_solved_lps++; + row = GBR_lp_add_row(lp, B->row[1+i]+1, dim); + GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim); + ctx->stats->gbr_solved_lps++; unbounded = GBR_lp_solve(lp); - isl_assert(bset->ctx, !unbounded, goto error); + isl_assert(ctx, !unbounded, goto error); GBR_lp_get_obj_val(lp, &F_new); + fixed = GBR_lp_is_fixed(lp); GBR_lp_get_alpha(lp, row, &alpha); if (i > 0) save_alpha(lp, row-i, i, alpha_saved); - GBR_lp_del_row(lp); + if (GBR_lp_del_row(lp) < 0) + goto error; } GBR_set(F[i+1], F_new); @@ -129,13 +191,14 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) for (j = 0; j <= 1; ++j) { isl_int_set(tmp, mu[j]); isl_seq_combine(b_tmp->el, - bset->ctx->one, basis->row[i+1], - tmp, basis->row[i], dim); + ctx->one, B->row[1+i+1]+1, + tmp, B->row[1+i]+1, dim); GBR_lp_set_obj(lp, b_tmp->el, dim); - bset->ctx->stats->gbr_solved_lps++; + ctx->stats->gbr_solved_lps++; unbounded = GBR_lp_solve(lp); - isl_assert(bset->ctx, !unbounded, goto error); + isl_assert(ctx, !unbounded, goto error); GBR_lp_get_obj_val(lp, &mu_F[j]); + mu_fixed[j] = GBR_lp_is_fixed(lp); if (i > 0) save_alpha(lp, row-i, i, alpha_buffer[j]); } @@ -147,11 +210,21 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) isl_int_set(tmp, mu[j]); GBR_set(F_new, mu_F[j]); + fixed = mu_fixed[j]; alpha_saved = alpha_buffer[j]; } - isl_seq_combine(basis->row[i+1], - bset->ctx->one, basis->row[i+1], - tmp, basis->row[i], dim); + isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1, + tmp, B->row[1+i]+1, dim); + + if (i+1 == tab->n_zero && fixed) { + if (!GBR_is_zero(F[i+1])) { + empty = GBR_lp_cut(lp, B->row[1+i+1]+1); + if (empty) + goto done; + GBR_set_ui(F[i+1], 0); + } + tab->n_zero++; + } GBR_set(F_old, F[i]); @@ -162,34 +235,48 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) GBR_set_ui(mu_F[1], 3); GBR_mul(mu_F[1], mu_F[1], F_old); if (GBR_lt(mu_F[0], mu_F[1])) { - basis = isl_mat_swap_rows(basis, i, i + 1); - if (i > 0) { + B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1); + if (i > tab->n_zero) { use_saved = 1; GBR_set(F_saved, F_new); - GBR_lp_del_row(lp); + fixed_saved = fixed; + if (GBR_lp_del_row(lp) < 0) + goto error; --i; } else { - GBR_set(F[0], F_new); - if (bset->ctx->gbr_only_first && - GBR_lt(F[0], two)) + GBR_set(F[tab->n_zero], F_new); + if (gbr_only_first && GBR_lt(F[tab->n_zero], two)) break; + + if (fixed) { + if (!GBR_is_zero(F[tab->n_zero])) { + empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1); + if (empty) + goto done; + GBR_set_ui(F[tab->n_zero], 0); + } + tab->n_zero++; + } } } else { - GBR_lp_add_row(lp, basis->row[i], dim); + GBR_lp_add_row(lp, B->row[1+i]+1, dim); ++i; } - } while (i < dim-1); + } while (i < n_bounded - 1); if (0) { +done: + if (empty < 0) { error: - isl_mat_free(basis); - basis = NULL; + isl_mat_free(B); + B = NULL; + } } GBR_lp_delete(lp); if (alpha_buffer[1]) - for (i = 0; i < dim; ++i) { + for (i = 0; i < n_bounded; ++i) { GBR_clear(F[i]); GBR_clear(alpha_buffer[0][i]); GBR_clear(alpha_buffer[1][i]); @@ -207,10 +294,64 @@ error: GBR_clear(mu_F[0]); GBR_clear(mu_F[1]); GBR_clear(two); + GBR_clear(one); isl_int_clear(tmp); isl_int_clear(mu[0]); isl_int_clear(mu[1]); + tab->basis = B; + + return tab; +} + +/* Compute an affine form of a reduced basis of the given basic + * non-parametric set, which is assumed to be bounded and not + * include any integer divisions. + * The first column and the first row correspond to the constant term. + * + * If the input contains any equalities, we first create an initial + * basis with the equalities first. Otherwise, we start off with + * the identity matrix. + */ +struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset) +{ + struct isl_mat *basis; + struct isl_tab *tab; + + if (!bset) + return NULL; + + if (isl_basic_set_dim(bset, isl_dim_div) != 0) + isl_die(bset->ctx, isl_error_invalid, + "no integer division allowed", return NULL); + if (isl_basic_set_dim(bset, isl_dim_param) != 0) + isl_die(bset->ctx, isl_error_invalid, + "no parameters allowed", return NULL); + + tab = isl_tab_from_basic_set(bset, 0); + if (!tab) + return NULL; + + if (bset->n_eq == 0) + tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var); + else { + isl_mat *eq; + unsigned nvar = isl_basic_set_total_dim(bset); + eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq, + 1, nvar); + eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis); + tab->basis = isl_mat_lin_to_aff(tab->basis); + tab->n_zero = bset->n_eq; + isl_mat_free(eq); + } + tab = isl_tab_compute_reduced_basis(tab); + if (!tab) + return NULL; + + basis = isl_mat_copy(tab->basis); + + isl_tab_free(tab); + return basis; }