Context Navigation

source: git/kernel/f5gb.cc @ 210e07

spielwiese

Last change on this file since 210e07 was 210e07, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
ADD: testing headers with "make test.o" FIX: cleaning up headers in kernel: TODO: kutil.h?! FIX: febase.h -> old.febase.h (remove later on) ADD: dummy headers instead of some splited or moved: febase.h, modulop.h (for later fixing) FIX: renamed various obsolette files into "old.*"
Property mode set to `100644`
File size: 87.5 KB

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

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

Download in other formats: