File: matrix__permutations_8c_source.html

package info (click to toggle)
polylib 5.22.5-4%2Bdfsg
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, buster, trixie
  • size: 14,428 kB
  • sloc: ansic: 16,342; sh: 10,134; makefile: 506
file content (311 lines) | stat: -rw-r--r-- 36,239 bytes parent folder | download | duplicates (5)
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&nbsp;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&nbsp;List</span></a></li>
      <li><a href="globals.html"><span>File&nbsp;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 &lt;http://www.gnu.org/licenses/&gt;.</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 &lt;stdlib.h&gt;</span>
<a name="l00033"></a>00033 <span class="preprocessor">#include &lt;<a class="code" href="matrix__permutations_8h.html">polylib/matrix_permutations.h</a>&gt;</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&lt; 64; i++) {
<a name="l00040"></a>00040     n+=y%2;
<a name="l00041"></a>00041     y&gt;&gt;=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&lt; 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 &quot;position of the k^th variable, k \in [1..n] we can</span>
<a name="l00063"></a>00063 <span class="comment"> * call it a &quot;permutation vector&quot; if you wish transf[x][y] -&gt;</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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>==transf-&gt;<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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, transf-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>);
<a name="l00072"></a>00072   <span class="keywordflow">for</span> (i= 0; i&lt; transf-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00073"></a>00073     <span class="keywordflow">for</span> (j= 0; j&lt; transf-&gt;<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-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[permutation[i]][permutation[j]], transf-&gt;<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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, polyh-&gt;<a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00088"></a>00088   <span class="keywordflow">for</span> (i= 0; i&lt; polyh-&gt;<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-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0], polyh-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0]);
<a name="l00090"></a>00090     <span class="keywordflow">for</span> (j= 1; j&lt; polyh-&gt;<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-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][permutation[j-1]+1], polyh-&gt;<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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, C-&gt;<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)-&gt;NbRows == C-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a> &amp;&amp; (*Cp)-&gt;NbColumns==C-&gt;<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&lt; C-&gt;<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)-&gt;p[i][0], C-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0]);
<a name="l00114"></a>00114     <span class="keywordflow">for</span> (j= 1; j&lt; C-&gt;<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)-&gt;p[i][perm[j-1]+1], C-&gt;<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 &lt;i&gt;equalities&lt;/i&gt;, 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).  &lt;p&gt;</span>
<a name="l00124"></a>00124 <span class="comment"> * Notes: </span>
<a name="l00125"></a>00125 <span class="comment"> &lt;ul&gt;</span>
<a name="l00126"></a>00126 <span class="comment"> &lt;li&gt;brute force, surely enhanceable algorithm&lt;/li&gt;</span>
<a name="l00127"></a>00127 <span class="comment"> &lt;li&gt;limited number of variables in the zone: limit = bitwidth of long long</span>
<a name="l00128"></a>00128 <span class="comment"> &lt;/ul&gt;</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&gt;0 &amp;&amp; end &lt; Eqs-&gt;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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a> &gt;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 (&amp;#39;Constraints&amp;#39;), construct and return a polyhedron...">Constraints2Polyhedron</a>(Eqs2,
<a name="l00150"></a>00150                                              Eqs-&gt;<a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>*Eqs-&gt;<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&lt; Eqs-&gt;<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-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i], Eqs-&gt;<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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>, Eqs-&gt;<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-&gt;NbRows variables to eliminate.</span>
<a name="l00167"></a>00167 <span class="comment">     Generate all the combinations of Eqs-&gt;NbRows variables (-&gt; bits to 1 in</span>
<a name="l00168"></a>00168 <span class="comment">     the word &quot;combination&quot;) 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&lt;&lt;(Eqs-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>))-1;
<a name="l00173"></a>00173        (combination &lt; ((<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> <span class="keywordtype">int</span>) 1 &lt;&lt; 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-&gt;<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&lt; nb_vars; j++) {
<a name="l00179"></a>00179         <span class="keywordflow">if</span> ((combination&gt;&gt;j)%2) {
<a name="l00180"></a>00180           <span class="keywordflow">for</span> (i=0; i&lt; Eqs-&gt;<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-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][k], Eqs-&gt;<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, &amp;H, &amp;Q, &amp;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-&gt;<a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[Eqs-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>-1][Eqs-&gt;<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"> * &lt;i&gt;eliminable_vars&lt;/i&gt;</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-&gt;<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-&gt;<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&lt; 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-&gt;<a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a>+nb_parms+ i-k;
<a name="l00237"></a>00237     combination&gt;&gt;=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&lt; nb_parms; i++) {
<a name="l00241"></a>00241     permutation[nb_vars+i] = Eqs-&gt;<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-&gt;<a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-2] = Eqs-&gt;<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&lt; 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&lt; 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&nbsp;
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>