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