Context Navigation

source: git/kernel/f5gb.cc @ 338842d

spielwiese

Last change on this file since 338842d was 338842d, checked in by Christian Eder, 15 years ago
gPrevRedCheck is no longer part of LPoly, less data to take care of git-svn-id: file:///usr/local/Singular/svn/trunk@11503 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 38.1 KB

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

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

Download in other formats: