Param_Polyhedron_Scale_Integer.c

   1 #include <barvinok/polylib.h>
   2
   3 /*
   4  * Scales the parametric polyhedron such that all vertices are integer.
   5  */
   6 void Param_Polyhedron_Scale_Integer(Param_Polyhedron *PP, Polyhedron **P,
   7                                     Value *det, unsigned MaxRays)
   8 {
   9   int i;
  10   int nb_param, nb_vars;
  11   Vector *denoms;
  12   Param_Vertices *V;
  13   Value global_var_lcm;
  14   Matrix *expansion;
  15
  16   value_set_si(*det, 1);
  17   if (!PP->nbV)
  18     return;
  19
  20   nb_param = PP->D->Domain->Dimension;
  21   nb_vars = PP->V->Vertex->NbRows;
  22
  23   /* Scan the vertices and make an orthogonal expansion of the variable
  24      space */
  25   /* a- prepare the array of common denominators */
  26   denoms = Vector_Alloc(nb_vars);
  27   value_init(global_var_lcm);
  28
  29   /* b- scan the vertices and compute the variables' global lcms */
  30   for (V = PP->V; V; V = V->next)
  31     for (i = 0; i < nb_vars; i++)
  32       Lcm3(denoms->p[i], V->Vertex->p[i][nb_param+1], &denoms->p[i]);
  33
  34   value_set_si(global_var_lcm, 1);
  35   for (i = 0; i < nb_vars; i++) {
  36     value_multiply(*det, *det, denoms->p[i]);
  37     Lcm3(global_var_lcm, denoms->p[i], &global_var_lcm);
  38   }
  39
  40   /* scale vertices */
  41   for (V = PP->V; V; V = V->next)
  42     for (i = 0; i < nb_vars; i++) {
  43       Vector_Scale(V->Vertex->p[i], V->Vertex->p[i], denoms->p[i], nb_param+1);
  44       Vector_Normalize(V->Vertex->p[i], nb_param+2);
  45     }
  46
  47   /* the expansion can be actually writen as global_var_lcm.L^{-1} */
  48   /* this is equivalent to multiply the rows of P by denoms_det */
  49   for (i = 0; i < nb_vars; i++)
  50     value_division(denoms->p[i], global_var_lcm, denoms->p[i]);
  51
  52   /* OPT : we could use a vector instead of a diagonal matrix here (c- and d-).*/
  53   /* c- make the quick expansion matrix */
  54   expansion = Matrix_Alloc(nb_vars+nb_param+1, nb_vars+nb_param+1);
  55   for (i = 0; i < nb_vars; i++)
  56     value_assign(expansion->p[i][i], denoms->p[i]);
  57   for (i = nb_vars; i < nb_vars+nb_param+1; i++)
  58     value_assign(expansion->p[i][i], global_var_lcm);
  59
  60   /* d- apply the variable expansion to the polyhedron */
  61   if (P)
  62     *P = Polyhedron_Preimage(*P, expansion, MaxRays);
  63
  64   Matrix_Free(expansion);
  65   value_clear(global_var_lcm);
  66   Vector_Free(denoms);
  67 }