counter.cc

   1 #include <assert.h>
   2 #include <barvinok/util.h>
   3 #include "counter.h"
   4 #include "lattice_point.h"
   5
   6 using std::cerr;
   7 using std::endl;
   8
   9 /* Computes the integer points in the fundamental parallelepiped and
  10  * passes them along (in num) to the counter specific (i.e., specialization
  11  * specific) add_lattice_points.
  12  */
  13 void counter_base::handle(const mat_ZZ& rays, Value *V, const QQ& c,
  14                           unsigned long det, barvinok_options *options)
  15 {
  16     Matrix* Rays = zz2matrix(rays);
  17
  18     assert(c.d == 1);
  19     assert(c.n == 1 || c.n == -1);
  20     int sign = to_int(c.n);
  21
  22     Matrix_Vector_Product(Rays, lambda->p, den->p_Init);
  23     for (int k = 0; k < dim; ++k)
  24         if (value_zero_p(den->p_Init[k])) {
  25             Matrix_Free(Rays);
  26             throw Orthogonal;
  27         }
  28     Inner_Product(lambda->p, V, dim, &tmp);
  29     lattice_points_fixed(V, &tmp, Rays, den, num, det);
  30     num->NbRows = det;
  31     Matrix_Free(Rays);
  32
  33     if (dim % 2)
  34         sign = -sign;
  35
  36     add_lattice_points(sign);
  37 }
  38
  39 static void add_falling_powers(dpoly& n, Value degree)
  40 {
  41     value_increment(n.coeff->p[0], n.coeff->p[0]);
  42     if (n.coeff->Size == 1)
  43         return;
  44
  45     int min = n.coeff->Size-1;
  46     if (value_posz_p(degree) && value_cmp_si(degree, min) < 0)
  47         min = VALUE_TO_INT(degree);
  48
  49     Value tmp;
  50     value_init(tmp);
  51     value_assign(tmp, degree);
  52     value_addto(n.coeff->p[1], n.coeff->p[1], tmp);
  53     for (int i = 2; i <= min; ++i) {
  54         value_decrement(degree, degree);
  55         value_multiply(tmp, tmp, degree);
  56         mpz_divexact_ui(tmp, tmp, i);
  57         value_addto(n.coeff->p[i], n.coeff->p[i], tmp);
  58     }
  59     value_clear(tmp);
  60 }
  61
  62 void counter::add_lattice_points(int sign)
  63 {
  64     dpoly d(dim);
  65     for (int k = 0; k < num->NbRows; ++k)
  66         add_falling_powers(d, num->p_Init[k]);
  67     dpoly n(dim, den->p_Init[0], 1);
  68     for (int k = 1; k < dim; ++k) {
  69         dpoly fact(dim, den->p_Init[k], 1);
  70         n *= fact;
  71     }
  72     d.div(n, count, sign);
  73 }
  74
  75
  76
  77
  78 void tcounter::setup_todd(unsigned dim)
  79 {
  80     value_set_si(todd.coeff->p[0], 1);
  81
  82     dpoly d(dim);
  83     value_set_si(d.coeff->p[dim], 1);
  84     for (int i = dim-1; i >= 0; --i)
  85         mpz_mul_ui(d.coeff->p[i], d.coeff->p[i+1], i+2);
  86
  87     todd_denom = todd.div(d);
  88     /* shift denominators up -> divide by (dim+1)! */
  89     for (int i = todd.coeff->Size-1; i >= 1; --i)
  90         value_assign(todd_denom->p[i], todd_denom->p[i-1]);
  91     value_set_si(todd_denom->p[0], 1);
  92 }
  93
  94 void tcounter::adapt_todd(dpoly& t, const Value c)
  95 {
  96     if (t.coeff->Size <= 1)
  97         return;
  98     value_assign(tmp, c);
  99     value_multiply(t.coeff->p[1], t.coeff->p[1], tmp);
 100     for (int i = 2; i < t.coeff->Size; ++i) {
 101         value_multiply(tmp, tmp, c);
 102         value_multiply(t.coeff->p[i], t.coeff->p[i], tmp);
 103     }
 104 }
 105
 106 void tcounter::add_powers(dpoly& n, const Value c)
 107 {
 108     value_increment(n.coeff->p[0], n.coeff->p[0]);
 109     if (n.coeff->Size == 1)
 110         return;
 111     value_assign(tmp, c);
 112     value_addto(n.coeff->p[1], n.coeff->p[1], tmp);
 113     for (int i = 2; i < n.coeff->Size; ++i) {
 114         value_multiply(tmp, tmp, c);
 115         value_addto(n.coeff->p[i], n.coeff->p[i], tmp);
 116     }
 117 }
 118
 119 void tcounter::add_lattice_points(int sign)
 120 {
 121     dpoly t(todd);
 122     value_assign(denom, den->p_Init[0]);
 123     adapt_todd(t, den->p_Init[0]);
 124     for (int k = 1; k < dim; ++k) {
 125         dpoly fact(todd);
 126         value_multiply(denom, denom, den->p_Init[k]);
 127         adapt_todd(fact, den->p_Init[k]);
 128         t *= fact;
 129     }
 130
 131     dpoly n(dim);
 132     for (int k = 0; k < num->NbRows; ++k)
 133         add_powers(n, num->p_Init[k]);
 134
 135     for (int i = 0; i < n.coeff->Size; ++i)
 136         value_multiply(n.coeff->p[i], n.coeff->p[i], todd_denom->p[i]);
 137     value_multiply(denom, denom, todd_denom->p[todd_denom->Size-1]);
 138
 139     value_set_si(tmp, 1);
 140     for (int i = 2; i < n.coeff->Size; ++i) {
 141         mpz_mul_ui(tmp, tmp, i);
 142         mpz_divexact(n.coeff->p[i], n.coeff->p[i], tmp);
 143     }
 144
 145     value_multiply(tmp, t.coeff->p[0], n.coeff->p[n.coeff->Size-1]);
 146     for (int i = 1; i < n.coeff->Size; ++i)
 147         value_addmul(tmp, t.coeff->p[i], n.coeff->p[n.coeff->Size-1-i]);
 148
 149     value_assign(mpq_numref(tcount), tmp);
 150     value_assign(mpq_denref(tcount), denom);
 151     mpq_canonicalize(tcount);
 152     if (sign == -1)
 153         mpq_sub(count, count, tcount);
 154     else
 155         mpq_add(count, count, tcount);
 156 }
 157
 158
 159 /*
 160  * Set lambda to a random vector that has a positive inner product
 161  * with all the rays of the context { x | A x + b >= 0 }.
 162  *
 163  * To do so, we take d rows A' from the constraint matrix A.
 164  * For every ray, we have
 165  *              A' r >= 0
 166  * We compute a random positive row vector x' and set x = x' A'.
 167  * We then have, for each ray r,
 168  *              x r = x' A' r >= 0
 169  * Although we can take any d rows from A, we choose linearly
 170  * independent rows from A to avoid the elements of the transformed
 171  * random vector to have simple linear relations, which would
 172  * increase the risk of the vector being orthogonal to one of
 173  * powers in the denominator of one of the terms in the generating
 174  * function.
 175  */
 176 void infinite_counter::init(Polyhedron *context)
 177 {
 178     Matrix *M, *H, *Q, *U;
 179     mat_ZZ A;
 180
 181     randomvector(context, lambda, context->Dimension);
 182
 183     M = Matrix_Alloc(context->NbConstraints, context->Dimension);
 184     for (int i = 0; i < context->NbConstraints; ++i)
 185         Vector_Copy(context->Constraint[i]+1, M->p[i], context->Dimension);
 186     left_hermite(M, &H, &Q, &U);
 187     Matrix_Free(Q);
 188     Matrix_Free(U);
 189
 190     for (int col = 0, row = 0; col < H->NbColumns; ++col, ++row) {
 191         for (; row < H->NbRows; ++row)
 192             if (value_notzero_p(H->p[row][col]))
 193                 break;
 194         assert(row < H->NbRows);
 195         Vector_Copy(M->p[row], M->p[col], M->NbColumns);
 196     }
 197     matrix2zz(M, A, context->Dimension, context->Dimension);
 198     Matrix_Free(H);
 199     Matrix_Free(M);
 200
 201     for (int i = 0; i < lambda.length(); ++i)
 202         lambda[i] = abs(lambda[i]);
 203     lambda = lambda * A;
 204 }
 205
 206 static ZZ LCM(const ZZ& a, const ZZ& b)
 207 {
 208     return a * b / GCD(a, b);
 209 }
 210
 211 /* Normalize the powers in the denominator to be positive
 212  * and return -1 is the sign has to be changed.
 213  */
 214 static int normalized_sign(vec_ZZ& num, vec_ZZ& den)
 215 {
 216     int change = 0;
 217
 218     for (int j = 0; j < den.length(); ++j) {
 219         if (den[j] > 0)
 220             change ^= 1;
 221         else {
 222             den[j] = abs(den[j]);
 223             for (int k = 0; k < num.length(); ++k)
 224                 num[k] += den[j];
 225         }
 226     }
 227     return change ? -1 : 1;
 228 }
 229
 230 void infinite_counter::reduce(const vec_QQ& c, const mat_ZZ& num,
 231                               const mat_ZZ& den_f)
 232 {
 233     mpq_t factor;
 234     mpq_init(factor);
 235     unsigned len = den_f.NumRows();
 236
 237     ZZ lcm = c[0].d;
 238     for (int i = 1; i < c.length(); ++i)
 239         lcm = LCM(lcm, c[i].d);
 240
 241     vec_ZZ coeff;
 242     coeff.SetLength(c.length());
 243     for (int i = 0; i < c.length(); ++i)
 244         coeff[i] = c[i].n * lcm/c[i].d;
 245
 246     if (len == 0) {
 247         for (int i = 0; i < c.length(); ++i) {
 248             zz2value(coeff[i], tz);
 249             value_addto(mpq_numref(factor), mpq_numref(factor), tz);
 250         }
 251         zz2value(lcm, tz);
 252         value_assign(mpq_denref(factor), tz);
 253         mpq_add(count[0], count[0], factor);
 254         mpq_clear(factor);
 255         return;
 256     }
 257
 258     vec_ZZ num_s = num * lambda;
 259     vec_ZZ den_s = den_f * lambda;
 260     for (int i = 0; i < den_s.length(); ++i)
 261         assert(den_s[i] != 0);
 262     int sign = normalized_sign(num_s, den_s);
 263     if (sign < 0)
 264         coeff = -coeff;
 265
 266     dpoly n(len);
 267     zz2value(num_s[0], tz);
 268     add_falling_powers(n, tz);
 269     zz2value(coeff[0], tz);
 270     n *= tz;
 271     for (int i = 1; i < c.length(); ++i) {
 272         dpoly t(len);
 273         zz2value(num_s[i], tz);
 274         add_falling_powers(t, tz);
 275         zz2value(coeff[i], tz);
 276         t *= tz;
 277         n += t;
 278     }
 279     zz2value(den_s[0], tz);
 280     dpoly d(len, tz, 1);
 281     for (int i = 1; i < len; ++i) {
 282         zz2value(den_s[i], tz);
 283         dpoly fact(len, tz, 1);
 284         d *= fact;
 285     }
 286     value_set_si(mpq_numref(factor), 1);
 287     zz2value(lcm, tz);
 288     value_assign(mpq_denref(factor), tz);
 289     n.div(d, count, factor);
 290
 291     mpq_clear(factor);
 292 }