1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>polylib: matrix_permutations.c Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.1 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="main.html"><span>Main Page</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<h1>matrix_permutations.c</h1><a href="matrix__permutations_8c.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> This file is part of PolyLib.</span>
<a name="l00003"></a>00003 <span class="comment"></span>
<a name="l00004"></a>00004 <span class="comment"> PolyLib is free software: you can redistribute it and/or modify</span>
<a name="l00005"></a>00005 <span class="comment"> it under the terms of the GNU General Public License as published by</span>
<a name="l00006"></a>00006 <span class="comment"> the Free Software Foundation, either version 3 of the License, or</span>
<a name="l00007"></a>00007 <span class="comment"> (at your option) any later version.</span>
<a name="l00008"></a>00008 <span class="comment"></span>
<a name="l00009"></a>00009 <span class="comment"> PolyLib is distributed in the hope that it will be useful,</span>
<a name="l00010"></a>00010 <span class="comment"> but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00011"></a>00011 <span class="comment"> MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span>
<a name="l00012"></a>00012 <span class="comment"> GNU General Public License for more details.</span>
<a name="l00013"></a>00013 <span class="comment"></span>
<a name="l00014"></a>00014 <span class="comment"> You should have received a copy of the GNU General Public License</span>
<a name="l00015"></a>00015 <span class="comment"> along with PolyLib. If not, see <http://www.gnu.org/licenses/>.</span>
<a name="l00016"></a>00016 <span class="comment">*/</span>
<a name="l00017"></a>00017 <span class="comment"></span>
<a name="l00018"></a>00018 <span class="comment">/** </span>
<a name="l00019"></a>00019 <span class="comment"> * $Id: matrix_permutations.c,v 1.8 2006/10/01 02:10:46 meister Exp $</span>
<a name="l00020"></a>00020 <span class="comment"> *</span>
<a name="l00021"></a>00021 <span class="comment"> * Permutations on matrices Matrices are seen either as transformations</span>
<a name="l00022"></a>00022 <span class="comment"> * (mtransformation) or as polyhedra (mpolyhedron)</span>
<a name="l00023"></a>00023 <span class="comment"> * @author B. Meister</span>
<a name="l00024"></a>00024 <span class="comment"> * LSIIT -ICPS </span>
<a name="l00025"></a>00025 <span class="comment"> * UMR 7005 CNRS</span>
<a name="l00026"></a>00026 <span class="comment"> * Louis Pasteur University (ULP), Strasbourg, France </span>
<a name="l00027"></a>00027 <span class="comment"> * </span>
<a name="l00028"></a>00028 <span class="comment"> * Permutations are just indirection vectors: the k^th element of a permutation</span>
<a name="l00029"></a>00029 <span class="comment"> * vector is the position of the k^th variable in the permuted object.</span>
<a name="l00030"></a>00030 <span class="comment"> */</span>
<a name="l00031"></a>00031
<a name="l00032"></a>00032 <span class="preprocessor">#include <stdlib.h></span>
<a name="l00033"></a>00033 <span class="preprocessor">#include <<a class="code" href="matrix__permutations_8h.html">polylib/matrix_permutations.h</a>></span>
<a name="l00034"></a>00034 <span class="comment"></span>
<a name="l00035"></a>00035 <span class="comment">/** utility function : bit count (i know, there are faster methods) */</span>
<a name="l00036"></a><a class="code" href="matrix__permutations_8h.html#a9258ae89e8c6c38ba0a82824cd790fef">00036</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="matrix__permutations_8c.html#a9258ae89e8c6c38ba0a82824cd790fef" title="Idmatrix_permutations.c,v 1.8 2006/10/01 02:10:46 meister Exp ">nb_bits</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span> x) {
<a name="l00037"></a>00037 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,<a class="code" href="polyparam_8c.html#a76f11d9a0a47b94f72c2d0e77fb32240">n</a>=0;
<a name="l00038"></a>00038 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span> y=x;
<a name="l00039"></a>00039 <span class="keywordflow">for</span> (i=0; i< 64; i++) {
<a name="l00040"></a>00040 n+=y%2;
<a name="l00041"></a>00041 y>>=1;
<a name="l00042"></a>00042 }
<a name="l00043"></a>00043 <span class="keywordflow">return</span> n;
<a name="l00044"></a>00044 }
<a name="l00045"></a>00045
<a name="l00046"></a>00046 <span class="comment"></span>
<a name="l00047"></a>00047 <span class="comment">/** Gives the inverse permutation vector of a permutation vector </span>
<a name="l00048"></a>00048 <span class="comment"> * @param perm the permutation vector</span>
<a name="l00049"></a>00049 <span class="comment"> * @param </span>
<a name="l00050"></a>00050 <span class="comment">*/</span>
<a name="l00051"></a><a class="code" href="matrix__permutations_8h.html#afbe2c7462b899ca85c30140ac5403089">00051</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * <a class="code" href="matrix__permutations_8c.html#afbe2c7462b899ca85c30140ac5403089" title="Gives the inverse permutation vector of a permutation vector.">permutation_inverse</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * perm, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_elems) {
<a name="l00052"></a>00052 <span class="keywordtype">int</span> i;
<a name="l00053"></a>00053 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * inv_perm = (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> *)malloc(<span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>) * nb_elems);
<a name="l00054"></a>00054 <span class="keywordflow">for</span> (i=0; i< nb_elems; i++) inv_perm[perm[i]] = i;
<a name="l00055"></a>00055 <span class="keywordflow">return</span> inv_perm;
<a name="l00056"></a>00056 }
<a name="l00057"></a>00057
<a name="l00058"></a>00058 <span class="comment"></span>
<a name="l00059"></a>00059 <span class="comment">/**</span>
<a name="l00060"></a>00060 <span class="comment"> * Given a linear tranformation on initial variables, and a variable</span>
<a name="l00061"></a>00061 <span class="comment"> * permutation, computes the tranformation for the permuted variables. perm is</span>
<a name="l00062"></a>00062 <span class="comment"> * a vector giving the new "position of the k^th variable, k \in [1..n] we can</span>
<a name="l00063"></a>00063 <span class="comment"> * call it a "permutation vector" if you wish transf[x][y] -></span>
<a name="l00064"></a>00064 <span class="comment"> * permuted[permutation(x)][permutation(y)]</span>
<a name="l00065"></a>00065 <span class="comment"> */</span>
<a name="l00066"></a><a class="code" href="matrix__permutations_8h.html#ace85f1b44be83dc08923e3a7bc66804c">00066</a> <a class="code" href="structmatrix.html">Matrix</a> * <a class="code" href="matrix__permutations_8c.html#ace85f1b44be83dc08923e3a7bc66804c" title="Given a linear tranformation on initial variables, and a variable permutation, computes...">mtransformation_permute</a>(<a class="code" href="structmatrix.html">Matrix</a> * transf, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * permutation) {
<a name="l00067"></a>00067 <a class="code" href="structmatrix.html">Matrix</a> * permuted;
<a name="l00068"></a>00068 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00069"></a>00069 <span class="comment">/* the transformation is supposed to be from Q^n to Q^n, so a square matrix. */</span>
<a name="l00070"></a>00070 <a class="code" href="assert_8h.html#a07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(transf-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>==transf-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00071"></a>00071 permuted = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(transf-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, transf-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>);
<a name="l00072"></a>00072 <span class="keywordflow">for</span> (i= 0; i< transf-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00073"></a>00073 <span class="keywordflow">for</span> (j= 0; j< transf-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; j++) {
<a name="l00074"></a>00074 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>(permuted-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[permutation[i]][permutation[j]], transf-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00075"></a>00075 }
<a name="l00076"></a>00076 }
<a name="l00077"></a>00077 <span class="keywordflow">return</span> permuted;
<a name="l00078"></a>00078 }
<a name="l00079"></a>00079
<a name="l00080"></a>00080 <span class="comment"></span>
<a name="l00081"></a>00081 <span class="comment">/** permutes the variables of the constraints of a polyhedron </span>
<a name="l00082"></a>00082 <span class="comment"> * @param polyh the constraints of the polyhedron</span>
<a name="l00083"></a>00083 <span class="comment"> * @param permutation a permutation vector</span>
<a name="l00084"></a>00084 <span class="comment">*/</span>
<a name="l00085"></a><a class="code" href="matrix__permutations_8h.html#ae642907b1f7aac2f4ec8f174b27ab830">00085</a> <a class="code" href="structmatrix.html">Matrix</a> * <a class="code" href="matrix__permutations_8c.html#ae642907b1f7aac2f4ec8f174b27ab830" title="permutes the variables of the constraints of a polyhedron">mpolyhedron_permute</a>(<a class="code" href="structmatrix.html">Matrix</a> * polyh, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * permutation) {
<a name="l00086"></a>00086 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00087"></a>00087 <a class="code" href="structmatrix.html">Matrix</a> * permuted = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(polyh-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, polyh-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00088"></a>00088 <span class="keywordflow">for</span> (i= 0; i< polyh-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00089"></a>00089 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>(permuted-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0], polyh-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0]);
<a name="l00090"></a>00090 <span class="keywordflow">for</span> (j= 1; j< polyh-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>; j++) {
<a name="l00091"></a>00091 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>(permuted-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][permutation[j-1]+1], polyh-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00092"></a>00092 }
<a name="l00093"></a>00093 }
<a name="l00094"></a>00094 <span class="keywordflow">return</span> permuted;
<a name="l00095"></a>00095 }
<a name="l00096"></a>00096
<a name="l00097"></a>00097 <span class="comment"></span>
<a name="l00098"></a>00098 <span class="comment">/** permutes the variables of the constraints of a polyhedron </span>
<a name="l00099"></a>00099 <span class="comment"> * @param C the original set of constraints</span>
<a name="l00100"></a>00100 <span class="comment"> * @param perm a permutation vector</span>
<a name="l00101"></a>00101 <span class="comment"> * @param Cp (returned) the set of constraints whose variables are</span>
<a name="l00102"></a>00102 <span class="comment"> * permuted. Allocated if set to NULL, assumed to be already allocated if not.</span>
<a name="l00103"></a>00103 <span class="comment"> */</span>
<a name="l00104"></a><a class="code" href="matrix__permutations_8h.html#a1714c230c3b1785a1da3c38bcbf7e661">00104</a> <span class="keywordtype">void</span> <a class="code" href="matrix__permutations_8c.html#a1714c230c3b1785a1da3c38bcbf7e661" title="permutes the variables of the constraints of a polyhedron">Constraints_permute</a>(<a class="code" href="structmatrix.html">Matrix</a> * C, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * perm, <a class="code" href="structmatrix.html">Matrix</a> ** Cp) {
<a name="l00105"></a>00105 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00106"></a>00106 <span class="keywordflow">if</span> ((*Cp)==NULL) {
<a name="l00107"></a>00107 (*Cp) = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(C-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, C-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00108"></a>00108 }
<a name="l00109"></a>00109 <span class="keywordflow">else</span> {
<a name="l00110"></a>00110 <a class="code" href="assert_8h.html#a07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>((*Cp)->NbRows == C-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a> && (*Cp)->NbColumns==C-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00111"></a>00111 }
<a name="l00112"></a>00112 <span class="keywordflow">for</span> (i= 0; i< C-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00113"></a>00113 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>((*Cp)->p[i][0], C-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0]);
<a name="l00114"></a>00114 <span class="keywordflow">for</span> (j= 1; j< C-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>; j++) {
<a name="l00115"></a>00115 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>((*Cp)->p[i][perm[j-1]+1], C-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00116"></a>00116 }
<a name="l00117"></a>00117 }
<a name="l00118"></a>00118 } <span class="comment">/* Constraints_permute */</span>
<a name="l00119"></a>00119
<a name="l00120"></a>00120 <span class="comment"></span>
<a name="l00121"></a>00121 <span class="comment">/** Given a set of <i>equalities</i>, find a set of variables that can be</span>
<a name="l00122"></a>00122 <span class="comment"> * eliminated using these equalities. The variables that we agree to eliminate</span>
<a name="l00123"></a>00123 <span class="comment"> * are in a zone of contiguous variables (or parameters). <p></span>
<a name="l00124"></a>00124 <span class="comment"> * Notes: </span>
<a name="l00125"></a>00125 <span class="comment"> <ul></span>
<a name="l00126"></a>00126 <span class="comment"> <li>brute force, surely enhanceable algorithm</li></span>
<a name="l00127"></a>00127 <span class="comment"> <li>limited number of variables in the zone: limit = bitwidth of long long</span>
<a name="l00128"></a>00128 <span class="comment"> </ul></span>
<a name="l00129"></a>00129 <span class="comment"> * @param Eqs the matrix of equalities.</span>
<a name="l00130"></a>00130 <span class="comment"> * @param start the rank of the first variable (inclusive) of the zone in Eqs</span>
<a name="l00131"></a>00131 <span class="comment"> * @param end the rank of the last variable (inclusive) of the zone</span>
<a name="l00132"></a>00132 <span class="comment"> * return a bitfield where bits set to one define the variables to eliminate</span>
<a name="l00133"></a>00133 <span class="comment">*/</span>
<a name="l00134"></a><a class="code" href="matrix__permutations_8h.html#a46efd59d133aa22046bd57718c7be05a">00134</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span> <a class="code" href="matrix__permutations_8c.html#a46efd59d133aa22046bd57718c7be05a" title="Given a set of equalities, find a set of variables that can be eliminated using these...">eliminable_vars</a>(<a class="code" href="structmatrix.html">Matrix</a> * Eqs, <span class="keywordtype">unsigned</span> start,
<a name="l00135"></a>00135 <span class="keywordtype">unsigned</span> end) {
<a name="l00136"></a>00136 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span> combination;
<a name="l00137"></a>00137 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j,k;
<a name="l00138"></a>00138 <a class="code" href="structmatrix.html">Matrix</a> * M, * H, * Q, *U;
<a name="l00139"></a>00139 <a class="code" href="structmatrix.html">Matrix</a> * Square_Mat, *Eqs2;
<a name="l00140"></a>00140 <span class="keywordtype">unsigned</span> nb_vars = end - start + 1 ;
<a name="l00141"></a>00141 <a class="code" href="structpolyhedron.html">Polyhedron</a> * OverConstrained;
<a name="l00142"></a>00142
<a name="l00143"></a>00143 <a class="code" href="assert_8h.html#a07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a> (start>0 && end < Eqs->NbColumns-1);
<a name="l00144"></a>00144
<a name="l00145"></a>00145 <span class="comment">/* if the affine hull is overconstrained, return 0 */</span>
<a name="l00146"></a>00146 <span class="keywordflow">if</span> (Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a> >nb_vars) {
<a name="l00147"></a>00147 <span class="comment">/* FIXME: there is a magic maximum number of rays here */</span>
<a name="l00148"></a>00148 Eqs2 = <a class="code" href="Matop_8c.html#a9d027e9fc6b85e6fa37fc284bf1b5e06">Matrix_Copy</a>(Eqs);
<a name="l00149"></a>00149 OverConstrained = <a class="code" href="polyhedron_8c.html#aefb77665a187d751bdd44f106b12465e" title="Given a matrix of constraints (&#39;Constraints&#39;), construct and return a polyhedron...">Constraints2Polyhedron</a>(Eqs2,
<a name="l00150"></a>00150 Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>*Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00151"></a>00151 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(Eqs2);
<a name="l00152"></a>00152 <span class="keywordflow">if</span> (<a class="code" href="types_8h.html#a156641ae25106f9a6ac5c5c2a624c168">emptyQ</a>(OverConstrained)) {
<a name="l00153"></a>00153 <a class="code" href="polyhedron_8c.html#a4ae97b9794e3a616f1d38c68e6515cc3">Polyhedron_Free</a>(OverConstrained);
<a name="l00154"></a>00154 <span class="keywordflow">return</span> 0;
<a name="l00155"></a>00155 }
<a name="l00156"></a>00156 <a class="code" href="polyhedron_8c.html#a4ae97b9794e3a616f1d38c68e6515cc3">Polyhedron_Free</a>(OverConstrained);
<a name="l00157"></a>00157 }
<a name="l00158"></a>00158
<a name="l00159"></a>00159 <span class="comment">/* do not accept 0 = 0 equalities */</span>
<a name="l00160"></a>00160 <span class="keywordflow">for</span> (i=0; i< Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00161"></a>00161 <a class="code" href="assert_8h.html#a07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a> (!<a class="code" href="vector_8c.html#a4f5f43ecdfb5c63f8c3ecbf875887869">Vector_IsZero</a>(Eqs-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i], Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>));
<a name="l00162"></a>00162 }
<a name="l00163"></a>00163
<a name="l00164"></a>00164 Square_Mat= <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>);
<a name="l00165"></a>00165
<a name="l00166"></a>00166 <span class="comment">/* There are Eqs->NbRows variables to eliminate.</span>
<a name="l00167"></a>00167 <span class="comment"> Generate all the combinations of Eqs->NbRows variables (-> bits to 1 in</span>
<a name="l00168"></a>00168 <span class="comment"> the word "combination") among nb_vars WARNING : we assume here that we</span>
<a name="l00169"></a>00169 <span class="comment"> have not more than 64 variables. You may convert it to use GNU MP to</span>
<a name="l00170"></a>00170 <span class="comment"> set it to an infinite number of bits </span>
<a name="l00171"></a>00171 <span class="comment"> */</span>
<a name="l00172"></a>00172 <span class="keywordflow">for</span> (combination = ((<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span>) 1<<(Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>))-1;
<a name="l00173"></a>00173 (combination < ((<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span>) 1 << nb_vars)) ;
<a name="l00174"></a>00174 combination++) {
<a name="l00175"></a>00175 <span class="keywordflow">if</span> (<a class="code" href="matrix__permutations_8c.html#a9258ae89e8c6c38ba0a82824cd790fef" title="Idmatrix_permutations.c,v 1.8 2006/10/01 02:10:46 meister Exp ">nb_bits</a>(combination) == Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>) {
<a name="l00176"></a>00176 k=0;
<a name="l00177"></a>00177 <span class="comment">/* 1- put the m colums in a square matrix */</span>
<a name="l00178"></a>00178 <span class="keywordflow">for</span> (j=0; j< nb_vars; j++) {
<a name="l00179"></a>00179 <span class="keywordflow">if</span> ((combination>>j)%2) {
<a name="l00180"></a>00180 <span class="keywordflow">for</span> (i=0; i< Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00181"></a>00181 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>(Square_Mat-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][k], Eqs-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j+start]);
<a name="l00182"></a>00182 }
<a name="l00183"></a>00183 k++;
<a name="l00184"></a>00184 }
<a name="l00185"></a>00185 }
<a name="l00186"></a>00186 <span class="comment">/* 2- see if the matrix is full-row-rank */</span>
<a name="l00187"></a>00187 <a class="code" href="matrix_8c.html#a9d112ac078583626580f848b51a515f3">right_hermite</a>(Square_Mat, &H, &Q, &U);
<a name="l00188"></a>00188 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(Q);
<a name="l00189"></a>00189 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(U);
<a name="l00190"></a>00190
<a name="l00191"></a>00191 <span class="comment">/* if it is full-row-rank, we have found a set of variables that can be</span>
<a name="l00192"></a>00192 <span class="comment"> eliminated. */</span>
<a name="l00193"></a>00193 <span class="keywordflow">if</span> ( <a class="code" href="source_2arith_2arithmetique_8h.html#a47d32925340d2dc99ef2d4215080a60d">value_notzero_p</a>((H-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>-1][Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>-1])) ) {
<a name="l00194"></a>00194 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(Square_Mat);
<a name="l00195"></a>00195 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(H);
<a name="l00196"></a>00196 <span class="keywordflow">return</span> combination;
<a name="l00197"></a>00197 }
<a name="l00198"></a>00198 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(H);
<a name="l00199"></a>00199 }
<a name="l00200"></a>00200 }
<a name="l00201"></a>00201 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(Square_Mat);
<a name="l00202"></a>00202 <span class="keywordflow">return</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span>) 0;
<a name="l00203"></a>00203 } <span class="comment">/* eliminable_vars */</span>
<a name="l00204"></a>00204
<a name="l00205"></a>00205
<a name="l00206"></a>00206 <span class="comment"></span>
<a name="l00207"></a>00207 <span class="comment">/** </span>
<a name="l00208"></a>00208 <span class="comment"> * finds a valid permutation : for a set of m equations, find m variables that</span>
<a name="l00209"></a>00209 <span class="comment"> * will be put at the beginning (to be eliminated). </span>
<a name="l00210"></a>00210 <span class="comment"> * Note: inherits the limited the number of variables from</span>
<a name="l00211"></a>00211 <span class="comment"> * <i>eliminable_vars</i></span>
<a name="l00212"></a>00212 <span class="comment"> */</span>
<a name="l00213"></a><a class="code" href="matrix__permutations_8h.html#af43c186b57b2df6caa02a812c175a4d1">00213</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * <a class="code" href="matrix__permutations_8c.html#af43c186b57b2df6caa02a812c175a4d1" title="finds a valid permutation : for a set of m equations, find m variables that will...">find_a_permutation</a>(<a class="code" href="structmatrix.html">Matrix</a> * Eqs, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_parms) {
<a name="l00214"></a>00214 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i, j, k;
<a name="l00215"></a>00215 <span class="keywordtype">int</span> nb_vars = Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-nb_parms-2;
<a name="l00216"></a>00216 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span> combination;
<a name="l00217"></a>00217 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * permutation = (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> *)malloc(<span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>) *
<a name="l00218"></a>00218 Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1);
<a name="l00219"></a>00219
<a name="l00220"></a>00220 <span class="comment">/* 1- find a set of variables to eliminate */</span>
<a name="l00221"></a>00221 <span class="keywordflow">if</span> ((combination = <a class="code" href="matrix__permutations_8c.html#a46efd59d133aa22046bd57718c7be05a" title="Given a set of equalities, find a set of variables that can be eliminated using these...">eliminable_vars</a>(Eqs, 1, nb_vars)) == 0) {
<a name="l00222"></a>00222 <span class="comment">/* if it is impossible to eliminate enough variables, return error code */</span>
<a name="l00223"></a>00223 <span class="keywordflow">return</span> NULL;
<a name="l00224"></a>00224 }
<a name="l00225"></a>00225
<a name="l00226"></a>00226 <span class="comment">/* 2- make the permutation matrix</span>
<a name="l00227"></a>00227 <span class="comment"> * a- deal with the variables */</span>
<a name="l00228"></a>00228 k=0;
<a name="l00229"></a>00229 <span class="keywordflow">for</span> (i=0; i< nb_vars; i++) {
<a name="l00230"></a>00230 <span class="comment">/* if the variable has to be eliminated, put them at the beginning */</span>
<a name="l00231"></a>00231 <span class="keywordflow">if</span> (combination%2) {
<a name="l00232"></a>00232 permutation[i] = k;
<a name="l00233"></a>00233 k++;
<a name="l00234"></a>00234 }
<a name="l00235"></a>00235 <span class="comment">/* if not, put the variables at the end */</span>
<a name="l00236"></a>00236 <span class="keywordflow">else</span> permutation[i] = Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>+nb_parms+ i-k;
<a name="l00237"></a>00237 combination>>=1;
<a name="l00238"></a>00238 }
<a name="l00239"></a>00239 <span class="comment">/* b- deal with the parameters */</span>
<a name="l00240"></a>00240 <span class="keywordflow">for</span> (i=0; i< nb_parms; i++) {
<a name="l00241"></a>00241 permutation[nb_vars+i] = Eqs-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>+i;
<a name="l00242"></a>00242 }
<a name="l00243"></a>00243 <span class="comment">/* c- deal with the constant */</span>
<a name="l00244"></a>00244 permutation[Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-2] = Eqs-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-2;
<a name="l00245"></a>00245
<a name="l00246"></a>00246 <span class="keywordflow">return</span> permutation;
<a name="l00247"></a>00247 } <span class="comment">/* find_a_permutation */</span>
<a name="l00248"></a>00248
<a name="l00249"></a>00249
<a name="l00250"></a>00250 <span class="comment"></span>
<a name="l00251"></a>00251 <span class="comment">/** computes the permutation of variables and parameters, according to some</span>
<a name="l00252"></a>00252 <span class="comment"> * variables to keep. put the variables not to be kept at the beginning, then</span>
<a name="l00253"></a>00253 <span class="comment"> * the parameters and finally the variables to be kept. strongly related to</span>
<a name="l00254"></a>00254 <span class="comment"> * the function compress_to_full_dim2</span>
<a name="l00255"></a>00255 <span class="comment"> */</span>
<a name="l00256"></a><a class="code" href="matrix__permutations_8h.html#a2969569d57d59249e748e075e2494789">00256</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * <a class="code" href="matrix__permutations_8c.html#a2969569d57d59249e748e075e2494789" title="computes the permutation of variables and parameters, according to some variables...">permutation_for_full_dim2</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * vars_to_keep,
<a name="l00257"></a>00257 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_keep,
<a name="l00258"></a>00258 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_vars_parms,
<a name="l00259"></a>00259 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_parms) {
<a name="l00260"></a>00260 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> * permutation =
<a name="l00261"></a>00261 (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>*)malloc(<span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>) * nb_vars_parms+1);
<a name="l00262"></a>00262 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
<a name="l00263"></a>00263 <span class="keywordtype">int</span> cur_keep =0, cur_go = 0;<span class="comment">/*current number of variables to eliminate/keep*/</span>
<a name="l00264"></a>00264 <span class="keywordflow">for</span> (i=0; i< nb_vars_parms - nb_parms; i++) {
<a name="l00265"></a>00265 <span class="keywordflow">if</span> (i==vars_to_keep[cur_keep]) {
<a name="l00266"></a>00266 permutation[i] = nb_vars_parms-nb_keep+cur_keep;
<a name="l00267"></a>00267 cur_keep++;
<a name="l00268"></a>00268 }
<a name="l00269"></a>00269 <span class="keywordflow">else</span> {
<a name="l00270"></a>00270 permutation[i] = cur_go;
<a name="l00271"></a>00271 cur_go++;
<a name="l00272"></a>00272 }
<a name="l00273"></a>00273 }
<a name="l00274"></a>00274 <span class="comment">/* parameters are just left-shifted */</span>
<a name="l00275"></a>00275 <span class="keywordflow">for</span> (i=0; i< nb_parms; i++)
<a name="l00276"></a>00276 permutation[i+nb_vars_parms-nb_parms] = i+nb_vars_parms-nb_parms-nb_keep;
<a name="l00277"></a>00277
<a name="l00278"></a>00278 <span class="comment">/* contants stay where they are */</span>
<a name="l00279"></a>00279 permutation[nb_vars_parms] = nb_vars_parms;
<a name="l00280"></a>00280 <span class="keywordflow">return</span> permutation;
<a name="l00281"></a>00281 } <span class="comment">/* permutation_for_full_dim2 */</span>
</pre></div></div>
<hr size="1"/><address style="text-align: right;"><small>Generated on Wed Nov 25 17:45:26 2009 for polylib by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
|