1 // ideal_stuff.cc
2
3 // implementation of the special ideal features needed by the IP-algorithms
4
5 #ifndef IDEAL_STUFF_CC
6 #define IDEAL_STUFF_CC
7
8 #include "ideal.h"
9
10 ////////////////////// elimination stuff ///////////////////////////////////
11
eliminate()12 ideal& ideal::eliminate()
13 {
14 // eliminates the generators of the ideal involving elimination variables
15 // with respect to w
16
17 if(w.number_of_elimination_variables()<=0)
18 // elimination unnecessary
19 return *this;
20
21 list_iterator iter;
22
23 #ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
24
25 // Simply iterate over the generator list and delete the elements involving
26 // elimination variables.
27 // There is no need to change the done/undone or the reduced/unreduced mark of
28 // an element.
29
30 iter.set_to_list(generators);
31
32 while((iter.is_at_end())==FALSE)
33 {
34 binomial& bin=iter.get_element();
35
36 if(bin.involves_elimination_variables(w)==TRUE)
37 {
38 iter.delete_element();
39 size--;
40 }
41 else
42 {
43 bin.drop_elimination_variables(w);
44 iter.next();
45 }
46 }
47
48 #endif // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
49
50
51 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
52
53 // Iterate over the generator lists and check whether the elements involve
54 // elimination variables.
55 // As the set of support variables can be changed by the elimination, the
56 // elements that are not deleted are first moved to the aux_list and then
57 // reinserted according to their new support.
58 // The elimination variables are droppd while reinserting.
59 // In general, elimination is done only once. The time needed for this is
60 // linear in the number of generators (in the Groebner basis). The elimination
61 // itself is therefore very fast in comparison to the Groebner basis
62 // computation needed for it... So we renounce to a complicated optimization
63 // of this procedure (the support information is not used). In fact, tests
64 // show that elimination time is really negligible.
65
66 // elimination
67 for(int i=0;i<Number_of_Lists;i++)
68 {
69 iter.set_to_list(generators[i]);
70
71 while((iter.is_at_end())==FALSE)
72 {
73 binomial& bin=iter.get_element();
74
75 if(bin.involves_elimination_variables(w)==TRUE)
76 {
77 iter.delete_element();
78 size--;
79 }
80 else
81 {
82 aux_list._insert(bin);
83 iter.extract_element();
84 // As the generators are reinserted later, we do not decrement the
85 // size (and so do not need to increment it during reinsertion).
86 }
87 }
88 }
89
90 // reinsertion
91 iter.set_to_list(aux_list);
92
93 while(iter.is_at_end()==FALSE)
94 {
95 binomial& bin=iter.get_element();
96 bin.drop_elimination_variables(w);
97 generators[bin.head_support%Number_of_Lists].insert(bin);
98 // size is not incremented, see above...
99 iter.extract_element();
100 }
101
102 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED
103
104
105 // finally adapt term ordering
106 w.convert_to_weighted_ordering();
107
108 return *this;
109 }
110
111
112
113
pseudo_eliminate()114 ideal& ideal::pseudo_eliminate()
115 {
116
117 if(w.number_of_weighted_variables()<=0)
118 {
119 cerr<<"WARNING: ideal& ideal::pseudo_eliminate():\n"
120 "cannot be performed without weighted variables"<<endl;
121 return *this;
122 }
123
124
125 list_iterator iter;
126
127 int last_weighted_variable=w.number_of_weighted_variables()-1;
128
129
130 #ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
131
132 // Simply iterate over the generator list and delete the elements involving
133 // the last weighted variable.
134 // There is no need to change the done/undone or the reduced/unreduced mark of
135 // an element.
136
137 iter.set_to_list(generators);
138
139 while(iter.is_at_end()==FALSE)
140 {
141 binomial& bin=iter.get_element();
142
143 if(bin[last_weighted_variable]!=0)
144 // weighted variable to drop is involved in bin
145 {
146 iter.delete_element();
147 size--;
148 }
149 else
150 {
151 bin.drop_last_weighted_variable(w);
152 iter.next();
153 }
154 }
155
156 #endif // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
157
158
159 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
160
161 // Iterate over the generator lists and check whether the elements involve
162 // the last weighted variable.
163 // As the set of support variables can be changed by the pseudo-elimination,
164 // the elements that are not deleted are first moved to the aux_list and then
165 // reinserted according to their new support.
166 // The last weight variable is dropped while reinserting.
167 // For the time needed by this function see the remarks for ideal::eliminate().
168
169 for(int i=0;i<Number_of_Lists;i++)
170 {
171 iter.set_to_list(generators[i]);
172
173 while((iter.is_at_end())==FALSE)
174 {
175 binomial& bin=iter.get_element();
176
177 if(bin[last_weighted_variable]!=0)
178 {
179 iter.delete_element();
180 size--;
181 }
182 else
183 {
184 aux_list._insert(bin);
185 iter.extract_element();
186 // As the generators are reinserted later, we do not decrement the
187 // size (and so do not need to increment it during reinsertion).
188 }
189 }
190 }
191
192
193 iter.set_to_list(aux_list);
194
195 while(iter.is_at_end()==FALSE)
196 {
197 binomial& bin=iter.get_element();
198 bin.drop_last_weighted_variable(w);
199 generators[bin.head_support%Number_of_Lists].insert(bin);
200 // size is not incremented, see above...
201 iter.extract_element();
202 }
203
204 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED
205
206 // finally adapt term ordering
207 w.delete_last_weighted_variable();
208
209 return *this;
210 }
211
212
213
214
215 /////////////////// management of the term ordering /////////////////////////
216
217
218
219
change_term_ordering_to(const term_ordering & _w)220 ideal& ideal::change_term_ordering_to(const term_ordering& _w)
221 {
222
223 // first check compatibility
224 if((w.number_of_weighted_variables()+w.number_of_elimination_variables())!=
225 (_w.number_of_weighted_variables()+_w.number_of_elimination_variables()))
226 {
227 cerr<<"WARNING: ideal& ideal::change_term_ordering_to"
228 "(const term_ordering&):\nincompatibility detected, term ordering not"
229 "changed."<<endl;
230 return *this;
231 }
232
233 // change term ordering
234 w=_w;
235
236 list_iterator iter;
237
238
239 #ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
240
241 // Simply iterate over the generator list. Because the change of the term
242 // ordering, the "done" and "reduced" marks of the elements have to be deleted.
243
244 iter.set_to_list(generators);
245
246 while((iter.is_at_end())==FALSE)
247 {
248 (iter.get_element()).adapt_to_term_ordering(w);
249 iter.mark_element_undone();
250 iter.mark_element_head_unreduced();
251 iter.next();
252 }
253
254 #endif // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
255
256
257 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
258
259 // As head and tail might have to be exchanged, the elements are first moved to
260 // the aux_list and then reinserted according to their new head.
261
262 for(int i=0;i<Number_of_Lists;i++)
263 {
264 iter.set_to_list(generators[i]);
265
266 while((iter.is_at_end())==FALSE)
267 {
268 binomial& bin=iter.get_element();
269
270 if(bin.adapt_to_term_ordering(w)==-1)
271 // head and tail exchanged
272 {
273 aux_list._insert(bin);
274 iter.extract_element();
275 // As the generators are reinserted later, we do not decrement the
276 // size (and so do not need to increment it during reinsertion).
277 }
278 else
279 {
280 // Although the S-pairs of the remaining elements have already been
281 // computed once, the "done" marks have to be deleted: With a new
282 // term ordering, the results of the S-pair reduction can change -
283 // as well as the interreduction results.
284 iter.mark_element_undone();
285 iter.mark_element_head_unreduced();
286 iter.next();
287 }
288 }
289 }
290
291 // reinsertion
292 iter.set_to_list(aux_list);
293
294 while(iter.is_at_end()==FALSE)
295 {
296 binomial& bin=iter.get_element();
297 generators[bin.head_support%Number_of_Lists].insert(bin);
298 // size is not incremented, see above...
299 iter.extract_element();
300 }
301
302 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED
303
304
305 return *this;
306 }
307
308
309
310
311 /////////// manipulation of the variables ///////////////////////////////////
312
313
314
315
swap_variables_unsafe(const int & i,const int & j)316 ideal& ideal::swap_variables_unsafe(const int& i, const int& j)
317 {
318 // first check arguments
319 if((i<0) || (i>=w.number_of_weighted_variables())
320 || (j<0) || (j>=w.number_of_weighted_variables()))
321 {
322 cout<<"WARNING: ideal::swap_variables(const int&, const int&)\n "
323 "or ideal::swap_variables_unsafe(const int&, const int&):\n"
324 "index out of range"<<endl;
325 return *this;
326 }
327
328 if(i==j)
329 return(*this);
330 // special case to avoid unnecessary overhead
331
332
333 list_iterator iter;
334
335
336 #ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
337
338 iter.set_to_list(generators);
339
340 while((iter.is_at_end())==FALSE)
341 {
342 (iter.get_element()).swap_variables(i,j);
343 iter.next();
344 }
345
346 #endif // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
347
348
349 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
350
351 // As head_support and tail_support are manipulated, the elements are first
352 // moved to the aux_list and then reinserted according to their new head.
353 // But head and tail are not adapted to the new term ordering induced by
354 // the change of the variable order - this is only done in the "safe"
355 // routine swap_variables(const int&, const int&).
356
357 for(int l=0;l<Number_of_Lists;l++)
358 {
359 iter.set_to_list(generators[l]);
360
361 while((iter.is_at_end())==FALSE)
362 {
363 binomial& bin=iter.get_element();
364 bin.swap_variables(i,j);
365 aux_list._insert(bin);
366 iter.extract_element();
367 // As the generators are reinserted later, we do not decrement the
368 // size (and so do not need to increment it during reinsertion).
369 }
370 }
371
372 // reinsertion
373 iter.set_to_list(aux_list);
374
375 while(iter.is_at_end()==FALSE)
376 {
377 binomial& bin=iter.get_element();
378 generators[bin.head_support%Number_of_Lists].insert(bin);
379 // size is not incremented, see above...
380 iter.extract_element();
381 }
382
383 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED
384
385
386 // finally adapt term ordering
387 w.swap_weights(i,j);
388
389 return *this;
390 }
391
392
393
394
swap_variables(const int & i,const int & j)395 ideal& ideal::swap_variables(const int& i, const int& j)
396 {
397
398 swap_variables_unsafe(i,j);
399
400 change_term_ordering_to(w);
401 // This rebuilds the list structure...
402
403 return *this;
404 }
405
406
407
408
flip_variable_unsafe(const int & i)409 ideal& ideal::flip_variable_unsafe(const int& i)
410 {
411 // first check argument
412 if((i<0) || (i>=w.number_of_weighted_variables()))
413 {
414 cout<<"WARNING: ideal::flip_variables(const int&):\n"
415 "argument out of range, nothing done"<<endl;
416 return *this;
417 }
418
419
420 list_iterator iter;
421
422
423 #ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
424
425 iter.set_to_list(generators);
426
427 while((iter.is_at_end())==FALSE)
428 {
429 (iter.get_element()).flip_variable(i);
430 iter.next();
431 }
432
433 #endif // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
434
435
436 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
437
438 // As head_support and tail_support can change, the elements are first moved
439 // to the aux_list and then reinserted according to their new head.
440
441 for(int l=0;l<Number_of_Lists;l++)
442 {
443 iter.set_to_list(generators[l]);
444
445 while((iter.is_at_end())==FALSE)
446 {
447 binomial& bin=iter.get_element();
448 bin.flip_variable(i);
449 aux_list._insert(bin);
450 iter.extract_element();
451 // As the generators are reinserted later, we do not decrement the
452 // size (and so do not need to increment it during reinsertion).
453 }
454 }
455
456 // reinsertion
457 iter.set_to_list(aux_list);
458
459 while(iter.is_at_end()==FALSE)
460 {
461 binomial& bin=iter.get_element();
462 generators[bin.head_support%Number_of_Lists].insert(bin);
463 iter.extract_element();
464 // size is not incremented, see above...
465 }
466
467 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED
468
469 return *this;
470 }
471 #endif // IDEAL_STUFF_CC
472