My Project  UNKNOWN_GIT_VERSION
Functions
f5gb.h File Reference
#include "kernel/GBEngine/f5data.h"
#include "kernel/GBEngine/f5lists.h"

Go to the source code of this file.

Functions

void qsortDegree (poly *left, poly *right)
 
long sumVector (int *v, int k)
 
bool compareMonomials (int *m1, int **m2, int numberOfRuleOlds)
 
LListF5inc (int i, poly f_i, LList *gPrev, LList *reducers, ideal gbPrev, poly ONE, LTagList *lTag, RList *rules, RTagList *rTag, int plus, int termination)
 
void criticalPair (LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList, int plus)
 
bool checkDGB (LList *gPrev)
 
bool arrisCheck (CNode *first, LNode *firstGCurr, long arrisdeg)
 
void criticalPair2 (LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList)
 
bool criterion1 (LList *gPrev, poly t, LNode *l, LTagList *lTag)
 
bool criterion2 (int idx, poly t, LNode *l, RList *RuleOlds, RTagList *rTag)
 
bool criterion2 (poly t, LPolyOld *l, RList *RuleOlds, RuleOld *testedRuleOld)
 
int computeUsefulMinDeg (CNode *first)
 
void computeSPols (CNode *first, RTagList *rTag, RList *RuleOlds, LList *sPolyList, PList *rejectedGBList)
 
void reduction (LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
 
void newReduction (LList *sPolyList, CListOld *critPairs, LList *gPrev, LList *reducers, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, int termination, PList *rejectedGBList, int plus)
 
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)
 
void topReduction (LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
 
LNodefindReductor (LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag)
 
ideal F5main (ideal i, ring r, int opt, int plus, int termination)
 

Function Documentation

◆ arrisCheck()

bool arrisCheck ( CNode first,
LNode firstGCurr,
long  arrisdeg 
)

Definition at line 383 of file f5gb.cc.

383  {
384  CNode* temp = first;
385 
386  //product criterion check
387  while(NULL != temp) {
388  if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) {
389  return 0;
390  }
391  temp = temp->getNext();
392  }
393 
394  // chain criterion
395  LNode* tempPoly = firstGCurr;
396  while(NULL != tempPoly) {
397  LNode* tempPoly2 = tempPoly->getNext();
398  while(NULL != tempPoly2) {
399  number nOne = nInit(1);
400  poly lcm = pOne();
401  pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm);
402  pSetCoeff(lcm,nOne);
403  pSetm(lcm);
404  if(pDeg(lcm) > arrideg) {
405  LNode* tempPoly3 = firstGCurr;
406  while(NULL != tempPoly3) {
407  if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) {
408  poly lcm1 = pOne();
409  poly lcm2 = pOne();
410  pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1);
411  pSetCoeff(lcm1,nOne);
412  pSetm(lcm1);
413  pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2);
414  pSetCoeff(lcm2,nOne);
415  pSetm(lcm2);
416  if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) {
417  return 0;
418  }
419  }
420  tempPoly3 = tempPoly3->getNext();
421  }
422  }
423  tempPoly2 = tempPoly2->getNext();
424  }
425  tempPoly = tempPoly->getNext();
426  }
427  return 1;
428 }

◆ checkDGB()

bool checkDGB ( LList gPrev)

Definition at line 300 of file f5gb.cc.

300  {
301  Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly()));
302  LNode* temp = gPrev->getFirst();
303  LNode* temp2;
304  bool isDGb = 0;
305  // construct the d-GB gb
306  ideal gb = idInit(gPrev->getLength(),1);
307  for(int j=0;j<=gPrev->getLength()-1;j++) {
308  gb->m[j] = temp->getPoly();
309  pWrite(gb->m[j]);
310  temp = temp->getNext();
311  }
312  /*
313  Kstd1_deg = pDeg(gPrev->getLast()->getPoly());
314  BITSET save = test;
315  test |= Sy_bit(OPT_DEGBOUND);
316  kStd();
317  test = save;
318  */
319  temp = gPrev->getFirst();
320  while(NULL != temp) {
321  temp2 = temp->getNext();
322  number nOne = nInit(1);
323  poly lcm = pOne();
324  poly sp = pOne();
325  while(NULL != temp2) {
326  pLcm(temp->getPoly(),temp2->getPoly(),lcm);
327  pSetCoeff(lcm,nOne);
328  pSetm(lcm);
329  PrintS("LCM: ");
330  pWrite(lcm);
331  if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) {
332  poly u1 = pOne();
333  poly u2 = pOne();
334  u1 = pMDivide(lcm,temp->getPoly());
335  pSetCoeff(u1,nOne);
336  u2 = pMDivide(lcm,temp2->getPoly());
337  pSetCoeff(u2,nOne);
338  sp = ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()),
339  ppMult_qq(u2,temp2->getPoly()));
340  pNorm(sp);
341 
342  poly reducer = pOne();
343  //reducer = gb->m[0];
344  int i = 0;
345  pWrite(pHead(sp));
346 
347  while(i<IDELEMS(gb)) {
348  reducer = gb->m[i];
349  if(pDivisibleBy(reducer,pHead(sp))) {
350  poly uReducer = pOne();
351  uReducer = pMDivide(lcm,reducer);
352  pSetCoeff(uReducer,nOne);
353  sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer));
354  //pNorm(tempSP);
355  //sp = tempSP;
356  pNorm(sp);
357  pWrite(sp);
358  i = 0;
359  }
360  else {
361  i++;
362  }
363  }
364 
365  pWrite(pHead(sp));
366  }
367  temp2 = temp2->getNext();
368  }
369  temp = temp->getNext();
370  }
371  PrintS("------------------\n");
372  return isDGb;
373 }

◆ compareMonomials()

bool compareMonomials ( int *  m1,
int **  m2,
int  numberOfRuleOlds 
)

compare monomials, i.e. divisibility tests for criterion 1 and criterion 2

◆ computeSPols()

void computeSPols ( CNode first,
RTagList rTag,
RList RuleOlds,
LList sPolyList,
PList rejectedGBList 
)
inline

Definition at line 845 of file f5gb.cc.

845  {
846  CNode* temp = first;
847  //Print("\nDegree: %d\n",temp->getData()->getDeg());
848  // only GB-critical pairs are computed
849  //while(NULL != temp && temp->getDel()) {
850  // temp = temp->getNext();
851  //}
852  //if(temp->getData()->getDeg() == 11) {
853  // Print("PAIRS OF DEG 11:\n");
854  //}
855  RList* f5rules = new RList();
856  CListOld* f5pairs = new CListOld();
857  poly sp = pInit();
858  number sign = nInit(-1);
859  //Print("###############################IN SPOLS##############################\n");
860  //first->print();
861 /*
862  * first of all: do everything for GB critical pairs
863  */
864  while(NULL != temp) {
865  // if(temp->getData()->getDeg() == 11) {
866  //Print("--------------------------\n");
867  //Print("redundant? %d\n",temp->getDel());
868  //pWrite(pHead(temp->getLp1Poly()));
869  //Print("redundant: %d\n",temp->getAdLp1()->getDel());
870  //pWrite(pHead(temp->getLp2Poly()));
871  //Print("redundant: %d\n",temp->getAdLp2()->getDel());
872  //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
873  // sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
874  // ppMult_qq(temp->getT2(),temp->getLp2Poly()));
875  //Print("BEGIN SPOLY2\n====================\n");
876  // pNorm(sp);
877  // pWrite(pHead(sp));
878  //Print("--------------------------\n");
879  //}
880  if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
881  //if(temp->getDel() == 0 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
882  if(temp->getLp2Index() == temp->getLp1Index()) {
883  if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
884  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
885  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
886  pNorm(sp);
887  if(NULL == sp) {
889  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
890  numberOfRules++;
891  pDelete(&sp);
892  }
893  else {
894  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
895  numberOfRules++;
896  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
897  //Print("INSERTED\n");
898  numberOfSpolys++;
899  }
900  }
901  else {
902  if(highestDegreeGBCriticalPair < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
904  }
905  rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
906  //Print("rejected!\n");
907 
908  //Print("CRITERION 2 in SPOLS 2nd generator\n");
909  }
910  }
911  else {
912  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
913  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
914  //Print("BEGIN SPOLY2\n====================\n");
915  pNorm(sp);
916  //pWrite(sp);
917  //Print("END SPOLY2\n====================\n");
918  if(NULL == sp) {
920  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
921  numberOfRules++;
922  pDelete(&sp);
923  }
924  else {
925  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
926  numberOfRules++;
927  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
928  //Print("INSERTED\n");
929  numberOfSpolys++;
930  }
931  }
932  }
933  /*
934  if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
935  //Print("rejected!\n");
936  rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
937  }
938 
939 
940  if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
941  if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
942  highestDegree = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
943  }
944  if(temp->getLp2Index() == temp->getLp1Index()) {
945  if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
946  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
947  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
948  pNorm(sp);
949  if(NULL == sp) {
950  reductionsToZero++;
951  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
952  numberOfRules++;
953  pDelete(&sp);
954  }
955  else {
956  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
957  numberOfRules++;
958 
959 
960  // save the address of the rule again in a different
961  // list
962 
963  f5rules->insert(rules->getFirst()->getRuleOld());
964  f5pairs->insertWithoutSort(temp->getData());
965  ///////////////////////////////////////
966 
967  //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
968  }
969  }
970  }
971  else {
972  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
973  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
974  //Print("BEGIN SPOLY2\n====================\n");
975  pNorm(sp);
976  //pWrite(sp);
977  //Print("END SPOLY2\n====================\n");
978  if(NULL == sp) {
979  reductionsToZero++;
980  //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
981  numberOfRules++;
982  pDelete(&sp);
983  }
984  else {
985  rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
986  numberOfRules++;
987  // save the address of the rule again in a different
988  // list
989 
990  f5rules->insert(rules->getFirst()->getRuleOld());
991  f5pairs->insertWithoutSort(temp->getData());
992  ///////////////////////////////////////
993  //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
994  // numberOfSpolys++;
995  }
996  }
997  }
998  // the following else is not needed at all as we are checking
999  // F5-critical pairs in this step
1000  /*
1001  else {
1002  if(!temp->getDel()) {
1003  rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1004  }
1005 
1006  }
1007  */
1008 
1009  temp = temp->getNext();
1010 
1011  }
1012 
1013  /*
1014  temp = f5pairs->getFirst();
1015  RNode* tempRule = f5rules->getFirst();
1016  int howmany = 1;
1017  while(NULL != temp) {
1018  //Print("RULE: ");
1019  //pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
1020  sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
1021  ppMult_qq(temp->getT2(),temp->getLp2Poly()));
1022  pNorm(sp);
1023  if(rejectedGBList->check(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())))) { //|| (temp->getData()->getDeg() == 10 && howmany == 2)) {
1024  if((temp->getData()->getDeg() == 10) && (howmany == 2)) {
1025  //Print("HIER DRIN IM SAFTLADEN\n");
1026  }
1027  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
1028  numberOfSpolys++;
1029  howmany++;
1030  }
1031  else {
1032  numberRejectedF5CriticalPairs++;
1033  howmany++;
1034  if(numberRejectedF5CriticalPairs < -1) { // ||
1035  }
1036  else {
1037  //numberRejectedF5CriticalPairs == 7) {
1038  /*
1039  PrintS("--------------------------------- rejected F5-critical pair-------------------------------------\n");
1040  pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1041  PrintS("Label: ");
1042  pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
1043  Print("%d\n",temp->getDel());
1044  PrintS("Comes from:\n ");
1045  pWrite(pHead(temp->getLp1Poly()));
1046  PrintS("Label: ");
1047  pWrite(temp->getLp1Term());
1048  Print("%d\n",temp->getLp1Index());
1049  pWrite(pHead(temp->getLp2Poly()));
1050  PrintS("Label: ");
1051  pWrite(temp->getLp2Term());
1052  Print("%d\n",temp->getLp2Index());
1053  //Print("--------------------------------------LIST OF GB PAIRS REJECTED-----------------------------------------\n");
1054  //rejectedGBList->print();
1055  PrintS("--------------------------------------------------------------------------------------------------------\n");
1056  //if(temp->getLp1Index() < 7) {
1057  sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
1058 
1059  //}
1060  //numberOfSpolys++;
1061  }
1062  //pSetExp(tempRule->getRuleOld()->getTerm(),1,1000);
1063  }
1064  temp = temp->getNext();
1065  tempRule = tempRule->getNext();
1066 
1067  }
1068  */
1069  // these critical pairs can be deleted now as they are either useless for further computations or
1070  // already saved as an S-polynomial to be reduced in the following
1071  delete first;
1072 //Print("NUMBER SPOLYS: %d\n", numberOfSpolys);
1073 //Print("SPOLY LIST: \n");
1074 //LNode* tempSpoly = sPolyList->getFirst();
1075 //if(NULL != tempSpoly) {
1076 // pWrite(pHead(tempSpoly->getPoly()));
1077 // tempSpoly = tempSpoly->getNext();
1078 //}
1079 //Print("-----SP------\n");
1080 //else {
1081 // Print("EMPTY SPOLYLIST!\n");
1082 //}
1083 }

◆ computeUsefulMinDeg()

int computeUsefulMinDeg ( CNode first)

Definition at line 829 of file f5gb.cc.

829  {
830  CNode* temp = first;
831  int numberUsefulPairsMinDeg = 0;
832  while(NULL != temp) {
833  if(!temp->getDel()) {
835  }
836  temp = temp->getNext();
837  }
839 }

◆ criterion1()

bool criterion1 ( LList gPrev,
poly  t,
LNode l,
LTagList lTag 
)
inline

Definition at line 615 of file f5gb.cc.

615  {
616  // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
617  int idx = l->getIndex();
618  int i;
619  if(idx == 1) {
620  //Print("HIER\n");
621  return false;
622  }
623  else {
624  LNode* testNode = gPrev->getFirst();
625  // save the monom t1*label_term(l) as it is tested various times in the following
626  poly u1 = ppMult_qq(t,l->getTerm());
627  //Print("------------------------------IN CRITERION 1-----------------------------------------\n");
628  //Print("TESTED ELEMENT: ");
629  //pWrite(l->getPoly());
630  //pWrite(l->getTerm());
631  //pWrite(ppMult_qq(t,l->getTerm()));
632  //Print("%d\n\n",l->getIndex());
633  while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) {
634  //pWrite(testNode->getPoly());
635  //Print("%d\n",testNode->getIndex());
636  if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
637  //Print("Criterion 1 NOT passed!\n");
638  if(idx != gPrev->getLast()->getIndex()) {
639  //Print("DOCH!\n");
640  }
641  return true;
642  }
643  //pWrite(testNode->getNext()->getPoly());
644  testNode = testNode->getNext();
645  }
646  /*
647  ideal testId = idInit(idx-1,1);
648  for(i=0;i<idx-1;i++) {
649  testId->m[i] = pHead(testNode->getPoly());
650  testNode = testNode->getNext();
651  }
652  poly temp = kNF(testId,currRing->qideal,u1);
653  //pWrite(temp);
654  for(i=0;i<IDELEMS(testId);i++) {
655  testId->m[i] = NULL;
656  }
657  idDelete(&testId);
658  if(NULL == temp) {
659  //if(l->getIndex() != gPrev->getFirst()->getIndex()) {
660  // Print("----------------------------Criterion1 not passed----------------------------------\n");
661  //}
662  return true;
663  }
664  */
665  return false;
666  }
667 }

◆ criterion2() [1/2]

bool criterion2 ( int  idx,
poly  t,
LNode l,
RList RuleOlds,
RTagList rTag 
)
inline

Definition at line 676 of file f5gb.cc.

676  {
677  //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n");
678  /*
679  PrintS("RULES: \n");
680  RNode* tempR = rules->getFirst();
681  Print("%p\n",tempR);
682  int i = 1;
683  while(NULL != tempR) {
684  Print("ADDRESS OF %d RNODE: %p\n",i,tempR);
685  Print("ADDRESS OF RULE: %p\n",tempR->getRule());
686  pWrite(tempR->getRuleTerm());
687  Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
688  Print("%d\n\n",tempR->getRuleIndex());
689  tempR = tempR->getNext();
690  i++;
691  }
692  //Print("TESTED ELEMENT: ");
693  //pWrite(l->getPoly());
694  //pWrite(l->getTerm());
695  //pWrite(ppMult_qq(t,l->getTerm()));
696  //Print("%d\n\n",l->getIndex());
697  */
698 // start at the previously added element to gPrev, as all other elements will have the same index for sure
699  if(idx > l->getIndex()) {
700  return false;
701  }
702 
703  RNode* testNode; // = new RNode();
704  testNode = rules->getFirst();
705  /*
706  if(NULL == rTag->getFirst()) {
707  if(NULL != rules->getFirst()) {
708  testNode = rules->getFirst();
709  }
710  else {
711  return false;
712  }
713  }
714 
715  else {
716 
717  if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
718  testNode = rules->getFirst();
719  }
720  else {
721  //Print("HIER\n");
722  //Print("DEBUG\n");
723  //Print("L INDEX: %d\n",l->getIndex());
724  *-------------------------------------
725  * TODO: WHEN INTERREDUCING THE GB THE
726  * INDEX OF THE PREVIOUS ELEMENTS
727  * GETS HIGHER!
728  *-----------------------------------*
729  //testNode = rules->getFirst();
730  testNode = rTag->get(l->getIndex());
731  if(NULL == testNode) {
732  testNode = rules->getFirst();
733  }
734  //Print("TESTNODE ADDRESS: %p\n",testNode);
735  }
736  }
737  */
738  //testNode = rules->getFirst();
739  // save the monom t1*label_term(l) as it is tested various times in the following
740  poly u1 = ppMult_qq(t,l->getTerm());
741  // first element added to rTag was NULL, check for this
742  //Print("%p\n",testNode->getRule());
743  // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
744  //Print("TESTNODE: %p\n",testNode);
745  //pWrite(testNode->getRuleTerm());
746  if(NULL != testNode ) {
747  //pWrite(testNode->getRuleTerm());
748  }
749  if(NULL != testNode) {
750  if(testNode->getRuleOld() == l->getRuleOld()) {
751  //Print("%p\n%p\n",testNode->getRule(),l->getRule());
752  //Print("EQUAL\n");
753  }
754  else {
755  //Print("NOT EQUAL\n");
756  }
757  }
758  while(NULL != testNode && testNode->getRuleOld() != l->getRuleOld()
759  && l->getIndex() == testNode->getRuleOldIndex()) {
760  //Print("%p\n",testNode);
761  //pWrite(testNode->getRuleTerm());
762  //pWrite(t);
763  //pWrite(l->getTerm());
764  //pWrite(u1);
765  //Print("%d\n",testNode->getRuleIndex());
766  if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
767  //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
768  //Print("INDEX: %d\n",l->getIndex());
769  pDelete(&u1);
770  //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
771  return true;
772  }
773  testNode = testNode->getNext();
774  }
775  //delete testNode;
776  pDelete(&u1);
777  //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
778  return false;
779 }

◆ criterion2() [2/2]

bool criterion2 ( poly  t,
LPolyOld l,
RList RuleOlds,
RuleOld testedRuleOld 
)
inline

Definition at line 788 of file f5gb.cc.

788  {
789  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
790  //Print("LAST RuleOld TESTED: %p",testedRuleOld);
791  /*
792  PrintS("RULES: \n");
793  RNode* tempR = rules->getFirst();
794  while(NULL != tempR) {
795  pWrite(tempR->getRuleTerm());
796  Print("%d\n\n",tempR->getRuleIndex());
797  tempR = tempR->getNext();
798  }
799  //Print("TESTED ELEMENT: ");
800  //pWrite(l->getPoly());
801  //pWrite(l->getTerm());
802  //pWrite(ppMult_qq(t,l->getTerm()));
803  //Print("%d\n\n",l->getIndex());
804  */
805 // start at the previously added element to gPrev, as all other elements will have the same index for sure
806  RNode* testNode = rules->getFirst();
807  // save the monom t1*label_term(l) as it is tested various times in the following
808  poly u1 = ppMult_qq(t,l->getTerm());
809  // first element added to rTag was NULL, check for this
810  while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) {
811  //pWrite(testNode->getRuleTerm());
812  if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
813  //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
814  //Print("INDEX: %d\n",l->getIndex());
815  pDelete(&u1);
816  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
817  return true;
818  }
819  testNode = testNode->getNext();
820  }
821  pDelete(&u1);
822  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
823  return false;
824 }

◆ criticalPair()

void criticalPair ( LList gPrev,
CListOld critPairs,
LTagList lTag,
RTagList rTag,
RList RuleOlds,
PList rejectedGBList,
int  plus 
)
inline

Definition at line 442 of file f5gb.cc.

442  {
443  //Print("IN CRITPAIRS\n");
444  // initialization for usage in pLcm()
445  number nOne = nInit(1);
446  LNode* newElement = gPrev->getLast();
447  LNode* temp = gPrev->getFirst();
448  poly u1 = pOne();
449  poly u2 = pOne();
450  poly lcm = pOne();
451  poly t = pHead(newElement->getPoly());
452  RuleOld* testedRuleOld = NULL;
453  //Print("NEW: ");
454  //pWrite(newElement->getPoly());
455  //Print("ADDRESS: %p",newElement);
456  if(NULL != rules->getFirst()) {
457  testedRuleOld = rules->getFirst()->getRuleOld();
458  }
459  // computation of critical pairs
460  while( gPrev->getLast() != temp) {
461  //Print("TEMP: ");
462  //pWrite(pHead(temp->getPoly()));
463  //Print("ADDRESS: %p",temp);
464  pLcm(newElement->getPoly(), temp->getPoly(), lcm);
465  pSetCoeff(lcm,nOne);
466  // computing factors u2 for new labels
467  u1 = pMDivide(lcm,t);
468  if(NULL == u1) {
469  break;
470  }
471  pSetCoeff(u1,nOne);
472  u2 = pMDivide(lcm,temp->getPoly());
473  pSetCoeff(u2,nOne);
474  int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly())));
475  // testing both new labels by the F5 Criterion
476  if(!temp->getDel()) {
477  if(plus && highestDegreeGBCriticalPair < degree) {
479  }
480  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
481  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
482  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
483  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
484  // label as first element in the CPairOld
485  if(newElement->getIndex() == temp->getIndex() &&
486  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
487  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
488  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);
489  critPairs->insert(cp);
490  // counting the number of useful pairs
492  }
493  else {
494  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
495  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);
496  critPairs->insert(cp);
497  // counting the number of useful pairs
499  }
500  }
501  else {
502  // TODO: generate a list of lcms of rejected GB critical pairs and
503  // check F5 critical pairs with it at their creation
504  //Print("--------------------------------------------------------------------\n");
505  //Print("--------------------------------------------------------------------\n");
506  pSetm(lcm);
507  rejectedGBList->insert(lcm);
508  //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n");
509  //pWrite(lcm);
510  //Print("--------------------------------------------------------------------\n");
511  //rejectedGBList->print();
512  }
513  }
514  else {
515  //Print("LABEL: ");
516  //pWrite(ppMult_qq(u1,newElement->getTerm()));
517  //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
518  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
519  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
520  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
521  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
522  // label as first element in the CPairOld
523  if(newElement->getIndex() == temp->getIndex() &&
524  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
525  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
526  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
527  critPairs->insert(cp);
529  }
530  else {
531  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
532  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
533  critPairs->insert(cp);
535  }
536  }
537  //}
538  }
539  temp = temp->getNext();
540  }
541 }

◆ criticalPair2()

void criticalPair2 ( LList gPrev,
CListOld critPairs,
LTagList lTag,
RTagList rTag,
RList RuleOlds,
PList rejectedGBList 
)
inline

Definition at line 554 of file f5gb.cc.

554  {
555  //Print("IN CRITPAIRS\n");
556  // initialization for usage in pLcm()
557  number nOne = nInit(1);
558  LNode* newElement = gPrev->getLast();
559  LNode* temp = gPrev->getFirst();
560  poly u1 = pOne();
561  poly u2 = pOne();
562  poly lcm = pOne();
563  poly t = pHead(newElement->getPoly());
564  RuleOld* testedRuleOld = NULL;
565  if(NULL != rules->getFirst()) {
566  testedRuleOld = rules->getFirst()->getRuleOld();
567  }
568  // computation of critical pairs
569  while( gPrev->getLast() != temp) {
570  pLcm(newElement->getPoly(), temp->getPoly(), lcm);
571  pSetCoeff(lcm,nOne);
572  // computing factors u2 for new labels
573  u1 = pMDivide(lcm,t);
574  if(NULL == u1) {
575  break;
576  }
577  pSetCoeff(u1,nOne);
578  u2 = pMDivide(lcm,temp->getPoly());
579  pSetCoeff(u2,nOne);
580  // testing both new labels by the F5 Criterion
581  //Print("LABEL: ");
582  //pWrite(ppMult_qq(u1,newElement->getTerm()));
583  //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
584  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
585  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
586  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
587  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
588  // label as first element in the CPairOld
589  if(newElement->getIndex() == temp->getIndex() &&
590  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
591  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
592  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
593  critPairs->insert(cp);
595  }
596  else {
597  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
598  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
599  critPairs->insert(cp);
601  }
602  }
603  //}
604  temp = temp->getNext();
605  }
606 }

◆ F5inc()

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 at line 131 of file f5gb.cc.

131  {
132  //Print("in f5inc\n");
133  //pWrite(rules->getFirst()->getRuleTerm());
134  int iterationstep = i;
135  int j;
136  //Print("%p\n",gPrev->getFirst());
137  //pWrite(gPrev->getFirst()->getPoly());
138  poly tempNF = kNF(gbPrev,currRing->qideal,f_i);
139  f_i = tempNF;
140  //gPrev->insert(ONE,i,f_i);
141  gPrev->insert(ONE,gPrev->getLength()+1,f_i);
142  // tag the first element in gPrev of the current index for findReductor()
143  lTag->setFirstCurrentIdx(gPrev->getLast());
144  //Print("1st gPrev: ");
145  //pWrite(gPrev->getFirst()->getPoly());
146  //Print("2nd gPrev: ");
147  //pWrite(gPrev->getFirst()->getNext()->getPoly());
148  //pWrite(gPrev->getFirst()->getNext()->getPoly());
149  CListOld* critPairs = new CListOld();
150  CNode* critPairsMinDeg = new CNode();
151  PList* rejectedGBList = new PList();
152  // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
153  // in the list critPairs
154  criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
155  static LList* sPolyList = new LList();
156  //sPolyList->print();
157  // labeled polynomials which have passed reduction() and have to be added to list gPrev
158  static LList* completed = new LList();
159  // the reduced labeled polynomials which are returned from subalgorithm reduction()
160  static LList* reducedLPolys = new LList();
161  // while there are critical pairs to be further checked and deleted/computed
162  while(NULL != critPairs->getFirst()) {
163  // critPairs->getMinDeg() deletes the first elements of minimal degree from
164  // critPairs, thus the while loop is not infinite.
165  // adds all to be reduced S-polynomials in the list sPolyList and adds
166  // the corresponding rules to the list rules
167  // NOTE: inside there is a second check of criterion 2 if new rules are
168  // added
169  //int timer4 = initTimer();
170  //startTimer();
171  //critPairs->print();
172 
173  //definition of a local numberUsefulPairs variable for the next degree
174  //step:
175  //if in this degree all pairs are useless, skip this degree step
176  //completely!
177  //long arrideg = critPairs->getFirst()->getData()->getDeg();
178  //if(plus && highestDegreeGBCriticalPair < critPairs->getFirst()->getData()->getDeg()) {
179  // return gPrev;
180  //}
181  //else {
182  critPairsMinDeg = critPairs->getMinDeg();
183  //numberUsefulPairsMinDeg = computeUsefulMinDeg(critPairsMinDeg);
184  //if(numberUsefulPairs > 0) {
185  //if(numberUsefulPairsMinDeg > 0) {
186  //Print("number of useful pairs: %d\n",numberUsefulPairs);
187  //Print("number of useless pairs: %d\n\n",numberUselessPairs);
188  //Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg());
189  long degreecheck = critPairsMinDeg->getData()->getDeg();
190 
191  computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
192  //}
193  //}
194  //}
195  //else {
196  // return gPrev;
197  //}
198  //timer4 = getTimer();
199  //Print("SPOLS TIMER: %d\n",timer4);
200  //spolsTime = spolsTime + timer4;
201  // DEBUG STUFF FOR SPOLYLIST
202  LNode* temp = sPolyList->getFirst();
203  //while(NULL != temp && NULL != temp->getLPoly()) {
204  //Print("Spolylist element: ");
205  //pWrite(temp->getPoly());
206  //temp = temp->getNext();
207  //}
208  // reduction process of new S-polynomials and also adds new critical pairs to critPairs
209  //int timer3 = initTimer();
210  //startTimer();
211  //sPolyList->print();
212  //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
213  //Print("BEFORE REDUCTION: \n");
214  //Print("number of useful pairs: %d\n",numberUsefulPairs);
215  //Print("number of useless pairs: %d\n\n",numberUselessPairs);
216  newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
217  //Print("ITERATION: %d",iterationstep);
218  //Print("NAECHSTER GRAD: %ld",degreecheck);
219  //sleep(5);
220  //if(i == 5 && pDeg(gPrev->getLast()->getPoly()) == 8) {
221  // Print("RAUS BEI DEG 8 \n");
222  // return gPrev;
223  //}
224  //Print("ARRIS DEG: %ld\n",arrideg);
225  // Arris idea stated by John in an email
226  //if(arrisCheck(critPairs->getFirst(),gPrev->getFirst(),arrideg)) {
227  // Print("ARRIS DEGREE: %ld\n", arrideg);
228  // return gPrev;
229  //}
230 
231 
232  //bool aha = checkDGB(gPrev);
233 
234 
235  //timer3 = getTimer();
236  //reductionTime = reductionTime + timer3;
237  //Print("REDUCTION TIMER: %d\n",timer3);
238  // DEBUG STUFF FOR GPREV
239  //temp = gPrev->getFirst();
240  //int number = 1;
241  //Print("\n\n");
242  //while(NULL != temp) {
243  // Print("%d. ",number);
244  // pWrite(temp->getPoly());
245  // temp = temp->getNext();
246  // number++;
247  // Print("\n");
248  //}
249  //sleep(5);
250 
251  }
252  //Print("REDUCTION DONE\n");
253  //Print("%p\n",rules->getFirst());
254  //Print("%p\n",rTag->getFirst());
255  //if(rules->getFirst() != rTag->getFirst()) {
256  //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
257  //rTag->insert(rules->getFirst());
258  //}
259  //else {
260  //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
261  //}
262  lTag->insert(lTag->getFirstCurrentIdx());
263  //Print("INDEX: %d\n",tempTag->getIndex());
264  //pWrite(tempTag->getPoly());
265  //Print("COMPLETED FIRST IN F5INC: \n");
266  //Print("1st gPrev: ");
267  //pWrite(gPrev->getFirst()->getPoly());
268  //Print("2nd gPrev: ");
269  //pWrite(gPrev->getFirst()->getNext()->getPoly());
270  //Print("3rd gPrev: ");
271  //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
272  //delete sPolyList;
273  //critPairs->print();
274  delete critPairs;
275  //Print("IN F5INC\n");
276  /*
277  PrintS("\n\n\nRULES: \n");
278  RNode* tempR = rules->getFirst();
279  Print("%p\n",tempR);
280  int t = 1;
281  while(NULL != tempR) {
282  Print("ADDRESS OF %d RNODE: %p\n",t,tempR);
283  Print("ADDRESS OF RULE: %p\n",tempR->getRule());
284  pWrite(tempR->getRuleTerm());
285  Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
286  Print("%d\n\n",tempR->getRuleIndex());
287  tempR = tempR->getNext();
288  t++;
289  }
290  */
291  //gPrev->print();
292  //Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
293  //Print("COMPLETE SPOLS TIME UNTIL NOW: %d\n",spolsTime);
294  degreeBound = 0;
295  return gPrev;
296 }

◆ F5main()

ideal F5main ( ideal  i,
ring  r,
int  opt,
int  plus,
int  termination 
)

Definition at line 1890 of file f5gb.cc.

1891 {
1892  switch(opt)
1893  {
1894  case 0:
1895  PrintS("\nComputations are done by the standard F5 Algorithm");
1896  break;
1897  case 1:
1898  PrintS("\nComputations are done by the variant F5R of the F5 Algorithm");
1899  break;
1900  case 2:
1901  PrintS("\nComputations are done by the variant F5C of the F5 Algorithm");
1902  break;
1903  default:
1904  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");
1905  return id;
1906  }
1907 
1908  int timer = initTimer();
1909  startTimer();
1910  int i,j,k,l;
1911  int gbLength;
1912  // 1 polynomial for defining initial labels & further tests
1913  poly ONE = pOne();
1914  poly pOne = pOne();
1915  number nOne = nInit(1);
1916  // tag the first element of index i-1 for criterion 1
1917  //Print("LTAG BEGINNING: %p\n",lTag);
1918 
1919  // DEBUGGING STUFF START
1920  //Print("NUMBER: %d\n",r->N);
1921  /*
1922  int* ev = new int[r->N +1];
1923  for(i=0;i<IDELEMS(id);i++) {
1924  p_GetExpV(id->m[i],ev,currRing);
1925  //ev2 = pGetExp(id->m[i],1);
1926  pWrite(id->m[i]);
1927  Print("EXP1: %d\n",ev[1]);
1928  Print("EXP2: %d\n",ev[2]);
1929  Print("EXP3: %d\n\n",ev[3]);
1930  Print("SUM: %ld\n\n\n",sumVector(ev,r->N));
1931  }
1932  delete ev;
1933  */
1934  /*DEBUGGING STUFF END */
1935 
1936  // first element in rTag is first element of rules which is NULL RNode,
1937  // this must be done due to possible later improvements
1938  RList* rules = new RList();
1939  //Print("RULES FIRST: %p\n",rules->getFirst());
1940  //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule());
1941  //RTagList* rTag = new RTagList(rules->getFirst());
1942  RTagList* rTag = NULL;
1943  i = 1;
1944  /*for(j=0; j<IDELEMS(id); j++) {
1945  if(NULL != id->m[j]) {
1946  if(pComparePolys(id->m[j],ONE)) {
1947  PrintS("One Polynomial in Input => Computations stopped\n");
1948  ideal idNew = idInit(1,1);
1949  idNew->m[0] = ONE;
1950  return(idNew);
1951  }
1952  }
1953  }*/
1954  ideal idNew = kInterRed(id);
1955  id = idNew;
1956  //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
1957  //idShow(id);
1958  LList* gPrev = new LList(ONE, i, id->m[0]);
1959  LList* reducers = new LList();
1960  //idShow(id);
1961  //Print("%p\n",id->m[0]);
1962  //pWrite(id->m[0]);
1963  //Print("%p\n",gPrev->getFirst()->getPoly());
1964  //pWrite(gPrev->getFirst()->getPoly());
1965 
1966  LTagList* lTag = new LTagList(gPrev->getFirst());
1967  //lTag->insert(gPrev->getFirst());
1968  lTag->setFirstCurrentIdx(gPrev->getFirst());
1969  // computing the groebner basis of the elements of index < actual index
1970  gbLength = gPrev->getLength();
1971  //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
1972  ideal gbPrev = idInit(gbLength,1);
1973  // initializing the groebner basis of elements of index < actual index
1974  gbPrev->m[0] = gPrev->getFirst()->getPoly();
1975  //idShow(gbPrev);
1976  //idShow(currRing->qideal);
1977  for(i=2; i<=IDELEMS(id); i++) {
1978  LNode* gPrevTag = gPrev->getLast();
1979  //Print("Last POlynomial in GPREV: ");
1980  //Print("%p\n",gPrevTag);
1981  //pWrite(gPrevTag->getPoly());
1982  Print("Iteration: %d\n\n",i);
1983  gPrev = F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
1984  //Print("%d\n",gPrev->count(gPrevTag->getNext()));
1985  //Print("%d\n",gPrev->getLength());
1986  //Print("____________________________________ITERATION STEP DONE________________________________________\n");
1987 
1988  // DEBUGGING STUFF
1989  LNode* temp = gPrev->getFirst();
1990 
1991 
1992  /////////////////////////////////////////////////////////////////////////////////
1993  // //
1994  // one needs to choose one of the following 3 implementations of the algorithm //
1995  // F5,F5R or F5C //
1996  // //
1997  /////////////////////////////////////////////////////////////////////////////////
1998 
1999 
2000  //
2001  // standard "F5"
2002  //
2003  if(0 == opt) {
2004  if(gPrev->getLength() > gbLength) {
2005  if(i < IDELEMS(id)) {
2006  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2007  LNode* temp = gPrevTag;
2008  int counter = 0;
2009  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2010  temp = temp->getNext();
2011  if(0 == temp->getDel()) {
2012  counter++;
2013  gbAdd->m[j] = temp->getPoly();
2014  }
2015  }
2016  gbPrev = idAdd(gbPrev,gbAdd);
2017  }
2018  else {
2019  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2020  LNode* temp = gPrevTag;
2021  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2022  temp = temp->getNext();
2023  gbAdd->m[j] = temp->getPoly();
2024  }
2025  gbPrev = idAdd(gbPrev,gbAdd);
2026  }
2027  //if(i == IDELEMS(id)) {
2028  // ideal tempId = kInterRed(gbPrev);
2029  // gbPrev = tempId;
2030  //}
2031  }
2032  gbLength = gPrev->getLength();
2033  }
2034 
2035 
2036  //
2037  // "F5R"
2038  //
2039  if(1 == opt) {
2040  if(gPrev->getLength() > gbLength) {
2041  if(i < IDELEMS(id)) {
2042  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2043  LNode* temp = gPrevTag;
2044  int counter = 0;
2045  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2046  temp = temp->getNext();
2047  if(0 == temp->getDel()) {
2048  counter++;
2049  gbAdd->m[j] = temp->getPoly();
2050  }
2051  }
2052  gbPrev = idAdd(gbPrev,gbAdd);
2053  }
2054  else {
2055  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2056  LNode* temp = gPrevTag;
2057  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2058  temp = temp->getNext();
2059  gbAdd->m[j] = temp->getPoly();
2060  }
2061  gbPrev = idAdd(gbPrev,gbAdd);
2062  }
2063  // interreduction stuff
2064  // comment this out if you want F5 instead of F5R
2065  if(i<IDELEMS(id)) {
2066  ideal tempId = kInterRed(gbPrev);
2067  gbPrev = tempId;
2068  }
2069  }
2070  gbLength = gPrev->getLength();
2071  }
2072 
2073 
2074  //
2075  // "F5C"
2076  //
2077  if(2 == opt) {
2078  if(gPrev->getLength() > gbLength) {
2079  if(i < IDELEMS(id)) {
2080  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2081  LNode* temp = gPrevTag;
2082  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2083  temp = temp->getNext();
2084  gbAdd->m[j] = temp->getPoly();
2085  }
2086  gbPrev = idAdd(gbPrev,gbAdd);
2087  }
2088  else {
2089  ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
2090  LNode* temp = gPrevTag;
2091  for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2092  temp = temp->getNext();
2093  gbAdd->m[j] = temp->getPoly();
2094  }
2095  gbPrev = idAdd(gbPrev,gbAdd);
2096  }
2097  if(i<IDELEMS(id)) {
2098  ideal tempId = kInterRed(gbPrev);
2099  gbPrev = tempId;
2100  delete gPrev;
2101  delete rules;
2102  gPrev = new LList(pOne,1,gbPrev->m[0]);
2103  gPrev->insert(pOne,1,gbPrev->m[1]);
2104  rules = new RList();
2105  //rTag = new RTagList(rules->getFirst());
2106  for(k=2; k<IDELEMS(gbPrev); k++) {
2107  gPrev->insert(pOne,k+1,gbPrev->m[k]);
2108  /*
2109  for(l=0; l<k; l++) {
2110  }
2111  rTag->insert(rules->getFirst());
2112  */
2113  }
2114  }
2115  gbLength = gPrev->getLength();
2116  }
2117  }
2118 
2119 
2120  }
2121  timer = getTimer();
2122  //Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime);
2123  Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero);
2124  Print("Number of rules: %d\n",numberOfRules);
2125  Print("Number of rejected F5-critical pairs:%d\n",numberRejectedF5CriticalPairs);
2126  Print("Number of reductions: %d\n",numberOfReductions);
2127  Print("Elements not added to G: %d\n",notInG);
2128  Print("Highest Degree during computations: %d\n",highestDegree);
2129  Print("Degree d_0 in F5+: %d\n",highestDegreeGBCriticalPair);
2130  Print("Time for computations: %d/1000 seconds\n",timer);
2131  Print("Number of elements in gb: %d\n",IDELEMS(gbPrev));
2132  //LNode* temp = gPrev->getFirst();
2133  //while(NULL != temp) {
2134  // pWrite(temp->getPoly());
2135  // temp = temp->getNext();
2136  // }
2137  //gPrev->print();
2138  //delete lTag;
2139  delete rTag;
2140  delete gPrev;
2141  notInG = 0;
2142  numberOfRules = 0;
2143  reductionsToZero = 0;
2144  highestDegree = 0;
2146  reductionTime = 0;
2147  spolsTime = 0;
2148  numberUselessPairs = 0;
2149  numberUsefulPairs = 0;
2151  numberOfReductions = 0;
2152  numberOfSpolys = 0;
2153  return(gbPrev);
2154 
2155 
2156 }

