Context Navigation

source: git/kernel/f5gb.cc @ eab144e

spielwiese

Last change on this file since eab144e was eab144e, checked in by Christian Eder, 15 years ago
fmtm() example runs, cycli_n has problems, reductions are not made for some reason git-svn-id: file:///usr/local/Singular/svn/trunk@11407 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 28.4 KB

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

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

Download in other formats: