00001 /** 00002 * Permutations on matrices 00003 * Matrices are seen either as transformations (mtransformation) or as 00004 * polyhedra (mpolyhedron or Constraints). 00005 * @author B. Meister 00006 */ 00007 00008 #ifndef __BM_MATRIX_PERMUTATIONS_H__ 00009 #define __BM_MATRIX_PERMUTATIONS_H__ 00010 00011 #include<polylib/polylib.h> 00012 #include<assert.h> 00013 00014 /* Permutations here are vectors that give the future position for each 00015 variable */ 00016 00017 /* utility function : bit count */ 00018 unsigned int nb_bits(unsigned long long int x); 00019 00020 /* gives the inverse permutation vector of a permutation vector */ 00021 unsigned int * permutation_inverse(unsigned int * perm, unsigned int nb_elems); 00022 00023 /* 00024 * Given a linear tranformation on initial variables, and a variable 00025 * permutation, compute the tranformation for the permuted variables. perm is 00026 * a vector giving the new "position of the k^th variable, k \in [1..n] we can 00027 * call it a "permutation vector" if you wish transf[x][y] -> 00028 * permuted[permutation(x)][permutation(y)] 00029 */ 00030 Matrix * mtransformation_permute(Matrix * transf, unsigned int * permutation); 00031 00032 /* permutes the variables of a matrix seen as a polyhedron */ 00033 Matrix * mpolyhedron_permute(Matrix * polyh, unsigned int * permutation); 00034 00035 /* permutes the variables of a matrix seen as a polyhedron */ 00036 void Constraints_permute(Matrix * C, unsigned int * perm, Matrix ** Cp); 00037 00038 /** Given a set of <i>equalities</i>, find a set of variables that can be 00039 * eliminated using these equalities. The variables that we agree to eliminate 00040 * are in a zone of contiguous variables (or parameters). <p> 00041 * Notes: 00042 <ul> 00043 <li>brute force, surely enhanceable algorithm</li> 00044 <li>limited number of variables in the zone: limit = bitwidth of long long 00045 </ul> 00046 * @param Eqs the matrix of equalities. 00047 * @param start the rank of the first variable (inclusive) of the zone in Eqs 00048 * @param end the rank of the last variable (inclusive) of the zone 00049 * return a bitfield where bits set to one define the variables to eliminate 00050 */ 00051 unsigned long long int eliminable_vars(Matrix * Eqs, unsigned start, 00052 unsigned end); 00053 00054 /* 00055 * find a valid permutation : for a set of m equations, find m variables that 00056 * will be put at the beginning (to be eliminated) it must be possible to 00057 * eliminate these variables : the submatrix built with their columns must be 00058 * full-rank. brute force method, that tests all the combinations until finding 00059 * one which works. 00060 * <b>LIMITATIONS</b> : up to x-1 variables, where the long long 00061 * format is x-1 bits (often 64 in year 2005). 00062 */ 00063 unsigned int * find_a_permutation(Matrix * Eqs, unsigned int nb_parms); 00064 00065 /* 00066 * compute the permutation of variables and parameters, according to some 00067 * variables to keep. put the variables not to be kept at the beginning, then 00068 * the parameters and finally the variables to be kept. strongly related to the 00069 * function compress_to_full_dim2 00070 */ 00071 unsigned int * permutation_for_full_dim2(unsigned int * vars_to_keep, 00072 unsigned int nb_keep, 00073 unsigned int nb_vars_parms, 00074 unsigned int nb_parms); 00075 00076 #endif /*__BM_MATRIX_PERMUTATIONS_H__ */
1.5.6