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_AntiScale(V->Vertex->p[i], V->Vertex->p[i],
  45                        V->Vertex->p[i][nb_param+1], nb_param+2);
  46     }
  47
  48   /* the expansion can be actually writen as global_var_lcm.L^{-1} */
  49   /* this is equivalent to multiply the rows of P by denoms_det */
  50   for (i = 0; i < nb_vars; i++)
  51     value_division(denoms->p[i], global_var_lcm, denoms->p[i]);
  52
  53   /* OPT : we could use a vector instead of a diagonal matrix here (c- and d-).*/
  54   /* c- make the quick expansion matrix */
  55   expansion = Matrix_Alloc(nb_vars+nb_param+1, nb_vars+nb_param+1);
  56   for (i = 0; i < nb_vars; i++)
  57     value_assign(expansion->p[i][i], denoms->p[i]);
  58   for (i = nb_vars; i < nb_vars+nb_param+1; i++)
  59     value_assign(expansion->p[i][i], global_var_lcm);
  60
  61   /* d- apply the variable expansion to the polyhedron */
  62   if (P)
  63     *P = Polyhedron_Preimage(*P, expansion, MaxRays);
  64
  65   Matrix_Free(expansion);
  66   value_clear(global_var_lcm);
  67   Vector_Free(denoms);
  68 }