include/polylib/matrix_addon.h

   1 /**
   2  * Polylib matrix addons
   3  * Mainly, deals with polyhedra represented in implicit form (set of
   4  * constraints).
   5  * @author Benoit Meister
   6  */
   7
   8 #ifndef __BM_MATRIX_ADDON_H__
   9 #define __BM_MATRIX_ADDON_H__
  10
  11 #include<polylib/polylib.h>
  12 #include<assert.h>
  13
  14 /** Shortcut for Matrix_Print */
  15 #define show_matrix(M) { printf(#M"= \n"); \
  16                          if (M!=NULL) { \
  17                          Matrix_Print(stderr,P_VALUE_FMT,(M));} \
  18                          else {printf("<NULL>\n");} \
  19                        }
  20
  21 /**
  22  * Allocates a matrix if it is null, or else asserts that it has at least a
  23  * certain size */
  24 #define ensureMatrix(M, r, c) { if (M==NULL) M = Matrix_Alloc(r,c); \
  25                                 else assert (M->NbRows>=r && M->NbColumns>=c); \
  26                               }
  27
  28 /* Creates a view of the constraints of a polyhedron as a Matrix * */
  29 Matrix * constraintsView(Polyhedron * P);
  30
  31 /* "Frees" a view of the constraints of a polyhedron */
  32 void constraintsView_Free(Matrix * M);
  33
  34 /* splits a matrix of constraints M into a matrix of equalities Eqs and a
  35    matrix of inequalities Ineqs allocs the new matrices. */
  36 void split_constraints(Matrix const * M, Matrix ** Eqs, Matrix **Ineqs);
  37
  38 /* returns the dim-dimensional identity matrix */
  39 Matrix * Identity_Matrix(unsigned int dim);
  40
  41 void Matrix_identity(unsigned int dim, Matrix **I);
  42
  43 /* given a n x n integer transformation matrix transf, compute its inverse M/g,
  44  where M is a nxn integer matrix.  g is a common denominator for elements of
  45  (transf^{-1})*/
  46 void mtransformation_inverse(Matrix * transf, Matrix ** inv, Value * g);
  47
  48 /* simplifies a matrix seen as a polyhedron, by dividing its rows by the gcd of
  49 their elements. */
  50 void mpolyhedron_simplify(Matrix * polyh);
  51
  52 /* inflates a polyhedron (represented as a matrix) P, so that the apx of its
  53    Ehrhart Polynomial is an upper bound of the Ehrhart polynomial of P WARNING:
  54    this inflation is supposed to be applied on full-dimensional polyhedra. */
  55 void mpolyhedron_inflate(Matrix * polyh, unsigned int nb_parms);
  56
  57 /* deflates a polyhedron (represented as a matrix) P, so that the apx of its
  58    Ehrhart Polynomial is a lower bound of the Ehrhart polynomial of P WARNING:
  59    this deflation is supposed to be applied on full-dimensional polyhedra. */
  60 void mpolyhedron_deflate(Matrix * polyh, unsigned int nb_parms);
  61
  62 /* use an eliminator row to eliminate a variable in a victim row (without
  63 changing the sign of the victim row -> important if it is an inequality).  */
  64 void eliminate_var_with_constr(Matrix * Eliminator,
  65                                unsigned int eliminator_row, Matrix * Victim,
  66                                unsigned int victim_row,
  67                                unsigned int var_to_elim);
  68
  69
  70 /* ----- PARTIAL MAPPINGS ----- */
  71
  72 /* compresses the last vars/pars of the polyhedron M expressed as a polylib
  73    matrix
  74  - adresses the full-rank compressions only
  75  - modfies M */
  76 void mpolyhedron_compress_last_vars(Matrix * M, Matrix * compression);
  77 #define Constraints_compressLastVars(a, b) mpolyhedron_compress_last_vars(a, b)
  78
  79 /* uses a set of m equalities Eqs to eliminate m variables in the polyhedron.
  80  Ineqs represented as a matrix eliminates the m first variables
  81 - assumes that Eqs allows to eliminate the m equalities
  82 - modifies Ineqs */
  83 unsigned int mpolyhedron_eliminate_first_variables(Matrix * Eqs,
  84                                                    Matrix * Ineqs);
  85 #define Constraints_eliminateFirstVars(a,b) mpolyhedron_eliminate_first_variables(a,b)
  86
  87 /** returns a contiguous submatrix of a matrix. */
  88 void Matrix_subMatrix(Matrix * M, unsigned int sr, unsigned int sc,
  89                       unsigned int nbR, unsigned int nbC, Matrix ** sub);
  90 /**
  91  * Cloning function. Similar to Matrix_Copy() but allocates the target matrix
  92  * if it is set to NULL.
  93  */
  94 void Matrix_clone(Matrix * M, Matrix ** Cl);
  95
  96 /**
  97  * Copies a contiguous submatrix of M1 into M2, at the indicated position.
  98  * M1 and M2 are assumed t be allocated already.
  99  */
 100 void Matrix_copySubMatrix(Matrix *M1,
 101                           unsigned int sr1, unsigned int sc1,
 102                           unsigned int nbR, unsigned int nbC,
 103                           Matrix * M2,
 104                           unsigned int sr2, unsigned int sc2);
 105
 106 /**
 107  * given a matrix M into -M
 108  */
 109 void Matrix_oppose(Matrix * M);
 110
 111 #endif /* __BM_MATRIX_ADDON_H__ */