f5gb.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: f5gb interface
6 */
7 
8 
9 
10 
11 #include <kernel/mod2.h>
12 #ifdef HAVE_F5
13 #include <unistd.h>
14 #include <omp.h>
15 #include <kernel/structs.h>
16 #include <kernel/GBEngine/kutil.h>
17 #include <omalloc/omalloc.h>
18 #include <kernel/polys.h>
21 #include <kernel/ideals.h>
22 #include <kernel/GBEngine/kstd1.h>
23 #include <kernel/GBEngine/khstd.h>
24 #include <polys/kbuckets.h>
25 #include <polys/weight.h>
26 #include <misc/intvec.h>
27 #include <kernel/polys.h>
28 #include <kernel/GBEngine/f5gb.h>
29 #include <kernel/GBEngine/f5data.h>
31 #include <kernel/oswrapper/timer.h>
32 
33 #define pDeg(A) p_Deg(A,currRing)
34 
35 int notInG = 0;
36 int numberOfRules = 0;
38 int reductionTime = 0;
39 int spolsTime = 0;
40 int highestDegree = 0;
41 int degreeBound = 0;
49 /*
50 ====================================================================
51 sorting ideals by decreasing total degree "left" and "right" are the
52 pointer of the first and last polynomial in the considered ideal
53 ====================================================================
54 */
55 void qsortDegree(poly* left, poly* right)
56 {
57  poly* ptr1 = left;
58  poly* ptr2 = right;
59  poly p1,p2;
60  p2 = *(left + (right - left >> 1));
61  do
62  {
63  while(p_Totaldegree(*ptr1, currRing) < p_Totaldegree(p2, currRing))
64  {
65  ptr1++;
66  }
67  while(p_Totaldegree(*ptr2, currRing) > p_Totaldegree(p2,currRing))
68  {
69  ptr2--;
70  }
71  if(ptr1 > ptr2)
72  {
73  break;
74  }
75  p1 = *ptr1;
76  *ptr1 = *ptr2;
77  *ptr2 = p1;
78  } while(++ptr1 <= --ptr2);
79 
80  if(left < ptr2)
81  {
82  qsortDegree(left,ptr2);
83  }
84  if(ptr1 < right)
85  {
86  qsortDegree(ptr1,right);
87  }
88 }
89 
90 /*!
91  * ======================================================================
92  * builds the sum of the entries of the exponent vectors, i.e. the degree
93  * of the corresponding monomial
94  * ======================================================================
95 */
96 long sumVector(int* v, int k) {
97  int i;
98  long sum = 0;
99  for(i=1; i<=k; i++) {
100  Print("%d\n",v[i]);
101  Print("%ld\n",sum);
102  sum = sum + v[i];
103  }
104  return sum;
105 }
106 
107 /*!
108 ==========================================================================
109 compares monomials, i.e. divisibility tests for criterion 1 and criterion 2
110 ==========================================================================
111 */
112 bool compareMonomials(int* m1, int** m2, int numberOfRules, int k) {
113  int i,j;
114  long sumM1 = sumVector(m1,k);
115  //int k = sizeof(m1) / sizeof(int);
116  for(i=0; i<numberOfRules; i++) {
117  if(sumVector(m2[i],k) <= sumM1) {
118  for(j=1; j<=k; j++) {
119  if(m1[j]>m2[i][j]) {
120  return true;
121  }
122  }
123  }
124  }
125  return false;
126 }
127 
128 /*
129 ==================================================
130 computes incrementally gbs of subsets of the input
131 gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
132 ==================================================
133 */
134 LList* F5inc(int i, poly f_i, LList* gPrev, LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus, int termination) {
135  //Print("in f5inc\n");
136  //pWrite(rules->getFirst()->getRuleTerm());
137  int iterationstep = i;
138  int j;
139  //Print("%p\n",gPrev->getFirst());
140  //pWrite(gPrev->getFirst()->getPoly());
141  poly tempNF = kNF(gbPrev,currRing->qideal,f_i);
142  f_i = tempNF;
143  //gPrev->insert(ONE,i,f_i);
144  gPrev->insert(ONE,gPrev->getLength()+1,f_i);
145  // tag the first element in gPrev of the current index for findReductor()
146  lTag->setFirstCurrentIdx(gPrev->getLast());
147  //Print("1st gPrev: ");
148  //pWrite(gPrev->getFirst()->getPoly());
149  //Print("2nd gPrev: ");
150  //pWrite(gPrev->getFirst()->getNext()->getPoly());
151  //pWrite(gPrev->getFirst()->getNext()->getPoly());
152  CListOld* critPairs = new CListOld();
153  CNode* critPairsMinDeg = new CNode();
154  PList* rejectedGBList = new PList();
155  // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
156  // in the list critPairs
157  criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
158  static LList* sPolyList = new LList();
159  //sPolyList->print();
160  // labeled polynomials which have passed reduction() and have to be added to list gPrev
161  static LList* completed = new LList();
162  // the reduced labeled polynomials which are returned from subalgorithm reduction()
163  static LList* reducedLPolys = new LList();
164  // while there are critical pairs to be further checked and deleted/computed
165  while(NULL != critPairs->getFirst()) {
166  // critPairs->getMinDeg() deletes the first elements of minimal degree from
167  // critPairs, thus the while loop is not infinite.
168  // adds all to be reduced S-polynomials in the list sPolyList and adds
169  // the corresponding rules to the list rules
170  // NOTE: inside there is a second check of criterion 2 if new rules are
171  // added
172  //int timer4 = initTimer();
173  //startTimer();
174  //critPairs->print();
175 
176  //definition of a local numberUsefulPairs variable for the next degree
177  //step:
178  //if in this degree all pairs are useless, skip this degree step
179  //completely!
180  //long arrideg = critPairs->getFirst()->getData()->getDeg();
181  //if(plus && highestDegreeGBCriticalPair < critPairs->getFirst()->getData()->getDeg()) {
182  // return gPrev;
183  //}
184  //else {
185  critPairsMinDeg = critPairs->getMinDeg();
186  //numberUsefulPairsMinDeg = computeUsefulMinDeg(critPairsMinDeg);
187  //if(numberUsefulPairs > 0) {
188  //if(numberUsefulPairsMinDeg > 0) {
189  //Print("number of useful pairs: %d\n",numberUsefulPairs);
190  //Print("number of useless pairs: %d\n\n",numberUselessPairs);
191  //Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg());
192  long degreecheck = critPairsMinDeg->getData()->getDeg();
193 
194  computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
195  //}
196  //}
197  //}
198  //else {
199  // return gPrev;
200  //}
201  //timer4 = getTimer();
202  //Print("SPOLS TIMER: %d\n",timer4);
203  //spolsTime = spolsTime + timer4;
204  // DEBUG STUFF FOR SPOLYLIST
205  LNode* temp = sPolyList->getFirst();
206  //while(NULL != temp && NULL != temp->getLPoly()) {
207  //Print("Spolylist element: ");
208  //pWrite(temp->getPoly());
209  //temp = temp->getNext();
210  //}
211  // reduction process of new S-polynomials and also adds new critical pairs to critPairs
212  //int timer3 = initTimer();
213  //startTimer();
214  //sPolyList->print();
215  //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
216  //Print("BEFORE REDUCTION: \n");
217  //Print("number of useful pairs: %d\n",numberUsefulPairs);
218  //Print("number of useless pairs: %d\n\n",numberUselessPairs);
219  newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
220  //Print("ITERATION: %d",iterationstep);
221  //Print("NAECHSTER GRAD: %ld",degreecheck);
222  //sleep(5);
223  //if(i == 5 && pDeg(gPrev->getLast()->getPoly()) == 8) {
224  // Print("RAUS BEI DEG 8 \n");
225  // return gPrev;
226  //}
227  //Print("ARRIS DEG: %ld\n",arrideg);
228  // Arris idea stated by John in an email
229  //if(arrisCheck(critPairs->getFirst(),gPrev->getFirst(),arrideg)) {
230  // Print("ARRIS DEGREE: %ld\n", arrideg);
231  // return gPrev;
232  //}
233 
234 
235  //bool aha = checkDGB(gPrev);
236 
237 
238  //timer3 = getTimer();
239  //reductionTime = reductionTime + timer3;
240  //Print("REDUCTION TIMER: %d\n",timer3);
241  // DEBUG STUFF FOR GPREV
242  //temp = gPrev->getFirst();
243  //int number = 1;
244  //Print("\n\n");
245  //while(NULL != temp) {
246  // Print("%d. ",number);
247  // pWrite(temp->getPoly());
248  // temp = temp->getNext();
249  // number++;
250  // Print("\n");
251  //}
252  //sleep(5);
253 
254  }
255  //Print("REDUCTION DONE\n");
256  //Print("%p\n",rules->getFirst());
257  //Print("%p\n",rTag->getFirst());
258  //if(rules->getFirst() != rTag->getFirst()) {
259  //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
260  //rTag->insert(rules->getFirst());
261  //}
262  //else {
263  //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
264  //}
265  lTag->insert(lTag->getFirstCurrentIdx());
266  //Print("INDEX: %d\n",tempTag->getIndex());
267  //pWrite(tempTag->getPoly());
268  //Print("COMPLETED FIRST IN F5INC: \n");
269  //Print("1st gPrev: ");
270  //pWrite(gPrev->getFirst()->getPoly());
271  //Print("2nd gPrev: ");
272  //pWrite(gPrev->getFirst()->getNext()->getPoly());
273  //Print("3rd gPrev: ");
274  //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
275  //delete sPolyList;
276  //critPairs->print();
277  delete critPairs;
278  //Print("IN F5INC\n");
279  /*
280  PrintS("\n\n\nRULES: \n");
281  RNode* tempR = rules->getFirst();
282  Print("%p\n",tempR);
283  int t = 1;
284  while(NULL != tempR) {
285  Print("ADDRESS OF %d RNODE: %p\n",t,tempR);
286  Print("ADDRESS OF RULE: %p\n",tempR->getRule());
287  pWrite(tempR->getRuleTerm());
288  Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
289  Print("%d\n\n",tempR->getRuleIndex());
290  tempR = tempR->getNext();
291  t++;
292  }
293  */
294  //gPrev->print();
295  //Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
296  //Print("COMPLETE SPOLS TIME UNTIL NOW: %d\n",spolsTime);
297  degreeBound = 0;
298  return gPrev;
299 }
300 
301 
302 
303 bool checkDGB(LList* gPrev) {
304  Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly()));
305  LNode* temp = gPrev->getFirst();
306  LNode* temp2;
307  bool isDGb = 0;
308  // construct the d-GB gb
309  ideal gb = idInit(gPrev->getLength(),1);
310  for(int j=0;j<=gPrev->getLength()-1;j++) {
311  gb->m[j] = temp->getPoly();
312  pWrite(gb->m[j]);
313  temp = temp->getNext();
314  }
315  /*
316  Kstd1_deg = pDeg(gPrev->getLast()->getPoly());
317  BITSET save = test;
318  test |= Sy_bit(OPT_DEGBOUND);
319  kStd();
320  test = save;
321  */
322  temp = gPrev->getFirst();
323  while(NULL != temp) {
324  temp2 = temp->getNext();
325  number nOne = nInit(1);
326  poly lcm = pOne();
327  poly sp = pOne();
328  while(NULL != temp2) {
329  pLcm(temp->getPoly(),temp2->getPoly(),lcm);
330  pSetCoeff(lcm,nOne);
331  pSetm(lcm);
332  PrintS("LCM: ");
333  pWrite(lcm);
334  if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) {
335  poly u1 = pOne();
336  poly u2 = pOne();
337  u1 = pDivide(lcm,pHead(temp->getPoly()));
338  pSetCoeff(u1,nOne);
339  u2 = pDivide(lcm,pHead(temp2->getPoly()));
340  pSetCoeff(u2,nOne);
341  sp = ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()),
342  ppMult_qq(u2,temp2->getPoly()));
343  pNorm(sp);
344 
345  poly reducer = pOne();
346  //reducer = gb->m[0];
347  int i = 0;
348  pWrite(pHead(sp));
349 
350  while(i<IDELEMS(gb)) {
351  reducer = gb->m[i];
352  if(pDivisibleBy(reducer,pHead(sp))) {
353  poly uReducer = pOne();
354  uReducer = pDivide(lcm,pHead(reducer));
355  pSetCoeff(uReducer,nOne);
356  sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer));
357  //pNorm(tempSP);
358  //sp = tempSP;
359  pNorm(sp);
360  pWrite(sp);
361  i = 0;
362  }
363  else {
364  i++;
365  }
366  }
367 
368  pWrite(pHead(sp));
369  }
370  temp2 = temp2->getNext();
371  }
372  temp = temp->getNext();
373  }
374  PrintS("------------------\n");
375  return isDGb;
376 }
377 
378 /*
379  * Arris Check if we are finished after the current degree step:
380  * Checks all remaining critical pairs, i.e. those of higher degree,
381  * by the two Buchberger criteria.
382  * return value: 0, if all remaining critical pairs are deleted by
383  * Buchberger's criteria
384  * 1, otherwise
385  */
386 bool arrisCheck(CNode* first, LNode* firstGCurr, long arrideg) {
387  CNode* temp = first;
388 
389  //product criterion check
390  while(NULL != temp) {
391  if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) {
392  return 0;
393  }
394  temp = temp->getNext();
395  }
396 
397  // chain criterion
398  LNode* tempPoly = firstGCurr;
399  while(NULL != tempPoly) {
400  LNode* tempPoly2 = tempPoly->getNext();
401  while(NULL != tempPoly2) {
402  number nOne = nInit(1);
403  poly lcm = pOne();
404  pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm);
405  pSetCoeff(lcm,nOne);
406  pSetm(lcm);
407  if(pDeg(lcm) > arrideg) {
408  LNode* tempPoly3 = firstGCurr;
409  while(NULL != tempPoly3) {
410  if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) {
411  poly lcm1 = pOne();
412  poly lcm2 = pOne();
413  pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1);
414  pSetCoeff(lcm1,nOne);
415  pSetm(lcm1);
416  pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2);
417  pSetCoeff(lcm2,nOne);
418  pSetm(lcm2);
419  if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) {
420  return 0;
421  }
422  }
423  tempPoly3 = tempPoly3->getNext();
424  }
425  }
426  tempPoly2 = tempPoly2->getNext();
427  }
428  tempPoly = tempPoly->getNext();
429  }
430  return 1;
431 }
432 
433 
434 
435 /*
436 ================================================================
437 computes a list of critical pairs for the next reduction process
438 the first element is always "useful" thus the critical pair
439 computed is either "useful" or "useless" depending on the second
440 element which generates the critical pair.
441 first element in gPrev is always the newest element which must
442 build critical pairs with all other elements in gPrev
443 ================================================================
444 */
445 inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList, int plus) {
446  //Print("IN CRITPAIRS\n");
447  // initialization for usage in pLcm()
448  number nOne = nInit(1);
449  LNode* newElement = gPrev->getLast();
450  LNode* temp = gPrev->getFirst();
451  poly u1 = pOne();
452  poly u2 = pOne();
453  poly lcm = pOne();
454  poly t = pHead(newElement->getPoly());
455  RuleOld* testedRuleOld = NULL;
456  //Print("NEW: ");
457  //pWrite(newElement->getPoly());
458  //Print("ADDRESS: %p",newElement);
459  if(NULL != rules->getFirst()) {
460  testedRuleOld = rules->getFirst()->getRuleOld();
461  }
462  // computation of critical pairs
463  while( gPrev->getLast() != temp) {
464  //Print("TEMP: ");
465  //pWrite(pHead(temp->getPoly()));
466  //Print("ADDRESS: %p",temp);
467  pLcm(newElement->getPoly(), temp->getPoly(), lcm);
468  pSetCoeff(lcm,nOne);
469  // computing factors u2 for new labels
470  u1 = pDivide(lcm,t);
471  if(NULL == u1) {
472  break;
473  }
474  pSetCoeff(u1,nOne);
475  u2 = pDivide(lcm,pHead(temp->getPoly()));
476  pSetCoeff(u2,nOne);
477  int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly())));
478  // testing both new labels by the F5 Criterion
479  if(!temp->getDel()) {
480  if(plus && highestDegreeGBCriticalPair < degree) {
482  }
483  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
484  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
485  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
486  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
487  // label as first element in the CPairOld
488  if(newElement->getIndex() == temp->getIndex() &&
489  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
490  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
491  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);
492  critPairs->insert(cp);
493  // counting the number of useful pairs
495  }
496  else {
497  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
498  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);
499  critPairs->insert(cp);
500  // counting the number of useful pairs
502  }
503  }
504  else {
505  // TODO: generate a list of lcms of rejected GB critical pairs and
506  // check F5 critical pairs with it at their creation
507  //Print("--------------------------------------------------------------------\n");
508  //Print("--------------------------------------------------------------------\n");
509  pSetm(lcm);
510  rejectedGBList->insert(lcm);
511  //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n");
512  //pWrite(lcm);
513  //Print("--------------------------------------------------------------------\n");
514  //rejectedGBList->print();
515  }
516  }
517  else {
518  //Print("LABEL: ");
519  //pWrite(ppMult_qq(u1,newElement->getTerm()));
520  //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
521  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
522  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
523  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
524  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
525  // label as first element in the CPairOld
526  if(newElement->getIndex() == temp->getIndex() &&
527  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
528  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
529  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
530  critPairs->insert(cp);
532  }
533  else {
534  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
535  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
536  critPairs->insert(cp);
538  }
539  }
540  //}
541  }
542  temp = temp->getNext();
543  }
544 }
545 
546 
547 
548 /*
549 ================================================================
550 computes a list of critical pairs for the next reduction process
551 the first element is always "useless" thus the critical pair
552 computed is "useless".
553 first element in gPrev is always the newest element which must
554 build critical pairs with all other elements in gPrev
555 ================================================================
556 */
557 inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList) {
558  //Print("IN CRITPAIRS\n");
559  // initialization for usage in pLcm()
560  number nOne = nInit(1);
561  LNode* newElement = gPrev->getLast();
562  LNode* temp = gPrev->getFirst();
563  poly u1 = pOne();
564  poly u2 = pOne();
565  poly lcm = pOne();
566  poly t = pHead(newElement->getPoly());
567  RuleOld* testedRuleOld = NULL;
568  if(NULL != rules->getFirst()) {
569  testedRuleOld = rules->getFirst()->getRuleOld();
570  }
571  // computation of critical pairs
572  while( gPrev->getLast() != temp) {
573  pLcm(newElement->getPoly(), temp->getPoly(), lcm);
574  pSetCoeff(lcm,nOne);
575  // computing factors u2 for new labels
576  u1 = pDivide(lcm,t);
577  if(NULL == u1) {
578  break;
579  }
580  pSetCoeff(u1,nOne);
581  u2 = pDivide(lcm,pHead(temp->getPoly()));
582  pSetCoeff(u2,nOne);
583  // testing both new labels by the F5 Criterion
584  //Print("LABEL: ");
585  //pWrite(ppMult_qq(u1,newElement->getTerm()));
586  //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
587  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
588  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
589  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
590  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
591  // label as first element in the CPairOld
592  if(newElement->getIndex() == temp->getIndex() &&
593  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
594  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
595  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
596  critPairs->insert(cp);
598  }
599  else {
600  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
601  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
602  critPairs->insert(cp);
604  }
605  }
606  //}
607  temp = temp->getNext();
608  }
609 }
610 
611 
612 
613 /*
614 ========================================
615 Criterion 1, i.e. Faugere's F5 Criterion
616 ========================================
617 */
618 inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
619  // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
620  int idx = l->getIndex();
621  int i;
622  if(idx == 1) {
623  //Print("HIER\n");
624  return false;
625  }
626  else {
627  LNode* testNode = gPrev->getFirst();
628  // save the monom t1*label_term(l) as it is tested various times in the following
629  poly u1 = ppMult_qq(t,l->getTerm());
630  //Print("------------------------------IN CRITERION 1-----------------------------------------\n");
631  //Print("TESTED ELEMENT: ");
632  //pWrite(l->getPoly());
633  //pWrite(l->getTerm());
634  //pWrite(ppMult_qq(t,l->getTerm()));
635  //Print("%d\n\n",l->getIndex());
636  while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) {
637  //pWrite(testNode->getPoly());
638  //Print("%d\n",testNode->getIndex());
639  if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
640  //Print("Criterion 1 NOT passed!\n");
641  if(idx != gPrev->getLast()->getIndex()) {
642  //Print("DOCH!\n");
643  }
644  return true;
645  }
646  //pWrite(testNode->getNext()->getPoly());
647  testNode = testNode->getNext();
648  }
649  /*
650  ideal testId = idInit(idx-1,1);
651  for(i=0;i<idx-1;i++) {
652  testId->m[i] = pHead(testNode->getPoly());
653  testNode = testNode->getNext();
654  }
655  poly temp = kNF(testId,currRing->qideal,u1);
656  //pWrite(temp);
657  for(i=0;i<IDELEMS(testId);i++) {
658  testId->m[i] = NULL;
659  }
660  idDelete(&testId);
661  if(NULL == temp) {
662  //if(l->getIndex() != gPrev->getFirst()->getIndex()) {
663  // Print("----------------------------Criterion1 not passed----------------------------------\n");
664  //}
665  return true;
666  }
667  */
668  return false;
669  }
670 }
671 
672 
673 
674 /*
675 =====================================
676 Criterion 2, i.e. Rewritten Criterion
677 =====================================
678 */
679 inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) {
680  //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n");
681  /*
682  PrintS("RULES: \n");
683  RNode* tempR = rules->getFirst();
684  Print("%p\n",tempR);
685  int i = 1;
686  while(NULL != tempR) {
687  Print("ADDRESS OF %d RNODE: %p\n",i,tempR);
688  Print("ADDRESS OF RULE: %p\n",tempR->getRule());
689  pWrite(tempR->getRuleTerm());
690  Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
691  Print("%d\n\n",tempR->getRuleIndex());
692  tempR = tempR->getNext();
693  i++;
694  }
695  //Print("TESTED ELEMENT: ");
696  //pWrite(l->getPoly());
697  //pWrite(l->getTerm());
698  //pWrite(ppMult_qq(t,l->getTerm()));
699  //Print("%d\n\n",l->getIndex());
700  */
701 // start at the previously added element to gPrev, as all other elements will have the same index for sure
702  if(idx > l->getIndex()) {
703  return false;
704  }
705 
706  RNode* testNode; // = new RNode();
707  testNode = rules->getFirst();
708  /*
709  if(NULL == rTag->getFirst()) {
710  if(NULL != rules->getFirst()) {
711  testNode = rules->getFirst();
712  }
713  else {
714  return false;
715  }
716  }
717 
718  else {
719 
720  if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
721  testNode = rules->getFirst();
722  }
723  else {
724  //Print("HIER\n");
725  //Print("DEBUG\n");
726  //Print("L INDEX: %d\n",l->getIndex());
727  *-------------------------------------
728  * TODO: WHEN INTERREDUCING THE GB THE
729  * INDEX OF THE PREVIOUS ELEMENTS
730  * GETS HIGHER!
731  *-----------------------------------*
732  //testNode = rules->getFirst();
733  testNode = rTag->get(l->getIndex());
734  if(NULL == testNode) {
735  testNode = rules->getFirst();
736  }
737  //Print("TESTNODE ADDRESS: %p\n",testNode);
738  }
739  }
740  */
741  //testNode = rules->getFirst();
742  // save the monom t1*label_term(l) as it is tested various times in the following
743  poly u1 = ppMult_qq(t,l->getTerm());
744  // first element added to rTag was NULL, check for this
745  //Print("%p\n",testNode->getRule());
746  // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
747  //Print("TESTNODE: %p\n",testNode);
748  //pWrite(testNode->getRuleTerm());
749  if(NULL != testNode ) {
750  //pWrite(testNode->getRuleTerm());
751  }
752  if(NULL != testNode) {
753  if(testNode->getRuleOld() == l->getRuleOld()) {
754  //Print("%p\n%p\n",testNode->getRule(),l->getRule());
755  //Print("EQUAL\n");
756  }
757  else {
758  //Print("NOT EQUAL\n");
759  }
760  }
761  while(NULL != testNode && testNode->getRuleOld() != l->getRuleOld()
762  && l->getIndex() == testNode->getRuleOldIndex()) {
763  //Print("%p\n",testNode);
764  //pWrite(testNode->getRuleTerm());
765  //pWrite(t);
766  //pWrite(l->getTerm());
767  //pWrite(u1);
768  //Print("%d\n",testNode->getRuleIndex());
769  if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
770  //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
771  //Print("INDEX: %d\n",l->getIndex());
772  pDelete(&u1);
773  //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
774  return true;
775  }
776  testNode = testNode->getNext();
777  }
778  //delete testNode;
779  pDelete(&u1);
780  //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
781  return false;
782 }
783 
784 
785 
786 /*
787 =================================================================================================================
788 Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
789 =================================================================================================================
790 */
791 inline bool criterion2(poly t, LPolyOld* l, RList* rules, RuleOld* testedRuleOld) {
792  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
793  //Print("LAST RuleOld TESTED: %p",testedRuleOld);
794  /*
795  PrintS("RULES: \n");
796  RNode* tempR = rules->getFirst();
797  while(NULL != tempR) {
798  pWrite(tempR->getRuleTerm());
799  Print("%d\n\n",tempR->getRuleIndex());
800  tempR = tempR->getNext();
801  }
802  //Print("TESTED ELEMENT: ");
803  //pWrite(l->getPoly());
804  //pWrite(l->getTerm());
805  //pWrite(ppMult_qq(t,l->getTerm()));
806  //Print("%d\n\n",l->getIndex());
807  */
808 // start at the previously added element to gPrev, as all other elements will have the same index for sure
809  RNode* testNode = rules->getFirst();
810  // save the monom t1*label_term(l) as it is tested various times in the following
811  poly u1 = ppMult_qq(t,l->getTerm());
812  // first element added to rTag was NULL, check for this
813  while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) {
814  //pWrite(testNode->getRuleTerm());
815  if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
816  //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
817  //Print("INDEX: %d\n",l->getIndex());
818  pDelete(&u1);
819  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
820  return true;
821  }
822  testNode = testNode->getNext();
823  }
824  pDelete(&u1);
825  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
826  return false;
827 }
828 
829 /*
830  * check for useful pairs in the given subset of critical pairs
831  */
833  CNode* temp = first;
834  int numberUsefulPairsMinDeg = 0;
835  while(NULL != temp) {
836  if(!temp->getDel()) {
837  numberUsefulPairsMinDeg++;
838  }
839  temp = temp->getNext();
840  }
842 }
843 /*
844 ==================================
845 Computation of S-Polynomials in F5
846 ==================================
847 */
848 void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, PList* rejectedGBList) {
849  CNode* temp = first;
850  //Print("\nDegree: %d\n",temp->getData()->getDeg());
851  // only GB-critical pairs are computed
852  //while(NULL != temp && temp->getDel()) {
853  // temp = temp->getNext();
854  //}
855  //if(temp->getData()->getDeg() == 11) {
856  // Print("PAIRS OF DEG 11:\n");
857  //}
858  RList* f5rules = new RList();
859  CListOld* f5pairs = new CListOld();
860  poly sp = pInit();
861  number sign = nInit(-1);
862  //Print("###############################IN SPOLS##############################\n");
863  //first->print();
864 /*
865  * first of all: do everything for GB critical pairs
866  */
867  while(NULL != temp) {
868  // if(temp->getData()->getDeg() == 11) {
869  //Print("--------------------------\n");
870  //Print("redundant? %d\n",temp->getDel());
871  //pWrite(pHead(temp->getLp1Poly()));
872  //Print("redundant: %d\n",temp->getAdLp1()->getDel());
873  //pWrite(pHead(temp->getLp2Poly()));
874  //Print("redundant: %d\n",temp->getAdLp2()->getDel());
875  //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
876  // sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
877  // ppMult_qq(temp->getT2(),temp->getLp2Poly()));
878  //Print("BEGIN SPOLY2\n====================\n");
879  // pNorm(sp);
880  // pWrite(pHead(sp));
881  //Print("--------------------------\n");
882  //}
883  if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
884  //if(temp->getDel() == 0 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
885  if(temp->getLp2Index() == temp->getLp1Index()) {
886  if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
887  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
888  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
889  pNorm(sp);
890  if(NULL == sp) {
892  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
893  numberOfRules++;
894  pDelete(&sp);
895  }
896  else {
897  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
898  numberOfRules++;
899  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
900  //Print("INSERTED\n");
901  numberOfSpolys++;
902  }
903  }
904  else {
905  if(highestDegreeGBCriticalPair < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
907  }
908  rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
909  //Print("rejected!\n");
910 
911  //Print("CRITERION 2 in SPOLS 2nd generator\n");
912  }
913  }
914  else {
915  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
916  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
917  //Print("BEGIN SPOLY2\n====================\n");
918  pNorm(sp);
919  //pWrite(sp);
920  //Print("END SPOLY2\n====================\n");
921  if(NULL == sp) {
923  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
924  numberOfRules++;
925  pDelete(&sp);
926  }
927  else {
928  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
929  numberOfRules++;
930  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
931  //Print("INSERTED\n");
932  numberOfSpolys++;
933  }
934  }
935  }
936  /*
937  if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
938  //Print("rejected!\n");
939  rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
940  }
941 
942 
943  if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
944  if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
945  highestDegree = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
946  }
947  if(temp->getLp2Index() == temp->getLp1Index()) {
948  if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
949  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
950  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
951  pNorm(sp);
952  if(NULL == sp) {
953  reductionsToZero++;
954  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
955  numberOfRules++;
956  pDelete(&sp);
957  }
958  else {
959  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
960  numberOfRules++;
961 
962 
963  // save the address of the rule again in a different
964  // list
965 
966  f5rules->insert(rules->getFirst()->getRuleOld());
967  f5pairs->insertWithoutSort(temp->getData());
968  ///////////////////////////////////////
969 
970  //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
971  }
972  }
973  }
974  else {
975  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
976  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
977  //Print("BEGIN SPOLY2\n====================\n");
978  pNorm(sp);
979  //pWrite(sp);
980  //Print("END SPOLY2\n====================\n");
981  if(NULL == sp) {
982  reductionsToZero++;
983  //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
984  numberOfRules++;
985  pDelete(&sp);
986  }
987  else {
988  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
989  numberOfRules++;
990  // save the address of the rule again in a different
991  // list
992 
993  f5rules->insert(rules->getFirst()->getRuleOld());
994  f5pairs->insertWithoutSort(temp->getData());
995  ///////////////////////////////////////
996  //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
997  // numberOfSpolys++;
998  }
999  }
1000  }
1001  // the following else is not needed at all as we are checking
1002  // F5-critical pairs in this step
1003  /*
1004  else {
1005  if(!temp->getDel()) {
1006  rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1007  }
1008 
1009  }
1010  */
1011 
1012  temp = temp->getNext();
1013 
1014  }
1015 
1016  /*
1017  temp = f5pairs->getFirst();
1018  RNode* tempRule = f5rules->getFirst();
1019  int howmany = 1;
1020  while(NULL != temp) {
1021  //Print("RULE: ");
1022  //pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
1023  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
1024  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
1025  pNorm(sp);
1026  if(rejectedGBList->check(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())))) { //|| (temp->getData()->getDeg() == 10 && howmany == 2)) {
1027  if((temp->getData()->getDeg() == 10) && (howmany == 2)) {
1028  //Print("HIER DRIN IM SAFTLADEN\n");
1029  }
1030  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
1031  numberOfSpolys++;
1032  howmany++;
1033  }
1034  else {
1035  numberRejectedF5CriticalPairs++;
1036  howmany++;
1037  if(numberRejectedF5CriticalPairs < -1) { // ||
1038  }
1039  else {
1040  //numberRejectedF5CriticalPairs == 7) {
1041  /*
1042  PrintS("--------------------------------- rejected F5-critical pair-------------------------------------\n");
1043  pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1044  PrintS("Label: ");
1045  pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
1046  Print("%d\n",temp->getDel());
1047  PrintS("Comes from:\n ");
1048  pWrite(pHead(temp->getLp1Poly()));
1049  PrintS("Label: ");
1050  pWrite(temp->getLp1Term());
1051  Print("%d\n",temp->getLp1Index());
1052  pWrite(pHead(temp->getLp2Poly()));
1053  PrintS("Label: ");
1054  pWrite(temp->getLp2Term());
1055  Print("%d\n",temp->getLp2Index());
1056  //Print("--------------------------------------LIST OF GB PAIRS REJECTED-----------------------------------------\n");
1057  //rejectedGBList->print();
1058  PrintS("--------------------------------------------------------------------------------------------------------\n");
1059  //if(temp->getLp1Index() < 7) {
1060  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
1061 
1062  //}
1063  //numberOfSpolys++;
1064  }
1065  //pSetExp(tempRule->getRuleOld()->getTerm(),1,1000);
1066  }
1067  temp = temp->getNext();
1068  tempRule = tempRule->getNext();
1069 
1070  }
1071  */
1072  // these critical pairs can be deleted now as they are either useless for further computations or
1073  // already saved as an S-polynomial to be reduced in the following
1074  delete first;
1075 //Print("NUMBER SPOLYS: %d\n", numberOfSpolys);
1076 //Print("SPOLY LIST: \n");
1077 //LNode* tempSpoly = sPolyList->getFirst();
1078 //if(NULL != tempSpoly) {
1079 // pWrite(pHead(tempSpoly->getPoly()));
1080 // tempSpoly = tempSpoly->getNext();
1081 //}
1082 //Print("-----SP------\n");
1083 //else {
1084 // Print("EMPTY SPOLYLIST!\n");
1085 //}
1086 }
1087 
1088 /*
1089 ========================================================================
1090 reduction including subalgorithm topReduction() using Faugere's criteria
1091 ========================================================================
1092 */
1093 void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
1094  ideal gbPrev, PList* rejectedGBList, int plus) {
1095  //Print("##########################################In REDUCTION!########################################\n");
1096  // check if sPolyList has any elements
1097  // NOTE: due to initialization sPolyList always has a default NULL element
1098  LNode* temp = sPolyList->getFirst();
1099  while(NULL != temp) {
1100  // temp is the first element in the sPolyList which should be reduced
1101  // due to earlier sorting this is the element of minimal degree AND
1102  // minimal label
1103  // delete the above first element from sPolyList, temp will be either reduced to
1104  // zero or added to gPrev, but never come back to sPolyList
1105  //pWrite(sPolyList->getFirst()->getPoly());
1106  //Print("LIST OF SPOLYNOMIALS!\n");
1107  //sPolyList->print();
1108  sPolyList->setFirst(temp->getNext());
1109  poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly());
1110  if(NULL != tempNF) {
1111  pNorm(tempNF);
1112  temp->setPoly(tempNF);
1113  // try further reductions of temp with polynomials in gPrev
1114  // with label index = current label index: this is done such that there
1115  // is no label corruption during the reduction process
1116  //Print("lower label reduction: ");
1117  //pWrite(tempNF);
1118  topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1119 
1120  }
1121  else {
1122  reductionsToZero++;
1123  delete temp;
1124  }
1125  //if(NULL != temp->getPoly()) {
1126  // criticalPair(gPrev,critPairs,lTag,rTag,rules);
1127  //}
1128  temp = sPolyList->getFirst();
1129  }
1130  //sPolyList->print();
1131  //delete sPolyList;
1132 }
1133 
1134 /*
1135 ========================================================================
1136 reduction including subalgorithm topReduction() using Faugere's criteria
1137 ========================================================================
1138 */
1139 void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag,
1140  ideal gbPrev, int termination, PList* rejectedGBList, int plus) {
1141  //Print("##########################################In REDUCTION!########################################\n");
1142  // check if sPolyList has any elements
1143  // NOTE: due to initialization sPolyList always has a default NULL element
1144  //Print("--1--\n");
1145  LNode* temp = sPolyList->getFirst();
1146  //Print("START OF REDUCTION: ");
1147  while(NULL != temp) {
1149  // temp is the first element in the sPolyList which should be reduced
1150  // due to earlier sorting this is the element of minimal degree AND
1151  // minimal label
1152  // delete the above first element from sPolyList, temp will be either reduced to
1153  // zero or added to gPrev, but never come back to sPolyList
1154  //Print("LIST OF SPOLYNOMIALS!\n");
1155  //sPolyList->print();
1156  //pWrite(sPolyList->getFirst()->getPoly());
1157  sPolyList->setFirst(temp->getNext());
1158  //if(pDeg(temp->getPoly()) > 11) {
1159  // Print("YES!!!!!!!!!!!!!!!!\n");
1160  //}
1161  //pWrite(temp->getPoly());
1162  //poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly());
1163  //Print("!!!\n");
1164  //if(NULL != tempNF) {
1165  //pNorm(tempNF);
1166  //temp->setPoly(tempNF);
1167  //Print("lower label reduction: ");
1168  //pWrite(tempNF);
1169  // try further reductions of temp with polynomials in gPrev
1170  // with label index = current label index: this is done such that there
1171  // is no label corruption during the reduction process
1172  findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1173  //}
1174  //else {
1175  // reductionsToZero++;
1176  // delete temp;
1177  //}
1178  //if(NULL != temp->getPoly()) {
1179  // criticalPair(gPrev,critPairs,lTag,rTag,rules);
1180  //}
1181  //Print("HIER AUCH ?\n");
1182  //Print("--2--\n");
1183  //sPolyList->print();
1184  //critPairs->print();
1185  temp = sPolyList->getFirst();
1186  //Print("%p\n",temp);
1187  }
1188  //sPolyList->print();
1189  //delete sPolyList;
1190  //Print("REDUCTION FERTIG\n");
1191 }
1192 
1193 
1194 /*!
1195  * ================================================================================
1196  * searches for reducers of temp similar to the symbolic preprocessing of F4 and
1197  * divides them into a "good" and "bad" part:
1198  *
1199  * the "good" ones are the reducers which do not corrupt the label of temp, with
1200  * these the normal form of temp is computed
1201  *
1202  * the "bad" ones are the reducers which corrupt the label of temp, they are tested
1203  * later on for possible new rules and S-polynomials to be added to the algorithm
1204  * ================================================================================
1205 */
1206 void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus) {
1207  int canonicalize = 0;
1208  //int timerRed = 0;
1209  bool addToG = 1;
1210  number sign = nInit(-1);
1211  LList* good = new LList();
1212  LList* bad = new LList();
1213  LList* monomials = new LList(l->getLPolyOld());
1214  poly u = pOne();
1215  number nOne = nInit(1);
1216  LNode* tempRed = lTag->getFirstCurrentIdx();
1217  LNode* tempMon = monomials->getFirst();
1218  poly tempPoly = pInit();
1219  poly redPoly = NULL;
1220  int idx = l->getIndex();
1221  //Print("IN FIND REDUCERS: ");
1222  //pWrite(l->getPoly());
1223  tempPoly = pCopy(l->getPoly());
1224  //tempMon->setPoly(tempPoly);
1225  //while(NULL != tempMon) {
1226  // iteration over all monomials in tempMon
1228  kBucketInit(bucket,tempPoly,0);
1229  tempPoly = kBucketGetLm(bucket);
1230  //Print("\n\n\nTO BE REDUCED: ");
1231  //pWrite(l->getPoly());
1232  //pWrite(l->getTerm());
1233  //pWrite(tempPoly);
1234  while(NULL != tempPoly) {
1235  // iteration of all elements in gPrev of the current index
1236  tempRed = gPrev->getFirst();
1237  while(NULL != tempRed) {
1238  //Print("TEMPREDPOLY: ");
1239  //pWrite(tempRed->getPoly());
1240  if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1241  u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1242  //Print("U: ");
1243  //pWrite(u);
1244  if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done!
1245  if(tempRed->getIndex() != idx) {
1246  // passing criterion1 ?
1247  if(!criterion1(gPrev,u,tempRed,lTag)) {
1248  poly tempRedPoly = tempRed->getPoly();
1249  //Print("REDUCER: ");
1250  //pWrite(tempRedPoly);
1251  pIter(tempRedPoly);
1252  int lTempRedPoly = pLength(tempRedPoly);
1253  kBucketExtractLm(bucket);
1254  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1255  canonicalize++;
1256  //Print("Reduction\n");
1257  if(!(canonicalize % 50)) {
1258  kBucketCanonicalize(bucket);
1259  }
1260  tempPoly = kBucketGetLm(bucket);
1261  //Print("TEMPPOLY: ");
1262  //pWrite(tempPoly);
1263  if(NULL != tempPoly) {
1264  tempRed = gPrev->getFirst();
1265  continue;
1266  }
1267  else {
1268  break;
1269  }
1270  }
1271 
1272  }
1273  else {
1274  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1275  //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1276  //pWrite(u);
1277  //pWrite(tempRed->getTerm());
1278  //pWrite(pHead(tempRed->getPoly()));
1279  addToG = 0;
1280  }
1281  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1282  // passing criterion2 ?
1283  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1284  // passing criterion1 ?
1285  if(!criterion1(gPrev,u,tempRed,lTag)) {
1286  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1287  if(NULL == redPoly) {
1288  bad->insert(tempRed->getLPolyOld());
1289  addToG = 1;
1290  //poly tempRedPoly = tempRed->getPoly();
1291  //break;
1292  }
1293  }
1294  else {
1295  poly tempRedPoly = tempRed->getPoly();
1296  //Print("REDUCER: ");
1297  //pWrite(tempRedPoly);
1298  pIter(tempRedPoly);
1299  int lTempRedPoly = pLength(tempRedPoly);
1300  //Print("HEAD MONOMIAL KBUCKET: ");
1301  //pWrite(kBucketGetLm(bucket));
1302  kBucketExtractLm(bucket);
1303  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1304  canonicalize++;
1305  //Print("REDUCTION\n");
1306  addToG = 1;
1307  if(!(canonicalize % 50)) {
1308  kBucketCanonicalize(bucket);
1309  }
1310  //Print("HEAD MONOMIAL KBUCKET: ");
1311  //pWrite(kBucketGetLm(bucket));
1312  tempPoly = kBucketGetLm(bucket);
1313  //Print("TEMPPOLY: ");
1314  //pWrite(tempPoly);
1315  if(NULL != tempPoly) {
1316  tempRed = gPrev->getFirst();
1317  continue;
1318  }
1319  else {
1320  break;
1321  }
1322  }
1323  }
1324  }
1325  else {
1326  //Print("CRIT 1 ");
1327 
1328  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1329  //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1330  //pWrite(u);
1331  //pWrite(tempRed->getTerm());
1332  //pWrite(tempRed->getPoly());
1333  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1334  //Print("REDUCER LABEL: ");
1335  //pWrite(tempRed->getTerm());
1336 addToG = 0;
1337  }
1338  }
1339  }
1340  }
1341  else {
1342  //Print("CRIT 2 ");
1343  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1344  //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1345  //pWrite(u);
1346  //pWrite(tempRed->getTerm());
1347  //pWrite(tempRed->getPoly());
1348  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1349  //Print("REDUCER LABEL: ");
1350  //pWrite(tempRed->getTerm());
1351 addToG = 0;
1352  }
1353  }
1354  }
1355  }
1356  }
1357  else { // u = 1 => reduce without checking criteria
1358  poly tempRedPoly = tempRed->getPoly();
1359  //Print("REDUCER: ");
1360  //pWrite(tempRedPoly);
1361  pIter(tempRedPoly);
1362  int lTempRedPoly = pLength(tempRedPoly);
1363  kBucketExtractLm(bucket);
1364  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1365  canonicalize++;
1366  //Print("Reduction\n");
1367  if(!(canonicalize % 50)) {
1368  kBucketCanonicalize(bucket);
1369  }
1370  tempPoly = kBucketGetLm(bucket);
1371  //Print("TEMPPOLY: ");
1372  //pWrite(tempPoly);
1373  if(NULL != tempPoly) {
1374  tempRed = gPrev->getFirst();
1375  continue;
1376  }
1377  else {
1378  break;
1379  }
1380 
1381  }
1382  }
1383  tempRed = tempRed->getNext();
1384  }
1385  // reduction process with elements in LList* reducers
1386  if(NULL != tempPoly) {
1387  //Print("HERE\n");
1388  tempRed = reducers->getFirst();
1389  while(NULL != tempRed) {
1390  //Print("TEMPREDPOLY: ");
1391  //pWrite(tempRed->getPoly());
1392  //pWrite(tempPoly);
1393  if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1394  //Print("A\n");
1395  u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1396  //Print("U: ");
1397  //pWrite(u);
1398  if(tempRed->getIndex() != idx) {
1399  // passing criterion1 ?
1400  if(!criterion1(gPrev,u,tempRed,lTag)) {
1401  poly tempRedPoly = tempRed->getPoly();
1402  //Print("REDUCER: ");
1403  //pWrite(ppMult_qq(u,tempRedPoly));
1404  pIter(tempRedPoly);
1405  int lTempRedPoly = pLength(tempRedPoly);
1406  kBucketExtractLm(bucket);
1407  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1408  canonicalize++;
1409  //Print("Reduction\n");
1410  if(!(canonicalize % 50)) {
1411  kBucketCanonicalize(bucket);
1412  }
1413  tempPoly = kBucketGetLm(bucket);
1414  //Print("TEMPPOLY: ");
1415  //pWrite(tempPoly);
1416  if(NULL != tempPoly) {
1417  tempRed = gPrev->getFirst();
1418  continue;
1419  }
1420  else {
1421  break;
1422  }
1423  }
1424 
1425  }
1426  else {
1427  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1428  //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1429  //pWrite(u);
1430  //pWrite(tempRed->getTerm());
1431  //pWrite(pHead(tempRed->getPoly()));
1432  //addToG = 0;
1433  }
1434  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1435  // passing criterion2 ?
1436  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1437  // passing criterion1 ?
1438  if(!criterion1(gPrev,u,tempRed,lTag)) {
1439  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1440  if(NULL == redPoly) {
1441  bad->insert(tempRed->getLPolyOld());
1442  addToG = 1;
1443  //poly tempRedPoly = tempRed->getPoly();
1444  //break;
1445  }
1446  }
1447  else {
1448  poly tempRedPoly = tempRed->getPoly();
1449  //Print("REDUCER: ");
1450  //pWrite(ppMult_qq(u,tempRedPoly));
1451  pIter(tempRedPoly);
1452  int lTempRedPoly = pLength(tempRedPoly);
1453  //Print("HEAD MONOMIAL KBUCKET: ");
1454  //pWrite(kBucketGetLm(bucket));
1455  kBucketExtractLm(bucket);
1456  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1457  canonicalize++;
1458  //Print("REDUCTION\n");
1459  addToG = 1;
1460  if(!(canonicalize % 50)) {
1461  kBucketCanonicalize(bucket);
1462  }
1463  //Print("HEAD MONOMIAL KBUCKET: ");
1464  //pWrite(kBucketGetLm(bucket));
1465  tempPoly = kBucketGetLm(bucket);
1466  //Print("TEMPPOLY: ");
1467  //pWrite(tempPoly);
1468  if(NULL != tempPoly) {
1469  tempRed = gPrev->getFirst();
1470  continue;
1471  }
1472  else {
1473  break;
1474  }
1475  }
1476  }
1477  }
1478  else {
1479  //Print("CRIT 1 ");
1480 
1481  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1482  //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1483  //pWrite(u);
1484  //pWrite(tempRed->getTerm());
1485  //pWrite(tempRed->getPoly());
1486  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1487  //Print("REDUCER LABEL: ");
1488  //pWrite(tempRed->getTerm());
1489  addToG = 0;
1490  }
1491  }
1492  }
1493  }
1494  else {
1495  //Print("CRIT 2 ");
1496  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1497  //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1498  //pWrite(u);
1499  //pWrite(tempRed->getTerm());
1500  //pWrite(tempRed->getPoly());
1501  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1502  //Print("REDUCER LABEL: ");
1503  //pWrite(tempRed->getTerm());
1504 addToG = 0;
1505  }
1506  }
1507  }
1508  }
1509 
1510  }
1511  tempRed = tempRed->getNext();
1512  }
1513  }
1514  if(NULL != tempPoly) {
1515  if(NULL == redPoly) {
1516  redPoly = kBucketExtractLm(bucket);
1517  }
1518  else {
1519  redPoly = p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing);
1520  }
1521  // for top-reduction only
1522  redPoly = p_Merge_q(redPoly,kBucketClear(bucket),currRing);
1523  break;
1524  // end for top-reduction only
1525  tempPoly = kBucketGetLm(bucket);
1526 
1527  }
1528  }
1529  if(NULL == redPoly) {
1530  reductionsToZero++;
1531  //pDelete(&redPoly);
1532  }
1533  else
1534  {
1535  PrintS("\nELEMENT ADDED TO GPREV: ");
1536  pNorm(redPoly);
1537  if(highestDegree < pDeg(redPoly))
1538  {
1539  highestDegree = pDeg(redPoly);
1540  }
1541  pWrite(pHead(redPoly));
1542  //pWrite(l->getTerm());
1543  //Print("%d\n",canonicalize);
1544  l->setPoly(redPoly);
1545  // give "l" the label if it is "useful" (addToG = 0) or "useless"
1546  // (addToG = 1)
1547  l->setDel(!addToG);
1548  Print("redundant? %d\n\n",l->getDel());
1549  if(addToG == 0 && termination == 1) {
1550  reducers->insert(l->getLPolyOld());
1551  }
1552  else {
1553  gPrev->insert(l->getLPolyOld());
1554  }
1555  //Print("%d\n\n",termination);
1556  if(termination == 1) {
1557  if(addToG) {
1558  //Print("----------------HERE?-----------------\n");
1559  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1560  }
1561  else {
1562  notInG++;
1563  //Print("\nNONONO");
1564  //pWrite(pHead(l->getPoly()));
1565  //pWrite(l->getTerm());
1566  }
1567  }
1568  // case in which all new elements are added to gPrev!
1569  // using boolean "addToG" to know if the element is "useful" (0) or
1570  // "useless" (1)
1571  else {
1572  if(!l->getDel()) {
1573  criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1574  }
1575  else {
1576  criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1577  }
1578  }
1579  }
1580 
1581  // if there are "bad" reducers than try to compute new S-polynomials and rules
1582 
1583  if(NULL != bad->getFirst()) {
1584  //Print("BAD STUFF LIST:\n");
1585  //bad->print();
1586  LNode* tempBad = bad->getFirst();
1587  //pWrite(l->getPoly());
1588  while(NULL != tempBad) {
1589  if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
1590  //Print("BAD STUFF\n");
1591  //pWrite(l->getPoly());
1592  //pWrite(tempBad->getPoly());
1593  u = pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly()));
1594  //Print("MULTIPLIER: ");
1595  //pWrite(u);
1596  pSetCoeff(u,nOne);
1597  if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) {
1598  // passing criterion2 ?
1599  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) {
1600  // passing criterion1 ?
1601  if(!criterion1(gPrev,u,tempBad,lTag)) {
1602  //Print("HIERHIERHIERHIERHIERHIER\n");
1603  rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
1604  numberOfRules++;
1605  //gPrev->print();
1606  //pWrite(l->getPoly());
1607  poly temp = ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly());
1608  //pWrite(l->getPoly());
1609  //Print("%p\n",temp);
1610  //gPrev->print();
1611  if(NULL != temp) {
1612  pNorm(temp);
1613  LNode* tempBadNew = new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
1614  //pWrite(temp);
1615  //pWrite(tempBadNew->getPoly());
1616  //pWrite(tempBadNew->getTerm());
1617  //pWrite(pHead(tempBadNew->getPoly()));
1618  //Print("%p\n",tempBadNew->getPoly());
1619  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1620  tempBadNew->setDel(1);
1621 
1622  sPolyList->insertByLabel(tempBadNew);
1623  //Print("BAD SPOLYLIST: \n");
1624  //sPolyList->print();
1625  }
1626  }
1627  }
1628  }
1629  }
1630  //Print("HIER\n");
1631  tempBad = tempBad->getNext();
1632  //Print("%p\n",tempBad);
1633  }
1634  // Print("-------------------BAD STUFF LIST-----------------------------\n");
1635  }
1636  //Print("HIER AUCH\n");
1637  //Print("SPOLYLIST IN BAD: \n");
1638  //sPolyList->print();
1639  //Print("END FIND REDUCERS\n");
1640 }
1641 
1642 /*
1643 =======================================================================================
1644 merging 2 polynomials p & q without requiring that all monomials of p & q are different
1645 if there are equal monomials in p & q only one of these monomials (always that of p!)
1646 is taken into account
1647 =======================================================================================
1648 
1649 poly p_MergeEq_q(poly p, poly q, const ring r) {
1650  assume(p != NULL && q != NULL);
1651  p_Test(p, r);
1652  p_Test(q, r);
1653 #if PDEBUG > 0
1654  int l = pLength(p) + pLength(q);
1655 #endif
1656 
1657  spolyrec rp;
1658  poly a = &rp;
1659  DECLARE_LENGTH(const unsigned long length = r->CmpL_Size);
1660  DECLARE_ORDSGN(const long* ordsgn = r->ordsgn);
1661 
1662  Top: // compare p and q w.r.t. monomial ordering
1663  p_MemCmp(p->exp, q->exp, length, ordsgn, goto Equal, goto Greater , goto Smaller);
1664 
1665  Equal:
1666  a = pNext(a) = p;
1667  pIter(p);
1668  pIter(q);
1669  if(NULL == p) {
1670  if(NULL == q) {
1671  goto Finish;
1672  }
1673  else {
1674  pNext(a) = q;
1675  goto Finish;
1676  }
1677  }
1678  goto Top;
1679 
1680  Greater:
1681  a = pNext(a) = p;
1682  pIter(p);
1683  if (p==NULL) { pNext(a) = q; goto Finish;}
1684  goto Top;
1685 
1686  Smaller:
1687  a = pNext(a) = q;
1688  pIter(q);
1689  if (q==NULL) { pNext(a) = p; goto Finish;}
1690  goto Top;
1691 
1692  Finish:
1693 
1694  p_Test(pNext(&rp), r);
1695 #if PDEBUG > 0
1696  pAssume1(l - pLength(pNext(&rp)) == 0);
1697 #endif
1698  return pNext(&rp);
1699 }
1700 */
1701 
1702 /*
1703 =====================================================================================
1704 top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
1705 the same index whereas the labels are taken into account
1706 =====================================================================================
1707 */
1708 void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) {
1709  //Print("##########################################In topREDUCTION!########################################\n");
1710  // try l as long as there are reductors found by findReductor()
1711  LNode* gPrevRedCheck = lTag->getFirstCurrentIdx();
1712  LNode* tempRed;
1713  poly pOne = pOne();
1714  do {
1715  //int timer5 = initTimer();
1716  //startTimer();
1717  //Print("TOP REDUCTION: ");
1718  //pWrite(l->getPoly());
1719  tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1720  //timer5 = getTimer();
1721  //reductionTime = reductionTime + timer5;
1722  // if a reductor for l is found and saved in tempRed
1723  if(NULL != tempRed) {
1724  // if label of reductor is greater than the label of l we have to built a new element
1725  // and add it to sPolyList
1726 
1727  if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1728  // needed sinc pSub destroys the arguments!
1729  //poly temp_poly_l = pInit();
1730  //temp_poly_l = pCopy(l->getPoly());
1731  //Print("VORHER: ");
1732  //pWrite(tempRed->getPoly());
1733  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1734  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1735  rules->insert(tempRed->getIndex(),tempRed->getTerm());
1736  //Print("NACHHER: ");
1737  //pWrite(tempRed->getPoly());
1738  //Print("TEMP: ");
1739  //pWrite(temp);
1740  if(NULL != temp) {
1741  pNorm(temp);
1742  //tempRed->setPoly(temp);
1743  //tempRed->setDel(1);
1744  //rules->insert(tempRed->getIndex(),tempRed->getTerm());
1745  LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld());
1746  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1747  tempRedNew->setDel(1);
1748  sPolyList->insertByLabel(tempRedNew);
1749  }
1750  else {
1751  pDelete(&temp);
1752  reductionsToZero++;
1753  //delete tempRed;
1754  }
1755  }
1756 
1757  // label of reductor is smaller than the label of l, subtract reductor from l and delete the
1758  // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
1759  // after subtraction
1760  else {
1761 
1762  //poly temp_poly_l = pInit();
1763  //temp_poly_l = pCopy(l->getPoly());
1764  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1765  //Print("REDUCER: ");
1766  //pWrite(tempRed->getPoly());
1767  //pWrite(tempRed->getTerm());
1768  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1769  //Print("REDUCED ELEMENT: ");
1770  if(NULL != temp) {
1771  pNorm(temp);
1772  //pWrite(temp);
1773  poly tempNF = kNF(gbPrev,currRing->qideal,temp);
1774  pNorm(tempNF);
1775  if(NULL == tempNF) {
1776  reductionsToZero++;
1777  pDelete(&tempNF);
1778  l->setPoly(NULL);
1779  break;
1780  }
1781  l->setPoly(tempNF);
1782 
1783  gPrevRedCheck = lTag->getFirstCurrentIdx();
1784  }
1785  else {
1786  reductionsToZero++;
1787  pDelete(&temp);
1788  l->setPoly(NULL);
1789  break;
1790  }
1791  }
1792  }
1793  else {
1794  if(NULL != l->getPoly()) {
1795  pNorm(l->getPoly());
1796  //Print("ELEMENT ADDED TO GPREV: ");
1797  //pWrite(l->getPoly());
1798  gPrev->insert(l->getLPolyOld());
1799  //Print("TEMP RED == 0 ");
1800  //pWrite(l->getPoly());
1801  //pWrite(l->getTerm());
1802  //rules->print();
1803  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1804  //Print("LIST OF CRITICAL PAIRS: \n");
1805  //critPairs->print();
1806  }
1807  break;
1808  }
1809  } while(1);
1810 }
1811 
1812 
1813 /*
1814 =====================================================================
1815 subalgorithm to find a possible reductor for the labeled polynomial l
1816 =====================================================================
1817 */
1818 LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag, PList* rejectedGBList) {
1819  // allociation of memory for the possible reductor
1820  //Print("LPOLY: ");
1821  //pWrite(l->getPoly());
1822  poly u = pOne();
1823  poly red;
1824  number nOne = nInit(1);
1825  LNode* temp;
1826  // head term of actual element such that we do not have to call pHead at each new reductor test
1827  poly t = pHead(l->getPoly());
1828  // if l was already checked use the information in gPrevRedCheck such
1829  // that we can start searching for new reducers from this point and
1830  // not from the first element of gPrev with the current index
1831  temp = gPrevRedCheck;
1832  // search for reductors until we are at the end of gPrev resp. at the
1833  // end of the elements of the current index
1834  while(NULL != temp && temp->getIndex() == l->getIndex()) {
1835  // does the head of the element of gPrev divides the head of
1836  // the to be reduced element?
1837  if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) {
1838  // get all the information needed for the following tests
1839  // of the criteria
1840  u = pDivide(t,pHead(temp->getPoly()));
1841  pSetCoeff(u,nOne);
1842  red = ppMult_qq(u,temp->getPoly());
1843  pNorm(red);
1844  // check if both have the same label
1845  if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) {
1846  // passing criterion2 ?
1847  if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1848  // passing criterion1 ?
1849  if(!criterion1(gPrev,u,temp,lTag)) {
1850  gPrevRedCheck = temp->getNext();
1851  LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
1852  return redNode;
1853  }
1854  }
1855  }
1856  if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == 1) {
1857  // passing criterion2 ?
1858  if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1859  // passing criterion1 ?
1860  if(!criterion1(gPrev,u,temp,lTag)) {
1861  poly tempSpoly = ksOldSpolyRedNew(red,l->getPoly());
1862  rules->insert(temp->getIndex(),ppMult_qq(u,temp->getTerm()));
1863  gPrevRedCheck = temp->getNext();
1864  if(NULL != tempSpoly) {
1865  pNorm(tempSpoly);
1866  sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld());
1867  //Print("NEW ONE: ");
1868  //pWrite(tempSpoly);
1869  //Print("HIER\n");
1870  //sPolyList->print();
1871  //sleep(5);
1872  }
1873  }
1874  }
1875  }
1876  }
1877  //Print("AUCH HIER\n");
1878  temp = temp->getNext();
1879  }
1880 
1881 // delete temp;
1882  return NULL;
1883 }
1884 
1885 
1886 
1887 /*
1888 ==========================================================================
1889 MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
1890 OPTIONS: INTEGER "opt" is to be set "0" for F5, "1" for F5R, "2" for F5C
1891 ==========================================================================
1892 */
1893 ideal F5main(ideal id, ring r, int opt, int plus, int termination)
1894 {
1895  switch(opt)
1896  {
1897  case 0:
1898  PrintS("\nComputations are done by the standard F5 Algorithm");
1899  break;
1900  case 1:
1901  PrintS("\nComputations are done by the variant F5R of the F5 Algorithm");
1902  break;
1903  case 2:
1904  PrintS("\nComputations are done by the variant F5C of the F5 Algorithm");
1905  break;
1906  default:
1907  WerrorS("\nThe option can only be set to \"0\", \"1\" or \"2\":\n\"0\": standard F5 Algorithm\n\"1\": variant F5R\n\"2\": variant F5C\nComputations are aborted!\n");
1908  return id;
1909  }
1910 
1911  int timer = initTimer();
1912  startTimer();
1913  int i,j,k,l;
1914  int gbLength;
1915  // 1 polynomial for defining initial labels & further tests
1916  poly ONE = pOne();
1917  poly pOne = pOne();
1918  number nOne = nInit(1);
1919  // tag the first element of index i-1 for criterion 1
1920  //Print("LTAG BEGINNING: %p\n",lTag);
1921 
1922  // DEBUGGING STUFF START
1923  //Print("NUMBER: %d\n",r->N);
1924  /*
1925  int* ev = new int[r->N +1];
1926  for(i=0;i<IDELEMS(id);i++) {
1927  pGetExpV(id->m[i],ev);
1928  //ev2 = pGetExp(id->m[i],1);
1929  pWrite(id->m[i]);
1930  Print("EXP1: %d\n",ev[1]);
1931  Print("EXP2: %d\n",ev[2]);
1932  Print("EXP3: %d\n\n",ev[3]);
1933  Print("SUM: %ld\n\n\n",sumVector(ev,r->N));
1934  }
1935  delete ev;
1936  */
1937  /*DEBUGGING STUFF END */
1938 
1939  // first element in rTag is first element of rules which is NULL RNode,
1940  // this must be done due to possible later improvements
1941  RList* rules = new RList();
1942  //Print("RULES FIRST: %p\n",rules->getFirst());
1943  //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule());
1944  //RTagList* rTag = new RTagList(rules->getFirst());
1945  RTagList* rTag = NULL;
1946  i = 1;
1947  /*for(j=0; j<IDELEMS(id); j++) {
1948  if(NULL != id->m[j]) {
1949  if(pComparePolys(id->m[j],ONE)) {
1950  PrintS("One Polynomial in Input => Computations stopped\n");
1951  ideal idNew = idInit(1,1);
1952  idNew->m[0] = ONE;
1953  return(idNew);
1954  }
1955  }
1956  }*/
1957  ideal idNew = kInterRed(id);
1958  id = idNew;
1959  //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
1960  //idShow(id);
1961  LList* gPrev = new LList(ONE, i, id->m[0]);
1962  LList* reducers = new LList();
1963  //idShow(id);
1964  //Print("%p\n",id->m[0]);
1965  //pWrite(id->m[0]);
1966  //Print("%p\n",gPrev->getFirst()->getPoly());
1967  //pWrite(gPrev->getFirst()->getPoly());
1968 
1969  LTagList* lTag = new LTagList(gPrev->getFirst());
1970  //lTag->insert(gPrev->getFirst());
1971  lTag->setFirstCurrentIdx(gPrev->getFirst());
1972  // computing the groebner basis of the elements of index < actual index
1973  gbLength = gPrev->getLength();
1974  //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
1975  ideal gbPrev = idInit(gbLength,1);
1976  // initializing the groebner basis of elements of index < actual index
1977  gbPrev->m[0] = gPrev->getFirst()->getPoly();
1978  //idShow(gbPrev);
1979  //idShow(currRing->qideal);
1980  for(i=2; i<=IDELEMS(id); i++) {
1981  LNode* gPrevTag = gPrev->getLast();
1982  //Print("Last POlynomial in GPREV: ");
1983  //Print("%p\n",gPrevTag);
1984  //pWrite(gPrevTag->getPoly());
1985  Print("Iteration: %d\n\n",i);
1986  gPrev = F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
1987  //Print("%d\n",gPrev->count(gPrevTag->getNext()));
1988  //Print("%d\n",gPrev->getLength());
1989  //Print("____________________________________ITERATION STEP DONE________________________________________\n");
1990 
1991  // DEBUGGING STUFF
1992  LNode* temp = gPrev->getFirst();
1993 
1994 
1995  /////////////////////////////////////////////////////////////////////////////////
1996  // //
1997  // one needs to choose one of the following 3 implementations of the algorithm //
1998  // F5,F5R or F5C //
1999  // //
2000  /////////////////////////////////////////////////////////////////////////////////
2001 
2002 
2003  //
2004  // standard "F5"
2005  //
2006  if(0 == opt) {
2007  if(gPrev->getLength() > gbLength) {
2008  if(i < IDELEMS(id)) {
2009  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2010  LNode* temp = gPrevTag;
2011  int counter = 0;
2012  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2013  temp = temp->getNext();
2014  if(0 == temp->getDel()) {
2015  counter++;
2016  gbAdd->m[j] = temp->getPoly();
2017  }
2018  }
2019  gbPrev = idAdd(gbPrev,gbAdd);
2020  }
2021  else {
2022  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2023  LNode* temp = gPrevTag;
2024  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2025  temp = temp->getNext();
2026  gbAdd->m[j] = temp->getPoly();
2027  }
2028  gbPrev = idAdd(gbPrev,gbAdd);
2029  }
2030  //if(i == IDELEMS(id)) {
2031  // ideal tempId = kInterRed(gbPrev);
2032  // gbPrev = tempId;
2033  //}
2034  }
2035  gbLength = gPrev->getLength();
2036  }
2037 
2038 
2039  //
2040  // "F5R"
2041  //
2042  if(1 == opt) {
2043  if(gPrev->getLength() > gbLength) {
2044  if(i < IDELEMS(id)) {
2045  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2046  LNode* temp = gPrevTag;
2047  int counter = 0;
2048  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2049  temp = temp->getNext();
2050  if(0 == temp->getDel()) {
2051  counter++;
2052  gbAdd->m[j] = temp->getPoly();
2053  }
2054  }
2055  gbPrev = idAdd(gbPrev,gbAdd);
2056  }
2057  else {
2058  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2059  LNode* temp = gPrevTag;
2060  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2061  temp = temp->getNext();
2062  gbAdd->m[j] = temp->getPoly();
2063  }
2064  gbPrev = idAdd(gbPrev,gbAdd);
2065  }
2066  // interreduction stuff
2067  // comment this out if you want F5 instead of F5R
2068  if(i<IDELEMS(id)) {
2069  ideal tempId = kInterRed(gbPrev);
2070  gbPrev = tempId;
2071  }
2072  }
2073  gbLength = gPrev->getLength();
2074  }
2075 
2076 
2077  //
2078  // "F5C"
2079  //
2080  if(2 == opt) {
2081  if(gPrev->getLength() > gbLength) {
2082  if(i < IDELEMS(id)) {
2083  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2084  LNode* temp = gPrevTag;
2085  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2086  temp = temp->getNext();
2087  gbAdd->m[j] = temp->getPoly();
2088  }
2089  gbPrev = idAdd(gbPrev,gbAdd);
2090  }
2091  else {
2092  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2093  LNode* temp = gPrevTag;
2094  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2095  temp = temp->getNext();
2096  gbAdd->m[j] = temp->getPoly();
2097  }
2098  gbPrev = idAdd(gbPrev,gbAdd);
2099  }
2100  if(i<IDELEMS(id)) {
2101  ideal tempId = kInterRed(gbPrev);
2102  gbPrev = tempId;
2103  delete gPrev;
2104  delete rules;
2105  gPrev = new LList(pOne,1,gbPrev->m[0]);
2106  gPrev->insert(pOne,1,gbPrev->m[1]);
2107  rules = new RList();
2108  //rTag = new RTagList(rules->getFirst());
2109  for(k=2; k<IDELEMS(gbPrev); k++) {
2110  gPrev->insert(pOne,k+1,gbPrev->m[k]);
2111  /*
2112  for(l=0; l<k; l++) {
2113  }
2114  rTag->insert(rules->getFirst());
2115  */
2116  }
2117  }
2118  gbLength = gPrev->getLength();
2119  }
2120  }
2121 
2122 
2123  }
2124  timer = getTimer();
2125  //Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime);
2126  Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero);
2127  Print("Number of rules: %d\n",numberOfRules);
2128  Print("Number of rejected F5-critical pairs:%d\n",numberRejectedF5CriticalPairs);
2129  Print("Number of reductions: %d\n",numberOfReductions);
2130  Print("Elements not added to G: %d\n",notInG);
2131  Print("Highest Degree during computations: %d\n",highestDegree);
2132  Print("Degree d_0 in F5+: %d\n",highestDegreeGBCriticalPair);
2133  Print("Time for computations: %d/1000 seconds\n",timer);
2134  Print("Number of elements in gb: %d\n",IDELEMS(gbPrev));
2135  //LNode* temp = gPrev->getFirst();
2136  //while(NULL != temp) {
2137  // pWrite(temp->getPoly());
2138  // temp = temp->getNext();
2139  // }
2140  //gPrev->print();
2141  //delete lTag;
2142  delete rTag;
2143  delete gPrev;
2144  notInG = 0;
2145  numberOfRules = 0;
2146  reductionsToZero = 0;
2147  highestDegree = 0;
2149  reductionTime = 0;
2150  spolsTime = 0;
2151  numberUselessPairs = 0;
2152  numberUsefulPairs = 0;
2154  numberOfReductions = 0;
2155  numberOfSpolys = 0;
2156  return(gbPrev);
2157 
2158 
2159 }
2160 
2161 #endif
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:495
int notInG
Definition: f5gb.cc:35
int highestDegreeGBCriticalPair
Definition: f5gb.cc:45
int reductionsToZero
Definition: f5gb.cc:37
#define ppMult_qq(p, q)
Definition: polys.h:191
#define pDivide(a, b)
Definition: polys.h:275
int numberUselessPairs
Definition: f5gb.cc:43
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
#define pSetm(p)
Definition: polys.h:253
LNode * getNext()
Definition: f5lists.cc:322
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:467
void qsortDegree(poly *left, poly *right)
Definition: f5gb.cc:55
#define Print
Definition: emacs.cc:83
poly getT2()
Definition: f5lists.cc:869
void insert(LNode *l)
Definition: f5lists.cc:629
int numberOfSpolys
Definition: f5gb.cc:48
long getDeg()
Definition: f5data.h:162
void findReducers(LNode *l, LList *sPolyList, ideal gbPrev, LList *gPrev, LList *reducers, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, int termination, PList *rejectedGBList, int plus)
searches for reducers of temp similar to the symbolic preprocessing of F4 and divides them into a "g...
Definition: f5gb.cc:1206
void insert(LPolyOld *lp)
Definition: f5lists.cc:458
void insert(poly p)
Definition: f5lists.cc:81
Compatiblity layer for legacy polynomial operations (over currRing)
int getLength()
Definition: f5lists.cc:528
CPairOld * getData()
Definition: f5lists.cc:821
bool getDel()
Definition: f5lists.cc:352
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
poly getTerm()
Definition: f5lists.cc:336
bool bad
Definition: facFactorize.cc:65
RuleOld * getRuleOld()
Definition: f5lists.cc:344
poly getT1()
Definition: f5lists.cc:861
Definition: f5lists.h:313
structure of RuleOlds(i.e.
Definition: f5data.h:232
void setFirstCurrentIdx(LNode *l)
Definition: f5lists.cc:634
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:480
bool arrisCheck(CNode *first, LNode *firstGCurr, long arrideg)
Definition: f5gb.cc:386
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1430
#define pLcm(a, b, m)
Definition: polys.h:277
void pWrite(poly p)
Definition: polys.h:290
poly getLp1Term()
Definition: f5lists.cc:845
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
poly getPoly()
Definition: f5lists.cc:332
LList * F5inc(int i, poly f_i, LList *gPrev, LList *reducers, ideal gbPrev, poly ONE, LTagList *lTag, RList *rules, RTagList *rTag, int plus, int termination)
Definition: f5gb.cc:134
int degreeBound
Definition: f5gb.cc:41
int numberOfReductions
Definition: f5gb.cc:47
void computeSPols(CNode *first, RTagList *rTag, RList *rules, LList *sPolyList, PList *rejectedGBList)
Definition: f5gb.cc:848
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:485
CNode * getMinDeg()
Definition: f5lists.cc:953
RNode * getNext()
Definition: f5lists.cc:1024
poly getLp1Poly()
Definition: f5lists.cc:837
poly getLp2Poly()
Definition: f5lists.cc:841
RuleOld * getTestedRuleOld()
Definition: f5lists.cc:881
class PList of lists of PNodes
Definition: f5lists.h:50
#define pIter(p)
Definition: monomials.h:44
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
int spolsTime
Definition: f5gb.cc:39
int numberOfRules
Definition: f5gb.cc:36
const ring r
Definition: syzextra.cc:208
int getLp1Index()
Definition: f5lists.cc:853
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
Definition: f5gb.cc:445
Definition: f5lists.h:65
Definition: f5lists.h:232
int j
Definition: myNF.cc:70
int reductionTime
Definition: f5gb.cc:38
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
LNode * getFirstCurrentIdx()
Definition: f5lists.cc:646
poly getTerm()
Definition: f5data.h:90
bool compareMonomials(int *m1, int **m2, int numberOfRules, int k)
compares monomials, i.e.
Definition: f5gb.cc:112
poly getRuleOldTerm()
Definition: f5lists.cc:1036
#define pDivideM(a, b)
Definition: polys.h:276
RuleOld * getRuleOld()
Definition: f5lists.cc:1028
class of labeled polynomials
Definition: f5data.h:28
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3542
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
Definition: f5gb.cc:1818
LPolyOld * getLPolyOld()
Definition: f5lists.cc:327
int getRuleOldIndex()
Definition: f5lists.cc:1032
P bucket
Definition: myNF.cc:79
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:618
LPolyOld * getAdLp2()
Definition: f5lists.cc:833
long sumVector(int *v, int k)
builds the sum of the entries of the exponent vectors, i.e.
Definition: f5gb.cc:96
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
int numberUsefulPairs
Definition: f5gb.cc:42
#define pOne()
Definition: polys.h:297
static unsigned pLength(poly a)
Definition: p_polys.h:189
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:690
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
#define IDELEMS(i)
Definition: simpleideals.h:24
int computeUsefulMinDeg(CNode *first)
Definition: f5gb.cc:832
void setPoly(poly p)
Definition: f5lists.cc:357
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1063
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:679
void insert(CPairOld *c)
Definition: f5lists.cc:939
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
void setDel(bool d)
Definition: f5lists.cc:373
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define pDeg(A)
Definition: f5gb.cc:33
#define NULL
Definition: omList.c:10
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition: polys.h:138
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1135
Definition: f5lists.h:127
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
CNode * getNext()
Definition: f5lists.cc:825
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
void insert(RuleOld *r)
Definition: f5lists.cc:1084
bool getDel()
Definition: f5lists.cc:877
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
Definition: f5lists.cc:494
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
#define pDelete(p_ptr)
Definition: polys.h:169
int highestDegree
Definition: f5gb.cc:40
int numberUsefulPairsMinDeg
Definition: f5gb.cc:44
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
Definition: f5gb.cc:557
int numberRejectedF5CriticalPairs
Definition: f5gb.cc:46
int initTimer()
Definition: timer.cc:69
bool checkDGB(LList *gPrev)
Definition: f5gb.cc:303
void setFirst(LNode *l)
Definition: f5lists.cc:532
END_NAMESPACE const void * p2
Definition: syzextra.cc:202
int getLp2Index()
Definition: f5lists.cc:857
ideal idAdd(ideal h1, ideal h2)
h1 + h2
Definition: ideals.h:68
LPolyOld * getAdLp1()
Definition: f5lists.cc:829
int degree(const CanonicalForm &f)
polyrec * poly
Definition: hilb.h:10
Definition: f5lists.h:290
int getIndex()
Definition: f5lists.cc:340
LNode * getFirst()
Definition: f5lists.cc:520
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:193
void newReduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, LList *reducers, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, int termination, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1139
int getTimer()
Definition: timer.cc:97
void startTimer()
Definition: timer.cc:82
#define nInit(i)
Definition: numbers.h:24
int kBucketCanonicalize(kBucket_pt bucket)
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
RNode * getFirst()
Definition: f5lists.cc:1092
static int sign(int x)
Definition: ring.cc:3328
#define pLmEqual(p1, p2)
Definition: polys.h:111
int l
Definition: cfEzgcd.cc:94
LNode * getLast()
Definition: f5lists.cc:524
CNode * getFirst()
Definition: f5lists.cc:947
void topReduction(LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1708
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168
ideal F5main(ideal id, ring r, int opt, int plus, int termination)
Definition: f5gb.cc:1893
structure of labeled critical pairs
Definition: f5data.h:123