Context Navigation

source: git/kernel/f5gb.cc @ 08a955

spielwiese

Last change on this file since 08a955 was 762407, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
config.h is for sources files only FIX: config.h should only be used by source (not from inside kernel/mod2.h!) NOTE: each source file should better include mod2.h right after config.h, while headers should better not include mod2.h.
Property mode set to `100644`
File size: 87.6 KB

Line
1	/****************************************
2	* Computer Algebra System SINGULAR *
3	****************************************/
4	/*
5	* ABSTRACT: f5gb interface
6	*/
7
8	#include "config.h"
9	#include <kernel/mod2.h>
10	#ifdef HAVE_F5
11	#include <unistd.h>
12	#include <omp.h>
13	#include <kernel/structs.h>
14	#include <kernel/kutil.h>
15	#include <omalloc/omalloc.h>
16	#include <kernel/polys.h>
17	#include <polys/monomials/p_polys.h>
18	#include <polys/templates/p_Procs.h>
19	#include <kernel/ideals.h>
20	#include <kernel/febase.h>
21	#include <kernel/kstd1.h>
22	#include <kernel/khstd.h>
23	#include <polys/kbuckets.h>
24	#include <polys/weight.h>
25	#include <misc/intvec.h>
26	#include <kernel/polys.h>
27	#include <kernel/f5gb.h>
28	#include <kernel/f5data.h>
29	#include <kernel/f5lists.h>
30	#include <kernel/timer.h>
31	int notInG = 0;
32	int numberOfRules = 0;
33	int reductionsToZero = 0;
34	int reductionTime = 0;
35	int spolsTime = 0;
36	int highestDegree = 0;
37	int degreeBound = 0;
38	int numberUsefulPairs = 0;
39	int numberUselessPairs = 0;
40	int numberUsefulPairsMinDeg = 0;
41	int highestDegreeGBCriticalPair = 0;
42	int numberRejectedF5CriticalPairs = 0;
43	int numberOfReductions = 0;
44	int numberOfSpolys = 0;
45	/*
46	====================================================================
47	sorting ideals by decreasing total degree "left" and "right" are the
48	pointer of the first and last polynomial in the considered ideal
49	====================================================================
50	*/
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++;
59	}
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	}
77	}
78
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	/*!
97	==========================================================================
98	compares monomials, i.e. divisibility tests for criterion 1 and criterion 2
99	==========================================================================
100	*/
101	bool compareMonomials(int* m1, int** m2, int numberOfRules, int k) {
102	int i,j;
103	long sumM1 = sumVector(m1,k);
104	//int k = sizeof(m1) / sizeof(int);
105	for(i=0; i<numberOfRules; i++) {
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	}
111	}
112	}
113	}
114	return false;
115	}
116
117	/*
118	==================================================
119	computes incrementally gbs of subsets of the input
120	gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
121	==================================================
122	*/
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) {
124	//Print("in f5inc\n");
125	//pWrite(rules->getFirst()->getRuleTerm());
126	int iterationstep = i;
127	int j;
128	//Print("%p\n",gPrev->getFirst());
129	//pWrite(gPrev->getFirst()->getPoly());
130	poly tempNF = kNF(gbPrev,currQuotient,f_i);
131	f_i = tempNF;
132	//gPrev->insert(ONE,i,f_i);
133	gPrev->insert(ONE,gPrev->getLength()+1,f_i);
134	// tag the first element in gPrev of the current index for findReductor()
135	lTag->setFirstCurrentIdx(gPrev->getLast());
136	//Print("1st gPrev: ");
137	//pWrite(gPrev->getFirst()->getPoly());
138	//Print("2nd gPrev: ");
139	//pWrite(gPrev->getFirst()->getNext()->getPoly());
140	//pWrite(gPrev->getFirst()->getNext()->getPoly());
141	CListOld* critPairs = new CListOld();
142	CNode* critPairsMinDeg = new CNode();
143	PList* rejectedGBList = new PList();
144	// computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
145	// in the list critPairs
146	criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
147	static LList* sPolyList = new LList();
148	//sPolyList->print();
149	// labeled polynomials which have passed reduction() and have to be added to list gPrev
150	static LList* completed = new LList();
151	// the reduced labeled polynomials which are returned from subalgorithm reduction()
152	static LList* reducedLPolys = new LList();
153	// while there are critical pairs to be further checked and deleted/computed
154	while(NULL != critPairs->getFirst()) {
155	// critPairs->getMinDeg() deletes the first elements of minimal degree from
156	// critPairs, thus the while loop is not infinite.
157	// adds all to be reduced S-polynomials in the list sPolyList and adds
158	// the corresponding rules to the list rules
159	// NOTE: inside there is a second check of criterion 2 if new rules are
160	// added
161	//int timer4 = initTimer();
162	//startTimer();
163	//critPairs->print();
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);
180	//Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg());
181	long degreecheck = critPairsMinDeg->getData()->getDeg();
182
183	computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
184	//}
185	//}
186	//}
187	//else {
188	// return gPrev;
189	//}
190	//timer4 = getTimer();
191	//Print("SPOLS TIMER: %d\n",timer4);
192	//spolsTime = spolsTime + timer4;
193	// DEBUG STUFF FOR SPOLYLIST
194	LNode* temp = sPolyList->getFirst();
195	//while(NULL != temp && NULL != temp->getLPoly()) {
196	//Print("Spolylist element: ");
197	//pWrite(temp->getPoly());
198	//temp = temp->getNext();
199	//}
200	// reduction process of new S-polynomials and also adds new critical pairs to critPairs
201	//int timer3 = initTimer();
202	//startTimer();
203	//sPolyList->print();
204	//reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
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	//}
216	//Print("ARRIS DEG: %ld\n",arrideg);
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	//}
222
223
224	//bool aha = checkDGB(gPrev);
225
226
227	//timer3 = getTimer();
228	//reductionTime = reductionTime + timer3;
229	//Print("REDUCTION TIMER: %d\n",timer3);
230	// DEBUG STUFF FOR GPREV
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);
242
243	}
244	//Print("REDUCTION DONE\n");
245	//Print("%p\n",rules->getFirst());
246	//Print("%p\n",rTag->getFirst());
247	//if(rules->getFirst() != rTag->getFirst()) {
248	//Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
249	//rTag->insert(rules->getFirst());
250	//}
251	//else {
252	//Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
253	//}
254	lTag->insert(lTag->getFirstCurrentIdx());
255	//Print("INDEX: %d\n",tempTag->getIndex());
256	//pWrite(tempTag->getPoly());
257	//Print("COMPLETED FIRST IN F5INC: \n");
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());
264	//delete sPolyList;
265	//critPairs->print();
266	delete critPairs;
267	//Print("IN F5INC\n");
268	/*
269	Print("\n\n\nRULES: \n");
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	}
282	*/
283	//gPrev->print();
284	//Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
285	//Print("COMPLETE SPOLS TIME UNTIL NOW: %d\n",spolsTime);
286	degreeBound = 0;
287	return gPrev;
288	}
289
290
291
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);
333
334	poly reducer = pOne();
335	//reducer = gb->m[0];
336	int i = 0;
337	pWrite(pHead(sp));
338
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	}
356
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.
371	* return value: 0, if all remaining critical pairs are deleted by
372	* Buchberger's criteria
373	* 1, otherwise
374	*/
375	bool arrisCheck(CNode* first, LNode* firstGCurr, long arrideg) {
376	CNode* temp = first;
377
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
422
423
424	/*
425	================================================================
426	computes a list of critical pairs for the next reduction process
427	the first element is always "useful" thus the critical pair
428	computed is either "useful" or "useless" depending on the second
429	element which generates the critical pair.
430	first element in gPrev is always the newest element which must
431	build critical pairs with all other elements in gPrev
432	================================================================
433	*/
434	inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList, int plus) {
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;
445	//Print("NEW: ");
446	//pWrite(newElement->getPoly());
447	//Print("ADDRESS: %p",newElement);
448	if(NULL != rules->getFirst()) {
449	testedRuleOld = rules->getFirst()->getRuleOld();
450	}
451	// computation of critical pairs
452	while( gPrev->getLast() != temp) {
453	//Print("TEMP: ");
454	//pWrite(pHead(temp->getPoly()));
455	//Print("ADDRESS: %p",temp);
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);
466	int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly())));
467	// testing both new labels by the F5 Criterion
468	if(!temp->getDel()) {
469	if(plus && highestDegreeGBCriticalPair < degree) {
470	highestDegreeGBCriticalPair = degree;
471	}
472	if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
473	&& !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
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
477	if(newElement->getIndex() == temp->getIndex() &&
478	-1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
479	CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
480	temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);
481	critPairs->insert(cp);
482	// counting the number of useful pairs
483	numberUsefulPairs++;
484	}
485	else {
486	CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
487	newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);
488	critPairs->insert(cp);
489	// counting the number of useful pairs
490	numberUsefulPairs++;
491	}
492	}
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	}
505	}
506	else {
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)
511	&& !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
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
515	if(newElement->getIndex() == temp->getIndex() &&
516	-1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
517	CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
518	temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
519	critPairs->insert(cp);
520	numberUselessPairs++;
521	}
522	else {
523	CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
524	newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
525	critPairs->insert(cp);
526	numberUselessPairs++;
527	}
528	}
529	//}
530	}
531	temp = temp->getNext();
532	}
533	}
534
535
536
537	/*
538	================================================================
539	computes a list of critical pairs for the next reduction process
540	the first element is always "useless" thus the critical pair
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	*/
546	inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList) {
547	//Print("IN CRITPAIRS\n");
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());
556	RuleOld* testedRuleOld = NULL;
557	if(NULL != rules->getFirst()) {
558	testedRuleOld = rules->getFirst()->getRuleOld();
559	}
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
565	u1 = pDivide(lcm,t);
566	if(NULL == u1) {
567	break;
568	}
569	pSetCoeff(u1,nOne);
570	u2 = pDivide(lcm,pHead(temp->getPoly()));
571	pSetCoeff(u2,nOne);
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)
577	&& !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
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
581	if(newElement->getIndex() == temp->getIndex() &&
582	-1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
583	CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
584	temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
585	critPairs->insert(cp);
586	numberUselessPairs++;
587	}
588	else {
589	CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
590	newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
591	critPairs->insert(cp);
592	numberUselessPairs++;
593	}
594	}
595	//}
596	temp = temp->getNext();
597	}
598	}
599
600
601
602	/*
603	========================================
604	Criterion 1, i.e. Faugere's F5 Criterion
605	========================================
606	*/
607	inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
608	// starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
609	int idx = l->getIndex();
610	int i;
611	if(idx == 1) {
612	//Print("HIER\n");
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());
619	//Print("------------------------------IN CRITERION 1-----------------------------------------\n");
620	//Print("TESTED ELEMENT: ");
621	//pWrite(l->getPoly());
622	//pWrite(l->getTerm());
623	//pWrite(ppMult_qq(t,l->getTerm()));
624	//Print("%d\n\n",l->getIndex());
625	while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) {
626	//pWrite(testNode->getPoly());
627	//Print("%d\n",testNode->getIndex());
628	if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
629	//Print("Criterion 1 NOT passed!\n");
630	if(idx != gPrev->getLast()->getIndex()) {
631	//Print("DOCH!\n");
632	}
633	return true;
634	}
635	//pWrite(testNode->getNext()->getPoly());
636	testNode = testNode->getNext();
637	}
638	/*
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	}
644	poly temp = kNF(testId,currQuotient,u1);
645	//pWrite(temp);
646	for(i=0;i<IDELEMS(testId);i++) {
647	testId->m[i] = NULL;
648	}
649	idDelete(&testId);
650	if(NULL == temp) {
651	//if(l->getIndex() != gPrev->getFirst()->getIndex()) {
652	// Print("----------------------------Criterion1 not passed----------------------------------\n");
653	//}
654	return true;
655	}
656	*/
657	return false;
658	}
659	}
660
661
662
663	/*
664	=====================================
665	Criterion 2, i.e. Rewritten Criterion
666	=====================================
667	*/
668	inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) {
669	//Print("------------------------------IN CRITERION 2/1-----------------------------------------\n");
670	/*
671	Print("RULES: \n");
672	RNode* tempR = rules->getFirst();
673	Print("%p\n",tempR);
674	int i = 1;
675	while(NULL != tempR) {
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	}
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());
689	*/
690	// start at the previously added element to gPrev, as all other elements will have the same index for sure
691	if(idx > l->getIndex()) {
692	return false;
693	}
694
695	RNode* testNode; // = new RNode();
696	testNode = rules->getFirst();
697	/*
698	if(NULL == rTag->getFirst()) {
699	if(NULL != rules->getFirst()) {
700	testNode = rules->getFirst();
701	}
702	else {
703	return false;
704	}
705	}
706
707	else {
708
709	if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
710	testNode = rules->getFirst();
711	}
712	else {
713	//Print("HIER\n");
714	//Print("DEBUG\n");
715	//Print("L INDEX: %d\n",l->getIndex());
716	*-------------------------------------
717	* TODO: WHEN INTERREDUCING THE GB THE
718	* INDEX OF THE PREVIOUS ELEMENTS
719	* GETS HIGHER!
720	-----------------------------------
721	//testNode = rules->getFirst();
722	testNode = rTag->get(l->getIndex());
723	if(NULL == testNode) {
724	testNode = rules->getFirst();
725	}
726	//Print("TESTNODE ADDRESS: %p\n",testNode);
727	}
728	}
729	*/
730	//testNode = rules->getFirst();
731	// save the monom t1*label_term(l) as it is tested various times in the following
732	poly u1 = ppMult_qq(t,l->getTerm());
733	// first element added to rTag was NULL, check for this
734	//Print("%p\n",testNode->getRule());
735	// NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
736	//Print("TESTNODE: %p\n",testNode);
737	//pWrite(testNode->getRuleTerm());
738	if(NULL != testNode ) {
739	//pWrite(testNode->getRuleTerm());
740	}
741	if(NULL != testNode) {
742	if(testNode->getRuleOld() == l->getRuleOld()) {
743	//Print("%p\n%p\n",testNode->getRule(),l->getRule());
744	//Print("EQUAL\n");
745	}
746	else {
747	//Print("NOT EQUAL\n");
748	}
749	}
750	while(NULL != testNode && testNode->getRuleOld() != l->getRuleOld()
751	&& l->getIndex() == testNode->getRuleOldIndex()) {
752	//Print("%p\n",testNode);
753	//pWrite(testNode->getRuleTerm());
754	//pWrite(t);
755	//pWrite(l->getTerm());
756	//pWrite(u1);
757	//Print("%d\n",testNode->getRuleIndex());
758	if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
759	//Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
760	//Print("INDEX: %d\n",l->getIndex());
761	pDelete(&u1);
762	//Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
763	return true;
764	}
765	testNode = testNode->getNext();
766	}
767	//delete testNode;
768	pDelete(&u1);
769	//Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
770	return false;
771	}
772
773
774
775	/*
776	=================================================================================================================
777	Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
778	=================================================================================================================
779	*/
780	inline bool criterion2(poly t, LPolyOld* l, RList* rules, RuleOld* testedRuleOld) {
781	//Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
782	//Print("LAST RuleOld TESTED: %p",testedRuleOld);
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	}
791	//Print("TESTED ELEMENT: ");
792	//pWrite(l->getPoly());
793	//pWrite(l->getTerm());
794	//pWrite(ppMult_qq(t,l->getTerm()));
795	//Print("%d\n\n",l->getIndex());
796	*/
797	// start at the previously added element to gPrev, as all other elements will have the same index for sure
798	RNode* testNode = rules->getFirst();
799	// save the monom t1*label_term(l) as it is tested various times in the following
800	poly u1 = ppMult_qq(t,l->getTerm());
801	// first element added to rTag was NULL, check for this
802	while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) {
803	//pWrite(testNode->getRuleTerm());
804	if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
805	//Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
806	//Print("INDEX: %d\n",l->getIndex());
807	pDelete(&u1);
808	//Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
809	return true;
810	}
811	testNode = testNode->getNext();
812	}
813	pDelete(&u1);
814	//Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
815	return false;
816	}
817
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	}
832	/*
833	==================================
834	Computation of S-Polynomials in F5
835	==================================
836	*/
837	void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, PList* rejectedGBList) {
838	CNode* temp = first;
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();
849	poly sp = pInit();
850	number sign = nInit(-1);
851	//Print("###############################IN SPOLS##############################\n");
852	//first->print();
853	/*
854	* first of all: do everything for GB critical pairs
855	*/
856	while(NULL != temp) {
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())));
898	//Print("rejected!\n");
899
900	//Print("CRITERION 2 in SPOLS 2nd generator\n");
901	}
902	}
903	else {
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	}
923	}
924	}
925	/*
926	if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
927	//Print("rejected!\n");
928	rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
929	}
930
931
932	if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
933	if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
934	highestDegree = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
935	}
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);
946	}
947	else {
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());
956	f5pairs->insertWithoutSort(temp->getData());
957	///////////////////////////////////////
958
959	//sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
960	}
961	}
962	}
963	else {
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());
983	f5pairs->insertWithoutSort(temp->getData());
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
1001	temp = temp->getNext();
1002
1003	}
1004
1005	/*
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++;
1026	if(numberRejectedF5CriticalPairs < -1) { // \|\|
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());
1050
1051	//}
1052	//numberOfSpolys++;
1053	}
1054	//pSetExp(tempRule->getRuleOld()->getTerm(),1,1000);
1055	}
1056	temp = temp->getNext();
1057	tempRule = tempRule->getNext();
1058
1059	}
1060	*/
1061	// these critical pairs can be deleted now as they are either useless for further computations or
1062	// already saved as an S-polynomial to be reduced in the following
1063	delete first;
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	}
1076
1077	/*
1078	========================================================================
1079	reduction including subalgorithm topReduction() using Faugere's criteria
1080	========================================================================
1081	*/
1082	void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
1083	ideal gbPrev, PList* rejectedGBList, int plus) {
1084	//Print("##########################################In REDUCTION!########################################\n");
1085	// check if sPolyList has any elements
1086	// NOTE: due to initialization sPolyList always has a default NULL element
1087	LNode* temp = sPolyList->getFirst();
1088	while(NULL != temp) {
1089	// temp is the first element in the sPolyList which should be reduced
1090	// due to earlier sorting this is the element of minimal degree AND
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
1094	//pWrite(sPolyList->getFirst()->getPoly());
1095	//Print("LIST OF SPOLYNOMIALS!\n");
1096	//sPolyList->print();
1097	sPolyList->setFirst(temp->getNext());
1098	poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
1099	if(NULL != tempNF) {
1100	pNorm(tempNF);
1101	temp->setPoly(tempNF);
1102	// try further reductions of temp with polynomials in gPrev
1103	// with label index = current label index: this is done such that there
1104	// is no label corruption during the reduction process
1105	//Print("lower label reduction: ");
1106	//pWrite(tempNF);
1107	topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1108
1109	}
1110	else {
1111	reductionsToZero++;
1112	delete temp;
1113	}
1114	//if(NULL != temp->getPoly()) {
1115	// criticalPair(gPrev,critPairs,lTag,rTag,rules);
1116	//}
1117	temp = sPolyList->getFirst();
1118	}
1119	//sPolyList->print();
1120	//delete sPolyList;
1121	}
1122
1123	/*
1124	========================================================================
1125	reduction including subalgorithm topReduction() using Faugere's criteria
1126	========================================================================
1127	*/
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) {
1130	//Print("##########################################In REDUCTION!########################################\n");
1131	// check if sPolyList has any elements
1132	// NOTE: due to initialization sPolyList always has a default NULL element
1133	//Print("--1--\n");
1134	LNode* temp = sPolyList->getFirst();
1135	//Print("START OF REDUCTION: ");
1136	while(NULL != temp) {
1137	numberOfReductions++;
1138	// temp is the first element in the sPolyList which should be reduced
1139	// due to earlier sorting this is the element of minimal degree AND
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
1143	//Print("LIST OF SPOLYNOMIALS!\n");
1144	//sPolyList->print();
1145	//pWrite(sPolyList->getFirst()->getPoly());
1146	sPolyList->setFirst(temp->getNext());
1147	//if(pDeg(temp->getPoly()) > 11) {
1148	// Print("YES!!!!!!!!!!!!!!!!\n");
1149	//}
1150	//pWrite(temp->getPoly());
1151	//poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
1152	//Print("!!!\n");
1153	//if(NULL != tempNF) {
1154	//pNorm(tempNF);
1155	//temp->setPoly(tempNF);
1156	//Print("lower label reduction: ");
1157	//pWrite(tempNF);
1158	// try further reductions of temp with polynomials in gPrev
1159	// with label index = current label index: this is done such that there
1160	// is no label corruption during the reduction process
1161	findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1162	//}
1163	//else {
1164	// reductionsToZero++;
1165	// delete temp;
1166	//}
1167	//if(NULL != temp->getPoly()) {
1168	// criticalPair(gPrev,critPairs,lTag,rTag,rules);
1169	//}
1170	//Print("HIER AUCH ?\n");
1171	//Print("--2--\n");
1172	//sPolyList->print();
1173	//critPairs->print();
1174	temp = sPolyList->getFirst();
1175	//Print("%p\n",temp);
1176	}
1177	//sPolyList->print();
1178	//delete sPolyList;
1179	//Print("REDUCTION FERTIG\n");
1180	}
1181
1182
1183	/*!
1184	* ================================================================================
1185	* searches for reducers of temp similar to the symbolic preprocessing of F4 and
1186	* divides them into a "good" and "bad" part:
1187	*
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	*
1191	* the "bad" ones are the reducers which corrupt the label of temp, they are tested
1192	* later on for possible new rules and S-polynomials to be added to the algorithm
1193	* ================================================================================
1194	*/
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) {
1196	int canonicalize = 0;
1197	//int timerRed = 0;
1198	bool addToG = 1;
1199	number sign = nInit(-1);
1200	LList* good = new LList();
1201	LList* bad = new LList();
1202	LList* monomials = new LList(l->getLPolyOld());
1203	poly u = pOne();
1204	number nOne = nInit(1);
1205	LNode* tempRed = lTag->getFirstCurrentIdx();
1206	LNode* tempMon = monomials->getFirst();
1207	poly tempPoly = pInit();
1208	poly redPoly = NULL;
1209	int idx = l->getIndex();
1210	//Print("IN FIND REDUCERS: ");
1211	//pWrite(l->getPoly());
1212	tempPoly = pCopy(l->getPoly());
1213	//tempMon->setPoly(tempPoly);
1214	//while(NULL != tempMon) {
1215	// iteration over all monomials in tempMon
1216	kBucket* bucket = kBucketCreate(currRing);
1217	kBucketInit(bucket,tempPoly,0);
1218	tempPoly = kBucketGetLm(bucket);
1219	//Print("\n\n\nTO BE REDUCED: ");
1220	//pWrite(l->getPoly());
1221	//pWrite(l->getTerm());
1222	//pWrite(tempPoly);
1223	while(NULL != tempPoly) {
1224	// iteration of all elements in gPrev of the current index
1225	tempRed = gPrev->getFirst();
1226	while(NULL != tempRed) {
1227	//Print("TEMPREDPOLY: ");
1228	//pWrite(tempRed->getPoly());
1229	if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1230	u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1231	//Print("U: ");
1232	//pWrite(u);
1233	if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done!
1234	if(tempRed->getIndex() != idx) {
1235	// passing criterion1 ?
1236	if(!criterion1(gPrev,u,tempRed,lTag)) {
1237	poly tempRedPoly = tempRed->getPoly();
1238	//Print("REDUCER: ");
1239	//pWrite(tempRedPoly);
1240	pIter(tempRedPoly);
1241	int lTempRedPoly = pLength(tempRedPoly);
1242	kBucketExtractLm(bucket);
1243	kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1244	canonicalize++;
1245	//Print("Reduction\n");
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	}
1259	}
1260
1261	}
1262	else {
1263	if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1264	//Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1265	//pWrite(u);
1266	//pWrite(tempRed->getTerm());
1267	//pWrite(pHead(tempRed->getPoly()));
1268	addToG = 0;
1269	}
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) {
1276	if(NULL == redPoly) {
1277	bad->insert(tempRed->getLPolyOld());
1278	addToG = 1;
1279	//poly tempRedPoly = tempRed->getPoly();
1280	//break;
1281	}
1282	}
1283	else {
1284	poly tempRedPoly = tempRed->getPoly();
1285	//Print("REDUCER: ");
1286	//pWrite(tempRedPoly);
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++;
1294	//Print("REDUCTION\n");
1295	addToG = 1;
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	}
1312	}
1313	}
1314	else {
1315	//Print("CRIT 1 ");
1316
1317	if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
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	}
1327	}
1328	}
1329	}
1330	else {
1331	//Print("CRIT 2 ");
1332	if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
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	}
1342	}
1343	}
1344	}
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	}
1369
1370	}
1371	}
1372	tempRed = tempRed->getNext();
1373	}
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());
1381	//pWrite(tempPoly);
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	}
1412	}
1413
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());
1420	//pWrite(pHead(tempRed->getPoly()));
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	}
1465	}
1466	}
1467	else {
1468	//Print("CRIT 1 ");
1469
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	}
1498
1499	}
1500	tempRed = tempRed->getNext();
1501	}
1502	}
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	}
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);
1515
1516	}
1517	}
1518	if(NULL == redPoly) {
1519	reductionsToZero++;
1520	//pDelete(&redPoly);
1521	}
1522	else {
1523	Print("\nELEMENT ADDED TO GPREV: ");
1524	pNorm(redPoly);
1525	if(highestDegree < pDeg(redPoly)) {
1526	highestDegree = pDeg(redPoly);
1527	}
1528	pWrite(pHead(redPoly));
1529	//pWrite(l->getTerm());
1530	//Print("%d\n",canonicalize);
1531	l->setPoly(redPoly);
1532	// give "l" the label if it is "useful" (addToG = 0) or "useless"
1533	// (addToG = 1)
1534	l->setDel(!addToG);
1535	Print("redundant? %d\n\n",l->getDel());
1536	if(addToG == 0 && termination == 1) {
1537	reducers->insert(l->getLPolyOld());
1538	}
1539	else {
1540	gPrev->insert(l->getLPolyOld());
1541	}
1542	//Print("%d\n\n",termination);
1543	if(termination == 1) {
1544	if(addToG) {
1545	//Print("----------------HERE?-----------------\n");
1546	criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1547	}
1548	else {
1549	notInG++;
1550	//Print("\nNONONO");
1551	//pWrite(pHead(l->getPoly()));
1552	//pWrite(l->getTerm());
1553	}
1554	}
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)
1558	else {
1559	if(!l->getDel()) {
1560	criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1561	}
1562	else {
1563	criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1564	}
1565	}
1566	}
1567
1568	// if there are "bad" reducers than try to compute new S-polynomials and rules
1569
1570	if(NULL != bad->getFirst()) {
1571	//Print("BAD STUFF LIST:\n");
1572	//bad->print();
1573	LNode* tempBad = bad->getFirst();
1574	//pWrite(l->getPoly());
1575	while(NULL != tempBad) {
1576	if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
1577	//Print("BAD STUFF\n");
1578	//pWrite(l->getPoly());
1579	//pWrite(tempBad->getPoly());
1580	u = pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly()));
1581	//Print("MULTIPLIER: ");
1582	//pWrite(u);
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)) {
1589	//Print("HIERHIERHIERHIERHIERHIER\n");
1590	rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
1591	numberOfRules++;
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);
1600	LNode* tempBadNew = new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
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);
1608
1609	sPolyList->insertByLabel(tempBadNew);
1610	//Print("BAD SPOLYLIST: \n");
1611	//sPolyList->print();
1612	}
1613	}
1614	}
1615	}
1616	}
1617	//Print("HIER\n");
1618	tempBad = tempBad->getNext();
1619	//Print("%p\n",tempBad);
1620	}
1621	// Print("-------------------BAD STUFF LIST-----------------------------\n");
1622	}
1623	//Print("HIER AUCH\n");
1624	//Print("SPOLYLIST IN BAD: \n");
1625	//sPolyList->print();
1626	//Print("END FIND REDUCERS\n");
1627	}
1628
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
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	*/
1695	void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) {
1696	//Print("##########################################In topREDUCTION!########################################\n");
1697	// try l as long as there are reductors found by findReductor()
1698	LNode* gPrevRedCheck = lTag->getFirstCurrentIdx();
1699	LNode* tempRed;
1700	poly pOne = pOne();
1701	do {
1702	//int timer5 = initTimer();
1703	//startTimer();
1704	//Print("TOP REDUCTION: ");
1705	//pWrite(l->getPoly());
1706	tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1707	//timer5 = getTimer();
1708	//reductionTime = reductionTime + timer5;
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
1713
1714	if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1715	// needed sinc pSub destroys the arguments!
1716	//poly temp_poly_l = pInit();
1717	//temp_poly_l = pCopy(l->getPoly());
1718	//Print("VORHER: ");
1719	//pWrite(tempRed->getPoly());
1720	//poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1721	poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1722	rules->insert(tempRed->getIndex(),tempRed->getTerm());
1723	//Print("NACHHER: ");
1724	//pWrite(tempRed->getPoly());
1725	//Print("TEMP: ");
1726	//pWrite(temp);
1727	if(NULL != temp) {
1728	pNorm(temp);
1729	//tempRed->setPoly(temp);
1730	//tempRed->setDel(1);
1731	//rules->insert(tempRed->getIndex(),tempRed->getTerm());
1732	LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld());
1733	//tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1734	tempRedNew->setDel(1);
1735	sPolyList->insertByLabel(tempRedNew);
1736	}
1737	else {
1738	pDelete(&temp);
1739	reductionsToZero++;
1740	//delete tempRed;
1741	}
1742	}
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
1747	else {
1748
1749	//poly temp_poly_l = pInit();
1750	//temp_poly_l = pCopy(l->getPoly());
1751	//poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1752	//Print("REDUCER: ");
1753	//pWrite(tempRed->getPoly());
1754	//pWrite(tempRed->getTerm());
1755	poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1756	//Print("REDUCED ELEMENT: ");
1757	if(NULL != temp) {
1758	pNorm(temp);
1759	//pWrite(temp);
1760	poly tempNF = kNF(gbPrev,currQuotient,temp);
1761	pNorm(tempNF);
1762	if(NULL == tempNF) {
1763	reductionsToZero++;
1764	pDelete(&tempNF);
1765	l->setPoly(NULL);
1766	break;
1767	}
1768	l->setPoly(tempNF);
1769
1770	gPrevRedCheck = lTag->getFirstCurrentIdx();
1771	}
1772	else {
1773	reductionsToZero++;
1774	pDelete(&temp);
1775	l->setPoly(NULL);
1776	break;
1777	}
1778	}
1779	}
1780	else {
1781	if(NULL != l->getPoly()) {
1782	pNorm(l->getPoly());
1783	//Print("ELEMENT ADDED TO GPREV: ");
1784	//pWrite(l->getPoly());
1785	gPrev->insert(l->getLPolyOld());
1786	//Print("TEMP RED == 0 ");
1787	//pWrite(l->getPoly());
1788	//pWrite(l->getTerm());
1789	//rules->print();
1790	criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1791	//Print("LIST OF CRITICAL PAIRS: \n");
1792	//critPairs->print();
1793	}
1794	break;
1795	}
1796	} while(1);
1797	}
1798
1799
1800	/*
1801	=====================================================================
1802	subalgorithm to find a possible reductor for the labeled polynomial l
1803	=====================================================================
1804	*/
1805	LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag, PList* rejectedGBList) {
1806	// allociation of memory for the possible reductor
1807	//Print("LPOLY: ");
1808	//pWrite(l->getPoly());
1809	poly u = pOne();
1810	poly red;
1811	number nOne = nInit(1);
1812	LNode* temp;
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
1816	// that we can start searching for new reducers from this point and
1817	// not from the first element of gPrev with the current index
1818	temp = gPrevRedCheck;
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?
1824	if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) {
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
1832	if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) {
1833	// passing criterion2 ?
1834	if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1835	// passing criterion1 ?
1836	if(!criterion1(gPrev,u,temp,lTag)) {
1837	gPrevRedCheck = temp->getNext();
1838	LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
1839	return redNode;
1840	}
1841	}
1842	}
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);
1853	sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld());
1854	//Print("NEW ONE: ");
1855	//pWrite(tempSpoly);
1856	//Print("HIER\n");
1857	//sPolyList->print();
1858	//sleep(5);
1859	}
1860	}
1861	}
1862	}
1863	}
1864	//Print("AUCH HIER\n");
1865	temp = temp->getNext();
1866	}
1867
1868	// delete temp;
1869	return NULL;
1870	}
1871
1872
1873
1874	/*
1875	==========================================================================
1876	MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
1877	OPTIONS: INTEGER "opt" is to be set "0" for F5, "1" for F5R, "2" for F5C
1878	==========================================================================
1879	*/
1880	ideal F5main(ideal id, ring r, int opt, int plus, int termination) {
1881	switch(opt) {
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	}
1895
1896	int timer = initTimer();
1897	startTimer();
1898	int i,j,k,l;
1899	int gbLength;
1900	// 1 polynomial for defining initial labels & further tests
1901	poly ONE = pOne();
1902	poly pOne = pOne();
1903	number nOne = nInit(1);
1904	// tag the first element of index i-1 for criterion 1
1905	//Print("LTAG BEGINNING: %p\n",lTag);
1906
1907	// DEBUGGING STUFF START
1908	//Print("NUMBER: %d\n",r->N);
1909	/*
1910	int* ev = new int[r->N +1];
1911	for(i=0;i<IDELEMS(id);i++) {
1912	pGetExpV(id->m[i],ev);
1913	//ev2 = pGetExp(id->m[i],1);
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]);
1918	Print("SUM: %ld\n\n\n",sumVector(ev,r->N));
1919	}
1920	delete ev;
1921	*/
1922	/DEBUGGING STUFF END /
1923
1924	// first element in rTag is first element of rules which is NULL RNode,
1925	// this must be done due to possible later improvements
1926	RList* rules = new RList();
1927	//Print("RULES FIRST: %p\n",rules->getFirst());
1928	//Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule());
1929	//RTagList* rTag = new RTagList(rules->getFirst());
1930	RTagList* rTag = NULL;
1931	i = 1;
1932	/*for(j=0; j<IDELEMS(id); j++) {
1933	if(NULL != id->m[j]) {
1934	if(pComparePolys(id->m[j],ONE)) {
1935	Print("One Polynomial in Input => Computations stopped\n");
1936	ideal idNew = idInit(1,1);
1937	idNew->m[0] = ONE;
1938	return(idNew);
1939	}
1940	}
1941	}*/
1942	ideal idNew = kInterRed(id);
1943	id = idNew;
1944	//qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
1945	//idShow(id);
1946	LList* gPrev = new LList(ONE, i, id->m[0]);
1947	LList* reducers = new LList();
1948	//idShow(id);
1949	//Print("%p\n",id->m[0]);
1950	//pWrite(id->m[0]);
1951	//Print("%p\n",gPrev->getFirst()->getPoly());
1952	//pWrite(gPrev->getFirst()->getPoly());
1953
1954	LTagList* lTag = new LTagList(gPrev->getFirst());
1955	//lTag->insert(gPrev->getFirst());
1956	lTag->setFirstCurrentIdx(gPrev->getFirst());
1957	// computing the groebner basis of the elements of index < actual index
1958	gbLength = gPrev->getLength();
1959	//Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
1960	ideal gbPrev = idInit(gbLength,1);
1961	// initializing the groebner basis of elements of index < actual index
1962	gbPrev->m[0] = gPrev->getFirst()->getPoly();
1963	//idShow(gbPrev);
1964	//idShow(currQuotient);
1965	for(i=2; i<=IDELEMS(id); i++) {
1966	LNode* gPrevTag = gPrev->getLast();
1967	//Print("Last POlynomial in GPREV: ");
1968	//Print("%p\n",gPrevTag);
1969	//pWrite(gPrevTag->getPoly());
1970	Print("Iteration: %d\n\n",i);
1971	gPrev = F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
1972	//Print("%d\n",gPrev->count(gPrevTag->getNext()));
1973	//Print("%d\n",gPrev->getLength());
1974	//Print("____________________________________ITERATION STEP DONE________________________________________\n");
1975
1976	// DEBUGGING STUFF
1977	LNode* temp = gPrev->getFirst();
1978
1979
1980	/////////////////////////////////////////////////////////////////////////////////
1981	// //
1982	// one needs to choose one of the following 3 implementations of the algorithm //
1983	// F5,F5R or F5C //
1984	// //
1985	/////////////////////////////////////////////////////////////////////////////////
1986
1987
1988	//
1989	// standard "F5"
1990	//
1991	if(0 == opt) {
1992	if(gPrev->getLength() > gbLength) {
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	}
2015	//if(i == IDELEMS(id)) {
2016	// ideal tempId = kInterRed(gbPrev);
2017	// gbPrev = tempId;
2018	//}
2019	}
2020	gbLength = gPrev->getLength();
2021	}
2022
2023
2024	//
2025	// "F5R"
2026	//
2027	if(1 == opt) {
2028	if(gPrev->getLength() > gbLength) {
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);
2050	}
2051	// interreduction stuff
2052	// comment this out if you want F5 instead of F5R
2053	if(i<IDELEMS(id)) {
2054	ideal tempId = kInterRed(gbPrev);
2055	gbPrev = tempId;
2056	}
2057	}
2058	gbLength = gPrev->getLength();
2059	}
2060
2061
2062	//
2063	// "F5C"
2064	//
2065	if(2 == opt) {
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	}
2085	if(i<IDELEMS(id)) {
2086	ideal tempId = kInterRed(gbPrev);
2087	gbPrev = tempId;
2088	delete gPrev;
2089	delete rules;
2090	gPrev = new LList(pOne,1,gbPrev->m[0]);
2091	gPrev->insert(pOne,1,gbPrev->m[1]);
2092	rules = new RList();
2093	//rTag = new RTagList(rules->getFirst());
2094	for(k=2; k<IDELEMS(gbPrev); k++) {
2095	gPrev->insert(pOne,k+1,gbPrev->m[k]);
2096	/*
2097	for(l=0; l<k; l++) {
2098	}
2099	rTag->insert(rules->getFirst());
2100	*/
2101	}
2102	}
2103	gbLength = gPrev->getLength();
2104	}
2105	}
2106
2107
2108	}
2109	timer = getTimer();
2110	//Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime);
2111	Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero);
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);
2116	Print("Highest Degree during computations: %d\n",highestDegree);
2117	Print("Degree d_0 in F5+: %d\n",highestDegreeGBCriticalPair);
2118	Print("Time for computations: %d/1000 seconds\n",timer);
2119	Print("Number of elements in gb: %d\n",IDELEMS(gbPrev));
2120	//LNode* temp = gPrev->getFirst();
2121	//while(NULL != temp) {
2122	// pWrite(temp->getPoly());
2123	// temp = temp->getNext();
2124	// }
2125	//gPrev->print();
2126	//delete lTag;
2127	delete rTag;
2128	delete gPrev;
2129	notInG = 0;
2130	numberOfRules = 0;
2131	reductionsToZero = 0;
2132	highestDegree = 0;
2133	highestDegreeGBCriticalPair = 0;
2134	reductionTime = 0;
2135	spolsTime = 0;
2136	numberUselessPairs = 0;
2137	numberUsefulPairs = 0;
2138	numberRejectedF5CriticalPairs = 0;
2139	numberOfReductions = 0;
2140	numberOfSpolys = 0;
2141	return(gbPrev);
2142
2143
2144	}
2145
2146	#endif

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

Download in other formats: