Macros | Functions | Variables
f5gb.cc File Reference
#include <kernel/mod2.h>
#include <unistd.h>
#include <omp.h>
#include <kernel/structs.h>
#include <kernel/GBEngine/kutil.h>
#include <omalloc/omalloc.h>
#include <kernel/polys.h>
#include <polys/monomials/p_polys.h>
#include <polys/templates/p_Procs.h>
#include <kernel/ideals.h>
#include <kernel/GBEngine/kstd1.h>
#include <kernel/GBEngine/khstd.h>
#include <polys/kbuckets.h>
#include <polys/weight.h>
#include <misc/intvec.h>
#include <kernel/GBEngine/f5gb.h>
#include <kernel/GBEngine/f5data.h>
#include <kernel/GBEngine/f5lists.h>
#include <kernel/oswrapper/timer.h>

Go to the source code of this file.

Macros

#define pDeg(A)   p_Deg(A,currRing)
 

Functions

void qsortDegree (poly *left, poly *right)
 
long sumVector (int *v, int k)
 

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

 
bool compareMonomials (int *m1, int **m2, int numberOfRules, int k)
 

compares monomials, i.e. More...

 
LListF5inc (int i, poly f_i, LList *gPrev, LList *reducers, ideal gbPrev, poly ONE, LTagList *lTag, RList *rules, RTagList *rTag, int plus, int termination)
 
bool checkDGB (LList *gPrev)
 
bool arrisCheck (CNode *first, LNode *firstGCurr, long arrideg)
 
void criticalPair (LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
 
void criticalPair2 (LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
 
bool criterion1 (LList *gPrev, poly t, LNode *l, LTagList *lTag)
 
bool criterion2 (int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
 
bool criterion2 (poly t, LPolyOld *l, RList *rules, RuleOld *testedRuleOld)
 
int computeUsefulMinDeg (CNode *first)
 
void computeSPols (CNode *first, RTagList *rTag, RList *rules, LList *sPolyList, PList *rejectedGBList)
 
void reduction (LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, 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)
 

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

 
void topReduction (LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
 
LNodefindReductor (LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
 
ideal F5main (ideal id, ring r, int opt, int plus, int termination)
 

Variables

int notInG = 0
 
int numberOfRules = 0
 
int reductionsToZero = 0
 
int reductionTime = 0
 
int spolsTime = 0
 
int highestDegree = 0
 
int degreeBound = 0
 
int numberUsefulPairs = 0
 
int numberUselessPairs = 0
 
int numberUsefulPairsMinDeg = 0
 
int highestDegreeGBCriticalPair = 0
 
int numberRejectedF5CriticalPairs = 0
 
int numberOfReductions = 0
 
int numberOfSpolys = 0
 

Macro Definition Documentation

◆ pDeg

#define pDeg (   A)    p_Deg(A,currRing)

Definition at line 33 of file f5gb.cc.

Function Documentation

◆ arrisCheck()

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

Definition at line 386 of file f5gb.cc.

386  {
387  CNode* temp = first;
388 
389  //product criterion check
390  while(NULL != temp) {
391  if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) {
392  return 0;
393  }
394  temp = temp->getNext();
395  }
396 
397  // chain criterion
398  LNode* tempPoly = firstGCurr;
399  while(NULL != tempPoly) {
400  LNode* tempPoly2 = tempPoly->getNext();
401  while(NULL != tempPoly2) {
402  number nOne = nInit(1);
403  poly lcm = pOne();
404  pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm);
405  pSetCoeff(lcm,nOne);
406  pSetm(lcm);
407  if(pDeg(lcm) > arrideg) {
408  LNode* tempPoly3 = firstGCurr;
409  while(NULL != tempPoly3) {
410  if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) {
411  poly lcm1 = pOne();
412  poly lcm2 = pOne();
413  pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1);
414  pSetCoeff(lcm1,nOne);
415  pSetm(lcm1);
416  pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2);
417  pSetCoeff(lcm2,nOne);
418  pSetm(lcm2);
419  if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) {
420  return 0;
421  }
422  }
423  tempPoly3 = tempPoly3->getNext();
424  }
425  }
426  tempPoly2 = tempPoly2->getNext();
427  }
428  tempPoly = tempPoly->getNext();
429  }
430  return 1;
431 }
#define pSetm(p)
Definition: polys.h:253
LNode * getNext()
Definition: f5lists.cc:322
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
poly getT1()
Definition: f5lists.cc:861
#define pLcm(a, b, m)
Definition: polys.h:277
poly getPoly()
Definition: f5lists.cc:332
poly getLp2Poly()
Definition: f5lists.cc:841
Definition: f5lists.h:65
Definition: f5lists.h:232
#define pOne()
Definition: polys.h:297
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
#define pDeg(A)
Definition: f5gb.cc:33
#define NULL
Definition: omList.c:10
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition: polys.h:138
CNode * getNext()
Definition: f5lists.cc:825
polyrec * poly
Definition: hilb.h:10
#define nInit(i)
Definition: numbers.h:24
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
#define pLmEqual(p1, p2)
Definition: polys.h:111

◆ checkDGB()

bool checkDGB ( LList gPrev)

Definition at line 303 of file f5gb.cc.

303  {
304  Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly()));
305  LNode* temp = gPrev->getFirst();
306  LNode* temp2;
307  bool isDGb = 0;
308  // construct the d-GB gb
309  ideal gb = idInit(gPrev->getLength(),1);
310  for(int j=0;j<=gPrev->getLength()-1;j++) {
311  gb->m[j] = temp->getPoly();
312  pWrite(gb->m[j]);
313  temp = temp->getNext();
314  }
315  /*
316  Kstd1_deg = pDeg(gPrev->getLast()->getPoly());
317  BITSET save = test;
318  test |= Sy_bit(OPT_DEGBOUND);
319  kStd();
320  test = save;
321  */
322  temp = gPrev->getFirst();
323  while(NULL != temp) {
324  temp2 = temp->getNext();
325  number nOne = nInit(1);
326  poly lcm = pOne();
327  poly sp = pOne();
328  while(NULL != temp2) {
329  pLcm(temp->getPoly(),temp2->getPoly(),lcm);
330  pSetCoeff(lcm,nOne);
331  pSetm(lcm);
332  PrintS("LCM: ");
333  pWrite(lcm);
334  if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) {
335  poly u1 = pOne();
336  poly u2 = pOne();
337  u1 = pDivide(lcm,pHead(temp->getPoly()));
338  pSetCoeff(u1,nOne);
339  u2 = pDivide(lcm,pHead(temp2->getPoly()));
340  pSetCoeff(u2,nOne);
341  sp = ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()),
342  ppMult_qq(u2,temp2->getPoly()));
343  pNorm(sp);
344 
345  poly reducer = pOne();
346  //reducer = gb->m[0];
347  int i = 0;
348  pWrite(pHead(sp));
349 
350  while(i<IDELEMS(gb)) {
351  reducer = gb->m[i];
352  if(pDivisibleBy(reducer,pHead(sp))) {
353  poly uReducer = pOne();
354  uReducer = pDivide(lcm,pHead(reducer));
355  pSetCoeff(uReducer,nOne);
356  sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer));
357  //pNorm(tempSP);
358  //sp = tempSP;
359  pNorm(sp);
360  pWrite(sp);
361  i = 0;
362  }
363  else {
364  i++;
365  }
366  }
367 
368  pWrite(pHead(sp));
369  }
370  temp2 = temp2->getNext();
371  }
372  temp = temp->getNext();
373  }
374  PrintS("------------------\n");
375  return isDGb;
376 }
#define ppMult_qq(p, q)
Definition: polys.h:191
#define pDivide(a, b)
Definition: polys.h:275
#define pSetm(p)
Definition: polys.h:253
LNode * getNext()
Definition: f5lists.cc:322
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
#define Print
Definition: emacs.cc:83
int getLength()
Definition: f5lists.cc:528
#define pLcm(a, b, m)
Definition: polys.h:277
void pWrite(poly p)
Definition: polys.h:290
poly getPoly()
Definition: f5lists.cc:332
Definition: f5lists.h:65
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
#define pOne()
Definition: polys.h:297
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
#define IDELEMS(i)
Definition: simpleideals.h:24
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1063
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
#define pDeg(A)
Definition: f5gb.cc:33
#define NULL
Definition: omList.c:10
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition: polys.h:138
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
polyrec * poly
Definition: hilb.h:10
LNode * getFirst()
Definition: f5lists.cc:520
#define nInit(i)
Definition: numbers.h:24
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
LNode * getLast()
Definition: f5lists.cc:524

◆ compareMonomials()

bool compareMonomials ( int *  m1,
int **  m2,
int  numberOfRules,
int  k 
)


compares monomials, i.e.

divisibility tests for criterion 1 and criterion 2

Definition at line 112 of file f5gb.cc.

112  {
113  int i,j;
114  long sumM1 = sumVector(m1,k);
115  //int k = sizeof(m1) / sizeof(int);
116  for(i=0; i<numberOfRules; i++) {
117  if(sumVector(m2[i],k) <= sumM1) {
118  for(j=1; j<=k; j++) {
119  if(m1[j]>m2[i][j]) {
120  return true;
121  }
122  }
123  }
124  }
125  return false;
126 }
int k
Definition: cfEzgcd.cc:93
int numberOfRules
Definition: f5gb.cc:36
int j
Definition: myNF.cc:70
long sumVector(int *v, int k)
builds the sum of the entries of the exponent vectors, i.e.
Definition: f5gb.cc:96
int i
Definition: cfEzgcd.cc:123

◆ computeSPols()

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

Definition at line 848 of file f5gb.cc.

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

◆ computeUsefulMinDeg()

int computeUsefulMinDeg ( CNode first)

Definition at line 832 of file f5gb.cc.

832  {
833  CNode* temp = first;
834  int numberUsefulPairsMinDeg = 0;
835  while(NULL != temp) {
836  if(!temp->getDel()) {
837  numberUsefulPairsMinDeg++;
838  }
839  temp = temp->getNext();
840  }
842 }
Definition: f5lists.h:232
#define NULL
Definition: omList.c:10
CNode * getNext()
Definition: f5lists.cc:825
bool getDel()
Definition: f5lists.cc:877
int numberUsefulPairsMinDeg
Definition: f5gb.cc:44

◆ criterion1()

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

Definition at line 618 of file f5gb.cc.

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

◆ criterion2() [1/2]

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

Definition at line 679 of file f5gb.cc.

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

◆ criterion2() [2/2]

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

Definition at line 791 of file f5gb.cc.

791  {
792  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
793  //Print("LAST RuleOld TESTED: %p",testedRuleOld);
794  /*
795  PrintS("RULES: \n");
796  RNode* tempR = rules->getFirst();
797  while(NULL != tempR) {
798  pWrite(tempR->getRuleTerm());
799  Print("%d\n\n",tempR->getRuleIndex());
800  tempR = tempR->getNext();
801  }
802  //Print("TESTED ELEMENT: ");
803  //pWrite(l->getPoly());
804  //pWrite(l->getTerm());
805  //pWrite(ppMult_qq(t,l->getTerm()));
806  //Print("%d\n\n",l->getIndex());
807  */
808 // start at the previously added element to gPrev, as all other elements will have the same index for sure
809  RNode* testNode = rules->getFirst();
810  // save the monom t1*label_term(l) as it is tested various times in the following
811  poly u1 = ppMult_qq(t,l->getTerm());
812  // first element added to rTag was NULL, check for this
813  while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) {
814  //pWrite(testNode->getRuleTerm());
815  if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
816  //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
817  //Print("INDEX: %d\n",l->getIndex());
818  pDelete(&u1);
819  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
820  return true;
821  }
822  testNode = testNode->getNext();
823  }
824  pDelete(&u1);
825  //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
826  return false;
827 }
#define ppMult_qq(p, q)
Definition: polys.h:191
RNode * getNext()
Definition: f5lists.cc:1024
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
poly getTerm()
Definition: f5data.h:90
poly getRuleOldTerm()
Definition: f5lists.cc:1036
RuleOld * getRuleOld()
Definition: f5lists.cc:1028
#define NULL
Definition: omList.c:10
#define pDelete(p_ptr)
Definition: polys.h:169
polyrec * poly
Definition: hilb.h:10
Definition: f5lists.h:290
RNode * getFirst()
Definition: f5lists.cc:1092

◆ criticalPair()

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

Definition at line 445 of file f5gb.cc.

445  {
446  //Print("IN CRITPAIRS\n");
447  // initialization for usage in pLcm()
448  number nOne = nInit(1);
449  LNode* newElement = gPrev->getLast();
450  LNode* temp = gPrev->getFirst();
451  poly u1 = pOne();
452  poly u2 = pOne();
453  poly lcm = pOne();
454  poly t = pHead(newElement->getPoly());
455  RuleOld* testedRuleOld = NULL;
456  //Print("NEW: ");
457  //pWrite(newElement->getPoly());
458  //Print("ADDRESS: %p",newElement);
459  if(NULL != rules->getFirst()) {
460  testedRuleOld = rules->getFirst()->getRuleOld();
461  }
462  // computation of critical pairs
463  while( gPrev->getLast() != temp) {
464  //Print("TEMP: ");
465  //pWrite(pHead(temp->getPoly()));
466  //Print("ADDRESS: %p",temp);
467  pLcm(newElement->getPoly(), temp->getPoly(), lcm);
468  pSetCoeff(lcm,nOne);
469  // computing factors u2 for new labels
470  u1 = pDivide(lcm,t);
471  if(NULL == u1) {
472  break;
473  }
474  pSetCoeff(u1,nOne);
475  u2 = pDivide(lcm,pHead(temp->getPoly()));
476  pSetCoeff(u2,nOne);
477  int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly())));
478  // testing both new labels by the F5 Criterion
479  if(!temp->getDel()) {
480  if(plus && highestDegreeGBCriticalPair < degree) {
482  }
483  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
484  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
485  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
486  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
487  // label as first element in the CPairOld
488  if(newElement->getIndex() == temp->getIndex() &&
489  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
490  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
491  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);
492  critPairs->insert(cp);
493  // counting the number of useful pairs
495  }
496  else {
497  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
498  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);
499  critPairs->insert(cp);
500  // counting the number of useful pairs
502  }
503  }
504  else {
505  // TODO: generate a list of lcms of rejected GB critical pairs and
506  // check F5 critical pairs with it at their creation
507  //Print("--------------------------------------------------------------------\n");
508  //Print("--------------------------------------------------------------------\n");
509  pSetm(lcm);
510  rejectedGBList->insert(lcm);
511  //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n");
512  //pWrite(lcm);
513  //Print("--------------------------------------------------------------------\n");
514  //rejectedGBList->print();
515  }
516  }
517  else {
518  //Print("LABEL: ");
519  //pWrite(ppMult_qq(u1,newElement->getTerm()));
520  //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
521  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
522  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
523  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
524  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
525  // label as first element in the CPairOld
526  if(newElement->getIndex() == temp->getIndex() &&
527  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
528  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
529  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
530  critPairs->insert(cp);
532  }
533  else {
534  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
535  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
536  critPairs->insert(cp);
538  }
539  }
540  //}
541  }
542  temp = temp->getNext();
543  }
544 }
int highestDegreeGBCriticalPair
Definition: f5gb.cc:45
#define ppMult_qq(p, q)
Definition: polys.h:191
#define pDivide(a, b)
Definition: polys.h:275
int numberUselessPairs
Definition: f5gb.cc:43
#define pSetm(p)
Definition: polys.h:253
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
void insert(poly p)
Definition: f5lists.cc:81
bool getDel()
Definition: f5lists.cc:352
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
structure of RuleOlds(i.e.
Definition: f5data.h:232
#define pLcm(a, b, m)
Definition: polys.h:277
poly getPoly()
Definition: f5lists.cc:332
Definition: f5lists.h:65
RuleOld * getRuleOld()
Definition: f5lists.cc:1028
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:618
int numberUsefulPairs
Definition: f5gb.cc:42
#define pOne()
Definition: polys.h:297
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:679
void insert(CPairOld *c)
Definition: f5lists.cc:939
#define pDeg(A)
Definition: f5gb.cc:33
#define NULL
Definition: omList.c:10
int degree(const CanonicalForm &f)
polyrec * poly
Definition: hilb.h:10
int getIndex()
Definition: f5lists.cc:340
LNode * getFirst()
Definition: f5lists.cc:520
#define nInit(i)
Definition: numbers.h:24
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
RNode * getFirst()
Definition: f5lists.cc:1092
LNode * getLast()
Definition: f5lists.cc:524
structure of labeled critical pairs
Definition: f5data.h:123

◆ criticalPair2()

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

Definition at line 557 of file f5gb.cc.

557  {
558  //Print("IN CRITPAIRS\n");
559  // initialization for usage in pLcm()
560  number nOne = nInit(1);
561  LNode* newElement = gPrev->getLast();
562  LNode* temp = gPrev->getFirst();
563  poly u1 = pOne();
564  poly u2 = pOne();
565  poly lcm = pOne();
566  poly t = pHead(newElement->getPoly());
567  RuleOld* testedRuleOld = NULL;
568  if(NULL != rules->getFirst()) {
569  testedRuleOld = rules->getFirst()->getRuleOld();
570  }
571  // computation of critical pairs
572  while( gPrev->getLast() != temp) {
573  pLcm(newElement->getPoly(), temp->getPoly(), lcm);
574  pSetCoeff(lcm,nOne);
575  // computing factors u2 for new labels
576  u1 = pDivide(lcm,t);
577  if(NULL == u1) {
578  break;
579  }
580  pSetCoeff(u1,nOne);
581  u2 = pDivide(lcm,pHead(temp->getPoly()));
582  pSetCoeff(u2,nOne);
583  // testing both new labels by the F5 Criterion
584  //Print("LABEL: ");
585  //pWrite(ppMult_qq(u1,newElement->getTerm()));
586  //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
587  if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
588  && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
589  && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
590  // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
591  // label as first element in the CPairOld
592  if(newElement->getIndex() == temp->getIndex() &&
593  -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
594  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
595  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
596  critPairs->insert(cp);
598  }
599  else {
600  CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
601  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
602  critPairs->insert(cp);
604  }
605  }
606  //}
607  temp = temp->getNext();
608  }
609 }
#define ppMult_qq(p, q)
Definition: polys.h:191
#define pDivide(a, b)
Definition: polys.h:275
int numberUselessPairs
Definition: f5gb.cc:43
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
structure of RuleOlds(i.e.
Definition: f5data.h:232
#define pLcm(a, b, m)
Definition: polys.h:277
poly getPoly()
Definition: f5lists.cc:332
Definition: f5lists.h:65
RuleOld * getRuleOld()
Definition: f5lists.cc:1028
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:618
#define pOne()
Definition: polys.h:297
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:679
void insert(CPairOld *c)
Definition: f5lists.cc:939
#define pDeg(A)
Definition: f5gb.cc:33
#define NULL
Definition: omList.c:10
polyrec * poly
Definition: hilb.h:10
int getIndex()
Definition: f5lists.cc:340
LNode * getFirst()
Definition: f5lists.cc:520
#define nInit(i)
Definition: numbers.h:24
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
RNode * getFirst()
Definition: f5lists.cc:1092
LNode * getLast()
Definition: f5lists.cc:524
structure of labeled critical pairs
Definition: f5data.h:123

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

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

◆ F5main()

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

Definition at line 1893 of file f5gb.cc.

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

◆ 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 rules and S-polynomials to be added to the algorithm

Definition at line 1206 of file f5gb.cc.

1206  {
1207  int canonicalize = 0;
1208  //int timerRed = 0;
1209  bool addToG = 1;
1210  number sign = nInit(-1);
1211  LList* good = new LList();
1212  LList* bad = new LList();
1213  LList* monomials = new LList(l->getLPolyOld());
1214  poly u = pOne();
1215  number nOne = nInit(1);
1216  LNode* tempRed = lTag->getFirstCurrentIdx();
1217  LNode* tempMon = monomials->getFirst();
1218  poly tempPoly = pInit();
1219  poly redPoly = NULL;
1220  int idx = l->getIndex();
1221  //Print("IN FIND REDUCERS: ");
1222  //pWrite(l->getPoly());
1223  tempPoly = pCopy(l->getPoly());
1224  //tempMon->setPoly(tempPoly);
1225  //while(NULL != tempMon) {
1226  // iteration over all monomials in tempMon
1228  kBucketInit(bucket,tempPoly,0);
1229  tempPoly = kBucketGetLm(bucket);
1230  //Print("\n\n\nTO BE REDUCED: ");
1231  //pWrite(l->getPoly());
1232  //pWrite(l->getTerm());
1233  //pWrite(tempPoly);
1234  while(NULL != tempPoly) {
1235  // iteration of all elements in gPrev of the current index
1236  tempRed = gPrev->getFirst();
1237  while(NULL != tempRed) {
1238  //Print("TEMPREDPOLY: ");
1239  //pWrite(tempRed->getPoly());
1240  if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1241  u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1242  //Print("U: ");
1243  //pWrite(u);
1244  if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done!
1245  if(tempRed->getIndex() != idx) {
1246  // passing criterion1 ?
1247  if(!criterion1(gPrev,u,tempRed,lTag)) {
1248  poly tempRedPoly = tempRed->getPoly();
1249  //Print("REDUCER: ");
1250  //pWrite(tempRedPoly);
1251  pIter(tempRedPoly);
1252  int lTempRedPoly = pLength(tempRedPoly);
1253  kBucketExtractLm(bucket);
1254  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1255  canonicalize++;
1256  //Print("Reduction\n");
1257  if(!(canonicalize % 50)) {
1258  kBucketCanonicalize(bucket);
1259  }
1260  tempPoly = kBucketGetLm(bucket);
1261  //Print("TEMPPOLY: ");
1262  //pWrite(tempPoly);
1263  if(NULL != tempPoly) {
1264  tempRed = gPrev->getFirst();
1265  continue;
1266  }
1267  else {
1268  break;
1269  }
1270  }
1271 
1272  }
1273  else {
1274  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1275  //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1276  //pWrite(u);
1277  //pWrite(tempRed->getTerm());
1278  //pWrite(pHead(tempRed->getPoly()));
1279  addToG = 0;
1280  }
1281  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1282  // passing criterion2 ?
1283  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1284  // passing criterion1 ?
1285  if(!criterion1(gPrev,u,tempRed,lTag)) {
1286  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1287  if(NULL == redPoly) {
1288  bad->insert(tempRed->getLPolyOld());
1289  addToG = 1;
1290  //poly tempRedPoly = tempRed->getPoly();
1291  //break;
1292  }
1293  }
1294  else {
1295  poly tempRedPoly = tempRed->getPoly();
1296  //Print("REDUCER: ");
1297  //pWrite(tempRedPoly);
1298  pIter(tempRedPoly);
1299  int lTempRedPoly = pLength(tempRedPoly);
1300  //Print("HEAD MONOMIAL KBUCKET: ");
1301  //pWrite(kBucketGetLm(bucket));
1302  kBucketExtractLm(bucket);
1303  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1304  canonicalize++;
1305  //Print("REDUCTION\n");
1306  addToG = 1;
1307  if(!(canonicalize % 50)) {
1308  kBucketCanonicalize(bucket);
1309  }
1310  //Print("HEAD MONOMIAL KBUCKET: ");
1311  //pWrite(kBucketGetLm(bucket));
1312  tempPoly = kBucketGetLm(bucket);
1313  //Print("TEMPPOLY: ");
1314  //pWrite(tempPoly);
1315  if(NULL != tempPoly) {
1316  tempRed = gPrev->getFirst();
1317  continue;
1318  }
1319  else {
1320  break;
1321  }
1322  }
1323  }
1324  }
1325  else {
1326  //Print("CRIT 1 ");
1327 
1328  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1329  //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1330  //pWrite(u);
1331  //pWrite(tempRed->getTerm());
1332  //pWrite(tempRed->getPoly());
1333  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1334  //Print("REDUCER LABEL: ");
1335  //pWrite(tempRed->getTerm());
1336 addToG = 0;
1337  }
1338  }
1339  }
1340  }
1341  else {
1342  //Print("CRIT 2 ");
1343  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1344  //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1345  //pWrite(u);
1346  //pWrite(tempRed->getTerm());
1347  //pWrite(tempRed->getPoly());
1348  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1349  //Print("REDUCER LABEL: ");
1350  //pWrite(tempRed->getTerm());
1351 addToG = 0;
1352  }
1353  }
1354  }
1355  }
1356  }
1357  else { // u = 1 => reduce without checking criteria
1358  poly tempRedPoly = tempRed->getPoly();
1359  //Print("REDUCER: ");
1360  //pWrite(tempRedPoly);
1361  pIter(tempRedPoly);
1362  int lTempRedPoly = pLength(tempRedPoly);
1363  kBucketExtractLm(bucket);
1364  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1365  canonicalize++;
1366  //Print("Reduction\n");
1367  if(!(canonicalize % 50)) {
1368  kBucketCanonicalize(bucket);
1369  }
1370  tempPoly = kBucketGetLm(bucket);
1371  //Print("TEMPPOLY: ");
1372  //pWrite(tempPoly);
1373  if(NULL != tempPoly) {
1374  tempRed = gPrev->getFirst();
1375  continue;
1376  }
1377  else {
1378  break;
1379  }
1380 
1381  }
1382  }
1383  tempRed = tempRed->getNext();
1384  }
1385  // reduction process with elements in LList* reducers
1386  if(NULL != tempPoly) {
1387  //Print("HERE\n");
1388  tempRed = reducers->getFirst();
1389  while(NULL != tempRed) {
1390  //Print("TEMPREDPOLY: ");
1391  //pWrite(tempRed->getPoly());
1392  //pWrite(tempPoly);
1393  if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1394  //Print("A\n");
1395  u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1396  //Print("U: ");
1397  //pWrite(u);
1398  if(tempRed->getIndex() != idx) {
1399  // passing criterion1 ?
1400  if(!criterion1(gPrev,u,tempRed,lTag)) {
1401  poly tempRedPoly = tempRed->getPoly();
1402  //Print("REDUCER: ");
1403  //pWrite(ppMult_qq(u,tempRedPoly));
1404  pIter(tempRedPoly);
1405  int lTempRedPoly = pLength(tempRedPoly);
1406  kBucketExtractLm(bucket);
1407  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1408  canonicalize++;
1409  //Print("Reduction\n");
1410  if(!(canonicalize % 50)) {
1411  kBucketCanonicalize(bucket);
1412  }
1413  tempPoly = kBucketGetLm(bucket);
1414  //Print("TEMPPOLY: ");
1415  //pWrite(tempPoly);
1416  if(NULL != tempPoly) {
1417  tempRed = gPrev->getFirst();
1418  continue;
1419  }
1420  else {
1421  break;
1422  }
1423  }
1424 
1425  }
1426  else {
1427  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1428  //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1429  //pWrite(u);
1430  //pWrite(tempRed->getTerm());
1431  //pWrite(pHead(tempRed->getPoly()));
1432  //addToG = 0;
1433  }
1434  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1435  // passing criterion2 ?
1436  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1437  // passing criterion1 ?
1438  if(!criterion1(gPrev,u,tempRed,lTag)) {
1439  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1440  if(NULL == redPoly) {
1441  bad->insert(tempRed->getLPolyOld());
1442  addToG = 1;
1443  //poly tempRedPoly = tempRed->getPoly();
1444  //break;
1445  }
1446  }
1447  else {
1448  poly tempRedPoly = tempRed->getPoly();
1449  //Print("REDUCER: ");
1450  //pWrite(ppMult_qq(u,tempRedPoly));
1451  pIter(tempRedPoly);
1452  int lTempRedPoly = pLength(tempRedPoly);
1453  //Print("HEAD MONOMIAL KBUCKET: ");
1454  //pWrite(kBucketGetLm(bucket));
1455  kBucketExtractLm(bucket);
1456  kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1457  canonicalize++;
1458  //Print("REDUCTION\n");
1459  addToG = 1;
1460  if(!(canonicalize % 50)) {
1461  kBucketCanonicalize(bucket);
1462  }
1463  //Print("HEAD MONOMIAL KBUCKET: ");
1464  //pWrite(kBucketGetLm(bucket));
1465  tempPoly = kBucketGetLm(bucket);
1466  //Print("TEMPPOLY: ");
1467  //pWrite(tempPoly);
1468  if(NULL != tempPoly) {
1469  tempRed = gPrev->getFirst();
1470  continue;
1471  }
1472  else {
1473  break;
1474  }
1475  }
1476  }
1477  }
1478  else {
1479  //Print("CRIT 1 ");
1480 
1481  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1482  //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1483  //pWrite(u);
1484  //pWrite(tempRed->getTerm());
1485  //pWrite(tempRed->getPoly());
1486  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1487  //Print("REDUCER LABEL: ");
1488  //pWrite(tempRed->getTerm());
1489  addToG = 0;
1490  }
1491  }
1492  }
1493  }
1494  else {
1495  //Print("CRIT 2 ");
1496  if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1497  //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1498  //pWrite(u);
1499  //pWrite(tempRed->getTerm());
1500  //pWrite(tempRed->getPoly());
1501  if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1502  //Print("REDUCER LABEL: ");
1503  //pWrite(tempRed->getTerm());
1504 addToG = 0;
1505  }
1506  }
1507  }
1508  }
1509 
1510  }
1511  tempRed = tempRed->getNext();
1512  }
1513  }
1514  if(NULL != tempPoly) {
1515  if(NULL == redPoly) {
1516  redPoly = kBucketExtractLm(bucket);
1517  }
1518  else {
1519  redPoly = p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing);
1520  }
1521  // for top-reduction only
1522  redPoly = p_Merge_q(redPoly,kBucketClear(bucket),currRing);
1523  break;
1524  // end for top-reduction only
1525  tempPoly = kBucketGetLm(bucket);
1526 
1527  }
1528  }
1529  if(NULL == redPoly) {
1530  reductionsToZero++;
1531  //pDelete(&redPoly);
1532  }
1533  else
1534  {
1535  PrintS("\nELEMENT ADDED TO GPREV: ");
1536  pNorm(redPoly);
1537  if(highestDegree < pDeg(redPoly))
1538  {
1539  highestDegree = pDeg(redPoly);
1540  }
1541  pWrite(pHead(redPoly));
1542  //pWrite(l->getTerm());
1543  //Print("%d\n",canonicalize);
1544  l->setPoly(redPoly);
1545  // give "l" the label if it is "useful" (addToG = 0) or "useless"
1546  // (addToG = 1)
1547  l->setDel(!addToG);
1548  Print("redundant? %d\n\n",l->getDel());
1549  if(addToG == 0 && termination == 1) {
1550  reducers->insert(l->getLPolyOld());
1551  }
1552  else {
1553  gPrev->insert(l->getLPolyOld());
1554  }
1555  //Print("%d\n\n",termination);
1556  if(termination == 1) {
1557  if(addToG) {
1558  //Print("----------------HERE?-----------------\n");
1559  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1560  }
1561  else {
1562  notInG++;
1563  //Print("\nNONONO");
1564  //pWrite(pHead(l->getPoly()));
1565  //pWrite(l->getTerm());
1566  }
1567  }
1568  // case in which all new elements are added to gPrev!
1569  // using boolean "addToG" to know if the element is "useful" (0) or
1570  // "useless" (1)
1571  else {
1572  if(!l->getDel()) {
1573  criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1574  }
1575  else {
1576  criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1577  }
1578  }
1579  }
1580 
1581  // if there are "bad" reducers than try to compute new S-polynomials and rules
1582 
1583  if(NULL != bad->getFirst()) {
1584  //Print("BAD STUFF LIST:\n");
1585  //bad->print();
1586  LNode* tempBad = bad->getFirst();
1587  //pWrite(l->getPoly());
1588  while(NULL != tempBad) {
1589  if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
1590  //Print("BAD STUFF\n");
1591  //pWrite(l->getPoly());
1592  //pWrite(tempBad->getPoly());
1593  u = pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly()));
1594  //Print("MULTIPLIER: ");
1595  //pWrite(u);
1596  pSetCoeff(u,nOne);
1597  if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) {
1598  // passing criterion2 ?
1599  if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) {
1600  // passing criterion1 ?
1601  if(!criterion1(gPrev,u,tempBad,lTag)) {
1602  //Print("HIERHIERHIERHIERHIERHIER\n");
1603  rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
1604  numberOfRules++;
1605  //gPrev->print();
1606  //pWrite(l->getPoly());
1607  poly temp = ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly());
1608  //pWrite(l->getPoly());
1609  //Print("%p\n",temp);
1610  //gPrev->print();
1611  if(NULL != temp) {
1612  pNorm(temp);
1613  LNode* tempBadNew = new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
1614  //pWrite(temp);
1615  //pWrite(tempBadNew->getPoly());
1616  //pWrite(tempBadNew->getTerm());
1617  //pWrite(pHead(tempBadNew->getPoly()));
1618  //Print("%p\n",tempBadNew->getPoly());
1619  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1620  tempBadNew->setDel(1);
1621 
1622  sPolyList->insertByLabel(tempBadNew);
1623  //Print("BAD SPOLYLIST: \n");
1624  //sPolyList->print();
1625  }
1626  }
1627  }
1628  }
1629  }
1630  //Print("HIER\n");
1631  tempBad = tempBad->getNext();
1632  //Print("%p\n",tempBad);
1633  }
1634  // Print("-------------------BAD STUFF LIST-----------------------------\n");
1635  }
1636  //Print("HIER AUCH\n");
1637  //Print("SPOLYLIST IN BAD: \n");
1638  //sPolyList->print();
1639  //Print("END FIND REDUCERS\n");
1640 }
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:495
int notInG
Definition: f5gb.cc:35
int reductionsToZero
Definition: f5gb.cc:37
#define ppMult_qq(p, q)
Definition: polys.h:191
#define pDivide(a, b)
Definition: polys.h:275
LNode * getNext()
Definition: f5lists.cc:322
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:467
#define Print
Definition: emacs.cc:83
void insert(LPolyOld *lp)
Definition: f5lists.cc:458
bool getDel()
Definition: f5lists.cc:352
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
poly getTerm()
Definition: f5lists.cc:336
bool bad
Definition: facFactorize.cc:65
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:480
void pWrite(poly p)
Definition: polys.h:290
poly getPoly()
Definition: f5lists.cc:332
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:485
#define pIter(p)
Definition: monomials.h:44
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
int numberOfRules
Definition: f5gb.cc:36
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
Definition: f5gb.cc:445
Definition: f5lists.h:65
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
LNode * getFirstCurrentIdx()
Definition: f5lists.cc:646
#define pDivideM(a, b)
Definition: polys.h:276
LPolyOld * getLPolyOld()
Definition: f5lists.cc:327
P bucket
Definition: myNF.cc:79
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:618
void PrintS(const char *s)
Definition: reporter.cc:284
#define pOne()
Definition: polys.h:297
static unsigned pLength(poly a)
Definition: p_polys.h:189
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:690
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
void setPoly(poly p)
Definition: f5lists.cc:357
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1063
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:679
void setDel(bool d)
Definition: f5lists.cc:373
#define pDeg(A)
Definition: f5gb.cc:33
#define NULL
Definition: omList.c:10
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition: polys.h:138
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1135
Definition: f5lists.h:127
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
Definition: f5lists.cc:494
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
int highestDegree
Definition: f5gb.cc:40
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
Definition: f5gb.cc:557
polyrec * poly
Definition: hilb.h:10
int getIndex()
Definition: f5lists.cc:340
LNode * getFirst()
Definition: f5lists.cc:520
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:193
#define nInit(i)
Definition: numbers.h:24
int kBucketCanonicalize(kBucket_pt bucket)
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
static int sign(int x)
Definition: ring.cc:3333
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168

◆ findReductor()

LNode* findReductor ( LNode l,
LList sPolyList,
LNode gPrevRedCheck,
LList gPrev,
RList rules,
LTagList lTag,
RTagList rTag,
PList rejectedGBList 
)

Definition at line 1818 of file f5gb.cc.

1818  {
1819  // allociation of memory for the possible reductor
1820  //Print("LPOLY: ");
1821  //pWrite(l->getPoly());
1822  poly u = pOne();
1823  poly red;
1824  number nOne = nInit(1);
1825  LNode* temp;
1826  // head term of actual element such that we do not have to call pHead at each new reductor test
1827  poly t = pHead(l->getPoly());
1828  // if l was already checked use the information in gPrevRedCheck such
1829  // that we can start searching for new reducers from this point and
1830  // not from the first element of gPrev with the current index
1831  temp = gPrevRedCheck;
1832  // search for reductors until we are at the end of gPrev resp. at the
1833  // end of the elements of the current index
1834  while(NULL != temp && temp->getIndex() == l->getIndex()) {
1835  // does the head of the element of gPrev divides the head of
1836  // the to be reduced element?
1837  if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) {
1838  // get all the information needed for the following tests
1839  // of the criteria
1840  u = pDivide(t,pHead(temp->getPoly()));
1841  pSetCoeff(u,nOne);
1842  red = ppMult_qq(u,temp->getPoly());
1843  pNorm(red);
1844  // check if both have the same label
1845  if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) {
1846  // passing criterion2 ?
1847  if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1848  // passing criterion1 ?
1849  if(!criterion1(gPrev,u,temp,lTag)) {
1850  gPrevRedCheck = temp->getNext();
1851  LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
1852  return redNode;
1853  }
1854  }
1855  }
1856  if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == 1) {
1857  // passing criterion2 ?
1858  if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1859  // passing criterion1 ?
1860  if(!criterion1(gPrev,u,temp,lTag)) {
1861  poly tempSpoly = ksOldSpolyRedNew(red,l->getPoly());
1862  rules->insert(temp->getIndex(),ppMult_qq(u,temp->getTerm()));
1863  gPrevRedCheck = temp->getNext();
1864  if(NULL != tempSpoly) {
1865  pNorm(tempSpoly);
1866  sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld());
1867  //Print("NEW ONE: ");
1868  //pWrite(tempSpoly);
1869  //Print("HIER\n");
1870  //sPolyList->print();
1871  //sleep(5);
1872  }
1873  }
1874  }
1875  }
1876  }
1877  //Print("AUCH HIER\n");
1878  temp = temp->getNext();
1879  }
1880 
1881 // delete temp;
1882  return NULL;
1883 }
#define ppMult_qq(p, q)
Definition: polys.h:191
#define pDivide(a, b)
Definition: polys.h:275
LNode * getNext()
Definition: f5lists.cc:322
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
poly getTerm()
Definition: f5lists.cc:336
poly getPoly()
Definition: f5lists.cc:332
Definition: f5lists.h:65
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:618
#define pOne()
Definition: polys.h:297
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1063
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
Definition: f5gb.cc:679
#define NULL
Definition: omList.c:10
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
Definition: f5lists.cc:494
polyrec * poly
Definition: hilb.h:10
int getIndex()
Definition: f5lists.cc:340
LNode * getFirst()
Definition: f5lists.cc:520
#define nInit(i)
Definition: numbers.h:24
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31

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

1140  {
1141  //Print("##########################################In REDUCTION!########################################\n");
1142  // check if sPolyList has any elements
1143  // NOTE: due to initialization sPolyList always has a default NULL element
1144  //Print("--1--\n");
1145  LNode* temp = sPolyList->getFirst();
1146  //Print("START OF REDUCTION: ");
1147  while(NULL != temp) {
1149  // temp is the first element in the sPolyList which should be reduced
1150  // due to earlier sorting this is the element of minimal degree AND
1151  // minimal label
1152  // delete the above first element from sPolyList, temp will be either reduced to
1153  // zero or added to gPrev, but never come back to sPolyList
1154  //Print("LIST OF SPOLYNOMIALS!\n");
1155  //sPolyList->print();
1156  //pWrite(sPolyList->getFirst()->getPoly());
1157  sPolyList->setFirst(temp->getNext());
1158  //if(pDeg(temp->getPoly()) > 11) {
1159  // Print("YES!!!!!!!!!!!!!!!!\n");
1160  //}
1161  //pWrite(temp->getPoly());
1162  //poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly());
1163  //Print("!!!\n");
1164  //if(NULL != tempNF) {
1165  //pNorm(tempNF);
1166  //temp->setPoly(tempNF);
1167  //Print("lower label reduction: ");
1168  //pWrite(tempNF);
1169  // try further reductions of temp with polynomials in gPrev
1170  // with label index = current label index: this is done such that there
1171  // is no label corruption during the reduction process
1172  findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1173  //}
1174  //else {
1175  // reductionsToZero++;
1176  // delete temp;
1177  //}
1178  //if(NULL != temp->getPoly()) {
1179  // criticalPair(gPrev,critPairs,lTag,rTag,rules);
1180  //}
1181  //Print("HIER AUCH ?\n");
1182  //Print("--2--\n");
1183  //sPolyList->print();
1184  //critPairs->print();
1185  temp = sPolyList->getFirst();
1186  //Print("%p\n",temp);
1187  }
1188  //sPolyList->print();
1189  //delete sPolyList;
1190  //Print("REDUCTION FERTIG\n");
1191 }
LNode * getNext()
Definition: f5lists.cc:322
void findReducers(LNode *l, LList *sPolyList, ideal gbPrev, LList *gPrev, LList *reducers, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, int termination, PList *rejectedGBList, int plus)
searches for reducers of temp similar to the symbolic preprocessing of F4 and divides them into a "g...
Definition: f5gb.cc:1206
int numberOfReductions
Definition: f5gb.cc:47
Definition: f5lists.h:65
#define NULL
Definition: omList.c:10
void setFirst(LNode *l)
Definition: f5lists.cc:532
LNode * getFirst()
Definition: f5lists.cc:520

◆ qsortDegree()

void qsortDegree ( poly left,
poly right 
)

Definition at line 55 of file f5gb.cc.

56 {
57  poly* ptr1 = left;
58  poly* ptr2 = right;
59  poly p1,p2;
60  p2 = *(left + (right - left >> 1));
61  do
62  {
63  while(p_Totaldegree(*ptr1, currRing) < p_Totaldegree(p2, currRing))
64  {
65  ptr1++;
66  }
67  while(p_Totaldegree(*ptr2, currRing) > p_Totaldegree(p2,currRing))
68  {
69  ptr2--;
70  }
71  if(ptr1 > ptr2)
72  {
73  break;
74  }
75  p1 = *ptr1;
76  *ptr1 = *ptr2;
77  *ptr2 = p1;
78  } while(++ptr1 <= --ptr2);
79 
80  if(left < ptr2)
81  {
82  qsortDegree(left,ptr2);
83  }
84  if(ptr1 < right)
85  {
86  qsortDegree(ptr1,right);
87  }
88 }
void qsortDegree(poly *left, poly *right)
Definition: f5gb.cc:55
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1430
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
END_NAMESPACE const void * p2
Definition: syzextra.cc:202
polyrec * poly
Definition: hilb.h:10

◆ reduction()

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

Definition at line 1093 of file f5gb.cc.

1094  {
1095  //Print("##########################################In REDUCTION!########################################\n");
1096  // check if sPolyList has any elements
1097  // NOTE: due to initialization sPolyList always has a default NULL element
1098  LNode* temp = sPolyList->getFirst();
1099  while(NULL != temp) {
1100  // temp is the first element in the sPolyList which should be reduced
1101  // due to earlier sorting this is the element of minimal degree AND
1102  // minimal label
1103  // delete the above first element from sPolyList, temp will be either reduced to
1104  // zero or added to gPrev, but never come back to sPolyList
1105  //pWrite(sPolyList->getFirst()->getPoly());
1106  //Print("LIST OF SPOLYNOMIALS!\n");
1107  //sPolyList->print();
1108  sPolyList->setFirst(temp->getNext());
1109  poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly());
1110  if(NULL != tempNF) {
1111  pNorm(tempNF);
1112  temp->setPoly(tempNF);
1113  // try further reductions of temp with polynomials in gPrev
1114  // with label index = current label index: this is done such that there
1115  // is no label corruption during the reduction process
1116  //Print("lower label reduction: ");
1117  //pWrite(tempNF);
1118  topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1119 
1120  }
1121  else {
1122  reductionsToZero++;
1123  delete temp;
1124  }
1125  //if(NULL != temp->getPoly()) {
1126  // criticalPair(gPrev,critPairs,lTag,rTag,rules);
1127  //}
1128  temp = sPolyList->getFirst();
1129  }
1130  //sPolyList->print();
1131  //delete sPolyList;
1132 }
int reductionsToZero
Definition: f5gb.cc:37
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
LNode * getNext()
Definition: f5lists.cc:322
poly getPoly()
Definition: f5lists.cc:332
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
Definition: f5lists.h:65
void setPoly(poly p)
Definition: f5lists.cc:357
#define NULL
Definition: omList.c:10
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
void setFirst(LNode *l)
Definition: f5lists.cc:532
polyrec * poly
Definition: hilb.h:10
LNode * getFirst()
Definition: f5lists.cc:520
void topReduction(LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1708

◆ 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

Definition at line 96 of file f5gb.cc.

96  {
97  int i;
98  long sum = 0;
99  for(i=1; i<=k; i++) {
100  Print("%d\n",v[i]);
101  Print("%ld\n",sum);
102  sum = sum + v[i];
103  }
104  return sum;
105 }
#define Print
Definition: emacs.cc:83
int k
Definition: cfEzgcd.cc:93
int i
Definition: cfEzgcd.cc:123
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37

◆ topReduction()

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

Definition at line 1708 of file f5gb.cc.

1708  {
1709  //Print("##########################################In topREDUCTION!########################################\n");
1710  // try l as long as there are reductors found by findReductor()
1711  LNode* gPrevRedCheck = lTag->getFirstCurrentIdx();
1712  LNode* tempRed;
1713  poly pOne = pOne();
1714  do {
1715  //int timer5 = initTimer();
1716  //startTimer();
1717  //Print("TOP REDUCTION: ");
1718  //pWrite(l->getPoly());
1719  tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1720  //timer5 = getTimer();
1721  //reductionTime = reductionTime + timer5;
1722  // if a reductor for l is found and saved in tempRed
1723  if(NULL != tempRed) {
1724  // if label of reductor is greater than the label of l we have to built a new element
1725  // and add it to sPolyList
1726 
1727  if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1728  // needed sinc pSub destroys the arguments!
1729  //poly temp_poly_l = pInit();
1730  //temp_poly_l = pCopy(l->getPoly());
1731  //Print("VORHER: ");
1732  //pWrite(tempRed->getPoly());
1733  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1734  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1735  rules->insert(tempRed->getIndex(),tempRed->getTerm());
1736  //Print("NACHHER: ");
1737  //pWrite(tempRed->getPoly());
1738  //Print("TEMP: ");
1739  //pWrite(temp);
1740  if(NULL != temp) {
1741  pNorm(temp);
1742  //tempRed->setPoly(temp);
1743  //tempRed->setDel(1);
1744  //rules->insert(tempRed->getIndex(),tempRed->getTerm());
1745  LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld());
1746  //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1747  tempRedNew->setDel(1);
1748  sPolyList->insertByLabel(tempRedNew);
1749  }
1750  else {
1751  pDelete(&temp);
1752  reductionsToZero++;
1753  //delete tempRed;
1754  }
1755  }
1756 
1757  // label of reductor is smaller than the label of l, subtract reductor from l and delete the
1758  // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
1759  // after subtraction
1760  else {
1761 
1762  //poly temp_poly_l = pInit();
1763  //temp_poly_l = pCopy(l->getPoly());
1764  //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1765  //Print("REDUCER: ");
1766  //pWrite(tempRed->getPoly());
1767  //pWrite(tempRed->getTerm());
1768  poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1769  //Print("REDUCED ELEMENT: ");
1770  if(NULL != temp) {
1771  pNorm(temp);
1772  //pWrite(temp);
1773  poly tempNF = kNF(gbPrev,currRing->qideal,temp);
1774  pNorm(tempNF);
1775  if(NULL == tempNF) {
1776  reductionsToZero++;
1777  pDelete(&tempNF);
1778  l->setPoly(NULL);
1779  break;
1780  }
1781  l->setPoly(tempNF);
1782 
1783  gPrevRedCheck = lTag->getFirstCurrentIdx();
1784  }
1785  else {
1786  reductionsToZero++;
1787  pDelete(&temp);
1788  l->setPoly(NULL);
1789  break;
1790  }
1791  }
1792  }
1793  else {
1794  if(NULL != l->getPoly()) {
1795  pNorm(l->getPoly());
1796  //Print("ELEMENT ADDED TO GPREV: ");
1797  //pWrite(l->getPoly());
1798  gPrev->insert(l->getLPolyOld());
1799  //Print("TEMP RED == 0 ");
1800  //pWrite(l->getPoly());
1801  //pWrite(l->getTerm());
1802  //rules->print();
1803  criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1804  //Print("LIST OF CRITICAL PAIRS: \n");
1805  //critPairs->print();
1806  }
1807  break;
1808  }
1809  } while(1);
1810 }
int reductionsToZero
Definition: f5gb.cc:37
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
void insert(LPolyOld *lp)
Definition: f5lists.cc:458
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
poly getTerm()
Definition: f5lists.cc:336
poly getPoly()
Definition: f5lists.cc:332
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
Definition: f5gb.cc:445
Definition: f5lists.h:65
LNode * getFirstCurrentIdx()
Definition: f5lists.cc:646
RuleOld * getRuleOld()
Definition: f5lists.cc:1028
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
Definition: f5gb.cc:1818
LPolyOld * getLPolyOld()
Definition: f5lists.cc:327
#define pOne()
Definition: polys.h:297
void setPoly(poly p)
Definition: f5lists.cc:357
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1063
void setDel(bool d)
Definition: f5lists.cc:373
#define NULL
Definition: omList.c:10
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
void insert(RuleOld *r)
Definition: f5lists.cc:1084
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
Definition: f5lists.cc:494
#define pDelete(p_ptr)
Definition: polys.h:169
polyrec * poly
Definition: hilb.h:10
int getIndex()
Definition: f5lists.cc:340
RNode * getFirst()
Definition: f5lists.cc:1092

Variable Documentation

◆ degreeBound

int degreeBound = 0

Definition at line 41 of file f5gb.cc.

◆ highestDegree

int highestDegree = 0

Definition at line 40 of file f5gb.cc.

◆ highestDegreeGBCriticalPair

int highestDegreeGBCriticalPair = 0

Definition at line 45 of file f5gb.cc.

◆ notInG

int notInG = 0

Definition at line 35 of file f5gb.cc.

◆ numberOfReductions

int numberOfReductions = 0

Definition at line 47 of file f5gb.cc.

◆ numberOfRules

int numberOfRules = 0

Definition at line 36 of file f5gb.cc.

◆ numberOfSpolys

int numberOfSpolys = 0

Definition at line 48 of file f5gb.cc.

◆ numberRejectedF5CriticalPairs

int numberRejectedF5CriticalPairs = 0

Definition at line 46 of file f5gb.cc.

◆ numberUsefulPairs

int numberUsefulPairs = 0

Definition at line 42 of file f5gb.cc.

◆ numberUsefulPairsMinDeg

int numberUsefulPairsMinDeg = 0

Definition at line 44 of file f5gb.cc.

◆ numberUselessPairs

int numberUselessPairs = 0

Definition at line 43 of file f5gb.cc.

◆ reductionsToZero

int reductionsToZero = 0

Definition at line 37 of file f5gb.cc.

◆ reductionTime

int reductionTime = 0

Definition at line 38 of file f5gb.cc.

◆ spolsTime

int spolsTime = 0

Definition at line 39 of file f5gb.cc.