source: git/IntegerProgramming/Buchberger.cc @ f07fec

spielwiese
Last change on this file since f07fec was 194c2e7, checked in by Hans Schönemann <hannes@…>, 14 years ago
short -> int git-svn-id: file:///usr/local/Singular/svn/trunk@12539 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 92.0 KB
Line 
1// Buchberger.cc
2
3// implementation of Buchberger's Algorithm.
4
5#ifndef BUCHBERGER_CC
6#define BUCHBERGER_CC
7
8#include "ideal.h"
9
10/////////////////////////////////////////////////////////////////////////////
11/////////////// S-pair computation //////////////////////////////////////////
12/////////////////////////////////////////////////////////////////////////////
13
14BOOLEAN ideal::unnecessary_S_pair(list_iterator& first_iter,
15                                  list_iterator& second_iter) const
16{
17// This function checks several criteria to discard th S-pair of the
18// binomials referenced by the iterators. The criteria depend on the
19// settings of the idealŽs S-pair flags.
20
21// The arguments are iterators instead of the referenced binomials
22// because we have to do some equality tests. These are more efficient on
23// iterators than on binomials.
24
25///////////// criterion of relatively prime leading terms ///////////////////
26
27  // An S-pair can discarded if the leading terms of the two binomials are
28  // relatively prime.
29
30  if(rel_primeness)
31    if(relatively_prime(first_iter.get_element(),second_iter.get_element())
32       ==TRUE)
33      return TRUE;
34
35//////////// criterion M ///////////////////////////////////////////////////
36
37  if(M_criterion)
38  {
39
40    list_iterator iter;
41    binomial& bin1=first_iter.get_element();
42    binomial& bin2=second_iter.get_element();
43
44    // The M-criterion of Gebauer/Moeller checks binomial triples as
45    // explained in binomial.h; these are built of the elements referenced
46    // by the argument iterators and a third element appearing before the
47    // element referenced by second_iter in the generator lists.
48
49
50#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
51
52    iter.set_to_list(generators);
53
54#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
55
56#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
57
58    // The support of the lcm of two monomials is the union of their supports.
59    // To test criterion M, we then only have to consider lists whose support
60    // is a subset of the union of (first_iter.get_element()).head_support and
61    // (second_iter.get_element()).head_support. As only elements before
62    // second_iter.get_element() are tested, we can stop iteraton as soon as
63    // we reach this element.
64
65    int supp2=bin2.head_support%Number_of_Lists;
66    int supp_union=(bin1.head_support%Number_of_Lists)|supp2;
67    // supp_union (read as binary vector) is the union of the supports of
68    // first_iter.get_element() and second_iter.get_element()
69    // (restricted to List_Support_Variables variables).
70
71    for(int i=0;i<S.number_of_subsets[supp_union];i++)
72      // Go through the lists that contain elements whose support is a
73      // subset of supp_union.
74    {
75      int actual_list=S.subsets_of_support[supp_union][i];
76      iter.set_to_list(generators[actual_list]);
77      // This is the i-th list among the generator list with elements
78      // whose support is a subset of supp_union.
79
80      if(actual_list==supp2)
81        break;
82      // The iteration has reached the list referenced by second_iter,
83      // this is handled alone to avoid unnecessary checks.
84      // Before breakin the loop, iter has to be set to this list.
85
86      while(iter.is_at_end()==FALSE)
87        // Iterate over the list with three iterators according to the
88        // description of criterion M.
89      {
90        if(M(iter.get_element(),bin1,bin2)==TRUE)
91          return TRUE;
92        iter.next();
93      }
94    }
95
96#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
97
98
99    // Now, iter references second_iter's list,
100    // if SUPPORT_DRIVEN_METHODS_EXTENDED are enabled or not.
101
102    while(iter!=second_iter)
103    {
104      if(M(iter.get_element(),bin1,bin2)==TRUE)
105        return TRUE;
106      iter.next();
107    }
108  }
109
110/////////////////////// criterion F ////////////////////////////////////////
111
112  if(F_criterion)
113  {
114
115    list_iterator iter;
116    binomial& bin1=first_iter.get_element();
117    binomial& bin2=second_iter.get_element();
118
119    // The F-criterion of Gebauer/Moeller checks binomial triples as
120    // explained in binomial.h; these are built of the elements referenced
121    // by the argument iterators and a third element appearing before the
122    // element referenced by first_iter in the generator lists.
123
124#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
125
126    iter.set_to_list(generators);
127
128#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
129
130
131#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
132
133    // Again, we only have to consider lists whose support is a subset of the
134    // union of (first_iter.get_element()).head_support and
135    // (second_iter.get_element()).head_support.
136    // Additionally,we can override lists whose support is to small.
137
138    int supp1=bin1.head_support%Number_of_Lists;
139    int supp2=bin2.head_support%Number_of_Lists;
140    int supp_union=supp1|supp2;
141    // supp_union (read as binary vector) is the union of the supports of
142    // first_iter.get_element() and second_iter.get_element()
143    // (restricted to List_Support_Variables variables).
144
145    for(int i=0;i<S.number_of_subsets[supp_union];i++)
146      // Go through the lists that contain elements whose support is a
147      // subset of supp_union.
148    {
149      int actual_list=S.subsets_of_support[supp_union][i];
150
151      if((actual_list|supp2) != supp_union)
152        continue;
153      // The support of the actual list is too small, so its elements cannot
154      // satisfie criterion F.
155
156      iter.set_to_list(generators[actual_list]);
157      // This is the i-th list among the generator list with elements
158      // whose support is a subset of supp_union.
159
160      if(actual_list==supp1)
161        break;
162      // The iteration has reached the list referenced by first_iter;
163      // this is handled alone to avoid unnecessary checks.
164      // iter has to be set to that list before breaking the loop.
165
166      while(iter.is_at_end()==FALSE)
167        // Iterate over the list with three iterators according to the
168        // description of criterion F.
169      {
170        if(F(iter.get_element(),bin1,bin2)==TRUE)
171          return TRUE;
172        iter.next();
173      }
174    }
175
176#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
177
178    // Now, iter references first_iter's list,
179    // if SUPPORT_DRIVEN_METHODS_EXTENDED are enabled or not.
180
181    while(iter!=first_iter)
182    {
183      if(F(iter.get_element(),bin1,bin2)==TRUE)
184        return TRUE;
185      iter.next();
186    }
187  }
188
189/////////////////////// criterion B /////////////////////////////////////////
190
191  if(B_criterion)
192  {
193
194    list_iterator iter;
195    binomial& bin1=first_iter.get_element();
196    binomial& bin2=second_iter.get_element();
197
198    // The B-criterion of Gebauer/Moeller checks binomial triples as
199    // explained in binomial.h; these are built of the elements referenced
200    // by the argument iterators and a third element appearing after the
201    // element referenced by second_iter in the generator lists.
202
203    iter=second_iter;
204    iter.next();
205
206    // First test second_iter's list.
207    // This is the only list if NO_SUPPORT_DRIVEN_METHODS are enabled.
208
209    while(iter.is_at_end()==FALSE)
210    {
211      if(B(iter.get_element(),bin1,bin2)==TRUE)
212        return(TRUE);
213      iter.next();
214    }
215
216#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
217
218    // Now consider the other lists.
219    // Again, we only have to consider lists whose support is a subset of the
220    // union of (first_iter.get_element()).head_support and
221    // (second_iter.get_element()).head_support.
222
223    int supp2=bin2.head_support%Number_of_Lists;
224    int supp_union=(bin1.head_support%Number_of_Lists)|supp2;
225    // supp_union (read as binary vector) is the union of the supports of
226    // first_iter.get_element() and second_iter.get_element()
227    // (restricted to List_Support_Variables variables).
228
229    for(int i=0;i<S.number_of_subsets[supp_union];i++)
230      // Go through the lists that contain elements whose support is a
231      // subset of supp_union.
232    {
233      int actual_list=S.subsets_of_support[supp_union][i];
234
235      if(actual_list<=supp2)
236        continue;
237      // Only lists after second_iter's list have to be considered.
238
239      iter.set_to_list(generators[actual_list]);
240      // This is the i-th list among the generator list with elements
241      // whose support is a subset of supp_union.
242
243      while(iter.is_at_end()==FALSE)
244      {
245        // Iterate over the list with three iterators according to the
246        // description of criterion B.
247        if(B(iter.get_element(),bin1,bin2)==TRUE)
248          return TRUE;
249        iter.next();
250      }
251    }
252
253#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
254  }
255
256////////////////////// BuchbergerŽs second criterion ////////////////////////
257
258  if(second_criterion)
259  {
260    list_iterator iter;
261    binomial& bin1=first_iter.get_element();
262    binomial& bin2=second_iter.get_element();
263
264    // The BuchbergerŽs second criterion checks binomial triples as
265    // explained in binomial.h; these are built of the elements referenced
266    // by the argument iterators and a third element appearing anywhere
267    // in the generator lists.
268
269#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
270
271    iter.set_to_list(generators);
272
273    while(iter.is_at_end()==FALSE)
274      // Iterate over the list with three iterators according to the
275      // description of the second criterion.
276    {
277      if((iter!=first_iter) && (iter!=second_iter))
278        // Else the second criterion must not be applied
279        // (lcm(a,b) is, of course, divisible by a and by b).
280        if(second_crit(iter.get_element(),bin1,bin2)==TRUE)
281          return TRUE;
282      iter.next();
283    }
284
285#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
286
287#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
288
289    // Again, we only have to consider lists whose support is a subset of
290    // the union of (first_iter.get_element()).head_support
291    // and (second_iter.get_element()).head_support.
292
293    int supp1=bin1.head_support%Number_of_Lists;
294    int supp2=bin2.head_support%Number_of_Lists;
295    int supp_union=supp1|supp2;
296    // supp_union (read as binary vector) is the union of the supports of
297    // first_iter.get_element() and second_iter.get_element()
298    // (restricted to List_Support_Variables variables)
299
300    for(int i=0;i<S.number_of_subsets[supp_union];i++)
301      // Go through the lists that contain elements whose support is a
302      // subset of supp_union.
303    {
304      int actual_list=S.subsets_of_support[supp_union][i];
305
306      if((actual_list==supp1) || (actual_list==supp2))
307        continue;
308      // The lists containing the elements referenced by the argument
309      // iterators are tested separately to avoid unnecessary checks for
310      // equality.
311
312      iter.set_to_list(generators[actual_list]);
313      // This is the i-th list among the generator list with elements
314      // whose support is a subset of supp_union.
315
316      while(iter.is_at_end()==FALSE)
317        // Iterate over the list with three iterators according to the
318        // description of the second criterion.
319      {
320        if(second_crit(iter.get_element(),bin1,bin2)==TRUE)
321          return TRUE;
322        iter.next();
323      }
324    }
325
326    if(supp1==supp2)
327      // The elements referenced by first_iter and second_iter appear in the
328      // same list.
329    {
330      iter.set_to_list(generators[supp1]);
331      while(iter.is_at_end()==FALSE)
332      {
333        if((iter!=first_iter) && (iter!=second_iter))
334          // Else the second criterion must not be applied
335          // (lcm(a,b) is, of course, divisible by a and by b).
336          if(second_crit(iter.get_element(),bin1,bin2)==TRUE)
337            return TRUE;
338        iter.next();
339      }
340    }
341    else
342      // The elements referenced by first_iter and second_iter appear in
343      // different lists.
344    {
345
346      // Test first_iterŽs list.
347      iter.set_to_list(generators[supp1]);
348      while(iter.is_at_end()==FALSE)
349      {
350        if(iter!=first_iter)
351          // Else the second criterion must not be applied
352          // (lcm(a,b) is, of course, divisible by a and by b).
353          if(second_crit(iter.get_element(),bin1,bin2)==TRUE)
354            return TRUE;
355        iter.next();
356      }
357
358      // Test second_iterŽs list.
359      iter.set_to_list(generators[supp2]);
360      while(iter.is_at_end()==FALSE)
361      {
362        if(iter!=second_iter)
363          // Else the second criterion must not be applied
364          // (lcm(a,b) is, of course, divisible by a and by b).
365          if(second_crit(iter.get_element(),bin1,bin2)==TRUE)
366            return TRUE;
367        iter.next();
368      }
369    }
370#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
371  }
372
373  // no criterion found to discard the S-Pair to compute
374  return FALSE;
375}
376
377ideal& ideal::compute_actual_S_pairs_1()
378{
379// This routine implements the simplest method for the S-pair computation
380// (and one of the most efficient methods). We simply iterate over the
381// generator list(s) with two pointers to look at each binomial pair.
382// The "done"-mark of each list element tells us if this element was
383// already considered in a previous S-pair computation; pairs of such
384// "old" binomials do not have to be computed anymore (but pairs of an old
385// and a new one have to be computed, of course). As the generator list are
386// ordered with respect to the "done"-flag (all undone elements preceed all
387// done elements), we can avoid unnecessary iteration steps by breaking
388// the iteration at the right point.
389
390// The computed S-pairs are stored in the aux_list for further computations.
391
392// For a better overview, the code for NO_SUPPORT_DRIVEN_METHODS_EXTENDED
393// and SUPPORT_DRIVEN_METHODS_EXTENDED is completetly separated in this
394// function.
395
396// Note that the "next()"-operations in the following routine do not reach a
397// NULL pointer because of the implementation of the "is_at_end()"-function
398// and because the "done"-component of the dummy element is set to zero.
399
400#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
401
402  list_iterator first_iter(generators);
403
404  while(first_iter.element_is_marked_done()==FALSE)
405    // new generator, compute S-pairs with all following generators
406    // Notice that the new generators are always at the beginning,
407    // the old generators at the end of the generator list.
408  {
409    binomial& bin=first_iter.get_element();
410    first_iter.mark_element_done();
411
412    list_iterator second_iter(first_iter);
413    second_iter.next();
414    // This may be the dummy element.
415
416    while(second_iter.is_at_end()==FALSE)
417    {
418      if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
419         aux_list._insert(S_binomial(bin,second_iter.get_element(),w));
420      second_iter.next();
421    }
422
423    first_iter.next();
424  }
425
426  // Now, first_iter references an old generator or the end of the generator
427  // list. As all following generators are old ones, we are done.
428
429#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
430
431
432#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
433
434  list_iterator first_iter;
435
436  for(int i=0;i<Number_of_Lists;i++)
437  {
438    first_iter.set_to_list(generators[i]);
439
440    while(first_iter.element_is_marked_done()==FALSE)
441      // new generator, compute S-pairs with all following elements
442      // Notice that the new generators are always at the beginning,
443      // the old generators at the end of the generator lists.
444    {
445      binomial& bin=first_iter.get_element();
446      first_iter.mark_element_done();
447
448      // First search over the actual list with the second iterator.
449
450      list_iterator second_iter(first_iter);
451      second_iter.next();
452
453      while(second_iter.is_at_end()==FALSE)
454      {
455        if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
456          aux_list._insert(S_binomial(bin,second_iter.get_element(),w));
457      second_iter.next();
458      }
459
460      // Then search over the remaining lists.
461
462      for(int j=i+1;j<Number_of_Lists;j++)
463      {
464        second_iter.set_to_list(generators[j]);
465
466        while(second_iter.is_at_end()==FALSE)
467        {
468          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
469            aux_list._insert(S_binomial(bin,second_iter.get_element(),w));
470          second_iter.next();
471        }
472      }
473      first_iter.next();
474    }
475
476    while(first_iter.is_at_end()==FALSE)
477      // old generator, compute only S-pairs with the following new generators
478      // (S-pairs with the following old generators were already computed
479      // before, first_iter.element_is_marked_done()==TRUE)
480      // As all generators in the actual list are old ones, we can
481      // start iteration with the next list.
482    {
483      binomial& bin=first_iter.get_element();
484
485      list_iterator second_iter;
486
487      for(int j=i+1;j<Number_of_Lists;j++)
488        // search over remaining lists
489      {
490        second_iter.set_to_list(generators[j]);
491
492        while(second_iter.element_is_marked_done()==FALSE)
493          // consider only new generators
494        {
495          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
496            aux_list._insert(S_binomial(bin,second_iter.get_element(),w));
497          second_iter.next();
498        }
499      }
500      first_iter.next();
501    }
502
503  }
504
505#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
506  return(*this);
507}
508
509ideal& ideal::compute_actual_S_pairs_1a()
510{
511// The only difference to the previous routine is that the aux_list is kept
512// ordered with respect to the idealŽs term ordering, i.e. the inserts are
513// replaced by ordered inserts.
514
515#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
516
517  list_iterator first_iter(generators);
518
519  while(first_iter.element_is_marked_done()==FALSE)
520    // new generator, compute S-pairs with all following generators
521    // Notice that the new generators are always at the beginning,
522    // the old generators at the end of the generator list.
523  {
524    binomial& bin=first_iter.get_element();
525    first_iter.mark_element_done();
526
527    list_iterator second_iter(first_iter);
528    second_iter.next();
529    // This may be the dummy element.
530
531    while(second_iter.is_at_end()==FALSE)
532    {
533      if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
534         aux_list._ordered_insert
535           (S_binomial(bin,second_iter.get_element(),w),w);
536      second_iter.next();
537    }
538    first_iter.next();
539  }
540
541  // Now, first_iter references an old generator or the end of the generator
542  // list. As all following generators are old ones, we are done.
543
544#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
545
546#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
547
548  list_iterator first_iter;
549
550  for(int i=0;i<Number_of_Lists;i++)
551  {
552    first_iter.set_to_list(generators[i]);
553
554    while(first_iter.element_is_marked_done()==FALSE)
555      // new generator, compute S-pairs with all following elements
556      // Notice that the new generators are always at the beginning,
557      // the old generators at the end of the generator lists.
558    {
559      binomial& bin=first_iter.get_element();
560      first_iter.mark_element_done();
561
562      // First search over the actual list with the second iterator.
563
564      list_iterator second_iter(first_iter);
565      second_iter.next();
566
567      while(second_iter.is_at_end()==FALSE)
568      {
569        if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
570          aux_list._ordered_insert
571            (S_binomial(bin,second_iter.get_element(),w),w);
572      second_iter.next();
573      }
574
575      // Then search over the remaining lists.
576
577      for(int j=i+1;j<Number_of_Lists;j++)
578      {
579        second_iter.set_to_list(generators[j]);
580
581        while(second_iter.is_at_end()==FALSE)
582        {
583          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
584            aux_list._ordered_insert
585              (S_binomial(bin,second_iter.get_element(),w),w);
586          second_iter.next();
587        }
588      }
589      first_iter.next();
590    }
591
592    while(first_iter.is_at_end()==FALSE)
593      // old generator, compute only S-pairs with the following new generators
594      // (S-pairs with the following old generators were already computed
595      // before, first_iter.element_is_marked_done()==TRUE)
596      // As all generators in the actual list are old ones, we can
597      // start iteration with the next list.
598    {
599      binomial& bin=first_iter.get_element();
600
601      list_iterator second_iter;
602
603      for(int j=i+1;j<Number_of_Lists;j++)
604        // search over remaining lists
605      {
606        second_iter.set_to_list(generators[j]);
607
608        while(second_iter.element_is_marked_done()==FALSE)
609          // consider only new generators
610        {
611          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
612            aux_list._ordered_insert
613              (S_binomial(bin,second_iter.get_element(),w),w);
614          second_iter.next();
615        }
616      }
617      first_iter.next();
618    }
619
620  }
621
622#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
623
624  return(*this);
625}
626
627ideal& ideal::compute_actual_S_pairs_2()
628{
629// This routine implements are mor dynamic S-pair-computation. As in the
630// previous routines, we iterate over the generator list(s) with two
631// iterators, forming pairs under the consideration of the "done"-flags.
632
633// But before inserting into the aux_list, these S-pairs are reduced by
634// the ideal generators. This seems to be clever, but shows to be a
635// disadvantage:
636// In the previous S-pair routines, the computed S-bionomials are not reduced
637// at all. This is done in the appropriate Groebner basis routine
638// (reduced_Groebner_basis_1 or ..._1a) when moving them from the aux_list
639// to the generator lists. This meens that S-binomials cannot only be reduced
640// by the generators known at the time of their computation, but also by
641// the S-pairs that where already treated.
642
643// The advantage of the current routine is that the immediately reduced
644// S-binomial can be used to reduce the ideal itself. This strategy keeps
645// the ideal almost reduced, so the minimalization will be faster.
646// Furthermore, the computation of S-pairs with unreduced generators is
647// avoided.
648// To provide a possibility to compensate the mentionned disadvantage,
649// I have written the routine minimalize_S_pairs() that interreduces the
650// binomials stored in aux_list.
651
652#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
653
654  list_iterator first_iter(generators);
655
656  Integer first_reduced=0;
657  Integer second_reduced=0;
658  // When reducing the ideal immediately by newly found generators, it
659  // can happen that the binomials referenced by the iterators are
660  // reduced to zero and then deleted. We need to make sure that the
661  // iterators do not reference freed memory in such a case. These two
662  // flags help us with this task.
663
664  while(first_iter.element_is_marked_done()==FALSE)
665    // new generator, compute S-pairs with all following generators
666  {
667    binomial& bin1=first_iter.get_element();
668    first_iter.mark_element_done();
669
670    list_iterator second_iter(first_iter);
671    second_iter.next();
672    // This may be the dummy element.
673
674    while((second_iter.is_at_end()==FALSE) && (first_reduced<=0))
675    {
676      if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
677      {
678        binomial& bin2=second_iter.get_element();
679
680        // compute S-binomial
681        binomial& S_bin=S_binomial(bin1,bin2,w);
682
683        // reduce S-binomial by the actual ideal generators
684        reduce(S_bin,FALSE);
685
686        if(S_bin!=0)
687        {
688          // reduce the ideal generators by the S-binomial
689          first_reduced=bin1.head_reductions_by(S_bin);
690          second_reduced=bin2.head_reductions_by(S_bin);
691          reduce_by(S_bin,first_iter,second_iter);
692          aux_list._insert(S_bin);
693        }
694        else
695          delete &S_bin;
696
697      }
698
699      // Move second_iter to the next element if its referenced binomial
700      // has not changed (if it has changed, the binomial was moved to the
701      // aux_list during the reduce_by(...)-procedure, and second_iter
702      // already references a new binomial).
703      if(second_reduced<=0)
704        second_iter.next();
705      else
706        second_reduced=0;
707
708    }
709
710    // same procedure for first_iter
711    if(first_reduced<=0)
712      first_iter.next();
713    else
714      first_reduced=0;
715  }
716
717#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
718
719
720#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
721
722  list_iterator first_iter;
723
724  Integer first_reduced=0;
725  Integer second_reduced=0;
726  // When reducing the ideal immediately by newly found generators, it
727  // can happen that the binomials referenced by the iterators are
728  // changed (including their support!) or even reduced to zero and then
729  // deleted. We need to make sure that the iterators do not reference
730  // freed memory in such a case. These two flags help us with this task.
731
732
733  for(int i=0;i<Number_of_Lists;i++)
734  {
735    first_iter.set_to_list(generators[i]);
736
737    while(first_iter.element_is_marked_done()==FALSE)
738      // new generator, compute S-pairs with all following elements
739    {
740      binomial& bin1=first_iter.get_element();
741      first_iter.mark_element_done();
742
743      list_iterator second_iter(first_iter);
744      second_iter.next();
745
746      // First search over the actual list.
747
748      while((second_iter.is_at_end()==FALSE) && (first_reduced<=0))
749      {
750        if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
751        {
752          binomial& bin2=second_iter.get_element();
753
754          // compute S-binomial
755          binomial& S_bin=S_binomial(bin1,bin2,w);
756
757          // reduce S-binomial by the actual ideal generators
758          reduce(S_bin,FALSE);
759
760          if((S_bin)!=0)
761          {
762            // reduce the ideal generators by the S-binomial
763            first_reduced=bin1.head_reductions_by(S_bin);
764            second_reduced=bin2.head_reductions_by(S_bin);
765            reduce_by(S_bin,first_iter,second_iter);
766            aux_list._insert(S_bin);
767          }
768          else
769            delete &S_bin;
770
771        }
772
773        // Move second_iter to the next element if its referenced binomial
774        // has not changed (if it has changed, the binomial was moved to the
775        // aux_list during the reduce_by(...)-procedure, and second_iter
776        // already references a new binomial).
777        if(second_reduced<=0)
778          second_iter.next();
779        else
780          second_reduced=0;
781
782      }
783
784      // Then search over the remaining lists.
785
786      for(int j=i+1;(j<Number_of_Lists) && (first_reduced<=0);j++)
787      {
788        second_iter.set_to_list(generators[j]);
789
790        while((second_iter.is_at_end()==FALSE) && (first_reduced<=0))
791        {
792          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
793          {
794            binomial& bin2=second_iter.get_element();
795
796            // compute S-binomial
797            binomial& S_bin=S_binomial(bin1,bin2,w);
798
799            // reduce S-binomial by the actual ideal generators
800            reduce(S_bin,FALSE);
801
802            if((S_bin)!=0)
803            {
804              // reduce the ideal generators by the S-binomial
805              first_reduced=bin1.head_reductions_by(S_bin);
806              second_reduced=bin2.head_reductions_by(S_bin);
807              reduce_by(S_bin,first_iter,second_iter);
808              aux_list._insert(S_bin);
809            }
810            else
811              delete& S_bin;
812
813          }
814
815          // Move second_iter to the next element if its referenced binomial
816          // has not changed.
817          if(second_reduced<=0)
818            second_iter.next();
819          else
820            second_reduced=0;
821        }
822      }
823
824      // same procedure for first_iter
825      if(first_reduced<=0)
826        first_iter.next();
827      else
828        first_reduced=0;
829
830    }
831
832
833    while(first_iter.is_at_end()==FALSE)
834      // old generator, compute only S-pairs with the following new generators
835      // As all generators in the actual list are old ones, we can
836      // start iteration with the next list.
837    {
838      binomial& bin1=first_iter.get_element();
839
840      list_iterator second_iter(first_iter);
841      second_iter.next();
842
843     for(int j=i+1;(j<Number_of_Lists) && (first_reduced<=0);j++)
844      {
845        second_iter.set_to_list(generators[j]);
846
847        while((second_iter.element_is_marked_done()==FALSE) &&
848              (first_reduced<=0))
849          // consider only new generators
850        {
851          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
852          {
853            binomial& bin2=second_iter.get_element();
854
855            // compute S-binomial
856            binomial& S_bin=S_binomial(bin1,bin2,w);
857
858            // reduce S-binomial by the actual ideal generators
859            reduce(S_bin,FALSE);
860
861            if((S_bin)!=0)
862            {
863              // reduce the ideal generators by the S-binomial
864              first_reduced=bin1.head_reductions_by(S_bin);
865              second_reduced=bin2.head_reductions_by(S_bin);
866              reduce_by(S_bin,first_iter,second_iter);
867              aux_list._insert(S_bin);
868            }
869            else
870              delete& S_bin;
871
872          }
873
874          // Move second_iter to the next element if its referenced binomial
875          // has not changed.
876          if(second_reduced<=0)
877            second_iter.next();
878          else
879            second_reduced=0;
880        }
881      }
882
883      // same procedure for first_iter
884      if(first_reduced<=0)
885        first_iter.next();
886      else
887        first_reduced=0;
888
889    }
890  }
891
892#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
893
894
895  return(*this);
896}
897
898
899
900
901
902ideal& ideal::compute_actual_S_pairs_3()
903{
904// This routine is quite similar to the preceeding.
905// The main difference is that the computed S-binomials are not stored in the
906// aux_list, but in new_generators. This makes a difference when minimalizing
907// the S-binomials in the appropriate Groebner basis routine
908// (reduced_Groebner_basis_3) with the help of the procedure
909// minimalize_new_generators(...).
910// If NO_SUPPORT_DRIVEN_METHODS_EXTENDED are enabled, only the organization
911// of the minimalization is different.
912// If SUPPORT_DRIVEN_METHODS_EXTENDED are enabled, the minimalization can
913// use the support information.
914
915
916#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
917
918  list_iterator first_iter(generators);
919
920  Integer first_reduced=0;
921  Integer second_reduced=0;
922  // When reducing the ideal immediately by newly found generators, it
923  // can happen that the binomials referenced by the iterators are
924  // reduced to zero and then deleted. We need to make sure that the
925  // iterators do not reference freed memory in such a case. These two
926  // flags help us with this task.
927
928  while(first_iter.element_is_marked_done()==FALSE)
929    // new generator, compute S-pairs with all following generators
930  {
931    binomial& bin1=first_iter.get_element();
932    first_iter.mark_element_done();
933
934    list_iterator second_iter(first_iter);
935    second_iter.next();
936    // This may be the dummy element.
937
938    while((second_iter.is_at_end()==FALSE) && (first_reduced<=0))
939    {
940      if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
941      {
942        binomial& bin2=second_iter.get_element();
943
944        // compute S-binomial
945        binomial& S_bin=S_binomial(bin1,bin2,w);
946
947        // reduce S-binomial by the actual ideal generators
948        reduce(S_bin,FALSE);
949
950        if(S_bin!=0)
951        {
952          // reduce the ideal generators by the S-binomial
953          first_reduced=bin1.head_reductions_by(S_bin);
954          second_reduced=bin2.head_reductions_by(S_bin);
955          reduce_by(S_bin,first_iter,second_iter);
956          add_new_generator(S_bin);
957        }
958        else
959          delete &S_bin;
960
961      }
962
963      // Move second_iter to the next element if its referenced binomial
964      // has not changed (if it has changed, the binomial was moved to the
965      // aux_list during the reduce_by(...)-procedure, and second_iter
966      // already references a new binomial).
967      if(second_reduced<=0)
968        second_iter.next();
969      else
970        second_reduced=0;
971
972    }
973
974    // same procedure for first_iter
975    if(first_reduced<=0)
976      first_iter.next();
977    else
978      first_reduced=0;
979  }
980
981#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
982
983
984#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
985
986  list_iterator first_iter;
987
988  Integer first_reduced=0;
989  Integer second_reduced=0;
990  // When reducing the ideal immediately by newly found generators, it
991  // can happen that the binomials referenced by the iterators are
992  // changed (including their support!) or even reduced to zero and then
993  // deleted. We need to make sure that the iterators do not reference
994  // freed memory in such a case. These two flags help us with this task.
995
996
997  for(int i=0;i<Number_of_Lists;i++)
998  {
999    first_iter.set_to_list(generators[i]);
1000
1001    while(first_iter.element_is_marked_done()==FALSE)
1002      // new generator, compute S-pairs with all following elements
1003    {
1004      binomial& bin1=first_iter.get_element();
1005      first_iter.mark_element_done();
1006
1007      list_iterator second_iter(first_iter);
1008      second_iter.next();
1009
1010      // First search over the actual list.
1011
1012      while((second_iter.is_at_end()==FALSE) && (first_reduced<=0))
1013      {
1014        if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
1015        {
1016          binomial& bin2=second_iter.get_element();
1017
1018          // compute S-binomial
1019          binomial& S_bin=S_binomial(bin1,bin2,w);
1020
1021          // reduce S-binomial by the actual ideal generators
1022          reduce(S_bin,FALSE);
1023
1024          if((S_bin)!=0)
1025          {
1026            // reduce the ideal generators by the S-binomial
1027            first_reduced=bin1.head_reductions_by(S_bin);
1028            second_reduced=bin2.head_reductions_by(S_bin);
1029            reduce_by(S_bin,first_iter,second_iter);
1030            add_new_generator(S_bin);
1031          }
1032          else
1033            delete &S_bin;
1034
1035        }
1036
1037        // Move second_iter to the next element if its referenced binomial
1038        // has not changed (if it has changed, the binomial was moved to the
1039        // aux_list during the reduce_by(...)-procedure, and second_iter
1040        // already references a new binomial).
1041        if(second_reduced<=0)
1042          second_iter.next();
1043        else
1044          second_reduced=0;
1045
1046      }
1047
1048      // Then search over the remaining lists.
1049
1050      for(int j=i+1;(j<Number_of_Lists) && (first_reduced<=0);j++)
1051      {
1052        second_iter.set_to_list(generators[j]);
1053
1054        while((second_iter.is_at_end()==FALSE) && (first_reduced<=0))
1055        {
1056          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
1057          {
1058            binomial& bin2=second_iter.get_element();
1059
1060            // compute S-binomial
1061            binomial& S_bin=S_binomial(bin1,bin2,w);
1062
1063            // reduce S-binomial by the actual ideal generators
1064            reduce(S_bin,FALSE);
1065
1066            if((S_bin)!=0)
1067            {
1068              // reduce the ideal generators by the S-binomial
1069              first_reduced=bin1.head_reductions_by(S_bin);
1070              second_reduced=bin2.head_reductions_by(S_bin);
1071              reduce_by(S_bin,first_iter,second_iter);
1072              add_new_generator(S_bin);
1073            }
1074            else
1075              delete& S_bin;
1076
1077          }
1078
1079          // Move second_iter to the next element if its referenced binomial
1080          // has not changed.
1081          if(second_reduced<=0)
1082            second_iter.next();
1083          else
1084            second_reduced=0;
1085        }
1086      }
1087
1088      // same procedure for first_iter
1089      if(first_reduced<=0)
1090        first_iter.next();
1091      else
1092        first_reduced=0;
1093
1094    }
1095
1096
1097    while(first_iter.is_at_end()==FALSE)
1098      // old generator, compute only S-pairs with the following new generators
1099      // As all generators in the actual list are old ones, we can
1100      // start iteration with the next list.
1101    {
1102      binomial& bin1=first_iter.get_element();
1103
1104      list_iterator second_iter(first_iter);
1105      second_iter.next();
1106
1107     for(int j=i+1;(j<Number_of_Lists) && (first_reduced<=0);j++)
1108      {
1109        second_iter.set_to_list(generators[j]);
1110
1111        while((second_iter.element_is_marked_done()==FALSE) &&
1112              (first_reduced<=0))
1113          // consider only new generators
1114        {
1115          if(unnecessary_S_pair(first_iter,second_iter)==FALSE)
1116          {
1117            binomial& bin2=second_iter.get_element();
1118
1119            // compute S-binomial
1120            binomial& S_bin=S_binomial(bin1,bin2,w);
1121
1122            // reduce S-binomial by the actual ideal generators
1123            reduce(S_bin,FALSE);
1124
1125            if((S_bin)!=0)
1126            {
1127              // reduce the ideal generators by the S-binomial
1128              first_reduced=bin1.head_reductions_by(S_bin);
1129              second_reduced=bin2.head_reductions_by(S_bin);
1130              reduce_by(S_bin,first_iter,second_iter);
1131              add_new_generator(S_bin);
1132            }
1133            else
1134              delete& S_bin;
1135
1136          }
1137
1138          // Move second_iter to the next element if its referenced binomial
1139          // has not changed.
1140          if(second_reduced<=0)
1141            second_iter.next();
1142          else
1143            second_reduced=0;
1144        }
1145      }
1146
1147      // same procedure for first_iter
1148      if(first_reduced<=0)
1149        first_iter.next();
1150      else
1151        first_reduced=0;
1152
1153    }
1154  }
1155
1156#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
1157
1158
1159  // During the reduce_by(...)-routines, some reduced generators were
1160  // perhaps moved to the aux_list. This list is emptied now: Like the
1161  // computed S-pairs, its elements are moved to the list(s) new_generators.
1162  // To avoid this construction, we would have to write a second version
1163  // of the reduce_by(...)-procedure. The efficiency gains would however
1164  // not be considerable.
1165
1166  list_iterator iter(aux_list);
1167
1168  while(iter.is_at_end()==FALSE)
1169  {
1170    add_new_generator(iter.get_element());
1171    iter.extract_element();
1172  }
1173
1174
1175  return(*this);
1176}
1177
1178
1179
1180
1181
1182//////////////////////////////////////////////////////////////////////////////
1183//////////// minimalization / autoreduction //////////////////////////////////
1184//////////////////////////////////////////////////////////////////////////////
1185
1186
1187
1188
1189
1190ideal& ideal::reduce_by(const binomial& bin, list_iterator& first_iter,
1191                        list_iterator& second_iter)
1192{
1193// This routine reduces the ideal by the argument binomial and takes
1194// care that the argument list iterators are not corrupted.
1195// Only head reductions are performed.
1196
1197
1198#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1199
1200  list_iterator iter(generators);
1201  Integer reduced;
1202
1203  while(iter.is_at_end()==FALSE)
1204  {
1205    binomial& actual=iter.get_element();
1206
1207    // reduce actual binomial by bin
1208    reduced=actual.head_reductions_by(bin);
1209
1210    if(reduced<=0)
1211      iter.next();
1212
1213    else
1214      // the actual binomial has changed and will be removed or
1215      // moved to the aux_list
1216    {
1217
1218#ifdef SL_LIST
1219
1220      // If we use a simply linked list, we have to take care of the
1221      // following binomial.
1222      if(iter.next_is(first_iter)==TRUE)
1223        first_iter=iter;
1224      if(iter.next_is(second_iter)==TRUE)
1225        second_iter=iter;
1226
1227#endif  // SL_LIST
1228
1229
1230#ifdef DL_LIST
1231
1232      // If we use a doubly linked list, we have to take care of the
1233      // binomial itself.
1234      if(iter==first_iter)
1235        first_iter.next();
1236      if(iter==second_iter)
1237        second_iter.next();
1238
1239#endif  // DL_LIST
1240
1241
1242      // move changed generator to the aux_list or delete it
1243      if(actual==0)
1244        iter.delete_element();
1245      else
1246      {
1247        aux_list._insert(actual);
1248        iter.extract_element();
1249      }
1250
1251      size--;
1252    }
1253  }
1254
1255#endif  // NO_SUPPORT_DRIVEN_METHOD_EXTENDED
1256
1257
1258#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
1259
1260  int supp1=(first_iter.get_element()).head_support%Number_of_Lists;
1261  int supp2=(second_iter.get_element()).head_support%Number_of_Lists;
1262
1263  // Determine the lists over which we have to iterate.
1264  // These are the lists with elements whose support contains the support
1265  // of bin.
1266  // List i has to be checked iff the set of bits in i that are 1 contains
1267  // the set of bits in supp that are 1.
1268  // Equivalent: List i has to be checked iff the set of bits in i
1269  // that are 0 is contained in the set of bits of supp that are 0.
1270  // With this formulation, we can use the subset tree as follows:
1271
1272  int supp=bin.head_support%Number_of_Lists;
1273  int inv_supp=Number_of_Lists-supp-1;
1274  // This bit vector is the bitwise inverse of bin.head_support (restricted
1275  // to the variables considered in the list indices.
1276
1277  list_iterator iter;
1278  Integer reduced;
1279
1280
1281  for(int i=0;i<S.number_of_subsets[inv_supp];i++)
1282  {
1283    int actual_list=Number_of_Lists-S.subsets_of_support[inv_supp][i]-1;
1284    // the actual list for iteration
1285    // The support of S.subsets_of_support[inv_supp][i] as a bit vector
1286    // is contained in that of inv_supp.
1287    // I.e. the support of
1288    // Number_of_Lists-S.subsets_of_support[inv_supp][i]-1
1289    // - which is the bitwise inverse of S.subsets_of_support[inv_supp][i] -
1290    // contains the support of the bitwise inverse of inv_supp, hence the
1291    // support of supp.
1292
1293    if((actual_list==supp1) || (actual_list==supp2))
1294      // The lists referenced by first_iter and second_iter are tested
1295      // separately to avoid unnecessary checks.
1296      continue;
1297
1298    iter.set_to_list(generators[actual_list]);
1299
1300    while(iter.is_at_end()==FALSE)
1301    {
1302      binomial& actual=iter.get_element();
1303
1304      // reduce actual binomial by bin
1305      reduced=actual.head_reductions_by(bin);
1306
1307      if(reduced<=0)
1308        iter.next();
1309
1310      else
1311        // the actual binomial has changed and will be removed or
1312      {
1313        if(actual==0)
1314          iter.delete_element();
1315
1316        else
1317        {
1318          aux_list._insert(actual);
1319          iter.extract_element();
1320        }
1321
1322        size--;
1323      }
1324    }
1325  }
1326
1327  // Now test the lists referenced by first_iter and second_iter.
1328
1329  if(supp1==supp2)
1330    // first_iter and second_iter reference the same list
1331  {
1332    if((supp1|supp)==supp1)
1333      // support of bin contained in that of the element referenced by
1334      // first_iter, else this list has not to be tested
1335    {
1336      iter.set_to_list(generators[supp1]);
1337
1338      while(iter.is_at_end()==FALSE)
1339      {
1340        binomial& actual=iter.get_element();
1341        reduced=actual.head_reductions_by(bin);
1342        if(reduced<=0)
1343          iter.next();
1344        else
1345        {
1346
1347#ifdef SL_LIST
1348
1349          if(iter.next_is(first_iter)==TRUE)
1350            first_iter=iter;
1351          if(iter.next_is(second_iter)==TRUE)
1352            second_iter=iter;
1353
1354#endif  // SL_LIST
1355
1356#ifdef DL_LIST
1357
1358          if(iter==first_iter)
1359            first_iter.next();
1360          if(iter==second_iter)
1361            second_iter.next();
1362
1363#endif  // DL_LIST
1364
1365          if(actual==0)
1366            iter.delete_element();
1367          else
1368          {
1369            aux_list._insert(actual);
1370            iter.extract_element();
1371          }
1372
1373          size--;
1374        }
1375      }
1376    }
1377  }
1378
1379  else
1380    // first_iter and second_iter reference different lists
1381  {
1382    if((supp1|supp)==supp1)
1383      // support of bin contained in that of the element referenced by
1384      // first_iter, else this list has not to be tested
1385    {
1386      iter.set_to_list(generators[supp1]);
1387
1388      while(iter.is_at_end()==FALSE)
1389      {
1390        binomial& actual=iter.get_element();
1391        reduced=actual.head_reductions_by(bin);
1392        if(reduced<=0)
1393          iter.next();
1394        else
1395        {
1396
1397#ifdef SL_LIST
1398
1399          if(iter.next_is(first_iter)==TRUE)
1400            first_iter=iter;
1401
1402#endif  // SL_LIST
1403
1404#ifdef DL_LIST
1405
1406          if(iter==first_iter)
1407            first_iter.next();
1408
1409#endif  // DL_LIST
1410
1411          if(actual==0)
1412            iter.delete_element();
1413          else
1414          {
1415            aux_list._insert(actual);
1416            iter.extract_element();
1417          }
1418
1419          size--;
1420        }
1421      }
1422    }
1423
1424    if((supp2|supp)==supp2)
1425      // support of bin contained in that of the element referenced by
1426      // second_iter, else this list has not to be tested
1427    {
1428      iter.set_to_list(generators[supp2]);
1429
1430      while(iter.is_at_end()==FALSE)
1431      {
1432        binomial& actual=iter.get_element();
1433        reduced=actual.head_reductions_by(bin);
1434        if(reduced<=0)
1435          iter.next();
1436        else
1437        {
1438
1439#ifdef SL_LIST
1440
1441          if(iter.next_is(second_iter)==TRUE)
1442            second_iter=iter;
1443
1444#endif  // SL_LIST
1445
1446#ifdef DL_LIST
1447
1448          if(iter==second_iter)
1449            second_iter.next();
1450
1451#endif  // DL_LIST
1452
1453          if(actual==0)
1454            iter.delete_element();
1455          else
1456          {
1457            aux_list._insert(actual);
1458            iter.extract_element();
1459          }
1460
1461          size--;
1462        }
1463      }
1464    }
1465  }
1466
1467#endif
1468
1469  return *this;
1470
1471}
1472
1473
1474
1475
1476
1477ideal& ideal::minimalize_S_pairs()
1478{
1479// This routine implements a very simple minimalization method. We iterate
1480// over the S-pair lists with two iterators, interreducing the two referenced
1481// binomials. Remember that the S-pair list does not use the "head_reduced"-
1482// flags. The iteration is repeated as long as some interreduction is done.
1483
1484  list_iterator first_iter;
1485  int found;
1486  // to control if a reduction has occurred during the actual iteration
1487
1488  do
1489  {
1490
1491    first_iter.set_to_list(aux_list);
1492    found=0;
1493    // no reduction occured yet
1494
1495    while(first_iter.is_at_end()==FALSE)
1496    {
1497
1498      binomial& bin1=first_iter.get_element();
1499      int first_changed=0;
1500      // to control if the first element has been reduced
1501
1502      // look at all following binomials
1503      list_iterator second_iter(first_iter);
1504      second_iter.next();
1505      // this may be the dummy element
1506
1507      while(second_iter.is_at_end()==FALSE)
1508      {
1509        binomial& bin2=second_iter.get_element();
1510        int second_changed=0;
1511
1512        if(bin1.reduce_head_by(bin2,w)!=0)
1513          // head of first binomial can be reduced by second
1514        {
1515
1516          if(bin1!=0)
1517            found=1;
1518            // found has not to be set if a binomial is reduced to zero
1519            // (then there are no new binomials)
1520
1521          else
1522            // the binomial referenced by bin1 is zero
1523          {
1524
1525#ifdef SL_LIST
1526
1527            if(first_iter.next_is(second_iter))
1528              second_iter.next();
1529
1530#endif  // SL_LIST
1531
1532            first_iter.delete_element();
1533            first_changed=1;
1534          }
1535
1536          break;
1537          // Breaks the while-loop.
1538          // As the element referenced by first_iter has changed,
1539          // the iteration with the second iterator can be restarted.
1540          // (We try to reduce as many elements as possible in one iteration.)
1541        }
1542
1543
1544        if(bin2.reduce_head_by(bin1,w)!=0)
1545           // head of second binomial can be reduced by first
1546        {
1547
1548          if(bin2!=0)
1549            found=1;
1550            // found has not to be set if a binomial is reduced to zero
1551            // (then there are no new binomials)
1552
1553          else
1554            // binomial referenced by bin2 is zero
1555          {
1556            second_iter.delete_element();
1557            second_changed=1;
1558          }
1559
1560          // As the second iterator always references an element coming
1561          // after first_iter's element in the generator list, we do not
1562          // pay attention to the deletion...
1563        }
1564
1565        if(second_changed==0)
1566          second_iter.next();
1567      }
1568
1569
1570      // Now second_iter has reached the end of the generator list or the
1571      // element referenced by first_iter has been reduced...The iteration
1572      // is continued with a new (or changed) first binomial.
1573
1574      if(first_changed==0)
1575        first_iter.next();
1576    }
1577
1578 }
1579  while(found==1);
1580
1581  // When leaving the loop, no generators have been interreduced during
1582  // the last iteration.
1583
1584  return *this;
1585}
1586
1587
1588
1589
1590
1591ideal& ideal::minimalize_new_generators()
1592{
1593// This routine is very similar to the following one, minimalize().
1594// The only difference is that we interreduce the elements stored in
1595// new_generators instead of those stored in generators.
1596// The size of the ideal has not to be manipulated hereby.
1597
1598
1599#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1600
1601  list_iterator first_iter;
1602  int found;
1603  // to control if a reduction has occurred during the actual iteration
1604
1605  do
1606  {
1607    first_iter.set_to_list(new_generators);
1608    found=0;
1609    // no reduction occured yet
1610
1611    while(first_iter.element_is_marked_head_reduced()==FALSE)
1612      // only the first element is tested for this flag
1613      // the second may be an old one
1614    {
1615      binomial& bin1=first_iter.get_element();
1616      int first_changed=0;
1617      // to control if the first element has been reduced
1618
1619      // look at all following binomials
1620      list_iterator second_iter(first_iter);
1621      second_iter.next();
1622      // this may be the dummy element
1623
1624      while(second_iter.is_at_end()==FALSE)
1625      {
1626        binomial& bin2=second_iter.get_element();
1627
1628        if(bin1.reduce_head_by(bin2,w)!=0)
1629          // head of first binomial can be reduced by second
1630        {
1631
1632#ifdef SL_LIST
1633
1634          // The binomial referenced by first_iter will be deleted or
1635          // extracted. When using a simply linked list, this also affects
1636          // the following element. We need to assure that this element does
1637          // not reference freed memory.
1638          if(first_iter.next_is(second_iter))
1639              second_iter.next();
1640
1641#endif  // SL_LIST
1642
1643          if(bin1!=0)
1644          {
1645            found=1;
1646            // found has not to be set if a binomial is reduced to zero
1647            // (then there are no new binomials to insert)
1648
1649            aux_list._insert(bin1);
1650            first_iter.extract_element();
1651            // moved changed binomial to aux_list
1652          }
1653
1654          else
1655            first_iter.delete_element();
1656
1657
1658          first_changed=1;
1659          break;
1660          // As the binomial referenced by first_iter has changed,
1661          // the iteration with the second iterator can be restarted.
1662          // (We try to reduce as many elements as possible in one iteration.)
1663        }
1664
1665
1666        if(bin2.reduce_head_by(bin1,w)!=0)
1667           // head of second binomial can be reduced by first
1668        {
1669          // Here we do not have to pay attention to the deletion or the
1670          // extraction of the element referenced by second_iter because
1671          // the element referenced by second_iter always comes after the
1672          // element referenced by first_iter in new_generators.
1673
1674          if(bin2!=0)
1675          {
1676            found=1;
1677            // found has not to be set if a binomial is reduced to zero
1678            // (then there are no new binomials to insert)
1679
1680            aux_list._insert(bin2);
1681            second_iter.extract_element();
1682            // move the element referenced by second_iter to aux_list
1683          }
1684
1685          else
1686            second_iter.delete_element();
1687
1688          // Here it makes not sense to restart iteration because the
1689          // deletion sets the pointers as desired.
1690        }
1691
1692        else
1693          // no reduction possible
1694          second_iter.next();
1695
1696      }
1697
1698      // Now second_iter has reached the end of the list new_generators or the
1699      // binomial referenced first_iter has been reduced...The iteration
1700      // is continued with a new (or changed) first binomial.
1701
1702      if(first_changed==0)
1703        first_iter.next();
1704    }
1705
1706
1707    // Now we have found all currently possible reductions.
1708    // The elements remaining in new_generators cannot be interreduced
1709    // and are marked head_reduced.
1710
1711    first_iter.set_to_list(new_generators);
1712    //   if(first_iter.is_at_end()==FALSE)
1713      while(first_iter.element_is_marked_head_reduced()==FALSE)
1714      {
1715        first_iter.mark_element_head_reduced();
1716        first_iter.next();
1717      }
1718
1719
1720    // Now reinsert reduced elements.
1721
1722    first_iter.set_to_list(aux_list);
1723
1724    while(first_iter.is_at_end()==FALSE)
1725    {
1726      binomial& bin=first_iter.get_element();
1727
1728      reduce(bin,FALSE);
1729      // The binomial was only reduced by one other binomial before it was
1730      // moved to aux_list. To reduce it by all other binomials now can
1731      // diminish the number of iterations (do-while-loop).
1732
1733      if(bin==0)
1734        first_iter.delete_element();
1735      else
1736      {
1737        add_new_generator(bin);
1738        first_iter.extract_element();
1739      }
1740
1741    }
1742
1743  }
1744  while(found==1);
1745
1746  // When leaving the loop, no generators have been interreduced during
1747  // the last iteration; we are done.
1748
1749#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1750
1751
1752#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
1753
1754  list_iterator first_iter;
1755  list_iterator second_iter;
1756  int found;
1757  // to control if a reduction has occurred during the actual iteration
1758
1759  do
1760  {
1761    found=0;
1762    // no reduction occurred yet
1763
1764    for(int i=0;i<Number_of_Lists;i++)
1765    {
1766      first_iter.set_to_list(new_generators[i]);
1767
1768// First try to reduce the binomials that are marked unreduced.
1769
1770      while(first_iter.element_is_marked_head_reduced()==FALSE)
1771        // all other elements have to be tested for interreduction
1772      {
1773
1774        binomial& bin=first_iter.get_element();
1775        Integer changed=0;
1776        // binomial referenced by bin not yet reduced
1777
1778// Look for head reductions:
1779// Iterate over the lists that could contain reducers for the head of bin.
1780// The list containing bin is tested separately to avoid an interreduction
1781// of a binomial by itself respectively unnecessary checks for this when the
1782// two iterators reference different lists.
1783
1784        for(int j=0;(j<S.number_of_subsets[i]-1)&&(changed==0);j++)
1785        {
1786          second_iter.set_to_list(new_generators[S.subsets_of_support[i][j]]);
1787          // This is the j-th list among the new_generator lists with elements
1788          // whose support is a subset of that of i.
1789          // The support of i is just the head support of bin (restricted
1790          // to the corresponding variables).
1791
1792          while((second_iter.is_at_end()==FALSE)&&(changed==0))
1793          {
1794            changed=bin.reduce_head_by(second_iter.get_element(),w);
1795
1796            if(changed!=0)
1797              // bin has been reduced
1798            {
1799              if(bin!=0)
1800              {
1801                found=1;
1802                // found has only to be set if the binomial has not been
1803                // reduced to zero (else there are no new binomials)
1804
1805                aux_list._insert(bin);
1806                first_iter.extract_element();
1807              }
1808              else
1809                first_iter.delete_element();
1810            }
1811            second_iter.next();
1812          }
1813        }
1814
1815        // The list new_generators[i]
1816        // =new_generators[S.subsets_of_support[i][S.number_of_subsets[i]-1]]
1817        // has to be tested separately to avoid a reduction of the actual
1818        // binomial by itself.
1819
1820        if(changed==0)
1821          // binomial referenced by first_iter has not yet been reduced
1822        {
1823          second_iter.set_to_list(new_generators[i]);
1824
1825          while((second_iter.is_at_end()==FALSE) && (changed==0))
1826          {
1827            if(second_iter!=first_iter)
1828              // the two iterators do not reference the same element
1829              changed=bin.reduce_head_by(second_iter.get_element(),w);
1830
1831            if(changed!=0)
1832              // bin has been reduced
1833            {
1834
1835#ifdef SL_LIST
1836
1837              // bin will be deleted ar extracted - maybe dangerous for
1838              // second_iter
1839              if(first_iter.next_is(second_iter))
1840                second_iter.next();
1841
1842#endif  // SL_LIST
1843
1844              if(bin!=0)
1845              {
1846                found=1;
1847                aux_list._insert(bin);
1848                first_iter.extract_element();
1849              }
1850              else
1851                first_iter.delete_element();
1852            }
1853
1854            else
1855              // bin has not been reduced
1856              second_iter.next();
1857          }
1858        }
1859
1860      if(changed==0)
1861        first_iter.next();
1862      // Else first_iter has already been set to the next element by deletion
1863      // or extraction.
1864      }
1865
1866
1867//  Now try to reduce the binomials that are marked reduced.
1868
1869      while(first_iter.is_at_end()==FALSE)
1870        // only unreduced elements have to be tested for interreduction
1871      {
1872        binomial& bin=first_iter.get_element();
1873        Integer changed=0;
1874        // binomial referenced by bin not yet reduced
1875
1876// Look for head reductions:
1877// Iterate over the lists that could contain reducers for the head of bin.
1878// The list containing bin is tested separately to avoid an interreduction
1879// of a binomial by itself respectively unnecessary checks for this when the
1880// two iterators reference different lists.
1881
1882        for(int j=0;(j<S.number_of_subsets[i]-1)&&(changed==0);j++)
1883        {
1884          second_iter.set_to_list(new_generators[S.subsets_of_support[i][j]]);
1885          // This is the j-th list among the new_generators lists with elements
1886          // whose support is a subset of that of i.
1887          // The support of i is just the head support of bin (restricted
1888          // to the corresponding variables).
1889
1890          while((second_iter.element_is_marked_head_reduced()==FALSE) &&
1891                (changed==0))
1892          {
1893            changed=bin.reduce_head_by(second_iter.get_element(),w);
1894
1895            if(changed!=0)
1896              // bin has been reduced
1897            {
1898              if(bin!=0)
1899              {
1900                found=1;
1901                // found has only to be set if the binomial has not been
1902                // reduced to zero (else there are no new binomials)
1903                aux_list._insert(bin);
1904                first_iter.extract_element();
1905              }
1906              else
1907                first_iter.delete_element();
1908            }
1909            second_iter.next();
1910          }
1911        }
1912
1913        // The list new_generators[i]
1914        // =new_generators[S.subsets_of_support[i][S.number_of_subsets[i]-1]]
1915        // has to be tested separately to avoid a reduction of the actual
1916        // binomial by itself.
1917
1918        if(changed==0)
1919          // binomial referenced by first_iter has not yet been reduced
1920        {
1921          second_iter.set_to_list(new_generators[i]);
1922
1923          while((second_iter.element_is_marked_head_reduced()==FALSE) &&
1924                (changed==0))
1925          {
1926            if(second_iter!=first_iter)
1927              // the two iterators do not reference the same element
1928              changed=bin.reduce_head_by(second_iter.get_element(),w);
1929
1930            if(changed!=0)
1931              // bin has been reduced
1932            {
1933
1934#ifdef SL_LIST
1935
1936              // bin will be deleted ar extracted - maybe dangerous for
1937              // second_iter
1938              if(first_iter.next_is(second_iter))
1939                second_iter.next();
1940
1941#endif  // SL_LIST
1942
1943              if(bin!=0)
1944              {
1945                found=1;
1946                aux_list._insert(bin);
1947                first_iter.extract_element();
1948              }
1949              else
1950                first_iter.delete_element();
1951            }
1952
1953            else
1954              // bin has not been reduced
1955              second_iter.next();
1956          }
1957        }
1958
1959      if(changed==0)
1960        first_iter.next();
1961      // Else first_iter has already been set to the next element by deletion
1962      // or extraction.
1963      }
1964
1965    }
1966
1967
1968    // Now we have found all currently possible reductions.
1969    // The elements remaining in the new_generator lists cannot be interreduced
1970    // and are marked reduced.
1971
1972    for(int i=0;i<Number_of_Lists;i++)
1973    {
1974      first_iter.set_to_list(new_generators[i]);
1975      if(first_iter.is_at_end()==FALSE)
1976        while(first_iter.element_is_marked_head_reduced()==FALSE)
1977        {
1978          first_iter.mark_element_head_reduced();
1979          first_iter.next();
1980        }
1981    }
1982
1983
1984    // Now reinsert reduced elements
1985    // It seems to be quite unimportant for the performance if an element is
1986    // completely reduced before reinsertion or not.
1987
1988    first_iter.set_to_list(aux_list);
1989    while(first_iter.is_at_end()==FALSE)
1990    {
1991      binomial& bin=first_iter.get_element();
1992      reduce(bin,FALSE);
1993
1994      if(bin==0)
1995        first_iter.delete_element();
1996      else
1997      {
1998        add_new_generator(bin);
1999        first_iter.extract_element();
2000      }
2001    }
2002
2003  }
2004  while(found==1);
2005
2006  // When leaving the loop, no generators have been interreduced during
2007  // the last iteration; we are done.
2008
2009#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
2010
2011
2012  return(*this);
2013
2014}
2015
2016
2017
2018
2019
2020ideal& ideal::minimalize()
2021{
2022// For a better overview, the code for NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2023// and SUPPORT_DRIVEN_METHODS_EXTENDED is completetly separated in this
2024// function. Note that th iteration methods are quite different for those
2025// two possibilities.
2026
2027
2028#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2029
2030// For technical simplicity, the interreduction is done as follows:
2031// We iterate over the generators with two iterators.
2032// For each binomial pair, we examine if one binomialŽs head can be
2033// reduced by the other. If this is the case, the reducible binomial is
2034// reduced and moved to the aux_list if it is not 0, else deleted.
2035// After one iteration, the elements of the aux_list are reinserted;
2036// then the interreduction is restarted until no new elements are found.
2037
2038// The above method of deleting and inserting is chosen for the following
2039// reasons:
2040// - The order undone elements - done elements in the generator lists
2041//   is not destroyed. Newly found elements are automatically marked
2042//   undone when they are reinserted.
2043//   The S-pair computation can as usually make use of this fact.
2044// - In analogy, the order head_unreduced elements - head_reduced elements
2045//   is not destroyed. Remark that an undone element can never be reduced, as
2046//   reduction is only done after an S-pair computation. Newly found
2047//   elements are automatically marked unreduced. With the "head_reduced"-
2048//   flag we make sure that any binomial pair is tested only once for
2049//   interreduction during the whole algorithm.
2050
2051  list_iterator first_iter;
2052  int found;
2053  // to control if a reduction has occurred during the actual iteration
2054
2055  do
2056  {
2057    first_iter.set_to_list(generators);
2058    found=0;
2059    // no reduction occured yet
2060
2061    while(first_iter.element_is_marked_head_reduced()==FALSE)
2062      // only the first element is tested for this flag
2063      // the second may be an old one
2064    {
2065      binomial& bin1=first_iter.get_element();
2066      int first_changed=0;
2067      // to control if the first element has been reduced
2068
2069      // look at all following binomials
2070      list_iterator second_iter(first_iter);
2071      second_iter.next();
2072      // this may be the dummy element
2073
2074      while(second_iter.is_at_end()==FALSE)
2075      {
2076        binomial& bin2=second_iter.get_element();
2077
2078        if(bin1.reduce_head_by(bin2,w)!=0)
2079          // head of first binomial can be reduced by second
2080        {
2081
2082#ifdef SL_LIST
2083
2084          // The binomial referenced by first_iter will be deleted or
2085          // extracted. When using a simply linked list, this also affects
2086          // the following element. We need to assure that this element does
2087          // not reference freed memory.
2088          if(first_iter.next_is(second_iter))
2089              second_iter.next();
2090
2091#endif  // SL_LIST
2092
2093          if(bin1!=0)
2094          {
2095            found=1;
2096            // found has not to be set if a binomial is reduced to zero
2097            // (then there are no new binomials to insert)
2098
2099            aux_list._insert(bin1);
2100            first_iter.extract_element();
2101            // moved changed binomial to aux_list
2102          }
2103
2104          else
2105            first_iter.delete_element();
2106
2107
2108          first_changed=1;
2109          size--;
2110          break;
2111          // As the binomial referenced by first_iter has changed,
2112          // the iteration with the second iterator can be restarted.
2113          // (We try to reduce as many elements as possible in one iteration.)
2114        }
2115
2116
2117        if(bin2.reduce_head_by(bin1,w)!=0)
2118           // head of second binomial can be reduced by first
2119        {
2120          // Here we do not have to pay attention to the deletion or the
2121          // extraction of the element referenced by second_iter because
2122          // the element referenced by second_iter always comes after the
2123          // element referenced by first_iter in the generator list.
2124
2125          if(bin2!=0)
2126          {
2127            found=1;
2128            // found has not to be set if a binomial is reduced to zero
2129            // (then there are no new binomials to insert)
2130
2131            aux_list._insert(bin2);
2132            second_iter.extract_element();
2133            // move the element referenced by second_iter to aux_list
2134          }
2135
2136          else
2137            second_iter.delete_element();
2138
2139          size--;
2140          // Here it makes not sense to restart iteration because the
2141          // deletion sets the pointers as desired.
2142        }
2143
2144        else
2145          // no reduction possible
2146          second_iter.next();
2147
2148      }
2149
2150      // Now second_iter has reached the end of the generator list or the
2151      // binomial referenced first_iter has been reduced...The iteration
2152      // is continued with a new (or changed) first binomial.
2153
2154      if(first_changed==0)
2155        first_iter.next();
2156    }
2157
2158
2159    // Now we have found all currently possible reductions.
2160    // The elements remaining in the generator list cannot be interreduced
2161    // and are marked head_reduced.
2162
2163    first_iter.set_to_list(generators);
2164    //   if(first_iter.is_at_end()==FALSE)
2165      while(first_iter.element_is_marked_head_reduced()==FALSE)
2166      {
2167        first_iter.mark_element_head_reduced();
2168        first_iter.next();
2169      }
2170
2171
2172    // Now reinsert reduced elements.
2173
2174    first_iter.set_to_list(aux_list);
2175
2176    while(first_iter.is_at_end()==FALSE)
2177    {
2178      binomial& bin=first_iter.get_element();
2179
2180      reduce(bin,FALSE);
2181      // The binomial was only reduced by one other generator before it was
2182      // moved to aux_list. To reduce it by all other generators now can
2183      // diminish the number of iterations (do-while-loop).
2184
2185      if(bin==0)
2186        first_iter.delete_element();
2187      else
2188      {
2189        generators.insert(bin);
2190        // We do not call the add_generator(...)-routine because we do not
2191        // want number_of_new_binomials to be incremented.
2192        size++;
2193        first_iter.extract_element();
2194      }
2195
2196    }
2197
2198  }
2199  while(found==1);
2200
2201  // When leaving the loop, no generators have been interreduced during
2202  // the last iteration; we are done.
2203
2204#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2205
2206
2207#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
2208
2209// In this case, the reduction has to be organized in a different way to
2210// use the support information to its full extend. Without the support
2211// methods, we test interreduction symmetrically: if we have a pair of
2212// generators, we test if generator 1 can be reduced by generator 2 AND
2213// if generator 2 can be reduced by generator 1. So each unordered pair is
2214// considered only once.
2215// If we would implement the same for the support methods, the second head
2216// reduction could not use the support information.
2217// For this reason, we test ordered pairs: For a given generator, we
2218// try to reduce his head by all other generators, considering its head
2219// support vector.
2220
2221// The method of moving changed binomials to aux_list and later reinserting
2222// them is kept. When using SUPPORT_DRIVEN_METHODS_EXTENDED, it is even
2223// necessary to choose such a method because the head support of some
2224// binomials may change, too, a fact that requires the list structure to be
2225// rebuilt.
2226
2227  list_iterator first_iter;
2228  list_iterator second_iter;
2229  int found;
2230  // to control if a reduction has occurred during the actual iteration
2231
2232  do
2233  {
2234    found=0;
2235    // no reduction occurred yet
2236
2237    for(int i=0;i<Number_of_Lists;i++)
2238    {
2239      first_iter.set_to_list(generators[i]);
2240
2241// First try to reduce the binomials that are marked unreduced.
2242
2243      while(first_iter.element_is_marked_head_reduced()==FALSE)
2244        // all other elements have to be tested for interreduction
2245      {
2246
2247        binomial& bin=first_iter.get_element();
2248        Integer changed=0;
2249        // binomial referenced by bin not yet reduced
2250
2251// Look for head reductions:
2252// Iterate over the lists that could contain reducers for the head of bin.
2253// The list containing bin is tested separately to avoid an interreduction
2254// of a binomial by itself respectively unnecessary checks for this when the
2255// two iterators reference different lists.
2256
2257        for(int j=0;(j<S.number_of_subsets[i]-1)&&(changed==0);j++)
2258        {
2259          second_iter.set_to_list(generators[S.subsets_of_support[i][j]]);
2260          // This is the j-th list among the generator lists with elements
2261          // whose support is a subset of that of i.
2262          // The support of i is just the head support of bin (restricted
2263          // to the corresponding variables).
2264
2265          while((second_iter.is_at_end()==FALSE)&&(changed==0))
2266          {
2267            changed=bin.reduce_head_by(second_iter.get_element(),w);
2268
2269            if(changed!=0)
2270              // bin has been reduced
2271            {
2272              if(bin!=0)
2273              {
2274                found=1;
2275                // found has only to be set if the binomial has not been
2276                // reduced to zero (else there are no new binomials)
2277
2278                aux_list._insert(bin);
2279                first_iter.extract_element();
2280              }
2281              else
2282                first_iter.delete_element();
2283
2284              size--;
2285            }
2286            second_iter.next();
2287          }
2288        }
2289
2290        // The list generators[i]
2291        // =generators[S.subsets_of_support[i][S.number_of_subsets[i]-1]]
2292        // has to be tested separately to avoid a reduction of the actual
2293        // binomial by itself.
2294
2295        if(changed==0)
2296          // binomial referenced by first_iter has not yet been reduced
2297        {
2298          second_iter.set_to_list(generators[i]);
2299
2300          while((second_iter.is_at_end()==FALSE) && (changed==0))
2301          {
2302            if(second_iter!=first_iter)
2303              // the two iterators do not reference the same element
2304              changed=bin.reduce_head_by(second_iter.get_element(),w);
2305
2306            if(changed!=0)
2307              // bin has been reduced
2308            {
2309
2310#ifdef SL_LIST
2311
2312              // bin will be deleted ar extracted - maybe dangerous for
2313              // second_iter
2314              if(first_iter.next_is(second_iter))
2315                second_iter.next();
2316
2317#endif  // SL_LIST
2318
2319              if(bin!=0)
2320              {
2321                found=1;
2322                aux_list._insert(bin);
2323                first_iter.extract_element();
2324              }
2325              else
2326                first_iter.delete_element();
2327
2328              size--;
2329            }
2330
2331            else
2332              // bin has not been reduced
2333              second_iter.next();
2334          }
2335        }
2336
2337      if(changed==0)
2338        first_iter.next();
2339      // Else first_iter has already been set to the next element by deletion
2340      // or extraction.
2341      }
2342
2343
2344//  Now try to reduce the binomials that are marked reduced.
2345
2346      while(first_iter.is_at_end()==FALSE)
2347        // only unreduced elements have to be tested for interreduction
2348      {
2349        binomial& bin=first_iter.get_element();
2350        Integer changed=0;
2351        // binomial referenced by bin not yet reduced
2352
2353// Look for head reductions:
2354// Iterate over the lists that could contain reducers for the head of bin.
2355// The list containing bin is tested separately to avoid an interreduction
2356// of a binomial by itself respectively unnecessary checks for this when the
2357// two iterators reference different lists.
2358
2359        for(int j=0;(j<S.number_of_subsets[i]-1)&&(changed==0);j++)
2360        {
2361          second_iter.set_to_list(generators[S.subsets_of_support[i][j]]);
2362          // This is the j-th list among the generator lists with elements
2363          // whose support is a subset of that of i.
2364          // The support of i is just the head support of bin (restricted
2365          // to the corresponding variables).
2366
2367          while((second_iter.element_is_marked_head_reduced()==FALSE) &&
2368                (changed==0))
2369          {
2370            changed=bin.reduce_head_by(second_iter.get_element(),w);
2371
2372            if(changed!=0)
2373              // bin has been reduced
2374            {
2375              if(bin!=0)
2376              {
2377                found=1;
2378                // found has only to be set if the binomial has not been
2379                // reduced to zero (else there are no new binomials)
2380                aux_list._insert(bin);
2381                first_iter.extract_element();
2382              }
2383              else
2384                first_iter.delete_element();
2385
2386              size--;
2387            }
2388            second_iter.next();
2389          }
2390        }
2391
2392        // The list generators[i]
2393        // =generators[S.subsets_of_support[i][S.number_of_subsets[i]-1]]
2394        // has to be tested separately to avoid a reduction of the actual
2395        // binomial by itself.
2396
2397        if(changed==0)
2398          // binomial referenced by first_iter has not yet been reduced
2399        {
2400          second_iter.set_to_list(generators[i]);
2401
2402          while((second_iter.element_is_marked_head_reduced()==FALSE) &&
2403                (changed==0))
2404          {
2405            if(second_iter!=first_iter)
2406              // the two iterators do not reference the same element
2407              changed=bin.reduce_head_by(second_iter.get_element(),w);
2408
2409            if(changed!=0)
2410              // bin has been reduced
2411            {
2412
2413#ifdef SL_LIST
2414
2415              // bin will be deleted ar extracted - maybe dangerous for
2416              // second_iter
2417              if(first_iter.next_is(second_iter))
2418                second_iter.next();
2419
2420#endif  // SL_LIST
2421
2422              if(bin!=0)
2423              {
2424                found=1;
2425                aux_list._insert(bin);
2426                first_iter.extract_element();
2427              }
2428              else
2429                first_iter.delete_element();
2430
2431              size--;
2432            }
2433
2434            else
2435              // bin has not been reduced
2436              second_iter.next();
2437          }
2438        }
2439
2440      if(changed==0)
2441        first_iter.next();
2442      // Else first_iter has already been set to the next element by deletion
2443      // or extraction.
2444      }
2445
2446    }
2447
2448
2449    // Now we have found all currently possible reductions.
2450    // The elements remaining in the generator lists cannot be interreduced
2451    // and are marked reduced.
2452
2453    for(int i=0;i<Number_of_Lists;i++)
2454    {
2455      first_iter.set_to_list(generators[i]);
2456      if(first_iter.is_at_end()==FALSE)
2457        while(first_iter.element_is_marked_head_reduced()==FALSE)
2458        {
2459          first_iter.mark_element_head_reduced();
2460          first_iter.next();
2461        }
2462    }
2463
2464
2465    // Now reinsert reduced elements
2466    // It seems to be quite unimportant for the performance if an element is
2467    // completely reduced before reinsertion or not.
2468
2469    first_iter.set_to_list(aux_list);
2470    while(first_iter.is_at_end()==FALSE)
2471    {
2472      binomial& bin=first_iter.get_element();
2473      reduce(bin,FALSE);
2474
2475      if(bin==0)
2476        first_iter.delete_element();
2477      else
2478      {
2479        generators[bin.head_support%Number_of_Lists].insert(bin);
2480        size++;
2481        // We do not call the add_generator(...)-routine because we do not
2482        // want number_of_new_binomials to be incremented.
2483        first_iter.extract_element();
2484      }
2485    }
2486
2487  }
2488  while(found==1);
2489
2490  // When leaving the loop, no generators have been interreduced during
2491  // the last iteration; we are done.
2492
2493#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
2494
2495
2496  return(*this);
2497}
2498
2499
2500
2501
2502
2503ideal& ideal::final_reduce()
2504{
2505// During BuchbergerŽs algorithm, we perform only head reductions
2506// (minimalizations). This strategy showed to be a little more efficient
2507// than the strategy to do reduce the ideal always completely.
2508// This method leads to a minimal, but in general not to the reduced Groebner
2509// basis. The actual procedure reduces such a minimal basis at the end of
2510// BuchbergerŽs algorithm. It will probably cause problems when called
2511// in the course of the algorithm. For an explaination of this fact, see
2512// the following comment.
2513
2514  minimalize();
2515
2516// Now there remain only tail reductions. They are quite simple: Each
2517// binomial's tail is reduced as long as possible. As no binomial can be
2518// reduced to zero by that and a binomial cannot reduce its own tail,
2519// we do not have to pay special attention to that (under the assumption
2520// that a real term ordering (i.e. a well-ordering) is used and that
2521// the head and the tail of the binomial are coorect with respect to this
2522// ordering).
2523
2524// Notice that the head can change because of a tail reduction due to the
2525// trivial factors elimination (the new head will always divide the
2526// old one). This change is especially dangerous if
2527// SUPPORT_DRIVEN_METHODS_EXTENDED are enabled: It may happen that the
2528// binomial is in the wrong list after a tail reduction.
2529// Furthermore, if a head change occurs, it may happen that the generating
2530// set is no more minimalized after this. So the reduction has to be restarted
2531// after such a head change (and the respective binomial has to be marked
2532// head_unreduced before).
2533// This does not seem to be very efficient.
2534
2535// For this reason, the reduction routine is only written for a final
2536// reduction (having already computed a Groebner basis of the ideal).
2537// This Groebner basis is first minimalized. After that, a head change during
2538// tail reduction is impossible because the head is already a minimal
2539// generator of the initial ideal (and the new head would divide the old).
2540
2541// However, this argumentation is only valid if the input ideal is saturated.
2542// In some algorithms (Hosten_Sturmfels...) this is not the case in
2543// intermediate steps. The final reduction may cause inconsistencies here.
2544// But as the list structure is rebuild after each intermediate Groebner
2545// basis calculation (change of the term ordering) and as the last Groebner
2546// basis calculation deals with a saturated ideal, the final result will be
2547// correct.
2548// (For non-saturated input ideals, the computed Groebner basis is in general
2549// not a Groebner basis of the input ideal, but one for an ideal "between"
2550// the input ideal and its saturation.)
2551
2552
2553#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2554
2555  list_iterator first_iter;
2556
2557  first_iter.set_to_list(generators);
2558
2559  while(first_iter.is_at_end()==FALSE)
2560  {
2561    binomial& bin=first_iter.get_element();
2562    int changed;
2563    // to control if bin has been reduced
2564
2565    do
2566    {
2567      changed=0;
2568      list_iterator second_iter;
2569      second_iter.set_to_list(generators);
2570
2571      while(second_iter.is_at_end()==FALSE)
2572      {
2573        changed+=bin.reduce_tail_by(second_iter.get_element(),w);
2574        // As soon as a reduction occurs, changed is set to a value !=0.
2575        second_iter.next();
2576      }
2577
2578    }
2579    while(changed>0);
2580
2581    first_iter.next();
2582  }
2583
2584#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2585
2586
2587#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
2588
2589// In this case, the reduction has to be organized in a slightly different
2590// way to use the support information to its full extend.
2591// As soon as an reduction has taken place, the iteration over the reducer
2592// lists is restarted using the new tail support information.
2593
2594  list_iterator first_iter;
2595
2596  for(int i=0;i<Number_of_Lists;i++)
2597  {
2598    first_iter.set_to_list(generators[i]);
2599
2600    while(first_iter.is_at_end()==FALSE)
2601    {
2602      binomial& bin=first_iter.get_element();
2603      int changed;
2604      // to control if bin has been reduced
2605
2606      do
2607      {
2608        changed=0;
2609        list_iterator second_iter;
2610
2611        int supp=bin.tail_support%Number_of_Lists;
2612        // determine the lists over which we have to iterate
2613
2614        for(int j=0;(j<S.number_of_subsets[supp]) && (changed==0);j++)
2615        {
2616          second_iter.set_to_list(generators[S.subsets_of_support[supp][j]]);
2617          // This is the j-th list among the generator lists with elements
2618          // whose support is a subset of supp.
2619
2620          while((second_iter.is_at_end()==FALSE) && (changed==0))
2621          {
2622            changed=bin.reduce_tail_by(second_iter.get_element(),w);
2623            // Here we can do a simple assignment; as the iteration is stopped
2624            // as soon as some reduction is done, reduced cannot be reset to
2625            // zero in this assignment.
2626            second_iter.next();
2627          }
2628        }
2629
2630      }
2631      while(changed>0);
2632
2633      first_iter.next();
2634    }
2635  }
2636
2637#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
2638
2639  return(*this);
2640}
2641
2642
2643
2644
2645
2646//////////////////////////////////////////////////////////////////////////////
2647////////////////////// auxiliary stuff ///////////////////////////////////////
2648//////////////////////////////////////////////////////////////////////////////
2649
2650
2651
2652
2653
2654int ideal::add_new_generators()
2655{
2656// Reduces the binomials in the "new_generators" list(s) by the generators
2657// and moves them to the "generators" list(s).
2658
2659
2660#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2661
2662  int result=0;
2663  // element inserted?
2664
2665  list_iterator iter(new_generators);
2666
2667  while(iter.is_at_end()==FALSE)
2668  {
2669    binomial& bin=iter.get_element();
2670    reduce(bin,FALSE);
2671
2672    if(bin==0)
2673      iter.delete_element();
2674    else
2675    {
2676      add_generator(bin);
2677      iter.extract_element();
2678      result=1;
2679    }
2680  }
2681
2682
2683#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2684
2685
2686#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
2687
2688  int result=0;
2689  // element inserted?
2690
2691  list_iterator iter;
2692
2693  for(int i=0;i<Number_of_Lists;i++)
2694  {
2695    iter.set_to_list(new_generators[i]);
2696
2697    while(iter.is_at_end()==FALSE)
2698    {
2699      binomial& bin=iter.get_element();
2700      reduce(bin,FALSE);
2701
2702      if(bin==0)
2703        iter.delete_element();
2704      else
2705      {
2706        add_generator(bin);
2707        iter.extract_element();
2708        result=1;
2709      }
2710    }
2711  }
2712
2713
2714#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
2715
2716
2717  return result;
2718}
2719
2720
2721
2722
2723
2724/////////////////////////////////////////////////////////////////////////////
2725///////////////////// binomial reduction ////////////////////////////////////
2726/////////////////////////////////////////////////////////////////////////////
2727
2728
2729
2730
2731
2732binomial& ideal::reduce(binomial& bin, BOOLEAN complete) const
2733{
2734// As bin is reduced by a fixed set of binomials, it is sufficient to do
2735// head reductions first, then tail reductions (cf. Pottier).
2736
2737  list_iterator iter;
2738  Integer reduced;
2739  // to control if the binomial has been reduced during the actual iteration
2740
2741
2742#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2743
2744  do
2745  {
2746    iter.set_to_list(generators);
2747    reduced=0;
2748    // not yet reduced
2749
2750    while(iter.is_at_end()==FALSE)
2751    {
2752      reduced+=bin.reduce_head_by(iter.get_element(),w);
2753      // reduced is incremented (and so set to a value >0) as soon as bin
2754      // is really reduced
2755      iter.next();
2756    }
2757  }
2758  while((reduced>0) && (bin!=0));
2759
2760  if(complete==TRUE)
2761    do
2762    {
2763      iter.set_to_list(generators);
2764      reduced=0;
2765      // not yet reduced
2766
2767      while(iter.is_at_end()==FALSE)
2768      {
2769        reduced+=bin.reduce_tail_by(iter.get_element(),w);
2770        // reduced is incremented (and so set to a value >0) as soon as bin
2771        // is really reduced
2772        iter.next();
2773      }
2774    }
2775    while((reduced>0) && (bin!=0));
2776
2777#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
2778
2779
2780#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
2781
2782  do
2783  {
2784    reduced=0;
2785    // not yet reduced
2786
2787    int supp=bin.head_support%Number_of_Lists;
2788    // determine the lists over which we have to iterate
2789
2790    // As soon as some reduction is done, the iteration is started with
2791    // the new support information; so we do not finish iterations over lists
2792    // that cannot contain reducers any more.
2793
2794    for(int i=0;(i<S.number_of_subsets[supp]) && (reduced==0);i++)
2795    {
2796      iter.set_to_list(generators[S.subsets_of_support[supp][i]]);
2797      // This is the i-th list among the generator lists with elements
2798      // whose support is a subset of that of supp.
2799
2800      while((iter.is_at_end()==FALSE)&&(reduced==0))
2801      {
2802        reduced=bin.reduce_head_by(iter.get_element(),w);
2803        // Here we can do a simple assignment; as the iteration is stopped
2804        // as soon as some reduction is done, reduced cannot be reset to zero
2805        // in this assignment.
2806        iter.next();
2807      }
2808    }
2809  }
2810  while((reduced>0) && (bin!=0));
2811
2812  if(complete==TRUE)
2813    do
2814    {
2815      reduced=0;
2816      // not yet reduced
2817
2818      int supp=bin.tail_support%Number_of_Lists;
2819      // determine the lists over which we have to iterate
2820
2821      // As soon as some reduction is done, the iteration is started with
2822      // the new support information; so we do not finish iterations over
2823      // lists that cannot contain reducers any more.
2824
2825      for(int i=0;(i<S.number_of_subsets[supp]) && (reduced==0);i++)
2826      {
2827        iter.set_to_list(generators[S.subsets_of_support[supp][i]]);
2828        // This is the i-th list among the generator lists with elements
2829        // whose support is a subset of that of supp.
2830
2831        while((iter.is_at_end()==FALSE)&&(reduced==0))
2832        {
2833          reduced=bin.reduce_tail_by(iter.get_element(),w);
2834          // Here we can do a simple assignment; as the iteration is stopped
2835          // as soon as some reduction is done, reduced cannot be reset to
2836          // zero in this assignment
2837        iter.next();
2838      }
2839    }
2840  }
2841  while(reduced>0);
2842  // bin cannot be reduced to zero by a tail reduction
2843
2844#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
2845
2846  return(bin);
2847}
2848
2849
2850
2851
2852
2853//////////////////////////////////////////////////////////////////////////////
2854/////////// variants of BuchbergerŽs algorithm ///////////////////////////////
2855//////////////////////////////////////////////////////////////////////////////
2856
2857
2858
2859
2860
2861ideal& ideal::reduced_Groebner_basis_1(const int& S_pair_criteria,
2862                                       const float& interred_percentage)
2863{
2864  // set flags for the use of the S-pair criteria
2865  // for an explaination see in globals.h
2866  rel_primeness=(S_pair_criteria & 1);
2867  M_criterion=(S_pair_criteria & 2);
2868  F_criterion=(S_pair_criteria & 4);
2869  B_criterion=(S_pair_criteria & 8);
2870  second_criterion=(S_pair_criteria & 16);
2871
2872  interreduction_percentage=interred_percentage;
2873
2874  int done;
2875  // control variable for recognizing when Buchberger's algorithm has reached
2876  // his end
2877
2878  // first minimalize the initial generating system
2879  minimalize();
2880
2881  do
2882  {
2883    done=1;
2884    // no new generators found yet
2885
2886    compute_actual_S_pairs_1();
2887    // compute the S-pairs of the actual generators
2888    // These are stored in a unreduced form in aux_list.
2889
2890    list_iterator S_pair_iter(aux_list);
2891    // now reduce and insert the computed S-pairs
2892
2893    while(S_pair_iter.is_at_end()==FALSE)
2894    {
2895      binomial& S_bin=S_pair_iter.get_element();
2896      reduce(S_bin,FALSE);
2897
2898      if(S_bin!=0)
2899        // new generator found
2900      {
2901        add_generator(S_bin);
2902        S_pair_iter.extract_element();
2903        done=0;
2904        // algorithm does not terminate when a new generator is found
2905      }
2906      else
2907        S_pair_iter.delete_element();
2908    }
2909
2910    // now all computed S-pairs are inserted as generators
2911    // enough for a minimalization?
2912
2913    if(interreduction_percentage>=0)
2914      // intermediate interreductions allowed
2915    {
2916      if(number_of_new_binomials>=size*interreduction_percentage/100)
2917        // enough new generators since last minimalization
2918      {
2919        minimalize();
2920        number_of_new_binomials=0;
2921      }
2922    }
2923
2924    // now we restart the algorithm with the new generating system
2925    // if the generating system has changed during the last iteration
2926
2927  }
2928  while(done==0);
2929  // if done==1, all computed S-pairs reduced to zero
2930
2931  // compute reduced from minimal Groebner basis
2932  final_reduce();
2933
2934  return(*this);
2935}
2936
2937
2938
2939
2940
2941
2942ideal& ideal::reduced_Groebner_basis_1a(const int& S_pair_criteria,
2943                                        const float& interred_percentage)
2944{
2945  // set flags for the use of the S-pair criteria
2946  // for an explaination see in globals.h
2947  rel_primeness=(S_pair_criteria & 1);
2948  M_criterion=(S_pair_criteria & 2);
2949  F_criterion=(S_pair_criteria & 4);
2950  B_criterion=(S_pair_criteria & 8);
2951  second_criterion=(S_pair_criteria & 16);
2952
2953  interreduction_percentage=interred_percentage;
2954
2955  int done;
2956  // control variable for recognizing when Buchberger's algorithm has reached
2957  // his end
2958
2959  // first minimalize the initial generating system
2960  minimalize();
2961
2962  do
2963  {
2964    done=1;
2965    // no new generators found yet
2966
2967    compute_actual_S_pairs_1a();
2968    // compute the S-pairs of the actual generators
2969    // These are stored in a unreduced form in aux_list.
2970    // aux_list is ordered according to the idealŽs term ordering.
2971
2972    list_iterator S_pair_iter(aux_list);
2973    // now reduce and insert the computed S-pairs
2974
2975    while(S_pair_iter.is_at_end()==FALSE)
2976    {
2977      binomial& S_bin=S_pair_iter.get_element();
2978      reduce(S_bin,FALSE);
2979
2980      if(S_pair_iter.get_element()!=0)
2981        // new generator found
2982      {
2983        add_generator(S_bin);
2984        S_pair_iter.extract_element();
2985        done=0;
2986        // algorithm does not terminate when a new generator is found
2987      }
2988      else
2989        S_pair_iter.delete_element();
2990    }
2991
2992    // now all computed S-pairs are inserted as generators
2993    // enough for a minimalization?
2994
2995    if(interreduction_percentage>=0)
2996      // intermediate interreductions allowed
2997    {
2998      if(number_of_new_binomials>=size*interreduction_percentage/100)
2999        // enough new generators since last minimalization
3000      {
3001        minimalize();
3002        number_of_new_binomials=0;
3003      }
3004    }
3005
3006    // now we restart the algorithm with the new generating system
3007    // if the generating system has changed during the last iteration
3008
3009  }
3010  while(done==0);
3011  // if done==1, all computed S-pairs reduced to zero
3012
3013  // compute reduced from minimal Groebner basis
3014  final_reduce();
3015
3016  return(*this);
3017}
3018
3019
3020
3021
3022
3023ideal& ideal::reduced_Groebner_basis_2(const int& S_pair_criteria,
3024                                       const float& interred_percentage)
3025{
3026  // set flags for the use of the S-pair criteria
3027  // for an explaination see in globals.h
3028  rel_primeness=(S_pair_criteria & 1);
3029  M_criterion=(S_pair_criteria & 2);
3030  F_criterion=(S_pair_criteria & 4);
3031  B_criterion=(S_pair_criteria & 8);
3032  second_criterion=(S_pair_criteria & 16);
3033
3034  interreduction_percentage=interred_percentage;
3035
3036  int done;
3037  // control variable for recognizing when Buchberger's algorithm has reached
3038  // his end
3039
3040  // first minimalize the initial generating system
3041  minimalize();
3042
3043  do
3044  {
3045    done=1;
3046    // no new generators found yet
3047
3048    compute_actual_S_pairs_2();
3049    // compute the S-pairs of the actual generators
3050    // These are stored in a reduced version in aux_list.
3051
3052    minimalize_S_pairs();
3053    // minimalize the binomials in aux_list
3054    // These are not only S-pairs, but also ideal generators that were
3055    // reduced by an S-pair during the S-pair computation.
3056
3057    list_iterator S_pair_iter(aux_list);
3058
3059    if(S_pair_iter.is_at_end()==FALSE)
3060      // Zero binomials are not inserted in aux_list during the S-pair
3061      // computation; i.e. if aux_list is not empty, a further iteration step
3062      // has to be done.
3063      done=0;
3064
3065    // now insert the computed S-pairs
3066    while(S_pair_iter.is_at_end()==FALSE)
3067      // S_pairs remaining
3068    {
3069      add_generator(S_pair_iter.get_element());
3070      S_pair_iter.extract_element();
3071    }
3072
3073    // now all computed S-pairs are inserted as generators
3074    // enough for a minimalization?
3075
3076    if(interreduction_percentage>=0)
3077      // intermediate interreductions allowed
3078    {
3079      if(number_of_new_binomials>=size*interreduction_percentage/100)
3080        // enough new generators since last minimalization
3081      {
3082        minimalize();
3083        number_of_new_binomials=0;
3084      }
3085    }
3086
3087    // now we restart the algorithm with the new generating system
3088    // if the generating system has changed during the last iteration
3089
3090  }
3091  while(done==0);
3092  // if done==1, all computed S-pairs reduced to zero
3093
3094  // compute reduced from minimal Groebner basis
3095  final_reduce();
3096
3097  return(*this);
3098}
3099
3100
3101
3102
3103
3104ideal& ideal::reduced_Groebner_basis_3(const int& S_pair_criteria,
3105                                       const float& interred_percentage)
3106{
3107  // set flags for the use of the S-pair criteria
3108  // for an explaination see in globals.h
3109  rel_primeness=(S_pair_criteria & 1);
3110  M_criterion=(S_pair_criteria & 2);
3111  F_criterion=(S_pair_criteria & 4);
3112  B_criterion=(S_pair_criteria & 8);
3113  second_criterion=(S_pair_criteria & 16);
3114
3115  interreduction_percentage=interred_percentage;
3116
3117  int not_done;
3118  // control variable for recognizing when Buchberger's algorithm has reached
3119  // his end
3120
3121  // first minimalize the initial generating system
3122  minimalize();
3123
3124  do
3125  {
3126
3127    compute_actual_S_pairs_3();
3128    // compute the S-pairs of the actual generators
3129    // These are stored in areduced version in the list(s) new_generators.
3130
3131    minimalize_new_generators();
3132    // minimalize the binomials in aux_list
3133    // These are not only S-pairs, but also ideal generators that were
3134    // reduced by an S-pair during the S-pair computation.
3135
3136    not_done=add_new_generators();
3137    // move binomials from new_generators to generators
3138
3139    // now all computed S-pairs are inserted as generators
3140    // enough for a minimalization?
3141
3142    if(interreduction_percentage>=0)
3143      // intermediate interreductions allowed
3144    {
3145      if(number_of_new_binomials>=size*interreduction_percentage/100)
3146        // enough new generators since last reduction
3147      {
3148        minimalize();
3149        number_of_new_binomials=0;
3150      }
3151    }
3152
3153    // now we restart the algorithm with the new generating system
3154    // if the generating system has changed during the last iteration
3155
3156  }
3157  while(not_done==1);
3158  // if not_done==0, all computed S-pairs reduced to zero
3159
3160  // compute reduced from minimal Groebner basis
3161  final_reduce();
3162
3163  return(*this);
3164}
3165
3166
3167
3168
3169
3170ideal& ideal::reduced_Groebner_basis(const int& version,
3171                                     const int& S_pair_criteria,
3172                                     const float& interred_percentage)
3173{
3174  switch(version)
3175  {
3176      case 0:
3177        return reduced_Groebner_basis_1a(S_pair_criteria, interred_percentage);
3178      case 1:
3179        return reduced_Groebner_basis_1(S_pair_criteria, interred_percentage);
3180      case 2:
3181        return reduced_Groebner_basis_2(S_pair_criteria, interred_percentage);
3182      case 3:
3183        return reduced_Groebner_basis_3(S_pair_criteria, interred_percentage);
3184      default:
3185        cerr<<"WARNING: ideal& ideal::reduced_Groebner_basis(const int&, "
3186          "const int&, const float&):\n"
3187          "version argument out of range, nothing done"<<endl;
3188        return*this;
3189  }
3190}
3191
3192
3193
3194
3195
3196#endif  // BUCHBERGER_CC
Note: See TracBrowser for help on using the repository browser.