◆ findReducers()

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 "good" and "bad" part:

the "good" ones are the reducers which do not corrupt the label of temp, with these the normal form of temp is computed

the "bad" ones are the reducers which corrupt the label of temp, they are tested

later on for possible new RuleOlds and S-polynomials to be added to the algorithm


searches for reducers of temp similar to the symbolic preprocessing of F4 and divides them into a "good" and "bad" part:

the "good" ones are the reducers which do not corrupt the label of temp, with these the normal form of temp is computed

the "bad" ones are the reducers which corrupt the label of temp, they are tested

later on for possible new rules and S-polynomials to be added to the algorithm

Definition at line 1203 of file f5gb.cc.

1203  {
1204  int canonicalize = 0;
1205  //int timerRed = 0;
1206  bool addToG = 1;
1207  number sign = nInit(-1);
1208  LList* good = new LList();
1209  LList* bad = new LList();
1210  LList* monomials = new LList(l->getLPolyOld());
1211  poly u = pOne();
1212  number nOne = nInit(1);
1213  LNode* tempRed = lTag->getFirstCurrentIdx();
1214  LNode* tempMon = monomials->getFirst();
1215  poly tempPoly = pInit();
1216  poly redPoly = NULL;
1217  int idx = l->getIndex();
1218  //Print("IN FIND REDUCERS: ");
1219  //pWrite(l->getPoly());
1220  tempPoly = pCopy(l->getPoly());
1221  //tempMon->setPoly(tempPoly);
1222  //while(NULL != tempMon) {
1223  // iteration over all monomials in tempMon
1224  kBucket* bucket = kBucketCreate(currRing);
1225  kBucketInit(bucket,tempPoly,0);
1226  tempPoly = kBucketGetLm(bucket);
1227  //Print("\n\n\nTO BE REDUCED: ");
1228  //pWrite(l->getPoly());
1229  //pWrite(l->getTerm());
1230  //pWrite(tempPoly);
1231  while(NULL != tempPoly) {
1232  // iteration of all elements in gPrev of the current index
1233  tempRed = gPrev->getFirst();
1234  while(NULL != tempRed) {
1235  //Print("TEMPREDPOLY: ");
1236  //pWrite(tempRed->getPoly());
1237  if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1238  u = pMDivideM(tempPoly,tempRed->getPoly());
1239  //Print("U: ");
1240  //pWrite(u);
1241  if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done!
1242  if(tempRed->getIndex() != idx) {
1243  // passing criterion1 ?
1244  if(!criterion1(gPrev,u,tempRed,lTag)) {
1245  poly tempRedPoly = tempRed->getPoly();
1246  //Print("REDUCER: ");
1247  //pWrite(tempRedPoly);
1248  pIter(tempRedPoly);
1249  int lTempRedPoly = pLength(tempRedPoly);
1250  kBucketExtractLm(bucket);
1251  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1252  canonicalize++;
1253  //Print("Reduction\n");
1254  if(!(canonicalize % 50)) {
1255  kBucketCanonicalize(bucket);
1256  }
1257  tempPoly = kBucketGetLm(bucket);
1258  //Print("TEMPPOLY: ");
1259  //pWrite(tempPoly);
1260  if(NULL != tempPoly) {
1261  tempRed = gPrev->getFirst();
1262  continue;
1263  }
1264  else {
1265  break;
1266  }
1267  }
1268 
1269  }
1270  else {
1271  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1272  //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1273  //pWrite(u);
1274  //pWrite(tempRed->getTerm());
1275  //pWrite(pHead(tempRed->getPoly()));
1276  addToG = 0;
1277  }
1278  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1279  // passing criterion2 ?
1280  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1281  // passing criterion1 ?
1282  if(!criterion1(gPrev,u,tempRed,lTag)) {
1283  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1284  if(NULL == redPoly) {
1285  bad->insert(tempRed->getLPolyOld());
1286  addToG = 1;
1287  //poly tempRedPoly = tempRed->getPoly();
1288  //break;
1289  }
1290  }
1291  else {
1292  poly tempRedPoly = tempRed->getPoly();
1293  //Print("REDUCER: ");
1294  //pWrite(tempRedPoly);
1295  pIter(tempRedPoly);
1296  int lTempRedPoly = pLength(tempRedPoly);
1297  //Print("HEAD MONOMIAL KBUCKET: ");
1298  //pWrite(kBucketGetLm(bucket));
1299  kBucketExtractLm(bucket);
1300  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1301  canonicalize++;
1302  //Print("REDUCTION\n");
1303  addToG = 1;
1304  if(!(canonicalize % 50)) {
1305  kBucketCanonicalize(bucket);
1306  }
1307  //Print("HEAD MONOMIAL KBUCKET: ");
1308  //pWrite(kBucketGetLm(bucket));
1309  tempPoly = kBucketGetLm(bucket);
1310  //Print("TEMPPOLY: ");
1311  //pWrite(tempPoly);
1312  if(NULL != tempPoly) {
1313  tempRed = gPrev->getFirst();
1314  continue;
1315  }
1316  else {
1317  break;
1318  }
1319  }
1320  }
1321  }
1322  else {
1323  //Print("CRIT 1 ");
1324 
1325  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1326  //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1327  //pWrite(u);
1328  //pWrite(tempRed->getTerm());
1329  //pWrite(tempRed->getPoly());
1330  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1331  //Print("REDUCER LABEL: ");
1332  //pWrite(tempRed->getTerm());
1333 addToG = 0;
1334  }
1335  }
1336  }
1337  }
1338  else {
1339  //Print("CRIT 2 ");
1340  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1341  //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1342  //pWrite(u);
1343  //pWrite(tempRed->getTerm());
1344  //pWrite(tempRed->getPoly());
1345  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1346  //Print("REDUCER LABEL: ");
1347  //pWrite(tempRed->getTerm());
1348 addToG = 0;
1349  }
1350  }
1351  }
1352  }
1353  }
1354  else { // u = 1 => reduce without checking criteria
1355  poly tempRedPoly = tempRed->getPoly();
1356  //Print("REDUCER: ");
1357  //pWrite(tempRedPoly);
1358  pIter(tempRedPoly);
1359  int lTempRedPoly = pLength(tempRedPoly);
1360  kBucketExtractLm(bucket);
1361  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1362  canonicalize++;
1363  //Print("Reduction\n");
1364  if(!(canonicalize % 50)) {
1365  kBucketCanonicalize(bucket);
1366  }
1367  tempPoly = kBucketGetLm(bucket);
1368  //Print("TEMPPOLY: ");
1369  //pWrite(tempPoly);
1370  if(NULL != tempPoly) {
1371  tempRed = gPrev->getFirst();
1372  continue;
1373  }
1374  else {
1375  break;
1376  }
1377 
1378  }
1379  }
1380  tempRed = tempRed->getNext();
1381  }
1382  // reduction process with elements in LList* reducers
1383  if(NULL != tempPoly) {
1384  //Print("HERE\n");
1385  tempRed = reducers->getFirst();
1386  while(NULL != tempRed) {
1387  //Print("TEMPREDPOLY: ");
1388  //pWrite(tempRed->getPoly());
1389  //pWrite(tempPoly);
1390  if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1391  //Print("A\n");
1392  u = pMDivideM(tempPoly,tempRed->getPoly());
1393  //Print("U: ");
1394  //pWrite(u);
1395  if(tempRed->getIndex() != idx) {
1396  // passing criterion1 ?
1397  if(!criterion1(gPrev,u,tempRed,lTag)) {
1398  poly tempRedPoly = tempRed->getPoly();
1399  //Print("REDUCER: ");
1400  //pWrite(ppMult_qq(u,tempRedPoly));
1401  pIter(tempRedPoly);
1402  int lTempRedPoly = pLength(tempRedPoly);
1403  kBucketExtractLm(bucket);
1404  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1405  canonicalize++;
1406  //Print("Reduction\n");
1407  if(!(canonicalize % 50)) {
1408  kBucketCanonicalize(bucket);
1409  }
1410  tempPoly = kBucketGetLm(bucket);
1411  //Print("TEMPPOLY: ");
1412  //pWrite(tempPoly);
1413  if(NULL != tempPoly) {
1414  tempRed = gPrev->getFirst();
1415  continue;
1416  }
1417  else {
1418  break;
1419  }
1420  }
1421 
1422  }
1423  else {
1424  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1425  //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1426  //pWrite(u);
1427  //pWrite(tempRed->getTerm());
1428  //pWrite(pHead(tempRed->getPoly()));
1429  //addToG = 0;
1430  }
1431  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1432  // passing criterion2 ?
1433  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1434  // passing criterion1 ?
1435  if(!criterion1(gPrev,u,tempRed,lTag)) {
1436  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1437  if(NULL == redPoly) {
1438  bad->insert(tempRed->getLPolyOld());
1439  addToG = 1;
1440  //poly tempRedPoly = tempRed->getPoly();
1441  //break;
1442  }
1443  }
1444  else {
1445  poly tempRedPoly = tempRed->getPoly();
1446  //Print("REDUCER: ");
1447  //pWrite(ppMult_qq(u,tempRedPoly));
1448  pIter(tempRedPoly);
1449  int lTempRedPoly = pLength(tempRedPoly);
1450  //Print("HEAD MONOMIAL KBUCKET: ");
1451  //pWrite(kBucketGetLm(bucket));
1452  kBucketExtractLm(bucket);
1453  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1454  canonicalize++;
1455  //Print("REDUCTION\n");
1456  addToG = 1;
1457  if(!(canonicalize % 50)) {
1458  kBucketCanonicalize(bucket);
1459  }
1460  //Print("HEAD MONOMIAL KBUCKET: ");
1461  //pWrite(kBucketGetLm(bucket));
1462  tempPoly = kBucketGetLm(bucket);
1463  //Print("TEMPPOLY: ");
1464  //pWrite(tempPoly);
1465  if(NULL != tempPoly) {
1466  tempRed = gPrev->getFirst();
1467  continue;
1468  }
1469  else {
1470  break;
1471  }
1472  }
1473  }
1474  }
1475  else {
1476  //Print("CRIT 1 ");
1477 
1478  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1479  //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1480  //pWrite(u);
1481  //pWrite(tempRed->getTerm());
1482  //pWrite(tempRed->getPoly());
1483  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1484  //Print("REDUCER LABEL: ");
1485  //pWrite(tempRed->getTerm());
1486  addToG = 0;
1487  }
1488  }
1489  }
1490  }
1491  else {
1492  //Print("CRIT 2 ");
1493  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1494  //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1495  //pWrite(u);
1496  //pWrite(tempRed->getTerm());
1497  //pWrite(tempRed->getPoly());
1498  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1499  //Print("REDUCER LABEL: ");
1500  //pWrite(tempRed->getTerm());
1501 addToG = 0;
1502  }
1503  }
1504  }
1505  }
1506 
1507  }
1508  tempRed = tempRed->getNext();
1509  }
1510  }
1511  if(NULL != tempPoly) {
1512  if(NULL == redPoly) {
1513  redPoly = kBucketExtractLm(bucket);
1514  }
1515  else {
1516  redPoly = p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing);
1517  }
1518  // for top-reduction only
1519  redPoly = p_Merge_q(redPoly,kBucketClear(bucket),currRing);
1520  break;
1521  // end for top-reduction only
1522  tempPoly = kBucketGetLm(bucket);
1523 
1524  }
1525  }
1526  if(NULL == redPoly) {
1527  reductionsToZero++;
1528  //pDelete(&redPoly);
1529  }
1530  else
1531  {
1532  PrintS("\nELEMENT ADDED TO GPREV: ");
1533  pNorm(redPoly);
1534  if(highestDegree < pDeg(redPoly))
1535  {
1536  highestDegree = pDeg(redPoly);
1537  }
1538  pWrite(pHead(redPoly));
1539  //pWrite(l->getTerm());
1540  //Print("%d\n",canonicalize);
1541  l->setPoly(redPoly);
1542  // give "l" the label if it is "useful" (addToG = 0) or "useless"
1543  // (addToG = 1)
1544  l->setDel(!addToG);
1545  Print("redundant? %d\n\n",l->getDel());
1546  if(addToG == 0 && termination == 1) {
1547  reducers->insert(l->getLPolyOld());
1548  }
1549  else {
1550  gPrev->insert(l->getLPolyOld());
1551  }
1552  //Print("%d\n\n",termination);
1553  if(termination == 1) {
1554  if(addToG) {
1555  //Print("----------------HERE?-----------------\n");
1556  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1557  }
1558  else {
1559  notInG++;
1560  //Print("\nNONONO");
1561  //pWrite(pHead(l->getPoly()));
1562  //pWrite(l->getTerm());
1563  }
1564  }
1565  // case in which all new elements are added to gPrev!
1566  // using boolean "addToG" to know if the element is "useful" (0) or
1567  // "useless" (1)
1568  else {
1569  if(!l->getDel()) {
1570  criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1571  }
1572  else {
1573  criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1574  }
1575  }
1576  }
1577 
1578  // if there are "bad" reducers than try to compute new S-polynomials and rules
1579 
1580  if(NULL != bad->getFirst()) {
1581  //Print("BAD STUFF LIST:\n");
1582  //bad->print();
1583  LNode* tempBad = bad->getFirst();
1584  //pWrite(l->getPoly());
1585  while(NULL != tempBad) {
1586  if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
1587  //Print("BAD STUFF\n");
1588  //pWrite(l->getPoly());
1589  //pWrite(tempBad->getPoly());
1590  u = pMDivide(l->getPoly(),tempBad->getPoly());
1591  //Print("MULTIPLIER: ");
1592  //pWrite(u);
1593  pSetCoeff(u,nOne);
1594  if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) {
1595  // passing criterion2 ?
1596  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) {
1597  // passing criterion1 ?
1598  if(!criterion1(gPrev,u,tempBad,lTag)) {
1599  //Print("HIERHIERHIERHIERHIERHIER\n");
1600  rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
1601  numberOfRules++;
1602  //gPrev->print();
1603  //pWrite(l->getPoly());
1604  poly temp = ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly());
1605  //pWrite(l->getPoly());
1606  //Print("%p\n",temp);
1607  //gPrev->print();
1608  if(NULL != temp) {
1609  pNorm(temp);
1610  LNode* tempBadNew = new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
1611  //pWrite(temp);
1612  //pWrite(tempBadNew->getPoly());
1613  //pWrite(tempBadNew->getTerm());
1614  //pWrite(pHead(tempBadNew->getPoly()));
1615  //Print("%p\n",tempBadNew->getPoly());
1616  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1617  tempBadNew->setDel(1);
1618 
1619  sPolyList->insertByLabel(tempBadNew);
1620  //Print("BAD SPOLYLIST: \n");
1621  //sPolyList->print();
1622  }
1623  }
1624  }
1625  }
1626  }
1627  //Print("HIER\n");
1628  tempBad = tempBad->getNext();
1629  //Print("%p\n",tempBad);
1630  }
1631  // Print("-------------------BAD STUFF LIST-----------------------------\n");
1632  }
1633  //Print("HIER AUCH\n");
1634  //Print("SPOLYLIST IN BAD: \n");
1635  //sPolyList->print();
1636  //Print("END FIND REDUCERS\n");
1637 }

