Context Navigation

source: git/kernel/GBEngine/f5gb.cc @ 9e8bfa

fieker-DuValspielwiese

Last change on this file since 9e8bfa was ac00e2f, checked in by Hans Schoenemann <hannes@…>, 10 years ago
removed currQuotient
Property mode set to `100644`
File size: 86.8 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: