Context Navigation

source: git/kernel/f5gb.cc @ 9cb4078

spielwiese

Last change on this file since 9cb4078 was 9cb4078, checked in by Christian Eder, 15 years ago
implemented interreduction, still with lots of bugs => commented out git-svn-id: file:///usr/local/Singular/svn/trunk@11514 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 37.1 KB

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

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

Download in other formats: