Context Navigation

source: git/kernel/GBEngine/f5gb.cc @ a3f0fea

spielwiese

Last change on this file since a3f0fea was a3f0fea, checked in by Reimer Behrends <behrends@…>, 5 years ago
Modify variable declarions for pSingular.
Property mode set to `100644`
File size: 86.9 KB

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

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

Download in other formats: