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
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>polylib: matrix_addon.c Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.6 -->
<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>
<h1>matrix_addon.c</h1><a href="matrix__addon_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"> * $Id: matrix_addon.c,v 1.17 2007/03/18 18:49:08 skimo Exp $</span>
<a name="l00003"></a>00003 <span class="comment"> * </span>
<a name="l00004"></a>00004 <span class="comment"> * Polylib matrix addons</span>
<a name="l00005"></a>00005 <span class="comment"> * Mainly, deals with polyhedra represented as a matrix (implicit form)</span>
<a name="l00006"></a>00006 <span class="comment"> * @author Benoit Meister <meister@icps.u-strasbg.fr></span>
<a name="l00007"></a>00007 <span class="comment"> * </span>
<a name="l00008"></a>00008 <span class="comment"> */</span>
<a name="l00009"></a>00009
<a name="l00010"></a>00010 <span class="preprocessor">#include <stdlib.h></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include<<a class="code" href="polylib_8h.html">polylib/polylib.h</a>></span>
<a name="l00012"></a>00012 <span class="preprocessor">#include <<a class="code" href="matrix__addon_8h.html">polylib/matrix_addon.h</a>></span>
<a name="l00013"></a>00013 <span class="comment"></span>
<a name="l00014"></a>00014 <span class="comment">/** Creates a view of the constraints of a polyhedron as a Matrix * */</span>
<a name="l00015"></a><a class="code" href="matrix__addon_8h.html#495de3cced5c0eecf74aef91b05502dd">00015</a> <a class="code" href="structmatrix.html">Matrix</a> * <a class="code" href="matrix__addon_8c.html#495de3cced5c0eecf74aef91b05502dd" title="Idmatrix_addon.c,v 1.17 2007/03/18 18:49:08 skimo Exp ">constraintsView</a>(<a class="code" href="structpolyhedron.html">Polyhedron</a> * P) {
<a name="l00016"></a>00016 <a class="code" href="structmatrix.html">Matrix</a> * view = (<a class="code" href="structmatrix.html">Matrix</a> *)malloc(<span class="keyword">sizeof</span>(<a class="code" href="structmatrix.html">Matrix</a>));
<a name="l00017"></a>00017 view-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a> = P-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>;
<a name="l00018"></a>00018 view-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a> = P-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+2;
<a name="l00019"></a>00019 view-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a> = P-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>;
<a name="l00020"></a>00020 <span class="keywordflow">return</span> view;
<a name="l00021"></a>00021 }
<a name="l00022"></a>00022 <span class="comment"></span>
<a name="l00023"></a>00023 <span class="comment">/** "Frees" a view of the constraints of a polyhedron */</span>
<a name="l00024"></a><a class="code" href="matrix__addon_8h.html#a0cc9da9320a0f253db72e78f4f6e56b">00024</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#a0cc9da9320a0f253db72e78f4f6e56b" title="&quot;Frees&quot; a view of the constraints of a polyhedron">constraintsView_Free</a>(<a class="code" href="structmatrix.html">Matrix</a> * M) {
<a name="l00025"></a>00025 free(M);
<a name="l00026"></a>00026 }
<a name="l00027"></a>00027 <span class="comment"></span>
<a name="l00028"></a>00028 <span class="comment">/** </span>
<a name="l00029"></a>00029 <span class="comment"> * splits a matrix of constraints M into a matrix of equalities Eqs and a</span>
<a name="l00030"></a>00030 <span class="comment"> * matrix of inequalities Ineqs allocs the new matrices. </span>
<a name="l00031"></a>00031 <span class="comment"> * Allocates Eqs and Ineqs.</span>
<a name="l00032"></a>00032 <span class="comment">*/</span>
<a name="l00033"></a><a class="code" href="matrix__addon_8h.html#288db1ffeb5425aada82cabf5c824bc4">00033</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#288db1ffeb5425aada82cabf5c824bc4" title="splits a matrix of constraints M into a matrix of equalities Eqs and a matrix of...">split_constraints</a>(<a class="code" href="structmatrix.html">Matrix</a> <span class="keyword">const</span> * M, <a class="code" href="structmatrix.html">Matrix</a> ** Eqs, <a class="code" href="structmatrix.html">Matrix</a> **Ineqs) {
<a name="l00034"></a>00034 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i, j, k_eq, k_ineq, nb_eqs=0;
<a name="l00035"></a>00035
<a name="l00036"></a>00036 <span class="comment">/* 1- count the number of equations */</span>
<a name="l00037"></a>00037 <span class="keywordflow">for</span> (i=0; i< M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++)
<a name="l00038"></a>00038 <span class="keywordflow">if</span> (<a class="code" href="source_2arith_2arithmetique_8h.html#827532f2140ae2aa96e46baebae09723">value_zero_p</a>(M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0])) nb_eqs++;
<a name="l00039"></a>00039
<a name="l00040"></a>00040 <span class="comment">/* 2- extract the two matrices of equations */</span>
<a name="l00041"></a>00041 (*Eqs) = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(nb_eqs, M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00042"></a>00042 (*Ineqs) = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>-nb_eqs, M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00043"></a>00043
<a name="l00044"></a>00044 k_eq = k_ineq = 0;
<a name="l00045"></a>00045 <span class="keywordflow">for</span>(i=0; i< M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00046"></a>00046 <span class="keywordflow">if</span> (<a class="code" href="source_2arith_2arithmetique_8h.html#827532f2140ae2aa96e46baebae09723">value_zero_p</a>(M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0]))
<a name="l00047"></a>00047 {
<a name="l00048"></a>00048 <span class="keywordflow">for</span>(j=0; j< M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>; j++)
<a name="l00049"></a>00049 <a class="code" href="source_2arith_2arithmetique_8h.html#864613888dc46f15679aa4f63e468f89">value_assign</a>((*Eqs)->p[k_eq][j], M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00050"></a>00050 k_eq++;
<a name="l00051"></a>00051 }
<a name="l00052"></a>00052 <span class="keywordflow">else</span>
<a name="l00053"></a>00053 {
<a name="l00054"></a>00054 <span class="keywordflow">for</span>(j=0; j< M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>; j++)
<a name="l00055"></a>00055 <a class="code" href="source_2arith_2arithmetique_8h.html#864613888dc46f15679aa4f63e468f89">value_assign</a>((*Ineqs)->p[k_ineq][j], M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00056"></a>00056 k_ineq++;
<a name="l00057"></a>00057 }
<a name="l00058"></a>00058 }
<a name="l00059"></a>00059 }
<a name="l00060"></a>00060
<a name="l00061"></a>00061
<a name="l00062"></a>00062 <span class="comment">/* returns the dim-dimensional identity matrix */</span>
<a name="l00063"></a><a class="code" href="matrix__addon_8h.html#33f64eb039ac943c1bddbafc3be3ece6">00063</a> <a class="code" href="structmatrix.html">Matrix</a> * <a class="code" href="matrix__addon_8c.html#33f64eb039ac943c1bddbafc3be3ece6">Identity_Matrix</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> dim) {
<a name="l00064"></a>00064 <a class="code" href="structmatrix.html">Matrix</a> * ret = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(dim, dim);
<a name="l00065"></a>00065 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00066"></a>00066 <span class="keywordflow">for</span> (i=0; i< dim; i++) {
<a name="l00067"></a>00067 <span class="keywordflow">for</span> (j=0; j< dim; j++) {
<a name="l00068"></a>00068 <span class="keywordflow">if</span> (i==j)
<a name="l00069"></a>00069 { <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(ret-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j], 1); }
<a name="l00070"></a>00070 <span class="keywordflow">else</span> <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(ret-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j], 0);
<a name="l00071"></a>00071 }
<a name="l00072"></a>00072 }
<a name="l00073"></a>00073 <span class="keywordflow">return</span> ret;
<a name="l00074"></a>00074 } <span class="comment">/* Identity_Matrix */</span>
<a name="l00075"></a>00075
<a name="l00076"></a>00076 <span class="comment"></span>
<a name="l00077"></a>00077 <span class="comment">/** </span>
<a name="l00078"></a>00078 <span class="comment"> * returns the dim-dimensional identity matrix. </span>
<a name="l00079"></a>00079 <span class="comment"> * If I is set to NULL, allocates it first. </span>
<a name="l00080"></a>00080 <span class="comment"> * Else, assumes an existing, allocated Matrix.</span>
<a name="l00081"></a>00081 <span class="comment">*/</span>
<a name="l00082"></a><a class="code" href="matrix__addon_8h.html#db1631ef2ddb3b386742b881b30f8ce6">00082</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#db1631ef2ddb3b386742b881b30f8ce6" title="returns the dim-dimensional identity matrix.">Matrix_identity</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> dim, <a class="code" href="structmatrix.html">Matrix</a> ** I) {
<a name="l00083"></a>00083 <span class="keywordtype">int</span> i,j;
<a name="l00084"></a>00084 <span class="keywordflow">if</span> (*I==NULL) {
<a name="l00085"></a>00085 (*I) = <a class="code" href="matrix__addon_8c.html#33f64eb039ac943c1bddbafc3be3ece6">Identity_Matrix</a>(dim);
<a name="l00086"></a>00086 }
<a name="l00087"></a>00087 <span class="keywordflow">else</span> {
<a name="l00088"></a>00088 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>((*I)->NbRows>=dim && (*I)->NbColumns>=dim);
<a name="l00089"></a>00089 <span class="keywordflow">for</span> (i=0; i< dim; i++) {
<a name="l00090"></a>00090 <span class="keywordflow">for</span> (j=0; j< dim; j++) {
<a name="l00091"></a>00091 <span class="keywordflow">if</span> (i==j) {
<a name="l00092"></a>00092 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>((*I)->p[i][j], 1);
<a name="l00093"></a>00093 }
<a name="l00094"></a>00094 <span class="keywordflow">else</span> {
<a name="l00095"></a>00095 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>((*I)->p[i][j], 0);
<a name="l00096"></a>00096 }
<a name="l00097"></a>00097 }
<a name="l00098"></a>00098 }
<a name="l00099"></a>00099 }
<a name="l00100"></a>00100 } <span class="comment">/* Matrix_identity */</span>
<a name="l00101"></a>00101
<a name="l00102"></a>00102 <span class="comment"></span>
<a name="l00103"></a>00103 <span class="comment">/** given a n x n integer transformation matrix transf, compute its inverse</span>
<a name="l00104"></a>00104 <span class="comment"> M/g, where M is a nxn integer matrix. g is a common denominator for</span>
<a name="l00105"></a>00105 <span class="comment"> elements of (transf^{-1}) */</span>
<a name="l00106"></a><a class="code" href="matrix__addon_8h.html#db8612672962c249e3ad9d4e7b4a1e0a">00106</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#b736f7ec39f7b625397e965e8b612ad2" title="given a n x n integer transformation matrix transf, compute its inverse M/g, where...">mtransformation_inverse</a>(<a class="code" href="structmatrix.html">Matrix</a> * transf, <a class="code" href="structmatrix.html">Matrix</a> ** inverse, Value * g) {
<a name="l00107"></a>00107 Value <a class="code" href="structfactor.html">factor</a>;
<a name="l00108"></a>00108 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00109"></a>00109 <a class="code" href="structmatrix.html">Matrix</a> *tmp, *inv;
<a name="l00110"></a>00110
<a name="l00111"></a>00111 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(*g);
<a name="l00112"></a>00112 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(*g,1);
<a name="l00113"></a>00113
<a name="l00114"></a>00114 <span class="comment">/* a - compute the inverse as usual (n x (n+1) matrix) */</span>
<a name="l00115"></a>00115 tmp = <a class="code" href="Matop_8c.html#9d027e9fc6b85e6fa37fc284bf1b5e06">Matrix_Copy</a>(transf);
<a name="l00116"></a>00116 inv = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(transf-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>, transf-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>+1);
<a name="l00117"></a>00117 <a class="code" href="matrix_8c.html#e2b2f031eb75c5011091536d7ef4befc">MatInverse</a>(tmp, inv);
<a name="l00118"></a>00118 <a class="code" href="matrix_8c.html#fcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(tmp);
<a name="l00119"></a>00119
<a name="l00120"></a>00120 <span class="comment">/* b - as it is rational, put it to the same denominator*/</span>
<a name="l00121"></a>00121 (*inverse) = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(transf-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>, transf-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>);
<a name="l00122"></a>00122 <span class="keywordflow">for</span> (i=0; i< inv-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++)
<a name="l00123"></a>00123 <a class="code" href="source_2arith_2arithmetique_8h.html#6da13dbfdd065b7609591ff6b3aee310">value_lcm</a>(*g, *g, inv-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][inv-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1]);
<a name="l00124"></a>00124 <span class="keywordflow">for</span> (i=0; i< inv-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00125"></a>00125 <a class="code" href="source_2arith_2arithmetique_8h.html#c633e4bcd9ed1d8412c67cda6d8ddb11">value_division</a>(factor, *g, inv-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][inv-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1]);
<a name="l00126"></a>00126 <span class="keywordflow">for</span> (j=0; j< (*inverse)->NbColumns; j++)
<a name="l00127"></a>00127 <a class="code" href="source_2arith_2arithmetique_8h.html#c9986d34264874727344f666079e2294">value_multiply</a>((*inverse)->p[i][j], inv-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j], factor);
<a name="l00128"></a>00128 }
<a name="l00129"></a>00129
<a name="l00130"></a>00130 <span class="comment">/* c- clean up */</span>
<a name="l00131"></a>00131 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(factor);
<a name="l00132"></a>00132 <a class="code" href="matrix_8c.html#fcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(inv);
<a name="l00133"></a>00133 } <span class="comment">/* mtransformation_inverse */</span>
<a name="l00134"></a>00134
<a name="l00135"></a>00135 <span class="comment"></span>
<a name="l00136"></a>00136 <span class="comment">/** takes a transformation matrix, and expands it to a higher dimension with</span>
<a name="l00137"></a>00137 <span class="comment"> the identity matrix regardless of it homogeneousness */</span>
<a name="l00138"></a><a class="code" href="matrix__addon_8c.html#0fd41929c8927ab1ce2ec603fe283865">00138</a> <a class="code" href="structmatrix.html">Matrix</a> * <a class="code" href="matrix__addon_8c.html#0fd41929c8927ab1ce2ec603fe283865" title="takes a transformation matrix, and expands it to a higher dimension with the identity...">mtransformation_expand_left_to_dim</a>(<a class="code" href="structmatrix.html">Matrix</a> * M, <span class="keywordtype">int</span> new_dim) {
<a name="l00139"></a>00139 <a class="code" href="structmatrix.html">Matrix</a> * ret = <a class="code" href="matrix__addon_8c.html#33f64eb039ac943c1bddbafc3be3ece6">Identity_Matrix</a>(new_dim);
<a name="l00140"></a>00140 <span class="keywordtype">int</span> offset = new_dim-M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>;
<a name="l00141"></a>00141 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00142"></a>00142
<a name="l00143"></a>00143 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(new_dim>=M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00144"></a>00144 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>==M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00145"></a>00145
<a name="l00146"></a>00146 <span class="keywordflow">for</span> (i=0; i< M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++)
<a name="l00147"></a>00147 <span class="keywordflow">for</span> (j=0; j< M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; j++)
<a name="l00148"></a>00148 <a class="code" href="source_2arith_2arithmetique_8h.html#864613888dc46f15679aa4f63e468f89">value_assign</a>(ret-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[offset+i][offset+j], M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00149"></a>00149 <span class="keywordflow">return</span> ret;
<a name="l00150"></a>00150 } <span class="comment">/* mtransformation_expand_left_to_dim */</span>
<a name="l00151"></a>00151
<a name="l00152"></a>00152 <span class="comment"></span>
<a name="l00153"></a>00153 <span class="comment">/** simplify a matrix seen as a polyhedron, by dividing its rows by the gcd of</span>
<a name="l00154"></a>00154 <span class="comment"> their elements. */</span>
<a name="l00155"></a><a class="code" href="matrix__addon_8h.html#ce44097b2d9d40d05934971b9716af89">00155</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#ce44097b2d9d40d05934971b9716af89" title="simplify a matrix seen as a polyhedron, by dividing its rows by the gcd of their...">mpolyhedron_simplify</a>(<a class="code" href="structmatrix.html">Matrix</a> * polyh) {
<a name="l00156"></a>00156 <span class="keywordtype">int</span> i, j;
<a name="l00157"></a>00157 Value cur_gcd;
<a name="l00158"></a>00158 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(cur_gcd);
<a name="l00159"></a>00159 <span class="keywordflow">for</span> (i=0; i< polyh-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00160"></a>00160 <a class="code" href="vector_8c.html#801486b45cadc8b9d22d99a79af91fa1">Vector_Gcd</a>(polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1, polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1, &cur_gcd);
<a name="l00161"></a>00161 printf(<span class="stringliteral">" gcd[%d] = "</span>, i);
<a name="l00162"></a>00162 <a class="code" href="source_2arith_2arithmetique_8h.html#d34605b56b571830b928b50a74d618b7">value_print</a>(stdout, VALUE_FMT, cur_gcd);printf(<span class="stringliteral">"\n"</span>);
<a name="l00163"></a>00163 <a class="code" href="vector_8c.html#95d6452a07b82054af71a14c686e66a8">Vector_AntiScale</a>(polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1, polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1, cur_gcd, polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1);
<a name="l00164"></a>00164 }
<a name="l00165"></a>00165 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(cur_gcd);
<a name="l00166"></a>00166 } <span class="comment">/* mpolyhedron_simplify */</span>
<a name="l00167"></a>00167
<a name="l00168"></a>00168 <span class="comment"></span>
<a name="l00169"></a>00169 <span class="comment">/** inflates a polyhedron (represented as a matrix) P, so that the apx of its</span>
<a name="l00170"></a>00170 <span class="comment"> Ehrhart Polynomial is an upper bound of the Ehrhart polynomial of P</span>
<a name="l00171"></a>00171 <span class="comment"> WARNING: this inflation is supposed to be applied on full-dimensional</span>
<a name="l00172"></a>00172 <span class="comment"> polyhedra. */</span>
<a name="l00173"></a><a class="code" href="matrix__addon_8h.html#c4b68d480196756e0deffafb3d99ecc7">00173</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#c4b68d480196756e0deffafb3d99ecc7" title="inflates a polyhedron (represented as a matrix) P, so that the apx of its Ehrhart...">mpolyhedron_inflate</a>(<a class="code" href="structmatrix.html">Matrix</a> * polyh, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_parms) {
<a name="l00174"></a>00174 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00175"></a>00175 <span class="keywordtype">unsigned</span> nb_vars = polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-nb_parms-2;
<a name="l00176"></a>00176 Value infl;
<a name="l00177"></a>00177 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(infl);
<a name="l00178"></a>00178 <span class="comment">/* subtract the sum of the negative coefficients of each inequality */</span>
<a name="l00179"></a>00179 <span class="keywordflow">for</span> (i=0; i< polyh-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00180"></a>00180 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(infl, 0);
<a name="l00181"></a>00181 <span class="keywordflow">for</span> (j=0; j< nb_vars; j++) {
<a name="l00182"></a>00182 <span class="keywordflow">if</span> (<a class="code" href="source_2arith_2arithmetique_8h.html#f031da52c8a160fd1ee6e4c793f8c78a">value_neg_p</a>(polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][1+j]))
<a name="l00183"></a>00183 <a class="code" href="source_2arith_2arithmetique_8h.html#ea216a0e750144f0e6eb9b0a82583739">value_addto</a>(infl, infl, polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][1+j]);
<a name="l00184"></a>00184 }
<a name="l00185"></a>00185 <span class="comment">/* here, we subtract a negative value */</span>
<a name="l00186"></a>00186 <a class="code" href="source_2arith_2arithmetique_8h.html#e92a58eee3b6f5c6a99e6837e68407e1">value_subtract</a>(polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1],
<a name="l00187"></a>00187 polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1], infl);
<a name="l00188"></a>00188 }
<a name="l00189"></a>00189 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(infl);
<a name="l00190"></a>00190 } <span class="comment">/* mpolyhedron_inflate */</span>
<a name="l00191"></a>00191
<a name="l00192"></a>00192 <span class="comment"></span>
<a name="l00193"></a>00193 <span class="comment">/** deflates a polyhedron (represented as a matrix) P, so that the apx of its</span>
<a name="l00194"></a>00194 <span class="comment"> Ehrhart Polynomial is a lower bound of the Ehrhart polynomial of P WARNING:</span>
<a name="l00195"></a>00195 <span class="comment"> this deflation is supposed to be applied on full-dimensional polyhedra. */</span>
<a name="l00196"></a><a class="code" href="matrix__addon_8h.html#0f0ba73176f5316a02e849b8c210204a">00196</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#0f0ba73176f5316a02e849b8c210204a" title="deflates a polyhedron (represented as a matrix) P, so that the apx of its Ehrhart...">mpolyhedron_deflate</a>(<a class="code" href="structmatrix.html">Matrix</a> * polyh, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nb_parms) {
<a name="l00197"></a>00197 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i,j;
<a name="l00198"></a>00198 <span class="keywordtype">unsigned</span> nb_vars = polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-nb_parms-2;
<a name="l00199"></a>00199 Value defl;
<a name="l00200"></a>00200 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(defl);
<a name="l00201"></a>00201 <span class="comment">/* substract the sum of the negative coefficients of each inequality */</span>
<a name="l00202"></a>00202 <span class="keywordflow">for</span> (i=0; i< polyh-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00203"></a>00203 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(defl, 0);
<a name="l00204"></a>00204 <span class="keywordflow">for</span> (j=0; j< nb_vars; j++) {
<a name="l00205"></a>00205 <span class="keywordflow">if</span> (<a class="code" href="source_2arith_2arithmetique_8h.html#01904c8c75c10d407a24c55f16ec27c7">value_pos_p</a>(polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][1+j]))
<a name="l00206"></a>00206 <a class="code" href="source_2arith_2arithmetique_8h.html#ea216a0e750144f0e6eb9b0a82583739">value_addto</a>(defl, defl, polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][1+j]);
<a name="l00207"></a>00207 }
<a name="l00208"></a>00208 <span class="comment">/* here, we substract a negative value */</span>
<a name="l00209"></a>00209 <a class="code" href="source_2arith_2arithmetique_8h.html#e92a58eee3b6f5c6a99e6837e68407e1">value_subtract</a>(polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1],
<a name="l00210"></a>00210 polyh-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][polyh-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1], defl);
<a name="l00211"></a>00211 }
<a name="l00212"></a>00212 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(defl);
<a name="l00213"></a>00213 } <span class="comment">/* mpolyhedron_deflate */</span>
<a name="l00214"></a>00214
<a name="l00215"></a>00215 <span class="comment"></span>
<a name="l00216"></a>00216 <span class="comment">/** use an eliminator row to eliminate a variable in a victim row (without</span>
<a name="l00217"></a>00217 <span class="comment"> * changing the sign of the victim row -> important if it is an inequality).</span>
<a name="l00218"></a>00218 <span class="comment"> * @param Eliminator the matrix containing the eliminator row</span>
<a name="l00219"></a>00219 <span class="comment"> * @param eliminator_row the index of the eliminator row in <tt>Eliminator</tt></span>
<a name="l00220"></a>00220 <span class="comment"> * @param Victim the matrix containing the row to be eliminated</span>
<a name="l00221"></a>00221 <span class="comment"> * @param victim_row the row to be eliminated in <tt>Victim</tt></span>
<a name="l00222"></a>00222 <span class="comment"> * @param var_to_elim the variable to be eliminated.</span>
<a name="l00223"></a>00223 <span class="comment"> */</span>
<a name="l00224"></a><a class="code" href="matrix__addon_8h.html#79d19aa329285819b31bc7a602241842">00224</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#79d19aa329285819b31bc7a602241842" title="use an eliminator row to eliminate a variable in a victim row (without changing the...">eliminate_var_with_constr</a>(<a class="code" href="structmatrix.html">Matrix</a> * Eliminator,
<a name="l00225"></a>00225 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> eliminator_row, <a class="code" href="structmatrix.html">Matrix</a> * Victim,
<a name="l00226"></a>00226 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> victim_row,
<a name="l00227"></a>00227 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> var_to_elim) {
<a name="l00228"></a>00228 Value cur_lcm, mul_a, mul_b;
<a name="l00229"></a>00229 Value tmp, tmp2;
<a name="l00230"></a>00230 <span class="keywordtype">int</span> k;
<a name="l00231"></a>00231
<a name="l00232"></a>00232 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(cur_lcm);
<a name="l00233"></a>00233 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(mul_a);
<a name="l00234"></a>00234 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(mul_b);
<a name="l00235"></a>00235 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(tmp);
<a name="l00236"></a>00236 <a class="code" href="source_2arith_2arithmetique_8h.html#f71a2ca0294a19cff0cdcbdcc052ee27">value_init</a>(tmp2);
<a name="l00237"></a>00237 <span class="comment">/* if the victim coefficient is not zero */</span>
<a name="l00238"></a>00238 <span class="keywordflow">if</span> (<a class="code" href="source_2arith_2arithmetique_8h.html#47d32925340d2dc99ef2d4215080a60d">value_notzero_p</a>(Victim-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[victim_row][var_to_elim+1])) {
<a name="l00239"></a>00239 <a class="code" href="source_2arith_2arithmetique_8h.html#6da13dbfdd065b7609591ff6b3aee310">value_lcm</a>(cur_lcm, Eliminator-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[eliminator_row][var_to_elim+1],
<a name="l00240"></a>00240 Victim-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[victim_row][var_to_elim+1]);
<a name="l00241"></a>00241 <span class="comment">/* multiplication factors */</span>
<a name="l00242"></a>00242 <a class="code" href="source_2arith_2arithmetique_8h.html#c633e4bcd9ed1d8412c67cda6d8ddb11">value_division</a>(mul_a, cur_lcm,
<a name="l00243"></a>00243 Eliminator-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[eliminator_row][var_to_elim+1]);
<a name="l00244"></a>00244 <a class="code" href="source_2arith_2arithmetique_8h.html#c633e4bcd9ed1d8412c67cda6d8ddb11">value_division</a>(mul_b, cur_lcm,
<a name="l00245"></a>00245 Victim-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[victim_row][var_to_elim+1]);
<a name="l00246"></a>00246 <span class="comment">/* the multiplicator for the vitim row has to be positive */</span>
<a name="l00247"></a>00247 <span class="keywordflow">if</span> (<a class="code" href="source_2arith_2arithmetique_8h.html#01904c8c75c10d407a24c55f16ec27c7">value_pos_p</a>(mul_b)) {
<a name="l00248"></a>00248 <a class="code" href="source_2arith_2arithmetique_8h.html#0daf9a8ecdc14e7a274832b0d2add830">value_oppose</a>(mul_a, mul_a);
<a name="l00249"></a>00249 }
<a name="l00250"></a>00250 <span class="keywordflow">else</span> {
<a name="l00251"></a>00251 <a class="code" href="source_2arith_2arithmetique_8h.html#0daf9a8ecdc14e7a274832b0d2add830">value_oppose</a>(mul_b, mul_b);
<a name="l00252"></a>00252 }
<a name="l00253"></a>00253 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(cur_lcm);
<a name="l00254"></a>00254 <span class="comment">/* now we have a.mul_a = -(b.mul_b) and mul_a > 0 */</span>
<a name="l00255"></a>00255 <span class="keywordflow">for</span> (k=1; k<Victim-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>; k++) {
<a name="l00256"></a>00256 <a class="code" href="source_2arith_2arithmetique_8h.html#c9986d34264874727344f666079e2294">value_multiply</a>(tmp, Eliminator-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[eliminator_row][k], mul_a);
<a name="l00257"></a>00257 <a class="code" href="source_2arith_2arithmetique_8h.html#c9986d34264874727344f666079e2294">value_multiply</a>(tmp2, Victim-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[victim_row][k], mul_b);
<a name="l00258"></a>00258 <a class="code" href="source_2arith_2arithmetique_8h.html#ea216a0e750144f0e6eb9b0a82583739">value_addto</a>(Victim-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[victim_row][k], tmp, tmp2);
<a name="l00259"></a>00259 }
<a name="l00260"></a>00260 }
<a name="l00261"></a>00261 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(mul_a);
<a name="l00262"></a>00262 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(mul_b);
<a name="l00263"></a>00263 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(tmp);
<a name="l00264"></a>00264 <a class="code" href="source_2arith_2arithmetique_8h.html#b9b282921e85a0527d462d331533d619">value_clear</a>(tmp2);
<a name="l00265"></a>00265 }
<a name="l00266"></a>00266 <span class="comment">/* eliminate_var_with_constr */</span>
<a name="l00267"></a>00267
<a name="l00268"></a>00268
<a name="l00269"></a>00269 <span class="comment">/* STUFF WITH PARTIAL MAPPINGS (Mappings to a subset of the</span>
<a name="l00270"></a>00270 <span class="comment"> variables/parameters) : on the first or last variables/parameters */</span>
<a name="l00271"></a>00271 <span class="comment"></span>
<a name="l00272"></a>00272 <span class="comment">/** compress the last vars/pars of the polyhedron M expressed as a polylib</span>
<a name="l00273"></a>00273 <span class="comment"> matrix</span>
<a name="l00274"></a>00274 <span class="comment"> - adresses the full-rank compressions only</span>
<a name="l00275"></a>00275 <span class="comment"> - modfies M */</span>
<a name="l00276"></a><a class="code" href="matrix__addon_8h.html#44f487e1b38f0f47c115d2115087a017">00276</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#44f487e1b38f0f47c115d2115087a017" title="compress the last vars/pars of the polyhedron M expressed as a polylib matrixadresses...">mpolyhedron_compress_last_vars</a>(<a class="code" href="structmatrix.html">Matrix</a> * M, <a class="code" href="structmatrix.html">Matrix</a> * compression) {
<a name="l00277"></a>00277 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i, j, k;
<a name="l00278"></a>00278 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> offset = M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a> - compression-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>;
<a name="l00279"></a>00279 <span class="comment">/* the computations on M will begin on column "offset" */</span>
<a name="l00280"></a>00280
<a name="l00281"></a>00281 <a class="code" href="structmatrix.html">Matrix</a> * M_tmp = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(1, M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00282"></a>00282 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(compression-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>==compression-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>);
<a name="l00283"></a>00283 <span class="comment">/* basic matrix multiplication (using a temporary row instead of a whole</span>
<a name="l00284"></a>00284 <span class="comment"> temporary matrix), but with a column offset */</span>
<a name="l00285"></a>00285 <span class="keywordflow">for</span>(i=0; i< M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00286"></a>00286 <span class="keywordflow">for</span> (j=0; j< compression-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; j++) {
<a name="l00287"></a>00287 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(M_tmp-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[0][j], 0);
<a name="l00288"></a>00288 <span class="keywordflow">for</span> (k=0; k< compression-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; k++) {
<a name="l00289"></a>00289 <a class="code" href="source_2arith_2arithmetique_8h.html#9900fbd029b36f5887e587642a064a52">value_addmul</a>(M_tmp-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[0][j], M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][k+offset],compression-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[k][j]);
<a name="l00290"></a>00290 }
<a name="l00291"></a>00291 }
<a name="l00292"></a>00292 <span class="keywordflow">for</span> (j=0; j< compression-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; j++)
<a name="l00293"></a>00293 <a class="code" href="source_2arith_2arithmetique_8h.html#864613888dc46f15679aa4f63e468f89">value_assign</a>(M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j+offset], M_tmp-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[0][j]);
<a name="l00294"></a>00294 }
<a name="l00295"></a>00295 <a class="code" href="matrix_8c.html#fcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(M_tmp);
<a name="l00296"></a>00296 } <span class="comment">/* mpolyhedron_compress_last_vars */</span>
<a name="l00297"></a>00297
<a name="l00298"></a>00298 <span class="comment"></span>
<a name="l00299"></a>00299 <span class="comment">/** use a set of m equalities Eqs to eliminate m variables in the polyhedron</span>
<a name="l00300"></a>00300 <span class="comment"> Ineqs represented as a matrix</span>
<a name="l00301"></a>00301 <span class="comment"> eliminates the m first variables</span>
<a name="l00302"></a>00302 <span class="comment"> - assumes that Eqs allow to eliminate the m equalities</span>
<a name="l00303"></a>00303 <span class="comment"> - modifies Eqs and Ineqs */</span>
<a name="l00304"></a><a class="code" href="matrix__addon_8h.html#649c9050ca9d6229d5b48e966da1f35c">00304</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="matrix__addon_8c.html#649c9050ca9d6229d5b48e966da1f35c" title="use a set of m equalities Eqs to eliminate m variables in the polyhedron Ineqs represented...">mpolyhedron_eliminate_first_variables</a>(<a class="code" href="structmatrix.html">Matrix</a> * Eqs,
<a name="l00305"></a>00305 <a class="code" href="structmatrix.html">Matrix</a> *Ineqs) {
<a name="l00306"></a>00306 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i, j, k;
<a name="l00307"></a>00307 <span class="comment">/* eliminate one variable (index i) after each other */</span>
<a name="l00308"></a>00308 <span class="keywordflow">for</span> (i=0; i< Eqs-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00309"></a>00309 <span class="comment">/* find j, the first (non-marked) row of Eqs with a non-zero coefficient */</span>
<a name="l00310"></a>00310 <span class="keywordflow">for</span> (j=0; j<Eqs-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a> && (Eqs-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[j][i+1]==0 ||
<a name="l00311"></a>00311 ( !<a class="code" href="source_2arith_2arithmetique_8h.html#fee537d2d3f20ba6a656fe84ce54c6ce">value_cmp_si</a>(Eqs-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[j][0],2) ));
<a name="l00312"></a>00312 j++);
<a name="l00313"></a>00313 <span class="comment">/* if no row is found in Eqs that allows to eliminate variable i, return an</span>
<a name="l00314"></a>00314 <span class="comment"> error code (0) */</span>
<a name="l00315"></a>00315 <span class="keywordflow">if</span> (j==Eqs-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>) <span class="keywordflow">return</span> 0;
<a name="l00316"></a>00316 <span class="comment">/* else, eliminate variable i in Eqs and Ineqs with the j^th row of Eqs</span>
<a name="l00317"></a>00317 <span class="comment"> (and mark this row so we don't use it again for an elimination) */</span>
<a name="l00318"></a>00318 <span class="keywordflow">for</span> (k=j+1; k<Eqs-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; k++)
<a name="l00319"></a>00319 <a class="code" href="matrix__addon_8c.html#79d19aa329285819b31bc7a602241842" title="use an eliminator row to eliminate a variable in a victim row (without changing the...">eliminate_var_with_constr</a>(Eqs, j, Eqs, k, i);
<a name="l00320"></a>00320 <span class="keywordflow">for</span> (k=0; k< Ineqs-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; k++)
<a name="l00321"></a>00321 <a class="code" href="matrix__addon_8c.html#79d19aa329285819b31bc7a602241842" title="use an eliminator row to eliminate a variable in a victim row (without changing the...">eliminate_var_with_constr</a>(Eqs, j, Ineqs, k, i);
<a name="l00322"></a>00322 <span class="comment">/* mark the row */</span>
<a name="l00323"></a>00323 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(Eqs-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[j][0],2);
<a name="l00324"></a>00324 }
<a name="l00325"></a>00325 <span class="comment">/* un-mark all the rows */</span>
<a name="l00326"></a>00326 <span class="keywordflow">for</span> (i=0; i< Eqs-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(Eqs-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0],0);
<a name="l00327"></a>00327 <span class="keywordflow">return</span> 1;
<a name="l00328"></a>00328 } <span class="comment">/* mpolyhedron_eliminate_first_variables */</span>
<a name="l00329"></a>00329
<a name="l00330"></a>00330 <span class="comment"></span>
<a name="l00331"></a>00331 <span class="comment">/** returns a contiguous submatrix of a matrix.</span>
<a name="l00332"></a>00332 <span class="comment"> * @param M the input matrix</span>
<a name="l00333"></a>00333 <span class="comment"> * @param sr the index of the starting row</span>
<a name="l00334"></a>00334 <span class="comment"> * @param sc the index of the starting column</span>
<a name="l00335"></a>00335 <span class="comment"> * @param er the index ofthe ending row (excluded)</span>
<a name="l00336"></a>00336 <span class="comment"> * @param ec the ined of the ending colummn (excluded)</span>
<a name="l00337"></a>00337 <span class="comment"> * @param sub (returned), the submatrix. Allocated if set to NULL, assumed to</span>
<a name="l00338"></a>00338 <span class="comment"> * be already allocated else.</span>
<a name="l00339"></a>00339 <span class="comment"> */</span>
<a name="l00340"></a><a class="code" href="matrix__addon_8h.html#deecb10364caa7f38fbd2b5acc0c3dbf">00340</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#33fec91bb879b7b4dda814ad9d33f41b" title="returns a contiguous submatrix of a matrix.">Matrix_subMatrix</a>(<a class="code" href="structmatrix.html">Matrix</a> * M, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sr, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sc,
<a name="l00341"></a>00341 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> er, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ec, <a class="code" href="structmatrix.html">Matrix</a> ** sub) {
<a name="l00342"></a>00342 <span class="keywordtype">int</span> i;
<a name="l00343"></a>00343 <span class="keywordtype">int</span> nbR = er-sr;
<a name="l00344"></a>00344 <span class="keywordtype">int</span> nbC = ec-sc;
<a name="l00345"></a>00345 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a> (er<=M->NbRows && ec<=M->NbColumns);
<a name="l00346"></a>00346 <span class="keywordflow">if</span> ((*sub)==NULL) {
<a name="l00347"></a>00347 (*sub) = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(nbR, nbC);
<a name="l00348"></a>00348 }
<a name="l00349"></a>00349 <span class="keywordflow">if</span> (nbR==0 || nbC==0) <span class="keywordflow">return</span>;
<a name="l00350"></a>00350 <span class="keywordflow">for</span> (i=0; i< nbR; i++) {
<a name="l00351"></a>00351 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(&(M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i+sr][sc]), (*sub)->p[i], nbC);
<a name="l00352"></a>00352 }
<a name="l00353"></a>00353 }<span class="comment">/* Matrix_subMatrix */</span>
<a name="l00354"></a>00354
<a name="l00355"></a>00355 <span class="comment"></span>
<a name="l00356"></a>00356 <span class="comment">/**</span>
<a name="l00357"></a>00357 <span class="comment"> * Cloning function. Similar to Matrix_Copy() but allocates the target matrix</span>
<a name="l00358"></a>00358 <span class="comment"> * if it is set to NULL.</span>
<a name="l00359"></a>00359 <span class="comment"> */</span>
<a name="l00360"></a><a class="code" href="matrix__addon_8h.html#8269bc80b6beba6d58a4c5b029f04bbf">00360</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#8269bc80b6beba6d58a4c5b029f04bbf" title="Cloning function.">Matrix_clone</a>(<a class="code" href="structmatrix.html">Matrix</a> * M, <a class="code" href="structmatrix.html">Matrix</a> ** Cl) {
<a name="l00361"></a>00361 <a class="code" href="matrix__addon_8c.html#33fec91bb879b7b4dda814ad9d33f41b" title="returns a contiguous submatrix of a matrix.">Matrix_subMatrix</a>(M, 0,0, M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>, M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>, Cl);
<a name="l00362"></a>00362 }
<a name="l00363"></a>00363
<a name="l00364"></a>00364 <span class="comment"></span>
<a name="l00365"></a>00365 <span class="comment">/**</span>
<a name="l00366"></a>00366 <span class="comment"> * Copies a contiguous submatrix of M1 into M2, at the indicated position.</span>
<a name="l00367"></a>00367 <span class="comment"> * M1 and M2 are assumed t be allocated already.</span>
<a name="l00368"></a>00368 <span class="comment"> * @param M1 the source matrix</span>
<a name="l00369"></a>00369 <span class="comment"> * @param sr1 the starting source row</span>
<a name="l00370"></a>00370 <span class="comment"> * @param sc1 the starting source column</span>
<a name="l00371"></a>00371 <span class="comment"> * @param nbR the number of rows</span>
<a name="l00372"></a>00372 <span class="comment"> * @param nbC the number of columns</span>
<a name="l00373"></a>00373 <span class="comment"> * @param M2 the target matrix</span>
<a name="l00374"></a>00374 <span class="comment"> * @param sr2 the starting target row</span>
<a name="l00375"></a>00375 <span class="comment"> * @param sc2 the starting target column</span>
<a name="l00376"></a>00376 <span class="comment">*/</span>
<a name="l00377"></a><a class="code" href="matrix__addon_8h.html#cb90cceb8e7a674a3d5796a1402f0c9e">00377</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#cb90cceb8e7a674a3d5796a1402f0c9e" title="Copies a contiguous submatrix of M1 into M2, at the indicated position.">Matrix_copySubMatrix</a>(<a class="code" href="structmatrix.html">Matrix</a> *M1,
<a name="l00378"></a>00378 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sr1, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sc1,
<a name="l00379"></a>00379 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nbR, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nbC,
<a name="l00380"></a>00380 <a class="code" href="structmatrix.html">Matrix</a> * M2,
<a name="l00381"></a>00381 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sr2, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sc2) {
<a name="l00382"></a>00382 <span class="keywordtype">int</span> i;
<a name="l00383"></a>00383 <span class="keywordflow">for</span> (i=0; i< nbR; i++) {
<a name="l00384"></a>00384 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(&(M1-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i+sr1][sc1]), &(M2-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i+sr2][sc2]), nbC);
<a name="l00385"></a>00385 }
<a name="l00386"></a>00386 } <span class="comment">/* Matrix_copySubMatrix */</span>
<a name="l00387"></a>00387
<a name="l00388"></a>00388 <span class="comment"></span>
<a name="l00389"></a>00389 <span class="comment">/** </span>
<a name="l00390"></a>00390 <span class="comment"> * transforms a matrix M into -M</span>
<a name="l00391"></a>00391 <span class="comment"> */</span>
<a name="l00392"></a><a class="code" href="matrix__addon_8h.html#cbbded0c02e89b1a7b6b08ee3f396986">00392</a> <span class="keywordtype">void</span> <a class="code" href="matrix__addon_8c.html#cbbded0c02e89b1a7b6b08ee3f396986" title="transforms a matrix M into -M">Matrix_oppose</a>(<a class="code" href="structmatrix.html">Matrix</a> * M) {
<a name="l00393"></a>00393 <span class="keywordtype">int</span> i,j;
<a name="l00394"></a>00394 <span class="keywordflow">for</span> (i=0; i<M-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a>; i++) {
<a name="l00395"></a>00395 <span class="keywordflow">for</span> (j=0; j< M-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>; j++) {
<a name="l00396"></a>00396 <a class="code" href="source_2arith_2arithmetique_8h.html#0daf9a8ecdc14e7a274832b0d2add830">value_oppose</a>(M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j], M-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][j]);
<a name="l00397"></a>00397 }
<a name="l00398"></a>00398 }
<a name="l00399"></a>00399 }
</pre></div></div>
<hr size="1"><address style="text-align: right;"><small>Generated on Tue Sep 15 18:33:59 2009 for polylib by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.6 </small></address>
</body>
</html>
|
