My Project  debian-1:4.1.2-p1+ds-2
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 382 of file f5gb.cc.

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

◆ checkDGB()

bool checkDGB ( LList gPrev)

Definition at line 299 of file f5gb.cc.

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

◆ 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 844 of file f5gb.cc.

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

◆ computeUsefulMinDeg()

int computeUsefulMinDeg ( CNode first)

Definition at line 828 of file f5gb.cc.

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

◆ criterion1()

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

Definition at line 614 of file f5gb.cc.

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

◆ criterion2() [1/2]

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

Definition at line 675 of file f5gb.cc.

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

◆ criterion2() [2/2]

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

Definition at line 787 of file f5gb.cc.

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

◆ criticalPair()

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

Definition at line 441 of file f5gb.cc.

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

◆ criticalPair2()

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

Definition at line 553 of file f5gb.cc.

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

◆ 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 130 of file f5gb.cc.

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

◆ F5main()

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

Definition at line 1889 of file f5gb.cc.

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

◆ 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 1202 of file f5gb.cc.

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

◆ 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 1135 of file f5gb.cc.

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

◆ qsortDegree()

void qsortDegree ( poly *  left,
poly *  right 
)

Definition at line 51 of file f5gb.cc.

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

◆ 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 1089 of file f5gb.cc.

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

◆ 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 92 of file f5gb.cc.

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

◆ 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 1704 of file f5gb.cc.

1704  {
1705  //Print("##########################################In topREDUCTION!########################################\n");
1706  // try l as long as there are reductors found by findReductor()
1707  LNode* gPrevRedCheck = lTag->getFirstCurrentIdx();
1708  LNode* tempRed;
1709  poly pOne = pOne();
1710  do {
1711  //int timer5 = initTimer();
1712  //startTimer();
1713  //Print("TOP REDUCTION: ");
1714  //pWrite(l->getPoly());
1715  tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1716  //timer5 = getTimer();
1717  //reductionTime = reductionTime + timer5;
1718  // if a reductor for l is found and saved in tempRed
1719  if(NULL != tempRed) {
1720  // if label of reductor is greater than the label of l we have to built a new element
1721  // and add it to sPolyList
1722 
1723  if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1724  // needed sinc pSub destroys the arguments!
1725  //poly temp_poly_l = pInit();
1726  //temp_poly_l = pCopy(l->getPoly());
1727  //Print("VORHER: ");
1728  //pWrite(tempRed->getPoly());
1729  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1730  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1731  rules->insert(tempRed->getIndex(),tempRed->getTerm());
1732  //Print("NACHHER: ");
1733  //pWrite(tempRed->getPoly());
1734  //Print("TEMP: ");
1735  //pWrite(temp);
1736  if(NULL != temp) {
1737  pNorm(temp);
1738  //tempRed->setPoly(temp);
1739  //tempRed->setDel(1);
1740  //rules->insert(tempRed->getIndex(),tempRed->getTerm());
1741  LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld());
1742  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1743  tempRedNew->setDel(1);
1744  sPolyList->insertByLabel(tempRedNew);
1745  }
1746  else {
1747  pDelete(&temp);
1748  reductionsToZero++;
1749  //delete tempRed;
1750  }
1751  }
1752 
1753  // label of reductor is smaller than the label of l, subtract reductor from l and delete the
1754  // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
1755  // after subtraction
1756  else {
1757 
1758  //poly temp_poly_l = pInit();
1759  //temp_poly_l = pCopy(l->getPoly());
1760  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1761  //Print("REDUCER: ");
1762  //pWrite(tempRed->getPoly());
1763  //pWrite(tempRed->getTerm());
1764  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1765  //Print("REDUCED ELEMENT: ");
1766  if(NULL != temp) {
1767  pNorm(temp);
1768  //pWrite(temp);
1769  poly tempNF = kNF(gbPrev,currRing->qideal,temp);
1770  pNorm(tempNF);
1771  if(NULL == tempNF) {
1772  reductionsToZero++;
1773  pDelete(&tempNF);
1774  l->setPoly(NULL);
1775  break;
1776  }
1777  l->setPoly(tempNF);
1778 
1779  gPrevRedCheck = lTag->getFirstCurrentIdx();
1780  }
1781  else {
1782  reductionsToZero++;
1783  pDelete(&temp);
1784  l->setPoly(NULL);
1785  break;
1786  }
1787  }
1788  }
1789  else {
1790  if(NULL != l->getPoly()) {
1791  pNorm(l->getPoly());
1792  //Print("ELEMENT ADDED TO GPREV: ");
1793  //pWrite(l->getPoly());
1794  gPrev->insert(l->getLPolyOld());
1795  //Print("TEMP RED == 0 ");
1796  //pWrite(l->getPoly());
1797  //pWrite(l->getTerm());
1798  //rules->print();
1799  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1800  //Print("LIST OF CRITICAL PAIRS: \n");
1801  //critPairs->print();
1802  }
1803  break;
1804  }
1805  } while(1);
1806 }
CNode::getData
CPairOld * getData()
Definition: f5lists.cc:820
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:132
LTagList
Definition: f5lists.h:187
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:126
pLmEqual
#define pLmEqual(p1, p2)
Definition: polys.h:107
qsortDegree
void qsortDegree(poly *left, poly *right)
Definition: f5gb.cc:51
j
int j
Definition: facHensel.cc:105
pNorm
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:347
LList::getFirst
LNode * getFirst()
Definition: f5lists.cc:519
notInG
VAR int notInG
Definition: f5gb.cc:31
k
int k
Definition: cfEzgcd.cc:92
computeSPols
void computeSPols(CNode *first, RTagList *rTag, RList *rules, LList *sPolyList, PList *rejectedGBList)
Definition: f5gb.cc:844
RuleOld
Definition: f5data.h:231
LTagList::getFirstCurrentIdx
LNode * getFirstCurrentIdx()
Definition: f5lists.cc:645
p_Merge_q
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1136
LList::setFirst
void setFirst(LNode *l)
Definition: f5lists.cc:531
idAdd
ideal idAdd(ideal h1, ideal h2)
h1 + h2
Definition: ideals.h:67
highestDegree
VAR int highestDegree
Definition: f5gb.cc:36
LNode::getPoly
poly getPoly()
Definition: f5lists.cc:331
highestDegreeGBCriticalPair
VAR int highestDegreeGBCriticalPair
Definition: f5gb.cc:41
findReductor
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
Definition: f5gb.cc:1814
numberOfSpolys
VAR int numberOfSpolys
Definition: f5gb.cc:44
PList::insert
void insert(poly p)
Definition: f5lists.cc:80
LList::getLast
LNode * getLast()
Definition: f5lists.cc:523
spolsTime
VAR int spolsTime
Definition: f5gb.cc:35
STATIC_VAR
#define STATIC_VAR
Definition: globaldefs.h:7
sign
static int sign(int x)
Definition: ring.cc:3374
bad
bool bad
Definition: facFactorize.cc:65
CNode::getT1
poly getT1()
Definition: f5lists.cc:860
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:505
pDelete
#define pDelete(p_ptr)
Definition: polys.h:175
criterion2
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:675
numberUsefulPairs
VAR int numberUsefulPairs
Definition: f5gb.cc:38
ppMult_qq
#define ppMult_qq(p, q)
Definition: polys.h:196
LNode::getTerm
poly getTerm()
Definition: f5lists.cc:335
criticalPair
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
Definition: f5gb.cc:441
RNode::getNext
RNode * getNext()
Definition: f5lists.cc:1023
CNode::getLp2Poly
poly getLp2Poly()
Definition: f5lists.cc:840
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:182
numberOfRules
VAR int numberOfRules
Definition: f5gb.cc:32
startTimer
void startTimer()
Definition: timer.cc:79
initTimer
int initTimer()
Definition: timer.cc:66
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:510
i
int i
Definition: cfEzgcd.cc:125
CNode::getLp1Index
int getLp1Index()
Definition: f5lists.cc:852
LNode::setPoly
void setPoly(poly p)
Definition: f5lists.cc:356
RNode
Definition: f5lists.h:289
RNode::getRuleOldIndex
int getRuleOldIndex()
Definition: f5lists.cc:1031
CNode::getAdLp2
LPolyOld * getAdLp2()
Definition: f5lists.cc:832
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
LList::getLength
int getLength()
Definition: f5lists.cc:527
CNode::getLp1Poly
poly getLp1Poly()
Definition: f5lists.cc:836
LNode::setDel
void setDel(bool d)
Definition: f5lists.cc:372
CNode::getTestedRuleOld
RuleOld * getTestedRuleOld()
Definition: f5lists.cc:880
CNode::getLp1Term
poly getLp1Term()
Definition: f5lists.cc:844
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:492
pLcm
#define pLcm(a, b, m)
Definition: polys.h:279
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:715
criterion1
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:614
getTimer
int getTimer()
Definition: timer.cc:94
numberOfReductions
VAR int numberOfReductions
Definition: f5gb.cc:43
pInit
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:59
LTagList::setFirstCurrentIdx
void setFirstCurrentIdx(LNode *l)
Definition: f5lists.cc:633
criticalPair2
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
Definition: f5gb.cc:553
pOne
#define pOne()
Definition: polys.h:299
LList::insertByLabel
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
Definition: f5lists.cc:493
pIter
#define pIter(p)
Definition: monomials.h:34
CPairOld
Definition: f5data.h:122
numberUsefulPairsMinDeg
VAR int numberUsefulPairsMinDeg
Definition: f5gb.cc:40
RNode::getRuleOld
RuleOld * getRuleOld()
Definition: f5lists.cc:1027
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:520
pMDivide
#define pMDivide(a, b)
Definition: polys.h:277
pLmDivisibleByNoComp
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:136
numberUselessPairs
VAR int numberUselessPairs
Definition: f5gb.cc:39
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:1202
CNode::getNext
CNode * getNext()
Definition: f5lists.cc:824
kNF
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2823
CNode::getDel
bool getDel()
Definition: f5lists.cc:876
CListOld::getMinDeg
CNode * getMinDeg()
Definition: f5lists.cc:952
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:30
LNode::getIndex
int getIndex()
Definition: f5lists.cc:339
RNode::getRuleOldTerm
poly getRuleOldTerm()
Definition: f5lists.cc:1035
RList
Definition: f5lists.h:312
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:1135
degreeBound
VAR int degreeBound
Definition: f5gb.cc:37
LTagList::insert
void insert(LNode *l)
Definition: f5lists.cc:628
CNode::getLp2Index
int getLp2Index()
Definition: f5lists.cc:856
Print
#define Print
Definition: emacs.cc:79
CNode::getAdLp1
LPolyOld * getAdLp1()
Definition: f5lists.cc:828
numberRejectedF5CriticalPairs
VAR int numberRejectedF5CriticalPairs
Definition: f5gb.cc:42
LNode
Definition: f5lists.h:64
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:34
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:1704
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
NULL
#define NULL
Definition: omList.c:11
pSetm
#define pSetm(p)
Definition: polys.h:256
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:321
kBucket
Definition: kbuckets.h:177
reductionTime
VAR int reductionTime
Definition: f5gb.cc:34
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:1428
CListOld
Definition: f5lists.h:268
CListOld::getFirst
CNode * getFirst()
Definition: f5lists.cc:946
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:208
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
nInit
#define nInit(i)
Definition: numbers.h:23
pLmCmp
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:101
PList
class PList of lists of PNodes
Definition: f5lists.h:49
pCopy
#define pCopy(p)
return a copy of the poly
Definition: polys.h:174
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:23
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:130
LNode::getDel
bool getDel()
Definition: f5lists.cc:351
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:65
kInterRed
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3399
CListOld::insert
void insert(CPairOld *c)
Definition: f5lists.cc:938
CNode::getT2
poly getT2()
Definition: f5lists.cc:868
reductionsToZero
VAR int reductionsToZero
Definition: f5gb.cc:33
pDeg
#define pDeg(A)
Definition: f5gb.cc:29
RTagList
Definition: f5lists.h:360
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
CPairOld::getDeg
long getDeg()
Definition: f5data.h:161
LList::insert
void insert(LPolyOld *lp)
Definition: f5lists.cc:457
CNode
Definition: f5lists.h:231
ksOldSpolyRedNew
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1124
pWrite
void pWrite(poly p)
Definition: polys.h:292