+/*
+ * 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 <stdlib.h>
+#include <isl_ctx_private.h>
+#include <isl_map_private.h>
+#include <isl_options_private.h>
#include "isl_basis_reduction.h"
static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
}
/* Compute a reduced basis for the set represented by the tableau "tab".
- * tab->basis, must be initialized by the calling function to an affine
+ * 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.
* for Integer Programming" of Cook el al. to compute a reduced basis.
* We use \epsilon = 1/4.
*
- * If ctx->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.
*/
int fixed_saved = 0;
int mu_fixed[2];
int n_bounded;
+ int gbr_only_first;
if (!tab)
return NULL;
+ if (tab->empty)
+ return tab;
+
ctx = tab->mat->ctx;
+ gbr_only_first = ctx->opt->gbr_only_first;
dim = tab->n_var;
B = tab->basis;
if (!B)
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);
use_saved = 1;
GBR_set(F_saved, F_new);
fixed_saved = fixed;
- GBR_lp_del_row(lp);
+ if (GBR_lp_del_row(lp) < 0)
+ goto error;
--i;
} else {
GBR_set(F[tab->n_zero], F_new);
- if (ctx->gbr_only_first && GBR_lt(F[tab->n_zero], two))
+ if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
break;
if (fixed) {
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;
- isl_assert(bset->ctx, bset->n_eq == 0, return NULL);
+ 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);
- tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
+ 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;