Context Navigation

source: git/kernel/f5gb.cc @ c9193a

spielwiese

Last change on this file since c9193a was c9193a, checked in by Christian Eder, 15 years ago
fixed bug: zero reduction after top reduction git-svn-id: file:///usr/local/Singular/svn/trunk@11501 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 38.0 KB

Line
1	/****************************************
2	* Computer Algebra System SINGULAR *
3	****************************************/
4	/* $Id: f5gb.cc,v 1.36 2009-02-28 21:14:06 ederc Exp $ */
5	/*
6	* ABSTRACT: f5gb interface
7	*/
8	#include "mod2.h"
9	#ifdef HAVE_F5
10	#include "kutil.h"
11	#include "structs.h"
12	#include "omalloc.h"
13	#include "polys.h"
14	#include "p_polys.h"
15	#include "ideals.h"
16	#include "febase.h"
17	#include "kstd1.h"
18	#include "khstd.h"
19	#include "kbuckets.h"
20	#include "weight.h"
21	#include "intvec.h"
22	#include "pInline1.h"
23	#include "f5gb.h"
24	#include "f5data.h"
25	#include "f5lists.h"
26
27	int reductionsToZero = 0;
28
29	/*
30	====================================================================
31	sorting ideals by decreasing total degree "left" and "right" are the
32	pointer of the first and last polynomial in the considered ideal
33	====================================================================
34	*/
35	void qsortDegree(poly* left, poly* right) {
36	poly* ptr1 = left;
37	poly* ptr2 = right;
38	poly p1,p2;
39	p2 = *(left + (right - left >> 1));
40	do {
41	while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
42	ptr1++;
43	}
44	while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
45	ptr2--;
46	}
47	if(ptr1 > ptr2) {
48	break;
49	}
50	p1 = *ptr1;
51	ptr1 = ptr2;
52	*ptr2 = p1;
53	} while(++ptr1 <= --ptr2);
54
55	if(left < ptr2) {
56	qsortDegree(left,ptr2);
57	}
58	if(ptr1 < right) {
59	qsortDegree(ptr1,right);
60	}
61	}
62
63
64
65	/*
66	==================================================
67	computes incrementally gbs of subsets of the input
68	gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
69	==================================================
70	*/
71	LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag) {
72	int j;
73	//Print("%p\n",gPrev->getFirst());
74	//pWrite(gPrev->getFirst()->getPoly());
75	poly tempNF = kNF(gbPrev,currQuotient,f_i);
76	f_i = tempNF;
77	gPrev->insert(ONE,i,f_i);
78	// tag the first element in gPrev of the current index for findReductor()
79	lTag->setFirstCurrentIdx(gPrev->getLast());
80	//Print("1st gPrev: ");
81	//pWrite(gPrev->getFirst()->getPoly());
82	//Print("2nd gPrev: ");
83	//pWrite(gPrev->getFirst()->getNext()->getPoly());
84	//pWrite(gPrev->getFirst()->getNext()->getPoly());
85	CList* critPairs = new CList();
86	CNode* critPairsMinDeg = new CNode();
87	// computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
88	// in the list critPairs
89	criticalPair(gPrev, critPairs, lTag, rTag, rules);
90	static LList* sPolyList = new LList();
91	// labeled polynomials which have passed reduction() and have to be added to list gPrev
92	static LList* completed = new LList();
93	// the reduced labeled polynomials which are returned from subalgorithm reduction()
94	static LList* reducedLPolys = new LList();
95	// while there are critical pairs to be further checked and deleted/computed
96	while(NULL != critPairs->getFirst()->getData()) {
97	// critPairs->getMinDeg() deletes the first elements of minimal degree from
98	// critPairs, thus the while loop is not infinite.
99	critPairsMinDeg = critPairs->getMinDeg();
100	// adds all to be reduced S-polynomials in the list sPolyList and adds
101	// the corresponding rules to the list rules
102	// NOTE: inside there is a second check of criterion 2 if new rules are
103	// added
104	computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
105
106	// DEBUG STUFF FOR SPOLYLIST
107	LNode* temp = sPolyList->getFirst();
108	//while(NULL != temp && NULL != temp->getLPoly()) {
109	//Print("Spolylist element: ");
110	//pWrite(temp->getPoly());
111	//temp = temp->getNext();
112	//}
113	// reduction process of new S-polynomials and also adds new critical pairs to critPairs
114	reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
115
116	// DEBUG STUFF FOR GPREV
117	//temp = gPrev->getFirst();
118	//int number = 1;
119	//Print("\n\n");
120	//while(NULL != temp) {
121	// Print("%d. ",number);
122	// pWrite(temp->getPoly());
123	// temp = temp->getNext();
124	// number++;
125	// Print("\n");
126	//}
127	//sleep(5);
128
129	}
130	//Print("REDUCTION DONE\n");
131	//Print("%p\n",rules->getFirst());
132	//Print("%p\n",rTag->getFirst());
133	if(rules->getFirst() != rTag->getFirst()) {
134	//Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
135	rTag->insert(rules->getFirst());
136	}
137	else {
138	//Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
139	}
140	lTag->insert(lTag->getFirstCurrentIdx());
141	//Print("LTAG LIST: \n");
142	LNode* tempTag = lTag->getFirst();
143	//Print("INDEX: %d\n",tempTag->getIndex());
144	//pWrite(tempTag->getPoly());
145	//Print("COMPLETED FIRST IN F5INC: \n");
146	//Print("1st gPrev: ");
147	//pWrite(gPrev->getFirst()->getPoly());
148	//Print("2nd gPrev: ");
149	//pWrite(gPrev->getFirst()->getNext()->getPoly());
150	//Print("3rd gPrev: ");
151	//pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
152
153
154	return gPrev;
155	}
156
157
158
159	/*
160	================================================================
161	computes a list of critical pairs for the next reduction process
162	first element in gPrev is always the newest element which must
163	build critical pairs with all other elements in gPrev
164	================================================================
165	*/
166	void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
167	// initialization for usage in pLcm()
168	number nOne = nInit(1);
169	LNode* newElement = gPrev->getLast();
170	LNode* temp = gPrev->getFirst();
171	poly u1 = pOne();
172	poly u2 = pOne();
173	poly lcm = pOne();
174	poly t = pHead(newElement->getPoly());
175	Rule* testedRule = rules->getFirst()->getRule();
176	// computation of critical pairs
177	while( gPrev->getLast() != temp) {
178	//pWrite( *(gPrev->getFirst()->getPoly()) );
179	// pWrite( *(l->getPoly()) );
180	pLcm(newElement->getPoly(), temp->getPoly(), lcm);
181	pSetCoeff(lcm,nOne);
182	// computing factors u2 for new labels
183	u1 = pDivide(lcm,t);
184	pSetCoeff(u1,nOne);
185	u2 = pDivide(lcm, pHead(temp->getPoly()));
186	pSetCoeff(u2,nOne);
187	//if(gPrev->getLast()->getIndex()==5) {
188	//Print("IN CRITPAIRS\n");
189	// pWrite(u1);
190	// Print("1st ELEMENT: ");
191	// pWrite(newElement->getPoly());
192	// Print("2nd ELEMENT: ");
193	// pWrite(temp->getPoly());
194	//}
195	// testing both new labels by the F5 Criterion
196	if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
197	//&& !criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
198	// if they pass the test, add them to CList critPairs, having the LPoly with greater
199	// label as first element in the CPair
200	if(newElement->getIndex() == temp->getIndex() &&
201	-1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
202	//Print("zweites groesser\n");
203	CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
204	temp->getLPoly(), u1, newElement->getLPoly(), testedRule);
205	critPairs->insert(cp);
206	}
207	else {
208	//Print("erstes groesser\n");
209	CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
210	newElement->getLPoly(), u2, temp->getLPoly(), testedRule);
211	critPairs->insert(cp);
212	}
213	}
214	else {
215	}
216
217	//Print("\n\n");
218	temp = temp->getNext();
219	}
220	// for debugging
221	//if(NULL != critPairs) {
222	//critPairs->print();
223	//sleep(5);
224	//}
225	}
226
227
228
229
230	/*
231	================================================================
232	computes a list of critical pairs for the next reduction process
233	first element in gPrev is always the newest element which must
234	build critical pairs with all other elements in gPrev
235	this is a special version for reduction() in which the first
236	generator of the critical pair is not tested by criterion2()
237	as there are no rules added until then to test for
238	================================================================
239	*/
240	void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
241	// initialization for usage in pLcm()
242	number nOne = nInit(1);
243	LNode* newElement = gPrev->getLast();
244	LNode* temp = gPrev->getFirst();
245	poly u1 = pOne();
246	poly u2 = pOne();
247	poly lcm = pOne();
248	poly t = pHead(newElement->getPoly());
249	Rule* testedRule = rules->getFirst()->getRule();
250	// computation of critical pairs
251	while( gPrev->getLast() != temp) {
252	//pWrite( *(gPrev->getFirst()->getPoly()) );
253	// pWrite( *(l->getPoly()) );
254	pLcm(newElement->getPoly(), temp->getPoly(), lcm);
255	pSetCoeff(lcm,nOne);
256	// computing factors u2 for new labels
257	u1 = pDivide(lcm,t);
258	pSetCoeff(u1,nOne);
259	u2 = pDivide(lcm, pHead(temp->getPoly()));
260	pSetCoeff(u2,nOne);
261	//if(gPrev->getLast()->getIndex()==5) {
262	//Print("IN CRITPAIRS\n");
263	// pWrite(u1);
264	// Print("1st ELEMENT: ");
265	// pWrite(newElement->getPoly());
266	// Print("2nd ELEMENT: ");
267	// pWrite(temp->getPoly());
268	//}
269	// testing both new labels by the F5 Criterion
270	if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag) &&
271	!criterion2(u2, temp, rules, rTag)) {
272	// if they pass the test, add them to CList critPairs, having the LPoly with greater
273	// label as first element in the CPair
274	if(newElement->getIndex() == temp->getIndex() &&
275	-1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
276	//Print("zweites groesser\n");
277	CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
278	temp->getLPoly(), u1, newElement->getLPoly(), testedRule);
279	critPairs->insert(cp);
280	}
281	else {
282	//Print("erstes groesser\n");
283	CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
284	newElement->getLPoly(), u2, temp->getLPoly(), testedRule);
285	critPairs->insert(cp);
286	}
287	}
288	else {
289	}
290
291	//Print("\n\n");
292	temp = temp->getNext();
293	}
294	// for debugging
295	//if(NULL != critPairs) {
296	//critPairs->print();
297	//sleep(5);
298	//}
299	}
300
301
302
303
304	/*
305	========================================
306	Criterion 1, i.e. Faugere's F5 Criterion
307	========================================
308	*/
309	bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
310	// starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
311	int idx = l->getIndex();
312	if(idx == 1) {
313	return false;
314	}
315	else {
316	LNode* testNode = gPrev->getFirst();
317	// save the monom t1*label_term(l) as it is tested various times in the following
318	poly u1 = ppMult_qq(t,l->getTerm());
319	//Print("------------------------------IN CRITERION 1-----------------------------------------\n");
320	//Print("TESTED ELEMENT: ");
321	//pWrite(l->getPoly());
322	//pWrite(l->getTerm());
323	//pWrite(ppMult_qq(t,l->getTerm()));
324	//Print("%d\n\n",l->getIndex());
325	while(testNode->getIndex() < idx && NULL != testNode->getLPoly()) {
326	//pWrite(testNode->getPoly());
327	//Print("%d\n",testNode->getIndex());
328	if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
329	//Print("Criterion 1 NOT passed!\n");
330	return true;
331	}
332	//pWrite(testNode->getNext()->getPoly());
333	testNode = testNode->getNext();
334	}
335	return false;
336	}
337	}
338
339
340
341	/*
342	=====================================
343	Criterion 2, i.e. Rewritten Criterion
344	=====================================
345	*/
346	bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) {
347	//Print("------------------------------IN CRITERION 2-----------------------------------------\n");
348	//Print("RULES: \n");
349	RNode* tempR = rules->getFirst();
350	while(NULL != tempR->getRule()) {
351	//Print("ADDRESS OF RULE: %p\n",tempR->getRule());
352	//pWrite(tempR->getRuleTerm());
353	//Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
354	//Print("%d\n\n",tempR->getRuleIndex());
355	tempR = tempR->getNext();
356	}
357	//Print("TESTED ELEMENT: ");
358	//pWrite(l->getPoly());
359	//pWrite(l->getTerm());
360	//pWrite(ppMult_qq(t,l->getTerm()));
361	//Print("%d\n\n",l->getIndex());
362	// start at the previously added element to gPrev, as all other elements will have the same index for sure
363	RNode* testNode = new RNode();
364	if(NULL == rTag->getFirst()->getRule()) {
365	testNode = rules->getFirst();
366	}
367	else {
368	if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
369	testNode = rules->getFirst();
370	}
371	else {
372	//Print("DEBUG\n");
373	//Print("L INDEX: %d\n",l->getIndex());
374	testNode = rTag->get(l->getIndex());
375	//Print("TESTNODE ADDRESS: %p\n",testNode);
376	}
377	}
378	// save the monom t1*label_term(l) as it is tested various times in the following
379	poly u1 = ppMult_qq(t,l->getTerm());
380	// first element added to rTag was NULL, check for this
381	//Print("%p\n",testNode->getRule());
382	// NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
383	if(NULL != testNode && NULL != testNode->getRule()) {
384	//pWrite(testNode->getRuleTerm());
385	}
386	if(NULL != testNode) {
387	if(testNode->getRule() == l->getRule()) {
388	//Print("%p\n%p\n",testNode->getRule(),l->getRule());
389	//Print("EQUAL\n");
390	}
391	else {
392	//Print("NOT EQUAL\n");
393	}
394	}
395	while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule()
396	&& l->getIndex() == testNode->getRuleIndex()) {
397	//pWrite(testNode->getRuleTerm());
398	//pWrite(testNode->getRuleTerm());
399	//pWrite(t);
400	//pWrite(l->getTerm());
401	//pWrite(u1);
402	//Print("%d\n",testNode->getRuleIndex());
403	if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
404	//Print("Criterion 2 NOT passed!\n");
405	pDelete(&u1);
406	return true;
407	}
408	testNode = testNode->getNext();
409	}
410	pDelete(&u1);
411	return false;
412	}
413
414
415
416	/*
417	=================================================================================================================
418	Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
419	=================================================================================================================
420	*/
421	bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) {
422	//Print("------------------------------IN CRITERION 2-----------------------------------------\n");
423	//Print("LAST RULE TESTED: %p",testedRule);
424	//Print("RULES: \n");
425	RNode* tempR = rules->getFirst();
426	//while(NULL != tempR->getRule()) {
427	//pWrite(tempR->getRuleTerm());
428	//Print("%d\n\n",tempR->getRuleIndex());
429	//tempR = tempR->getNext();
430	//}
431	//Print("TESTED ELEMENT: ");
432	//pWrite(l->getPoly());
433	//pWrite(l->getTerm());
434	//pWrite(ppMult_qq(t,l->getTerm()));
435	//Print("%d\n\n",l->getIndex());
436	// start at the previously added element to gPrev, as all other elements will have the same index for sure
437	RNode* testNode = rules->getFirst();
438	// save the monom t1*label_term(l) as it is tested various times in the following
439	poly u1 = ppMult_qq(t,l->getTerm());
440	// first element added to rTag was NULL, check for this
441	while(NULL != testNode->getRule() && testNode->getRule() != testedRule) {
442	//pWrite(testNode->getRuleTerm());
443	if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
444	//Print("Criterion 2 NOT passed!\n");
445	pDelete(&u1);
446	return true;
447	}
448	testNode = testNode->getNext();
449	}
450	pDelete(&u1);
451	return false;
452	}
453
454
455
456	/*
457	==================================
458	Computation of S-Polynomials in F5
459	==================================
460	*/
461	void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) {
462	CNode* temp = first;
463	poly sp = pInit();
464	//Print("###############################IN SPOLS##############################\n");
465	while(NULL != temp->getData()) {
466	// only if a new rule was added since the last test in subalgorithm criticalPair()
467	//if(rules->getFirst() != rTag->getFirst()) {
468	if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRule())) {
469	// the second component is tested only when it has the actual index, otherwise there is
470	// no new rule to test since the last test in subalgorithm criticalPair()
471	if(temp->getLp2Index() == temp->getLp1Index()) {
472	if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) {
473	// computation of S-polynomial
474	sp = pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
475	ppMult_qq(temp->getT2(),temp->getLp2Poly()));
476	//Print("BEGIN SPOLY1\n====================\n");
477	pNorm(sp);
478	//pWrite(sp);
479	//Print("END SPOLY1\n====================\n");
480	if(NULL == sp) {
481	// as rules consist only of pointers we need to save the labeled
482	// S-polynomial also of a zero S-polynomial
483	//zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
484	// origin of rule can be set NULL as the labeled polynomial
485	// will never be used again as it is zero => no problems with
486	// further criterion2() tests and termination conditions
487	//Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
488	reductionsToZero++;
489	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
490	//Print("RULE ADDED: \n");
491	//pWrite(rules->getFirst()->getRuleTerm());
492	// as sp = NULL, delete it
493	pDelete(&sp);
494	//Print("HIER\n");
495	}
496	else {
497	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
498	//Print("RULE ADDED: \n");
499	//pWrite(rules->getFirst()->getRuleTerm());
500	sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
501	}
502	// data is saved in sPolyList or zero => delete sp
503	}
504	}
505	else { // temp->getLp2Index() < temp->getLp1Index()
506	// computation of S-polynomial
507	sp = pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
508	ppMult_qq(temp->getT2(),temp->getLp2Poly()));
509	//Print("BEGIN SPOLY2\n====================\n");
510	pNorm(sp);
511	//pWrite(sp);
512	//Print("END SPOLY2\n====================\n");
513	if(NULL == sp) {
514	// zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
515	// origin of rule can be set NULL as the labeled polynomial
516	// will never be used again as it is zero => no problems with
517	// further criterion2() tests and termination conditions
518	//Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
519	reductionsToZero++;
520	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
521	//Print("RULE ADDED: \n");
522	//pWrite(rules->getFirst()->getRuleTerm());
523	// as sp = NULL, delete it
524	pDelete(&sp);
525	}
526	else {
527	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
528	//Print("RULE ADDED: \n");
529	//pWrite(rules->getFirst()->getRuleTerm());
530	//Print("%d\n",rules->getFirst()->getRuleIndex());
531	//Print("%p\n",sPolyList->getFirst());
532	sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
533	}
534	// data is saved in sPolyList or zero => delete sp
535	}
536	}
537	//}
538	temp = temp->getNext();
539	}
540	// these critical pairs can be deleted now as they are either useless for further computations or
541	// already saved as an S-polynomial to be reduced in the following
542	delete first;
543	}
544
545
546
547	/*
548	========================================================================
549	reduction including subalgorithm topReduction() using Faugere's criteria
550	========================================================================
551	*/
552	void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
553	ideal gbPrev) {
554	//Print("##########################################In REDUCTION!########################################\n");
555	// check if sPolyList has any elements
556	// NOTE: due to initialization sPolyList always has a default NULL element
557	while(sPolyList->getLength() > 0) {
558	//Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
559	if(sPolyList->getLength() > 1) {
560	//Print("%p\n",sPolyList->getFirst());
561	//Print("%p\n",sPolyList->getFirst()->getLPoly());
562	//Print("%p\n",sPolyList->getFirst()->getNext());
563	//Print("%p\n",sPolyList->getFirst()->getNext()->getLPoly());
564	//Print("%p\n",sPolyList->getFirst());
565	}
566	//if(gPrev->getLast()->getIndex() == 5) {
567	//sPolyList->print();
568	//sleep(5);
569	//}
570
571	// temp is the first element in the sPolyList which should be reduced
572	// due to earlier sorting this is the element of minimal degree AND
573	// minimal label
574	LNode* temp = sPolyList->getFirst();
575	//pWrite(temp->getPoly());
576	// delete the above first element from sPolyList, temp will be either reduced to
577	// zero or added to gPrev, but never come back to sPolyList
578	if(NULL != temp && NULL != temp->getLPoly()) {
579	sPolyList->setFirst(temp->getNext());
580	//Print("HIER\n");
581	}
582	else {
583	break;
584	}
585	//Print("HALLO %p\n",temp->getPoly());
586	//Print("%p\n",temp->getPoly());
587	//pWrite(temp->getPoly());
588	//idShow(gbPrev);
589	poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
590	//Print("LENGTH: %d\n",sPolyList->getLength());
591	//pWrite(tempNF);
592	//pWrite(temp->getPoly());
593	if(NULL != tempNF) {
594	pNorm(tempNF);
595	// write the reduced polynomial in temp
596	temp->setPoly(tempNF);
597	// try further reductions of temp with polynomials in gPrev
598	// with label index = current label index: this is done such that there
599	// is no label corruption during the reduction process
600	topReduction(temp,sPolyList,gPrev,rules,lTag,rTag,gbPrev);
601
602	}
603	if(NULL != temp->getPoly()) {
604	//CList* newCritPairs = new CList;
605	//Print("##################IN CRITPAIRS IN REDUCTION#####################\n");
606	criticalPairRed(gPrev,critPairs,lTag,rTag,rules);
607	//Print("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++H I E R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
608	}
609	else {
610	//delete temp;
611	LNode* tempLoop = gPrev->getFirst();
612	//Print("AUSGABE IN REDUCTION:\n");
613	//while(NULL != tempLoop) {
614	//pWrite(tempLoop->getPoly());
615	//tempLoop = tempLoop->getNext();
616	//}
617	//sleep(10);
618	}
619	}
620	}
621
622
623
624	/*
625	=====================================================================================
626	top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
627	the same index whereas the labels are taken into account
628	=====================================================================================
629	*/
630	void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) {
631	//Print("##########################################In topREDUCTION!########################################\n");
632	// try l as long as there are reductors found by findReductor()
633	do {
634	LNode* tempRed = new LNode();
635	//Print("TESTED POLYNOMIAL IN THE FOLLOWING: ");
636	//pWrite(l->getPoly());
637	//Print("HIER\n");
638	tempRed = findReductor(l,gPrev,rules,lTag,rTag);
639	//Print("--------------------------------HIER DEBUG 2----------------------------------\n");
640	// if a reductor for l is found and saved in tempRed
641	if(NULL != tempRed) {
642	// if label of reductor is greater than the label of l we have to built a new element
643	// and add it to sPolyList
644	//Print("REDUCTOR POLYNOMIAL: ");
645	//pWrite(tempRed->getPoly());
646	//Print("TERM: ");
647	//pWrite(tempRed->getTerm());
648	if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
649	// needed sinc pSub destroys the arguments!
650	//Print("H----------I------------E--------------R\n");
651	poly temp_poly_l = pInit();
652	temp_poly_l = pCopy(l->getPoly());
653	//Print("POLYNOMIAL L: ");
654	//pWrite(l->getPoly());
655	//pWrite(temp_poly_l);
656	poly temp = pSub(tempRed->getPoly(),temp_poly_l);
657	//Print("POLYNOMIAL L: ");
658	//pWrite(l->getPoly());
659	//pWrite(temp_poly_l);
660	//Print("AFTER REDUCTION STEP: ");
661	//pWrite(temp);
662	//sleep(20);
663	//pWrite(temp);
664	if(NULL != temp) {
665	pNorm(temp);
666	tempRed->setPoly(temp);
667	//pWrite(tempRed->getPoly());
668	// for debugging
669	//pWrite(tempRed->getPoly());
670	//Print("RULE ADDED\n");
671	rules->insert(tempRed->getIndex(),tempRed->getTerm());
672	tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
673	//Print("%p\n",sPolyList->getFirst());
674	//Print("%p\n",sPolyList->getFirst()->getLPoly());
675	//Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
676	//sPolyList->print();
677
678	sPolyList->insertByLabel(tempRed);
679	//sPolyList->print();
680	//Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
681	//Print("OH JE\n");
682	}
683	else {
684	pDelete(&temp);
685	reductionsToZero++;
686	//Print("RULE ADDED\n");
687	//Print("wieder hier2\n");
688	rules->insert(tempRed->getIndex(),tempRed->getTerm());
689	delete tempRed;
690	}
691	}
692	// label of reductor is smaller than the label of l, subtract reductor from l and delete the
693	// gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
694	// after subtraction
695	else {
696	poly temp_poly_l = pInit();
697	temp_poly_l = pCopy(l->getPoly());
698	poly temp = pSub(temp_poly_l,tempRed->getPoly());
699	//Print("AFTER REDUCTION STEP: ");
700	//pWrite(temp);
701	if(NULL != temp) {
702	pNorm(temp);
703	poly tempNF = kNF(gbPrev,currQuotient,temp);
704	pNorm(tempNF);
705	//pWrite(tempNF);
706	if(NULL == tempNF) {
707	reductionsToZero++;
708	pDelete(&tempNF);
709	l->setPoly(NULL);
710	break;
711	}
712	l->setPoly(tempNF);
713
714	//pWrite(l->getPoly());
715	l->setGPrevRedCheck(NULL);
716	}
717	else {
718	//Print("ZERO REDUCTION!\n");
719	reductionsToZero++;
720	pDelete(&temp);
721	l->setPoly(NULL);
722	//pWrite(gPrev->getLast()->getPoly());
723	break;
724	}
725	}
726	}
727	else {
728	if(NULL != l->getPoly()) {
729	pNorm(l->getPoly());
730	//Print("----------------------------------ADDED TO GPREV IN TOPREDUCTION:-------------------------------------- ");
731	//pWrite(l->getPoly());
732	//pWrite(l->getTerm());
733	//Print("INDEX: %d\n\n\n", l->getIndex());
734	//sleep(20);
735	gPrev->insert(l->getLPoly());
736	//Print("GPREV: \n");
737	LNode* tempLoop = gPrev->getFirst();
738	//while(NULL != tempLoop) {
739	//Print("HERE\n");
740	//pWrite(tempLoop->getPoly());
741	//tempLoop = tempLoop->getNext();
742	//}
743	}
744	break;
745	}
746	} while(1);
747	}
748
749
750	/*
751	=====================================================================
752	subalgorithm to find a possible reductor for the labeled polynomial l
753	=====================================================================
754	*/
755	LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
756	// allociation of memory for the possible reductor
757	//Print("IN FIND REDUCTOR\n");
758	poly u = pOne();
759	poly red = pOne();
760	number nOne = nInit(1);
761	LNode* temp = new LNode();
762	// head term of actual element such that we do not have to call pHead at each new reductor test
763	poly t = pHead(l->getPoly());
764	// if l was already checked use the information in gPrevRedCheck such
765	// that we can start searching for new reducers from this point and
766	// not from the first element of gPrev with the current index
767	if(NULL != l->getGPrevRedCheck()) {
768	temp = l->getGPrevRedCheck()->getNext();
769	}
770	// no reductors were searched for l before, thus start at the first
771	// element of gPrev with the current index, tagged by lTag
772	else {
773	temp = lTag->getFirstCurrentIdx();
774	}
775	// search for reductors until we are at the end of gPrev resp. at the
776	// end of the elements of the current index
777	while(NULL != temp && temp->getIndex() == l->getIndex()) {
778	// does the head of the element of gPrev divides the head of
779	// the to be reduced element?
780	//Print("-------------FOUND REDUCTORS----------------------\n");
781	//Print("\n");
782	//pWrite(temp->getPoly());
783	//pWrite(temp->getTerm());
784	//pWrite(t);
785	//pWrite(l->getPoly());
786	//Print("HALLO\n");
787	if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
788	//Print("HALLO\n");
789	// get all the information needed for the following tests
790	// of the criteria
791	u = pDivide(t,pHead(temp->getPoly()));
792	pSetCoeff(u,nOne);
793	//Print("HIER FINDRED\n");
794	//pWrite(u);
795	//Print("\n");
796	red = ppMult_qq(u,temp->getPoly());
797	pNorm(red);
798	//u = ppMult_qq(u,temp->getTerm());
799	//pSetCoeff(u,nOne);
800	// check if both have the same label
801	//Print("HALLO\n");
802	if(pLmCmp(u,l->getTerm()) != 0) {
803	//Print("HALLO\n");
804	// passing criterion2 ?
805	if(!criterion2(u,temp,rules,rTag)) {
806	// passing criterion1 ?
807	if(!criterion1(gPrev,u,temp,lTag)) {
808	//Print("HIER DEBUG\n");
809	l->setGPrevRedCheck(temp);
810	LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
811	return redNode;
812	}
813	}
814	}
815	}
816	//Print("%p\n",temp->getNext());
817	//pWrite(temp->getPoly());
818	//Print("HALLO\n");
819	temp = temp->getNext();
820	}
821
822	// delete temp;
823	//Print("1st gPrev: ");
824	//pWrite(gPrev->getFirst()->getPoly());
825	//Print("2nd gPrev: ");
826	//pWrite(gPrev->getFirst()->getNext()->getPoly());
827	return NULL;
828	}
829
830
831
832	/*
833	==========================================================================
834	MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
835	==========================================================================
836	*/
837	ideal F5main(ideal id, ring r) {
838	int i,j;
839	int gbLength;
840	// 1 polynomial for defining initial labels & further tests
841	poly ONE = pOne();
842	// tag the first element of index i-1 for criterion 1
843	LTagList* lTag = new LTagList();
844	//Print("LTAG BEGINNING: %p\n",lTag->getFirst());
845
846	// first element in rTag is first element of rules which is NULL RNode,
847	// this must be done due to possible later improvements
848	RList* rules = new RList();
849	RTagList* rTag = new RTagList(rules->getFirst());
850	i = 1;
851	for(j=0; j<IDELEMS(id); j++) {
852	if(NULL != id->m[j]) {
853	if(pComparePolys(id->m[j],ONE)) {
854	Print("One Polynomial in Input => Computations stopped\n");
855	ideal idNew = idInit(1,1);
856	idNew->m[0] = ONE;
857	return(idNew);
858	}
859	}
860	}
861	ideal idNew = kInterRed(id);
862	idDelete(&id);
863	id = idNew;
864	qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
865	LList* gPrev = new LList(ONE, i, id->m[0]);
866	//idShow(id);
867	//Print("%p\n",id->m[0]);
868	//pWrite(id->m[0]);
869	//Print("%p\n",gPrev->getFirst()->getPoly());
870	//pWrite(gPrev->getFirst()->getPoly());
871
872	lTag->insert(gPrev->getFirst());
873	lTag->setFirstCurrentIdx(gPrev->getFirst());
874	// computing the groebner basis of the elements of index < actual index
875	gbLength = gPrev->getLength();
876	//Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
877	ideal gbPrev = idInit(gbLength,1);
878	// initializing the groebner basis of elements of index < actual index
879	gbPrev->m[0] = gPrev->getFirst()->getPoly();
880	//idShow(gbPrev);
881	//idShow(currQuotient);
882
883	for(i=2; i<=IDELEMS(id); i++) {
884	LNode* gPrevTag = gPrev->getLast();
885	//Print("Last POlynomial in GPREV: ");
886	//Print("%p\n",gPrevTag);
887	//pWrite(gPrevTag->getPoly());
888	gPrev = F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
889	// DEBUGGING STUFF
890	LNode* temp = gPrev->getFirst();
891	// computing new groebner basis gbPrev
892	if(gPrev->getLength() > gbLength) {
893	ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
894	LNode* temp = gPrevTag;
895	//Print("%p\n",gPrevTag);
896	//Print("%p\n",gPrev->getLast());
897	//pWrite(temp->getPoly());
898	//Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
899	//Print("%d\n",gbLength);
900	for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
901	//Print("YES\n");
902	temp = temp->getNext();
903	gbAdd->m[j] = temp->getPoly();
904	//pWrite(temp->getPoly());
905	}
906	gbLength = gPrev->getLength();
907	gbPrev = idAdd(gbPrev,gbAdd);
908	}
909	int anzahl = 1;
910	//while(NULL != temp) {
911	// Print("%d. Element: ",anzahl);
912	// pWrite(temp->getPoly());
913	// Print("\n");
914	// temp = temp->getNext();
915	// anzahl++;
916	//}
917	//sleep(5);
918	//Print("GROEBNER BASIS:\n====================================================\n");
919	//idShow(gbPrev);
920	//Print("===================================================\n");
921	//Print("JA\n");
922	}
923	Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero);
924	//LNode* temp = gPrev->getFirst();
925	//while(NULL != temp) {
926	// pWrite(temp->getPoly());
927	// temp = temp->getNext();
928	// }
929	delete(gPrev);
930	return(gbPrev);
931
932
933	}
934
935	#endif

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

Download in other formats: