include/polylib/compress_parms.h

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