◆ findReductor()

LNode* findReductor ( LNode l,
LList sPolyList,
LNode gPrevRedCheck,
LList gPrev,
RList RuleOlds,
LTagList lTag,
RTagList rTag 
)
inline

◆ newReduction()

void newReduction ( LList sPolyList,
CListOld critPairs,
LList gPrev,
LList reducers,
RList rules,
LTagList lTag,
RTagList rTag,
ideal  gbPrev,
int  termination,
PList rejectedGBList,
int  plus 
)
inline

Definition at line 1136 of file f5gb.cc.

1137  {
1138  //Print("##########################################In REDUCTION!########################################\n");
1139  // check if sPolyList has any elements
1140  // NOTE: due to initialization sPolyList always has a default NULL element
1141  //Print("--1--\n");
1142  LNode* temp = sPolyList->getFirst();
1143  //Print("START OF REDUCTION: ");
1144  while(NULL != temp) {
1146  // temp is the first element in the sPolyList which should be reduced
1147  // due to earlier sorting this is the element of minimal degree AND
1148  // minimal label
1149  // delete the above first element from sPolyList, temp will be either reduced to
1150  // zero or added to gPrev, but never come back to sPolyList
1151  //Print("LIST OF SPOLYNOMIALS!\n");
1152  //sPolyList->print();
1153  //pWrite(sPolyList->getFirst()->getPoly());
1154  sPolyList->setFirst(temp->getNext());
1155  //if(pDeg(temp->getPoly()) > 11) {
1156  // Print("YES!!!!!!!!!!!!!!!!\n");
1157  //}
1158  //pWrite(temp->getPoly());
1159  //poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly());
1160  //Print("!!!\n");
1161  //if(NULL != tempNF) {
1162  //pNorm(tempNF);
1163  //temp->setPoly(tempNF);
1164  //Print("lower label reduction: ");
1165  //pWrite(tempNF);
1166  // try further reductions of temp with polynomials in gPrev
1167  // with label index = current label index: this is done such that there
1168  // is no label corruption during the reduction process
1169  findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1170  //}
1171  //else {
1172  // reductionsToZero++;
1173  // delete temp;
1174  //}
1175  //if(NULL != temp->getPoly()) {
1176  // criticalPair(gPrev,critPairs,lTag,rTag,rules);
1177  //}
1178  //Print("HIER AUCH ?\n");
1179  //Print("--2--\n");
1180  //sPolyList->print();
1181  //critPairs->print();
1182  temp = sPolyList->getFirst();
1183  //Print("%p\n",temp);
1184  }
1185  //sPolyList->print();
1186  //delete sPolyList;
1187  //Print("REDUCTION FERTIG\n");
1188 }

◆ qsortDegree()

void qsortDegree ( poly *  left,
poly *  right 
)

Definition at line 52 of file f5gb.cc.

53 {
54  poly* ptr1 = left;
55  poly* ptr2 = right;
56  poly p1,p2;
57  p2 = *(left + (right - left >> 1));
58  do
59  {
60  while(p_Totaldegree(*ptr1, currRing) < p_Totaldegree(p2, currRing))
61  {
62  ptr1++;
63  }
64  while(p_Totaldegree(*ptr2, currRing) > p_Totaldegree(p2,currRing))
65  {
66  ptr2--;
67  }
68  if(ptr1 > ptr2)
69  {
70  break;
71  }
72  p1 = *ptr1;
73  *ptr1 = *ptr2;
74  *ptr2 = p1;
75  } while(++ptr1 <= --ptr2);
76 
77  if(left < ptr2)
78  {
79  qsortDegree(left,ptr2);
80  }
81  if(ptr1 < right)
82  {
83  qsortDegree(ptr1,right);
84  }
85 }

◆ reduction()

void reduction ( LList sPolyList,
CListOld critPairs,
LList gPrev,
RList RuleOlds,
LTagList lTag,
RTagList rTag,
ideal  gbPrev,
PList rejectedGBList,
int  plus 
)
inline

Definition at line 1090 of file f5gb.cc.

1091  {
1092  //Print("##########################################In REDUCTION!########################################\n");
1093  // check if sPolyList has any elements
1094  // NOTE: due to initialization sPolyList always has a default NULL element
1095  LNode* temp = sPolyList->getFirst();
1096  while(NULL != temp) {
1097  // temp is the first element in the sPolyList which should be reduced
1098  // due to earlier sorting this is the element of minimal degree AND
1099  // minimal label
1100  // delete the above first element from sPolyList, temp will be either reduced to
1101  // zero or added to gPrev, but never come back to sPolyList
1102  //pWrite(sPolyList->getFirst()->getPoly());
1103  //Print("LIST OF SPOLYNOMIALS!\n");
1104  //sPolyList->print();
1105  sPolyList->setFirst(temp->getNext());
1106  poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly());
1107  if(NULL != tempNF) {
1108  pNorm(tempNF);
1109  temp->setPoly(tempNF);
1110  // try further reductions of temp with polynomials in gPrev
1111  // with label index = current label index: this is done such that there
1112  // is no label corruption during the reduction process
1113  //Print("lower label reduction: ");
1114  //pWrite(tempNF);
1115  topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1116 
1117  }
1118  else {
1119  reductionsToZero++;
1120  delete temp;
1121  }
1122  //if(NULL != temp->getPoly()) {
1123  // criticalPair(gPrev,critPairs,lTag,rTag,rules);
1124  //}
1125  temp = sPolyList->getFirst();
1126  }
1127  //sPolyList->print();
1128  //delete sPolyList;
1129 }

◆ sumVector()

long sumVector ( int *  v,
int  k 
)

builds the sum of the entries of the exponent vectors, i.e. the degree

of the corresponding monomial


builds the sum of the entries of the exponent vectors, i.e. the degree

of the corresponding monomial

Definition at line 93 of file f5gb.cc.

93  {
94  int i;
95  long sum = 0;
96  for(i=1; i<=k; i++) {
97  Print("%d\n",v[i]);
98  Print("%ld\n",sum);
99  sum = sum + v[i];
100  }
101  return sum;
102 }

◆ topReduction()

void topReduction ( LNode l,
LList sPolyList,
LList gPrev,
CListOld critPairs,
RList RuleOlds,
LTagList lTag,
RTagList rTag,
ideal  gbPrev,
PList rejectedGBList,
int  plus 
)
inline

Definition at line 1705 of file f5gb.cc.

1705  {
1706  //Print("##########################################In topREDUCTION!########################################\n");
1707  // try l as long as there are reductors found by findReductor()
1708  LNode* gPrevRedCheck = lTag->getFirstCurrentIdx();
1709  LNode* tempRed;
1710  poly pOne = pOne();
1711  do {
1712  //int timer5 = initTimer();
1713  //startTimer();
1714  //Print("TOP REDUCTION: ");
1715  //pWrite(l->getPoly());
1716  tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1717  //timer5 = getTimer();
1718  //reductionTime = reductionTime + timer5;
1719  // if a reductor for l is found and saved in tempRed
1720  if(NULL != tempRed) {
1721  // if label of reductor is greater than the label of l we have to built a new element
1722  // and add it to sPolyList
1723 
1724  if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1725  // needed sinc pSub destroys the arguments!
1726  //poly temp_poly_l = pInit();
1727  //temp_poly_l = pCopy(l->getPoly());
1728  //Print("VORHER: ");
1729  //pWrite(tempRed->getPoly());
1730  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1731  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1732  rules->insert(tempRed->getIndex(),tempRed->getTerm());
1733  //Print("NACHHER: ");
1734  //pWrite(tempRed->getPoly());
1735  //Print("TEMP: ");
1736  //pWrite(temp);
1737  if(NULL != temp) {
1738  pNorm(temp);
1739  //tempRed->setPoly(temp);
1740  //tempRed->setDel(1);
1741  //rules->insert(tempRed->getIndex(),tempRed->getTerm());
1742  LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld());
1743  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1744  tempRedNew->setDel(1);
1745  sPolyList->insertByLabel(tempRedNew);
1746  }
1747  else {
1748  pDelete(&temp);
1749  reductionsToZero++;
1750  //delete tempRed;
1751  }
1752  }
1753 
1754  // label of reductor is smaller than the label of l, subtract reductor from l and delete the
1755  // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
1756  // after subtraction
1757  else {
1758 
1759  //poly temp_poly_l = pInit();
1760  //temp_poly_l = pCopy(l->getPoly());
1761  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1762  //Print("REDUCER: ");
1763  //pWrite(tempRed->getPoly());
1764  //pWrite(tempRed->getTerm());
1765  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1766  //Print("REDUCED ELEMENT: ");
1767  if(NULL != temp) {
1768  pNorm(temp);
1769  //pWrite(temp);
1770  poly tempNF = kNF(gbPrev,currRing->qideal,temp);
1771  pNorm(tempNF);
1772  if(NULL == tempNF) {
1773  reductionsToZero++;
1774  pDelete(&tempNF);
1775  l->setPoly(NULL);
1776  break;
1777  }
1778  l->setPoly(tempNF);
1779 
1780  gPrevRedCheck = lTag->getFirstCurrentIdx();
1781  }
1782  else {
1783  reductionsToZero++;
1784  pDelete(&temp);
1785  l->setPoly(NULL);
1786  break;
1787  }
1788  }
1789  }
1790  else {
1791  if(NULL != l->getPoly()) {
1792  pNorm(l->getPoly());
1793  //Print("ELEMENT ADDED TO GPREV: ");
1794  //pWrite(l->getPoly());
1795  gPrev->insert(l->getLPolyOld());
1796  //Print("TEMP RED == 0 ");
1797  //pWrite(l->getPoly());
1798  //pWrite(l->getTerm());
1799  //rules->print();
1800  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1801  //Print("LIST OF CRITICAL PAIRS: \n");
1802  //critPairs->print();
1803  }
1804  break;
1805  }
1806  } while(1);
1807 }
CNode::getData
CPairOld * getData()
Definition: f5lists.cc:821
pDivisibleBy
#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
LTagList
Definition: f5lists.h:188
numberUselessPairs
int numberUselessPairs
Definition: f5gb.cc:40
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
LList
Definition: f5lists.h:127
pLmEqual
#define pLmEqual(p1, p2)
Definition: polys.h:111
qsortDegree
void qsortDegree(poly *left, poly *right)
Definition: f5gb.cc:52
j
int j
Definition: facHensel.cc:105
pNorm
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:357
LList::getFirst
LNode * getFirst()
Definition: f5lists.cc:520
numberRejectedF5CriticalPairs
int numberRejectedF5CriticalPairs
Definition: f5gb.cc:43
highestDegreeGBCriticalPair
int highestDegreeGBCriticalPair
Definition: f5gb.cc:42
k
int k
Definition: cfEzgcd.cc:92
computeSPols
void computeSPols(CNode *first, RTagList *rTag, RList *rules, LList *sPolyList, PList *rejectedGBList)
Definition: f5gb.cc:845
RuleOld
Definition: f5data.h:232
LTagList::getFirstCurrentIdx
LNode * getFirstCurrentIdx()
Definition: f5lists.cc:646
p_Merge_q
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1149
LList::setFirst
void setFirst(LNode *l)
Definition: f5lists.cc:532
RList::getFirst
RNode * getFirst()
Definition: f5lists.cc:1092
idAdd
ideal idAdd(ideal h1, ideal h2)
h1 + h2
Definition: ideals.h:68
LNode::getPoly
poly getPoly()
Definition: f5lists.cc:332
degreeBound
int degreeBound
Definition: f5gb.cc:38
findReductor
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
Definition: f5gb.cc:1815
highestDegree
int highestDegree
Definition: f5gb.cc:37
PList::insert
void insert(poly p)
Definition: f5lists.cc:81
LList::getLast
LNode * getLast()
Definition: f5lists.cc:524
spolsTime
int spolsTime
Definition: f5gb.cc:36
sign
static int sign(int x)
Definition: ring.cc:3346
bad
bool bad
Definition: facFactorize.cc:65
CNode::getT1
poly getT1()
Definition: f5lists.cc:861
reductionsToZero
int reductionsToZero
Definition: f5gb.cc:34
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:503
pDelete
#define pDelete(p_ptr)
Definition: polys.h:181
criterion2
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:676
LNode::getLPolyOld
LPolyOld * getLPolyOld()
Definition: f5lists.cc:327
ppMult_qq
#define ppMult_qq(p, q)
Definition: polys.h:203
LNode::getTerm
poly getTerm()
Definition: f5lists.cc:336
criticalPair
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
Definition: f5gb.cc:442
RNode::getNext
RNode * getNext()
Definition: f5lists.cc:1024
CNode::getLp2Poly
poly getLp2Poly()
Definition: f5lists.cc:841
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:193
startTimer
void startTimer()
Definition: timer.cc:82
currRing
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
notInG
int notInG
Definition: f5gb.cc:32
initTimer
int initTimer()
Definition: timer.cc:69
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:508
i
int i
Definition: cfEzgcd.cc:125
CNode::getLp1Index
int getLp1Index()
Definition: f5lists.cc:853
LNode::setPoly
void setPoly(poly p)
Definition: f5lists.cc:357
RNode
Definition: f5lists.h:290
RNode::getRuleOldIndex
int getRuleOldIndex()
Definition: f5lists.cc:1032
CNode::getAdLp2
LPolyOld * getAdLp2()
Definition: f5lists.cc:833
PrintS
void PrintS(const char *s)
Definition: reporter.cc:284
LList::getLength
int getLength()
Definition: f5lists.cc:528
CNode::getLp1Poly
poly getLp1Poly()
Definition: f5lists.cc:837
LNode::setDel
void setDel(bool d)
Definition: f5lists.cc:373
CNode::getTestedRuleOld
RuleOld * getTestedRuleOld()
Definition: f5lists.cc:881
CNode::getLp1Term
poly getLp1Term()
Definition: f5lists.cc:845
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:490
pLcm
#define pLcm(a, b, m)
Definition: polys.h:289
kBucket_Minus_m_Mult_p
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:713
criterion1
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:615
getTimer
int getTimer()
Definition: timer.cc:97
pInit
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
LTagList::setFirstCurrentIdx
void setFirstCurrentIdx(LNode *l)
Definition: f5lists.cc:634
criticalPair2
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
Definition: f5gb.cc:554
pOne
#define pOne()
Definition: polys.h:309
LList::insertByLabel
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
Definition: f5lists.cc:494
numberOfSpolys
int numberOfSpolys
Definition: f5gb.cc:45
pIter
#define pIter(p)
Definition: monomials.h:38
CPairOld
Definition: f5data.h:123
RNode::getRuleOld
RuleOld * getRuleOld()
Definition: f5lists.cc:1028
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:518
pMDivide
#define pMDivide(a, b)
Definition: polys.h:287
pLmDivisibleByNoComp
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
findReducers
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)
Definition: f5gb.cc:1203
CNode::getNext
CNode * getNext()
Definition: f5lists.cc:825
numberUsefulPairs
int numberUsefulPairs
Definition: f5gb.cc:39
kNF
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2822
CNode::getDel
bool getDel()
Definition: f5lists.cc:877
CListOld::getMinDeg
CNode * getMinDeg()
Definition: f5lists.cc:953
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
LNode::getIndex
int getIndex()
Definition: f5lists.cc:340
numberOfRules
int numberOfRules
Definition: f5gb.cc:33
RNode::getRuleOldTerm
poly getRuleOldTerm()
Definition: f5lists.cc:1036
RList
Definition: f5lists.h:313
newReduction
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:1136
LTagList::insert
void insert(LNode *l)
Definition: f5lists.cc:629
CNode::getLp2Index
int getLp2Index()
Definition: f5lists.cc:857
Print
#define Print
Definition: emacs.cc:80
CNode::getAdLp1
LPolyOld * getAdLp1()
Definition: f5lists.cc:829
LNode
Definition: f5lists.h:65
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
topReduction
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:1705
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
NULL
#define NULL
Definition: omList.c:10
pSetm
#define pSetm(p)
Definition: polys.h:265
l
int l
Definition: cfEzgcd.cc:93
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
LNode::getNext
LNode * getNext()
Definition: f5lists.cc:322
kBucket
Definition: kbuckets.h:178
numberOfReductions
int numberOfReductions
Definition: f5gb.cc:44
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p_Totaldegree
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1444
CListOld
Definition: f5lists.h:269
CListOld::getFirst
CNode * getFirst()
Definition: f5lists.cc:947
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
nInit
#define nInit(i)
Definition: numbers.h:25
pLmCmp
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
PList
class PList of lists of PNodes
Definition: f5lists.h:50
numberUsefulPairsMinDeg
int numberUsefulPairsMinDeg
Definition: f5gb.cc:41
pCopy
#define pCopy(p)
return a copy of the poly
Definition: polys.h:180
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:26
F5inc
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:131
LNode::getDel
bool getDel()
Definition: f5lists.cc:352
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
kInterRed
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3380
CListOld::insert
void insert(CPairOld *c)
Definition: f5lists.cc:939
CNode::getT2
poly getT2()
Definition: f5lists.cc:869
RList::insert
void insert(RuleOld *r)
Definition: f5lists.cc:1084
reductionTime
int reductionTime
Definition: f5gb.cc:35
pDeg
#define pDeg(A)
Definition: f5gb.cc:30
RTagList
Definition: f5lists.h:361
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
CPairOld::getDeg
long getDeg()
Definition: f5data.h:162
LList::insert
void insert(LPolyOld *lp)
Definition: f5lists.cc:458
CNode
Definition: f5lists.h:232
ksOldSpolyRedNew
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1059
pWrite
void pWrite(poly p)
Definition: polys.h:302