Context Navigation

source: git/kernel/f5gb.cc @ 70c15e

spielwiese

Last change on this file since 70c15e was 70c15e, checked in by Christian Eder, 15 years ago
problem in cyclic_n(4) solved git-svn-id: file:///usr/local/Singular/svn/trunk@11441 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 31.0 KB

Line
1	/****************************************
2	* Computer Algebra System SINGULAR *
3	****************************************/
4	/* $Id: f5gb.cc,v 1.32 2009-02-22 18:58:36 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	gPrev->insert(ONE,i,f_i);
76	// tag the first element in gPrev of the current index for findReductor()
77	lTag->setFirstCurrentIdx(gPrev->getLast());
78	//Print("1st gPrev: ");
79	//pWrite(gPrev->getFirst()->getPoly());
80	//Print("2nd gPrev: ");
81	//pWrite(gPrev->getFirst()->getNext()->getPoly());
82	//pWrite(gPrev->getFirst()->getNext()->getPoly());
83	CList* critPairs = new CList();
84	CNode* critPairsMinDeg = new CNode();
85	// computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
86	// in the list critPairs
87	criticalPair(gPrev, critPairs, lTag, rTag, rules);
88	static LList* sPolyList = new LList();
89	// labeled polynomials which have passed reduction() and have to be added to list gPrev
90	static LList* completed = new LList();
91	// the reduced labeled polynomials which are returned from subalgorithm reduction()
92	static LList* reducedLPolys = new LList();
93	// while there are critical pairs to be further checked and deleted/computed
94	while(NULL != critPairs->getFirst()->getData()) {
95	// critPairs->getMinDeg() deletes the first elements of minimal degree from
96	// critPairs, thus the while loop is not infinite.
97	critPairsMinDeg = critPairs->getMinDeg();
98	// adds all to be reduced S-polynomials in the list sPolyList and adds
99	// the corresponding rules to the list rules
100	// NOTE: inside there is a second check of criterion 2 if new rules are
101	// added
102	computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
103
104	// DEBUG STUFF FOR SPOLYLIST
105	LNode* temp = sPolyList->getFirst();
106	while(NULL != temp && NULL != temp->getLPoly()) {
107	Print("Spolylist element: ");
108	pWrite(temp->getPoly());
109	temp = temp->getNext();
110	}
111	// reduction process of new S-polynomials and also adds new critical pairs to critPairs
112	reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
113
114	// DEBUG STUFF FOR GPREV
115	temp = gPrev->getFirst();
116	Print("\n\n");
117	while(NULL != temp) {
118	pWrite(temp->getPoly());
119	temp = temp->getNext();
120	}
121	//sleep(10);
122
123	}
124	Print("REDUCTION DONE\n");
125	Print("%p\n",rules->getFirst());
126	Print("%p\n",rTag->getFirst());
127	if(rules->getFirst() != rTag->getFirst()) {
128	Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
129	rTag->insert(rules->getFirst());
130	}
131	else {
132	Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
133	}
134	lTag->insert(lTag->getFirstCurrentIdx());
135	Print("LTAG LIST: \n");
136	LNode* tempTag = lTag->getFirst();
137	Print("INDEX: %d\n",tempTag->getIndex());
138	pWrite(tempTag->getPoly());
139	Print("COMPLETED FIRST IN F5INC: \n");
140	//Print("1st gPrev: ");
141	//pWrite(gPrev->getFirst()->getPoly());
142	//Print("2nd gPrev: ");
143	//pWrite(gPrev->getFirst()->getNext()->getPoly());
144	//Print("3rd gPrev: ");
145	//pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
146
147
148	return gPrev;
149	}
150
151
152
153	/*
154	================================================================
155	computes a list of critical pairs for the next reduction process
156	first element in gPrev is always the newest element which must
157	build critical pairs with all other elements in gPrev
158	================================================================
159	*/
160	void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
161	// initialization for usage in pLcm()
162	number nOne = nInit(1);
163	LNode* newElement = gPrev->getLast();
164	LNode* temp = gPrev->getFirst();
165	poly u1 = pOne();
166	poly u2 = pOne();
167	poly lcm = pOne();
168	poly t = pHead(newElement->getPoly());
169	Rule* testedRule = rules->getFirst()->getRule();
170	// computation of critical pairs
171	while( gPrev->getLast() != temp) {
172	//pWrite( *(gPrev->getFirst()->getPoly()) );
173	// pWrite( *(l->getPoly()) );
174	pLcm(newElement->getPoly(), temp->getPoly(), lcm);
175	pSetCoeff(lcm,nOne);
176	// computing factors u2 for new labels
177	u1 = pDivide(lcm,t);
178	pSetCoeff(u1,nOne);
179	u2 = pDivide(lcm, pHead(temp->getPoly()));
180	pSetCoeff(u2,nOne);
181	Print("IN CRITPAIRS\n");
182	pWrite(u1);
183	Print("1st ELEMENT: ");
184	pWrite(newElement->getPoly());
185	Print("2nd ELEMENT: ");
186	pWrite(temp->getPoly());
187	// testing both new labels by the F5 Criterion
188	if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag) &&
189	!criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
190	// if they pass the test, add them to CList critPairs, having the LPoly with greater
191	// label as first element in the CPair
192	if(newElement->getIndex() == temp->getIndex() &&
193	-1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
194	Print("zweites groesser\n");
195	CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
196	temp->getLPoly(), u1, newElement->getLPoly(), testedRule);
197	critPairs->insert(cp);
198	}
199	else {
200	Print("erstes groesser\n");
201	CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
202	newElement->getLPoly(), u2, temp->getLPoly(), testedRule);
203	critPairs->insert(cp);
204	}
205	}
206	else {
207	}
208
209	Print("\n\n");
210	temp = temp->getNext();
211	}
212	// for debugging
213	if(NULL != critPairs) {
214	critPairs->print();
215	}
216	}
217
218
219
220
221	/*
222	========================================
223	Criterion 1, i.e. Faugere's F5 Criterion
224	========================================
225	*/
226	bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
227	// starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
228	int idx = l->getIndex();
229	if(idx == 1) {
230	return false;
231	}
232	else {
233	LNode* testNode = gPrev->getFirst();
234	// save the monom t1*label_term(l) as it is tested various times in the following
235	poly u1 = ppMult_qq(t,l->getTerm());
236	Print("------------------------------IN CRITERION 1-----------------------------------------\n");
237	Print("TESTED ELEMENT: ");
238	pWrite(l->getPoly());
239	pWrite(ppMult_qq(t,l->getTerm()));
240	Print("%d\n\n",l->getIndex());
241	while(testNode->getIndex() < idx && NULL != testNode->getLPoly()) {
242	pWrite(testNode->getPoly());
243	Print("%d\n",testNode->getIndex());
244	if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
245	Print("Criterion 1 NOT passed!\n");
246	return true;
247	}
248	pWrite(testNode->getNext()->getPoly());
249	testNode = testNode->getNext();
250	}
251	return false;
252	}
253	}
254
255
256
257	/*
258	=====================================
259	Criterion 2, i.e. Rewritten Criterion
260	=====================================
261	*/
262	bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) {
263	Print("------------------------------IN CRITERION 2-----------------------------------------\n");
264	Print("RULES: \n");
265	RNode* tempR = rules->getFirst();
266	while(NULL != tempR->getRule()) {
267	Print("ADDRESS OF RULE: %p\n",tempR->getRule());
268	pWrite(tempR->getRuleTerm());
269	Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
270	Print("%d\n\n",tempR->getRuleIndex());
271	tempR = tempR->getNext();
272	}
273	Print("TESTED ELEMENT: ");
274	pWrite(l->getPoly());
275	pWrite(ppMult_qq(t,l->getTerm()));
276	Print("%d\n\n",l->getIndex());
277	// start at the previously added element to gPrev, as all other elements will have the same index for sure
278	RNode* testNode = new RNode();
279	if(NULL == rTag->getFirst()->getRule()) {
280	testNode = rules->getFirst();
281	}
282	else {
283	if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
284	testNode = rules->getFirst();
285	}
286	else {
287	Print("DEBUG\n");
288	Print("L INDEX: %d\n",l->getIndex());
289	testNode = rTag->get(l->getIndex());
290	Print("TESTNODE ADDRESS: %p\n",testNode);
291	}
292	}
293	// save the monom t1*label_term(l) as it is tested various times in the following
294	poly u1 = ppMult_qq(t,l->getTerm());
295	// first element added to rTag was NULL, check for this
296	//Print("%p\n",testNode->getRule());
297	// NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
298	if(NULL != testNode && NULL != testNode->getRule()) {
299	pWrite(testNode->getRuleTerm());
300	}
301	if(NULL != testNode) {
302	if(testNode->getRule() == l->getRule()) {
303	Print("%p\n%p\n",testNode->getRule(),l->getRule());
304	Print("EQUAL\n");
305	}
306	else {
307	Print("NOT EQUAL\n");
308	}
309	}
310	while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule()
311	&& l->getIndex() == testNode->getRuleIndex()) {
312	pWrite(testNode->getRuleTerm());
313	if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
314	Print("Criterion 2 NOT passed!\n");
315	pDelete(&u1);
316	return true;
317	}
318	testNode = testNode->getNext();
319	}
320	pDelete(&u1);
321	return false;
322	}
323
324
325
326	/*
327	=================================================================================================================
328	Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
329	=================================================================================================================
330	*/
331	bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) {
332	Print("------------------------------IN CRITERION 2-----------------------------------------\n");
333	Print("LAST RULE TESTED: %p",testedRule);
334	Print("RULES: \n");
335	RNode* tempR = rules->getFirst();
336	while(NULL != tempR->getRule()) {
337	pWrite(tempR->getRuleTerm());
338	Print("%d\n\n",tempR->getRuleIndex());
339	tempR = tempR->getNext();
340	}
341	Print("TESTED ELEMENT: ");
342	pWrite(l->getPoly());
343	pWrite(ppMult_qq(t,l->getTerm()));
344	Print("%d\n\n",l->getIndex());
345	// start at the previously added element to gPrev, as all other elements will have the same index for sure
346	RNode* testNode = rules->getFirst();
347	// save the monom t1*label_term(l) as it is tested various times in the following
348	poly u1 = ppMult_qq(t,l->getTerm());
349	// first element added to rTag was NULL, check for this
350	while(NULL != testNode->getRule() && testNode->getRule() != testedRule) {
351	pWrite(testNode->getRuleTerm());
352	if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
353	Print("Criterion 2 NOT passed!\n");
354	pDelete(&u1);
355	return true;
356	}
357	testNode = testNode->getNext();
358	}
359	pDelete(&u1);
360	return false;
361	}
362
363
364
365	/*
366	==================================
367	Computation of S-Polynomials in F5
368	==================================
369	*/
370	void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) {
371	CNode* temp = first;
372	poly sp = pInit();
373	//Print("###############################IN SPOLS##############################\n");
374	while(NULL != temp->getData()) {
375	// only if a new rule was added since the last test in subalgorithm criticalPair()
376	//if(rules->getFirst() != rTag->getFirst()) {
377	if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRule())) {
378	// the second component is tested only when it has the actual index, otherwise there is
379	// no new rule to test since the last test in subalgorithm criticalPair()
380	if(temp->getLp2Index() == temp->getLp1Index()) {
381	if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) {
382	// computation of S-polynomial
383	sp = pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
384	ppMult_qq(temp->getT2(),temp->getLp2Poly()));
385	Print("BEGIN SPOLY1\n====================\n");
386	pNorm(sp);
387	pWrite(sp);
388	Print("END SPOLY1\n====================\n");
389	if(NULL == sp) {
390	// as rules consist only of pointers we need to save the labeled
391	// S-polynomial also of a zero S-polynomial
392	//zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
393	// origin of rule can be set NULL as the labeled polynomial
394	// will never be used again as it is zero => no problems with
395	// further criterion2() tests and termination conditions
396	Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
397	reductionsToZero++;
398	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
399	Print("RULE ADDED: \n");
400	pWrite(rules->getFirst()->getRuleTerm());
401	// as sp = NULL, delete it
402	pDelete(&sp);
403	Print("HIER\n");
404	}
405	else {
406	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
407	Print("RULE ADDED: \n");
408	pWrite(rules->getFirst()->getRuleTerm());
409	sPolyList->insertSP(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
410	}
411	// data is saved in sPolyList or zero => delete sp
412	}
413	}
414	else { // temp->getLp2Index() < temp->getLp1Index()
415	// computation of S-polynomial
416	sp = pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
417	ppMult_qq(temp->getT2(),temp->getLp2Poly()));
418	Print("BEGIN SPOLY2\n====================\n");
419	pNorm(sp);
420	pWrite(sp);
421	Print("END SPOLY2\n====================\n");
422	if(NULL == sp) {
423	// zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
424	// origin of rule can be set NULL as the labeled polynomial
425	// will never be used again as it is zero => no problems with
426	// further criterion2() tests and termination conditions
427	Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
428	reductionsToZero++;
429	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
430	Print("RULE ADDED: \n");
431	pWrite(rules->getFirst()->getRuleTerm());
432	// as sp = NULL, delete it
433	pDelete(&sp);
434	}
435	else {
436	rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
437	Print("RULE ADDED: \n");
438	pWrite(rules->getFirst()->getRuleTerm());
439	Print("%d\n",rules->getFirst()->getRuleIndex());
440	Print("%p\n",sPolyList->getFirst());
441	sPolyList->insertSP(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
442	}
443	// data is saved in sPolyList or zero => delete sp
444	}
445	}
446	//}
447	temp = temp->getNext();
448	}
449	// these critical pairs can be deleted now as they are either useless for further computations or
450	// already saved as an S-polynomial to be reduced in the following
451	delete first;
452	}
453
454
455
456	/*
457	========================================================================
458	reduction including subalgorithm topReduction() using Faugere's criteria
459	========================================================================
460	*/
461	void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
462	ideal gbPrev) {
463	Print("##########################################In REDUCTION!########################################\n");
464	// check if sPolyList has any elements
465	// NOTE: due to initialization sPolyList always has a default NULL element
466	while(sPolyList->getLength() > 0) {
467	Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
468	if(sPolyList->getLength() > 1) {
469	Print("%p\n",sPolyList->getFirst());
470	Print("%p\n",sPolyList->getFirst()->getLPoly());
471	Print("%p\n",sPolyList->getFirst()->getNext());
472	Print("%p\n",sPolyList->getFirst()->getNext()->getLPoly());
473	Print("%p\n",sPolyList->getFirst());
474	}
475	sPolyList->print();
476	// temp is the first element in the sPolyList which should be reduced
477	// due to earlier sorting this is the element of minimal degree AND
478	// minimal label
479	LNode* temp = sPolyList->getFirst();
480	pWrite(temp->getPoly());
481	// delete the above first element from sPolyList, temp will be either reduced to
482	// zero or added to gPrev, but never come back to sPolyList
483	sPolyList->setFirst(temp->getNext());
484	Print("HALLO %p\n",temp->getPoly());
485	Print("%p\n",temp->getPoly());
486	pWrite(temp->getPoly());
487	idShow(gbPrev);
488	poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
489	pNorm(tempNF);
490	Print("LENGTH: %d\n",sPolyList->getLength());
491	pWrite(tempNF);
492	pWrite(temp->getPoly());
493	if(NULL != tempNF) {
494	// write the reduced polynomial in temp
495	temp->setPoly(tempNF);
496	// try further reductions of temp with polynomials in gPrev
497	// with label index = current label index: this is done such that there
498	// is no label corruption during the reduction process
499	topReduction(temp,sPolyList,gPrev,rules,lTag,rTag);
500
501	}
502	if(NULL != temp->getPoly()) {
503	//CList* newCritPairs = new CList;
504	Print("##################IN CRITPAIRS IN REDUCTION#####################\n");
505	criticalPair(gPrev,critPairs,lTag,rTag,rules);
506	}
507	else {
508	//delete temp;
509	LNode* tempLoop = gPrev->getFirst();
510	Print("AUSGABE IN REDUCTION:\n");
511	while(NULL != tempLoop) {
512	pWrite(tempLoop->getPoly());
513	tempLoop = tempLoop->getNext();
514	}
515	//sleep(10);
516	}
517	}
518	}
519
520
521
522	/*
523	=====================================================================================
524	top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
525	the same index whereas the labels are taken into account
526	=====================================================================================
527	*/
528	void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
529	Print("##########################################In topREDUCTION!########################################\n");
530	// try l as long as there are reductors found by findReductor()
531	do {
532	LNode* tempRed = new LNode();
533	tempRed = findReductor(l,gPrev,rules,lTag,rTag);
534	Print("--------------------------------HIER DEBUG 2----------------------------------\n");
535	// if a reductor for l is found and saved in tempRed
536	if(NULL != tempRed) {
537	// if label of reductor is greater than the label of l we have to built a new element
538	// and add it to sPolyList
539	if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
540	poly temp = pSub(tempRed->getPoly(),l->getPoly());
541	Print("OH JE\n");
542	pWrite(temp);
543	if(NULL != temp) {
544	pNorm(temp);
545	tempRed->setPoly(temp);
546	// for debugging
547	pWrite(tempRed->getPoly());
548	Print("RULE ADDED\n");
549	rules->insert(tempRed->getIndex(),tempRed->getTerm());
550
551	tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
552	Print("%p\n",sPolyList->getFirst());
553	Print("%p\n",sPolyList->getFirst()->getLPoly());
554	Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
555	sPolyList->insertByLabel(tempRed);
556	}
557	else {
558	pDelete(&temp);
559	reductionsToZero++;
560	Print("RULE ADDED\n");
561	Print("wieder hier2\n");
562	rules->insert(tempRed->getIndex(),tempRed->getTerm());
563	delete tempRed;
564	}
565	}
566	// label of reductor is smaller than the label of l, subtract reductor from l and delete the
567	// gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
568	// after subtraction
569	else {
570	poly temp = pSub(l->getPoly(),tempRed->getPoly());
571	pWrite(temp);
572	if(NULL != temp) {
573	pNorm(temp);
574	l->setPoly(temp);
575	l->setGPrevRedCheck(NULL);
576	}
577	else {
578	Print("ZERO REDUCTION!\n");
579	reductionsToZero++;
580	pDelete(&temp);
581	l->setPoly(NULL);
582	pWrite(gPrev->getLast()->getPoly());
583	break;
584	}
585	}
586	}
587	else {
588	if(NULL != l->getPoly()) {
589	Print("ADDED TO GPREV IN TOPREDUCTION: ");
590	pWrite(l->getPoly());
591	pWrite(l->getTerm());
592	Print("INDEX: %d\n", l->getIndex());
593	//sleep(10);
594	gPrev->insert(l->getLPoly());
595	Print("GPREV: \n");
596	LNode* tempLoop = gPrev->getFirst();
597	while(NULL != tempLoop) {
598	Print("HERE\n");
599	pWrite(tempLoop->getPoly());
600	tempLoop = tempLoop->getNext();
601	}
602	}
603	break;
604	}
605	} while(1);
606	}
607
608
609	/*
610	=====================================================================
611	subalgorithm to find a possible reductor for the labeled polynomial l
612	=====================================================================
613	*/
614	LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
615	// allociation of memory for the possible reductor
616	Print("IN FIND REDUCTOR\n");
617	poly u = pOne();
618	poly red = pOne();
619	number nOne = nInit(1);
620	LNode* temp = new LNode();
621	// head term of actual element such that we do not have to call pHead at each new reductor test
622	poly t = pHead(l->getPoly());
623	// if l was already checked use the information in gPrevRedCheck such
624	// that we can start searching for new reducers from this point and
625	// not from the first element of gPrev with the current index
626	if(NULL != l->getGPrevRedCheck()) {
627	temp = l->getGPrevRedCheck()->getNext();
628	}
629	// no reductors were searched for l before, thus start at the first
630	// element of gPrev with the current index, tagged by lTag
631	else {
632	temp = lTag->getFirstCurrentIdx();
633	}
634	// search for reductors until we are at the end of gPrev resp. at the
635	// end of the elements of the current index
636	while(NULL != temp && temp->getIndex() == l->getIndex()) {
637	// does the head of the element of gPrev divides the head of
638	// the to be reduced element?
639	if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
640	// get all the information needed for the following tests
641	// of the criteria
642	u = pDivide(t,pHead(temp->getPoly()));
643	pSetCoeff(u,nOne);
644	red = ppMult_qq(u,temp->getPoly());
645	pNorm(red);
646	u = ppMult_qq(u,temp->getTerm());
647	pSetCoeff(u,nOne);
648	// check if both have the same label
649	if(pLmCmp(u,l->getTerm()) != 0) {
650	// passing criterion2 ?
651	if(!criterion2(u,temp,rules,rTag)) {
652	// passing criterion1 ?
653	if(!criterion1(gPrev,u,temp,lTag)) {
654	Print("HIER DEBUG\n");
655	l->setGPrevRedCheck(temp);
656	LNode* redNode = new LNode(u,temp->getIndex(),red,NULL,NULL);
657	return redNode;
658	}
659	}
660	}
661	}
662	temp = temp->getNext();
663	}
664
665	// delete temp;
666	Print("1st gPrev: ");
667	pWrite(gPrev->getFirst()->getPoly());
668	Print("2nd gPrev: ");
669	pWrite(gPrev->getFirst()->getNext()->getPoly());
670	return NULL;
671	}
672
673
674
675	/*
676	==========================================================================
677	MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
678	==========================================================================
679	*/
680	ideal F5main(ideal id, ring r) {
681	int i,j;
682	int gbLength;
683	// 1 polynomial for defining initial labels & further tests
684	poly ONE = pOne();
685	// tag the first element of index i-1 for criterion 1
686	LTagList* lTag = new LTagList();
687	Print("LTAG BEGINNING: %p\n",lTag->getFirst());
688
689	// first element in rTag is first element of rules which is NULL RNode,
690	// this must be done due to possible later improvements
691	RList* rules = new RList();
692	RTagList* rTag = new RTagList(rules->getFirst());
693	i = 1;
694	for(j=0; j<IDELEMS(id); j++) {
695	if(NULL != id->m[j]) {
696	if(pComparePolys(id->m[j],ONE)) {
697	Print("One Polynomial in Input => Computations stopped\n");
698	ideal idNew = idInit(1,1);
699	idNew->m[0] = ONE;
700	return(idNew);
701	}
702	}
703	}
704	LList* gPrev = new LList(ONE, i, id->m[0]);
705	Print("%p\n",id->m[0]);
706	pWrite(id->m[0]);
707	Print("%p\n",gPrev->getFirst()->getPoly());
708	pWrite(gPrev->getFirst()->getPoly());
709
710	lTag->insert(gPrev->getFirst());
711	lTag->setFirstCurrentIdx(gPrev->getFirst());
712	// computing the groebner basis of the elements of index < actual index
713	gbLength = gPrev->getLength();
714	Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
715	ideal gbPrev = idInit(gbLength,1);
716	// initializing the groebner basis of elements of index < actual index
717	gbPrev->m[0] = gPrev->getFirst()->getPoly();
718	idShow(gbPrev);
719	idShow(currQuotient);
720
721	for(i=2; i<=IDELEMS(id); i++) {
722	LNode* gPrevTag = gPrev->getLast();
723	Print("Last POlynomial in GPREV: ");
724	Print("%p\n",gPrevTag);
725	pWrite(gPrevTag->getPoly());
726	gPrev = F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
727	// DEBUGGING STUFF
728	LNode* temp = gPrev->getFirst();
729	while(NULL != temp) {
730	pWrite(temp->getPoly());
731	temp = temp->getNext();
732	}// comuting new groebner basis gbPrev
733	if(gPrev->getLength() > gbLength) {
734	ideal gbAdd = idInit(gPrev->getLength()-gbLength,1);
735	LNode* temp = gPrevTag;
736	Print("%p\n",gPrevTag);
737	Print("%p\n",gPrev->getLast());
738	pWrite(temp->getPoly());
739	Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
740	Print("%d\n",gbLength);
741	for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
742	Print("YES\n");
743	temp = temp->getNext();
744	gbAdd->m[j] = temp->getPoly();
745	pWrite(temp->getPoly());
746	}
747	gbLength = gPrev->getLength();
748	gbPrev = idAdd(gbPrev,gbAdd);
749	}
750	Print("GROEBNER BASIS:\n====================================================\n");
751	idShow(gbPrev);
752	Print("===================================================\n");
753	Print("JA\n");
754	}
755	Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero);
756	LNode* temp = gPrev->getFirst();
757	while(NULL != temp) {
758	pWrite(temp->getPoly());
759	temp = temp->getNext();
760	}
761	return(gbPrev);
762
763
764	}
765
766	#endif

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

Download in other formats: