include/polylib/compress_parms.h

   1 /**
   2  * @author B. Meister 12/2003-2006
   3  * LSIIT -ICPS
   4  * UMR 7005 CNRS
   5  * Louis Pasteur University (ULP), Strasbourg, France
   6  */
   7 #ifndef __BM_COMPRESS_PARMS_H__
   8 #define __BM_COMPRESS_PARMS_H__
   9
  10 #include "matrix_addon.h"
  11 #include "matrix_permutations.h"
  12 #include <assert.h>
  13
  14
  15 /* ----- functions applying on equalities ----- */
  16
  17 /**
  18  * Given a system of non-redundant equalities, looks if it has an integer
  19  * solution in the combined space, and if yes, returns one solution.
  20  */
  21 void Equalities_integerSolution(Matrix * Eqs, Matrix ** sol);
  22
  23 /**
  24  * Computes the validity lattice of a set of equalities. I.e., the lattice
  25  * induced on the last <tt>b</tt> variables by the equalities involving the
  26  * first <tt>a</tt> integer existential variables.
  27  */
  28 void Equalities_validityLattice(Matrix * Eqs, int a, Matrix** vl);
  29
  30 /**
  31  * Given an integer matrix B with m rows and integer m-vectors C and d,
  32  * computes the basis of the integer solutions to (BN+C) mod d = 0 (1).
  33  * This is an affine lattice (G): (N 1)^T= G(N' 1)^T, forall N' in Z^b.
  34  * If there is no solution, returns NULL.
  35 */
  36 void Equalities_intModBasis(Matrix * B, Matrix * C, Matrix * d, Matrix ** imb);
  37
  38
  39 /* ----- functions applying on constraints ----- */
  40
  41
  42 /**
  43  * Eliminates all the equalities in a set of constraints and returns the set of
  44  * constraints defining a full-dimensional polyhedron, such that there is a
  45  * bijection between integer points of the original polyhedron and these of the
  46  * resulting (projected) polyhedron).
  47  */
  48 void Constraints_fullDimensionize(Matrix ** M, Matrix ** C, Matrix ** VL,
  49                                   Matrix ** Eqs, Matrix ** ParmEqs,
  50                                   unsigned int ** elimVars,
  51                                   unsigned int ** elimParms,
  52                                   int maxRays);
  53
  54 /* extracts equalities involving only parameters */
  55 #define Constraints_removeParmEqs(a,b,c,d) Constraints_Remove_parm_eqs(a,b,c,d)
  56 Matrix * Constraints_Remove_parm_eqs(Matrix ** M, Matrix ** Ctxt,
  57                                      int renderSpace,
  58                                      unsigned int ** elimParms);
  59
  60 /**
  61  * Eliminates the columns corresponding to a list of eliminated parameters.
  62  */
  63 void Constraints_removeElimCols(Matrix * M, unsigned int nbVars,
  64                                 unsigned int *elimParms, Matrix ** newM);
  65
  66
  67 /* ----- function applying on a lattice ----- */
  68
  69 /**
  70  * Given a matrix that defines a full-dimensional affine lattice, returns the
  71  * affine sub-lattice spanned in the k first dimensions.
  72  * Useful for instance when you only look for the parameters' validity lattice.
  73  */
  74 void Lattice_extractSubLattice(Matrix * lat, unsigned int k, Matrix ** subLat);
  75
  76
  77 /* ----- functions applying on a polyhedron ----- */
  78
  79
  80 Polyhedron * Polyhedron_Remove_parm_eqs(Polyhedron ** P, Polyhedron ** C,
  81                                       int renderSpace,
  82                                       unsigned int ** elimParms,
  83                                       int maxRays);
  84 #define Polyhedron_removeParmEqs(a,b,c,d,e) Polyhedron_Remove_parm_eqs(a,b,c,d,e)
  85
  86
  87 /* ----- functions kept for backwards compatibility ----- */
  88
  89
  90 /**
  91  * given a full-row-rank nxm matrix M(made of row-vectors),
  92  * computes the basis K (made of n-m column-vectors) of the integer kernel of M
  93  * so we have: M.K = 0
  94 */
  95 Matrix * int_ker(Matrix * M);
  96
  97 /* given a matrix of m parameterized equations, compress the parameters and
  98  transform the variable space into a n-m space. */
  99 Matrix * full_dimensionize(Matrix const * M, int nb_parms,
 100                            Matrix ** Validity_Lattice);
 101
 102 /* Compute the overall period of the variables I for (MI) mod |d|,
 103  where M is a matrix and |d| a vector
 104  Produce a diagonal matrix S = (s_k) where s_k is the overall period of i_k */
 105 Matrix * affine_periods(Matrix * M, Matrix * d);
 106
 107 /* given a matrix B' with m rows and m-vectors C' and d, computes the
 108  basis of the integer solutions to (B'N+C') mod d = 0.
 109 returns NULL if there is no integer solution */
 110 Matrix * int_mod_basis(Matrix * Bp, Matrix * Cp, Matrix * d);
 111
 112 /* given a parameterized constraints matrix with m equalities, computes the
 113  compression matrix C such that there is an integer solution in the variables
 114  space for each value of N', with N = Cmp N' (N are the original parameters) */
 115 Matrix * compress_parms(Matrix * E, int nb_parms);
 116
 117
 118 #endif /* __BM_COMPRESS_PARMS_H__ */