Context Navigation

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

spielwiese

Last change on this file since cd7960 was c46f94, checked in by Hans Schoenemann <hannes@…>, 8 years ago
pDeg -> p_Deg
Property mode set to `100644`
File size: 86.9 KB

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

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

Download in other formats: