1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* |
---|
5 | * ABSTRACT: f5gb interface |
---|
6 | */ |
---|
7 | |
---|
8 | #ifdef HAVE_CONFIG_H |
---|
9 | #include "singularconfig.h" |
---|
10 | #endif /* HAVE_CONFIG_H */ |
---|
11 | #include <kernel/mod2.h> |
---|
12 | #ifdef HAVE_F5 |
---|
13 | #include <unistd.h> |
---|
14 | #include <omp.h> |
---|
15 | #include <kernel/structs.h> |
---|
16 | #include <kernel/kutil.h> |
---|
17 | #include <omalloc/omalloc.h> |
---|
18 | #include <kernel/polys.h> |
---|
19 | #include <polys/monomials/p_polys.h> |
---|
20 | #include <polys/templates/p_Procs.h> |
---|
21 | #include <kernel/ideals.h> |
---|
22 | #include <kernel/febase.h> |
---|
23 | #include <kernel/kstd1.h> |
---|
24 | #include <kernel/khstd.h> |
---|
25 | #include <polys/kbuckets.h> |
---|
26 | #include <polys/weight.h> |
---|
27 | #include <misc/intvec.h> |
---|
28 | #include <kernel/polys.h> |
---|
29 | #include <kernel/f5gb.h> |
---|
30 | #include <kernel/f5data.h> |
---|
31 | #include <kernel/f5lists.h> |
---|
32 | #include <kernel/timer.h> |
---|
33 | int notInG = 0; |
---|
34 | int numberOfRules = 0; |
---|
35 | int reductionsToZero = 0; |
---|
36 | int reductionTime = 0; |
---|
37 | int spolsTime = 0; |
---|
38 | int highestDegree = 0; |
---|
39 | int degreeBound = 0; |
---|
40 | int numberUsefulPairs = 0; |
---|
41 | int numberUselessPairs = 0; |
---|
42 | int numberUsefulPairsMinDeg = 0; |
---|
43 | int highestDegreeGBCriticalPair = 0; |
---|
44 | int numberRejectedF5CriticalPairs = 0; |
---|
45 | int numberOfReductions = 0; |
---|
46 | int numberOfSpolys = 0; |
---|
47 | /* |
---|
48 | ==================================================================== |
---|
49 | sorting ideals by decreasing total degree "left" and "right" are the |
---|
50 | pointer of the first and last polynomial in the considered ideal |
---|
51 | ==================================================================== |
---|
52 | */ |
---|
53 | void qsortDegree(poly* left, poly* right) { |
---|
54 | poly* ptr1 = left; |
---|
55 | poly* ptr2 = right; |
---|
56 | poly p1,p2; |
---|
57 | p2 = *(left + (right - left >> 1)); |
---|
58 | do { |
---|
59 | while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) { |
---|
60 | ptr1++; |
---|
61 | } |
---|
62 | while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) { |
---|
63 | ptr2--; |
---|
64 | } |
---|
65 | if(ptr1 > ptr2) { |
---|
66 | break; |
---|
67 | } |
---|
68 | p1 = *ptr1; |
---|
69 | *ptr1 = *ptr2; |
---|
70 | *ptr2 = p1; |
---|
71 | } while(++ptr1 <= --ptr2); |
---|
72 | |
---|
73 | if(left < ptr2) { |
---|
74 | qsortDegree(left,ptr2); |
---|
75 | } |
---|
76 | if(ptr1 < right) { |
---|
77 | qsortDegree(ptr1,right); |
---|
78 | } |
---|
79 | } |
---|
80 | |
---|
81 | /*! |
---|
82 | * ====================================================================== |
---|
83 | * builds the sum of the entries of the exponent vectors, i.e. the degree |
---|
84 | * of the corresponding monomial |
---|
85 | * ====================================================================== |
---|
86 | */ |
---|
87 | long sumVector(int* v, int k) { |
---|
88 | int i; |
---|
89 | long sum = 0; |
---|
90 | for(i=1; i<=k; i++) { |
---|
91 | Print("%d\n",v[i]); |
---|
92 | Print("%ld\n",sum); |
---|
93 | sum = sum + v[i]; |
---|
94 | } |
---|
95 | return sum; |
---|
96 | } |
---|
97 | |
---|
98 | /*! |
---|
99 | ========================================================================== |
---|
100 | compares monomials, i.e. divisibility tests for criterion 1 and criterion 2 |
---|
101 | ========================================================================== |
---|
102 | */ |
---|
103 | bool compareMonomials(int* m1, int** m2, int numberOfRules, int k) { |
---|
104 | int i,j; |
---|
105 | long sumM1 = sumVector(m1,k); |
---|
106 | //int k = sizeof(m1) / sizeof(int); |
---|
107 | for(i=0; i<numberOfRules; i++) { |
---|
108 | if(sumVector(m2[i],k) <= sumM1) { |
---|
109 | for(j=1; j<=k; j++) { |
---|
110 | if(m1[j]>m2[i][j]) { |
---|
111 | return true; |
---|
112 | } |
---|
113 | } |
---|
114 | } |
---|
115 | } |
---|
116 | return false; |
---|
117 | } |
---|
118 | |
---|
119 | /* |
---|
120 | ================================================== |
---|
121 | computes incrementally gbs of subsets of the input |
---|
122 | gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} |
---|
123 | ================================================== |
---|
124 | */ |
---|
125 | LList* F5inc(int i, poly f_i, LList* gPrev, LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus, int termination) { |
---|
126 | //Print("in f5inc\n"); |
---|
127 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
128 | int iterationstep = i; |
---|
129 | int j; |
---|
130 | //Print("%p\n",gPrev->getFirst()); |
---|
131 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
132 | poly tempNF = kNF(gbPrev,currQuotient,f_i); |
---|
133 | f_i = tempNF; |
---|
134 | //gPrev->insert(ONE,i,f_i); |
---|
135 | gPrev->insert(ONE,gPrev->getLength()+1,f_i); |
---|
136 | // tag the first element in gPrev of the current index for findReductor() |
---|
137 | lTag->setFirstCurrentIdx(gPrev->getLast()); |
---|
138 | //Print("1st gPrev: "); |
---|
139 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
140 | //Print("2nd gPrev: "); |
---|
141 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
142 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
143 | CListOld* critPairs = new CListOld(); |
---|
144 | CNode* critPairsMinDeg = new CNode(); |
---|
145 | PList* rejectedGBList = new PList(); |
---|
146 | // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them |
---|
147 | // in the list critPairs |
---|
148 | criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus); |
---|
149 | static LList* sPolyList = new LList(); |
---|
150 | //sPolyList->print(); |
---|
151 | // labeled polynomials which have passed reduction() and have to be added to list gPrev |
---|
152 | static LList* completed = new LList(); |
---|
153 | // the reduced labeled polynomials which are returned from subalgorithm reduction() |
---|
154 | static LList* reducedLPolys = new LList(); |
---|
155 | // while there are critical pairs to be further checked and deleted/computed |
---|
156 | while(NULL != critPairs->getFirst()) { |
---|
157 | // critPairs->getMinDeg() deletes the first elements of minimal degree from |
---|
158 | // critPairs, thus the while loop is not infinite. |
---|
159 | // adds all to be reduced S-polynomials in the list sPolyList and adds |
---|
160 | // the corresponding rules to the list rules |
---|
161 | // NOTE: inside there is a second check of criterion 2 if new rules are |
---|
162 | // added |
---|
163 | //int timer4 = initTimer(); |
---|
164 | //startTimer(); |
---|
165 | //critPairs->print(); |
---|
166 | |
---|
167 | //definition of a local numberUsefulPairs variable for the next degree |
---|
168 | //step: |
---|
169 | //if in this degree all pairs are useless, skip this degree step |
---|
170 | //completely! |
---|
171 | //long arrideg = critPairs->getFirst()->getData()->getDeg(); |
---|
172 | //if(plus && highestDegreeGBCriticalPair < critPairs->getFirst()->getData()->getDeg()) { |
---|
173 | // return gPrev; |
---|
174 | //} |
---|
175 | //else { |
---|
176 | critPairsMinDeg = critPairs->getMinDeg(); |
---|
177 | //numberUsefulPairsMinDeg = computeUsefulMinDeg(critPairsMinDeg); |
---|
178 | //if(numberUsefulPairs > 0) { |
---|
179 | //if(numberUsefulPairsMinDeg > 0) { |
---|
180 | //Print("number of useful pairs: %d\n",numberUsefulPairs); |
---|
181 | //Print("number of useless pairs: %d\n\n",numberUselessPairs); |
---|
182 | //Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg()); |
---|
183 | long degreecheck = critPairsMinDeg->getData()->getDeg(); |
---|
184 | |
---|
185 | computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList); |
---|
186 | //} |
---|
187 | //} |
---|
188 | //} |
---|
189 | //else { |
---|
190 | // return gPrev; |
---|
191 | //} |
---|
192 | //timer4 = getTimer(); |
---|
193 | //Print("SPOLS TIMER: %d\n",timer4); |
---|
194 | //spolsTime = spolsTime + timer4; |
---|
195 | // DEBUG STUFF FOR SPOLYLIST |
---|
196 | LNode* temp = sPolyList->getFirst(); |
---|
197 | //while(NULL != temp && NULL != temp->getLPoly()) { |
---|
198 | //Print("Spolylist element: "); |
---|
199 | //pWrite(temp->getPoly()); |
---|
200 | //temp = temp->getNext(); |
---|
201 | //} |
---|
202 | // reduction process of new S-polynomials and also adds new critical pairs to critPairs |
---|
203 | //int timer3 = initTimer(); |
---|
204 | //startTimer(); |
---|
205 | //sPolyList->print(); |
---|
206 | //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev); |
---|
207 | //Print("BEFORE REDUCTION: \n"); |
---|
208 | //Print("number of useful pairs: %d\n",numberUsefulPairs); |
---|
209 | //Print("number of useless pairs: %d\n\n",numberUselessPairs); |
---|
210 | newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus); |
---|
211 | //Print("ITERATION: %d",iterationstep); |
---|
212 | //Print("NAECHSTER GRAD: %ld",degreecheck); |
---|
213 | //sleep(5); |
---|
214 | //if(i == 5 && pDeg(gPrev->getLast()->getPoly()) == 8) { |
---|
215 | // Print("RAUS BEI DEG 8 \n"); |
---|
216 | // return gPrev; |
---|
217 | //} |
---|
218 | //Print("ARRIS DEG: %ld\n",arrideg); |
---|
219 | // Arris idea stated by John in an email |
---|
220 | //if(arrisCheck(critPairs->getFirst(),gPrev->getFirst(),arrideg)) { |
---|
221 | // Print("ARRIS DEGREE: %ld\n", arrideg); |
---|
222 | // return gPrev; |
---|
223 | //} |
---|
224 | |
---|
225 | |
---|
226 | //bool aha = checkDGB(gPrev); |
---|
227 | |
---|
228 | |
---|
229 | //timer3 = getTimer(); |
---|
230 | //reductionTime = reductionTime + timer3; |
---|
231 | //Print("REDUCTION TIMER: %d\n",timer3); |
---|
232 | // DEBUG STUFF FOR GPREV |
---|
233 | //temp = gPrev->getFirst(); |
---|
234 | //int number = 1; |
---|
235 | //Print("\n\n"); |
---|
236 | //while(NULL != temp) { |
---|
237 | // Print("%d. ",number); |
---|
238 | // pWrite(temp->getPoly()); |
---|
239 | // temp = temp->getNext(); |
---|
240 | // number++; |
---|
241 | // Print("\n"); |
---|
242 | //} |
---|
243 | //sleep(5); |
---|
244 | |
---|
245 | } |
---|
246 | //Print("REDUCTION DONE\n"); |
---|
247 | //Print("%p\n",rules->getFirst()); |
---|
248 | //Print("%p\n",rTag->getFirst()); |
---|
249 | //if(rules->getFirst() != rTag->getFirst()) { |
---|
250 | //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n"); |
---|
251 | //rTag->insert(rules->getFirst()); |
---|
252 | //} |
---|
253 | //else { |
---|
254 | //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n"); |
---|
255 | //} |
---|
256 | lTag->insert(lTag->getFirstCurrentIdx()); |
---|
257 | //Print("INDEX: %d\n",tempTag->getIndex()); |
---|
258 | //pWrite(tempTag->getPoly()); |
---|
259 | //Print("COMPLETED FIRST IN F5INC: \n"); |
---|
260 | //Print("1st gPrev: "); |
---|
261 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
262 | //Print("2nd gPrev: "); |
---|
263 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
264 | //Print("3rd gPrev: "); |
---|
265 | //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly()); |
---|
266 | //delete sPolyList; |
---|
267 | //critPairs->print(); |
---|
268 | delete critPairs; |
---|
269 | //Print("IN F5INC\n"); |
---|
270 | /* |
---|
271 | Print("\n\n\nRULES: \n"); |
---|
272 | RNode* tempR = rules->getFirst(); |
---|
273 | Print("%p\n",tempR); |
---|
274 | int t = 1; |
---|
275 | while(NULL != tempR) { |
---|
276 | Print("ADDRESS OF %d RNODE: %p\n",t,tempR); |
---|
277 | Print("ADDRESS OF RULE: %p\n",tempR->getRule()); |
---|
278 | pWrite(tempR->getRuleTerm()); |
---|
279 | Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm()); |
---|
280 | Print("%d\n\n",tempR->getRuleIndex()); |
---|
281 | tempR = tempR->getNext(); |
---|
282 | t++; |
---|
283 | } |
---|
284 | */ |
---|
285 | //gPrev->print(); |
---|
286 | //Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime); |
---|
287 | //Print("COMPLETE SPOLS TIME UNTIL NOW: %d\n",spolsTime); |
---|
288 | degreeBound = 0; |
---|
289 | return gPrev; |
---|
290 | } |
---|
291 | |
---|
292 | |
---|
293 | |
---|
294 | bool checkDGB(LList* gPrev) { |
---|
295 | Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly())); |
---|
296 | LNode* temp = gPrev->getFirst(); |
---|
297 | LNode* temp2; |
---|
298 | bool isDGb = 0; |
---|
299 | // construct the d-GB gb |
---|
300 | ideal gb = idInit(gPrev->getLength(),1); |
---|
301 | for(int j=0;j<=gPrev->getLength()-1;j++) { |
---|
302 | gb->m[j] = temp->getPoly(); |
---|
303 | pWrite(gb->m[j]); |
---|
304 | temp = temp->getNext(); |
---|
305 | } |
---|
306 | /* |
---|
307 | Kstd1_deg = pDeg(gPrev->getLast()->getPoly()); |
---|
308 | BITSET save = test; |
---|
309 | test |= Sy_bit(OPT_DEGBOUND); |
---|
310 | kStd(); |
---|
311 | test = save; |
---|
312 | */ |
---|
313 | temp = gPrev->getFirst(); |
---|
314 | while(NULL != temp) { |
---|
315 | temp2 = temp->getNext(); |
---|
316 | number nOne = nInit(1); |
---|
317 | poly lcm = pOne(); |
---|
318 | poly sp = pOne(); |
---|
319 | while(NULL != temp2) { |
---|
320 | pLcm(temp->getPoly(),temp2->getPoly(),lcm); |
---|
321 | pSetCoeff(lcm,nOne); |
---|
322 | pSetm(lcm); |
---|
323 | Print("LCM: "); |
---|
324 | pWrite(lcm); |
---|
325 | if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) { |
---|
326 | poly u1 = pOne(); |
---|
327 | poly u2 = pOne(); |
---|
328 | u1 = pDivide(lcm,pHead(temp->getPoly())); |
---|
329 | pSetCoeff(u1,nOne); |
---|
330 | u2 = pDivide(lcm,pHead(temp2->getPoly())); |
---|
331 | pSetCoeff(u2,nOne); |
---|
332 | sp = ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()), |
---|
333 | ppMult_qq(u2,temp2->getPoly())); |
---|
334 | pNorm(sp); |
---|
335 | |
---|
336 | poly reducer = pOne(); |
---|
337 | //reducer = gb->m[0]; |
---|
338 | int i = 0; |
---|
339 | pWrite(pHead(sp)); |
---|
340 | |
---|
341 | while(i<IDELEMS(gb)) { |
---|
342 | reducer = gb->m[i]; |
---|
343 | if(pDivisibleBy(reducer,pHead(sp))) { |
---|
344 | poly uReducer = pOne(); |
---|
345 | uReducer = pDivide(lcm,pHead(reducer)); |
---|
346 | pSetCoeff(uReducer,nOne); |
---|
347 | sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer)); |
---|
348 | //pNorm(tempSP); |
---|
349 | //sp = tempSP; |
---|
350 | pNorm(sp); |
---|
351 | pWrite(sp); |
---|
352 | i = 0; |
---|
353 | } |
---|
354 | else { |
---|
355 | i++; |
---|
356 | } |
---|
357 | } |
---|
358 | |
---|
359 | pWrite(pHead(sp)); |
---|
360 | } |
---|
361 | temp2 = temp2->getNext(); |
---|
362 | } |
---|
363 | temp = temp->getNext(); |
---|
364 | } |
---|
365 | Print("------------------\n"); |
---|
366 | return isDGb; |
---|
367 | } |
---|
368 | |
---|
369 | /* |
---|
370 | * Arris Check if we are finished after the current degree step: |
---|
371 | * Checks all remaining critical pairs, i.e. those of higher degree, |
---|
372 | * by the two Buchberger criteria. |
---|
373 | * return value: 0, if all remaining critical pairs are deleted by |
---|
374 | * Buchberger's criteria |
---|
375 | * 1, otherwise |
---|
376 | */ |
---|
377 | bool arrisCheck(CNode* first, LNode* firstGCurr, long arrideg) { |
---|
378 | CNode* temp = first; |
---|
379 | |
---|
380 | //product criterion check |
---|
381 | while(NULL != temp) { |
---|
382 | if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) { |
---|
383 | return 0; |
---|
384 | } |
---|
385 | temp = temp->getNext(); |
---|
386 | } |
---|
387 | |
---|
388 | // chain criterion |
---|
389 | LNode* tempPoly = firstGCurr; |
---|
390 | while(NULL != tempPoly) { |
---|
391 | LNode* tempPoly2 = tempPoly->getNext(); |
---|
392 | while(NULL != tempPoly2) { |
---|
393 | number nOne = nInit(1); |
---|
394 | poly lcm = pOne(); |
---|
395 | pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm); |
---|
396 | pSetCoeff(lcm,nOne); |
---|
397 | pSetm(lcm); |
---|
398 | if(pDeg(lcm) > arrideg) { |
---|
399 | LNode* tempPoly3 = firstGCurr; |
---|
400 | while(NULL != tempPoly3) { |
---|
401 | if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) { |
---|
402 | poly lcm1 = pOne(); |
---|
403 | poly lcm2 = pOne(); |
---|
404 | pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1); |
---|
405 | pSetCoeff(lcm1,nOne); |
---|
406 | pSetm(lcm1); |
---|
407 | pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2); |
---|
408 | pSetCoeff(lcm2,nOne); |
---|
409 | pSetm(lcm2); |
---|
410 | if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) { |
---|
411 | return 0; |
---|
412 | } |
---|
413 | } |
---|
414 | tempPoly3 = tempPoly3->getNext(); |
---|
415 | } |
---|
416 | } |
---|
417 | tempPoly2 = tempPoly2->getNext(); |
---|
418 | } |
---|
419 | tempPoly = tempPoly->getNext(); |
---|
420 | } |
---|
421 | return 1; |
---|
422 | } |
---|
423 | |
---|
424 | |
---|
425 | |
---|
426 | /* |
---|
427 | ================================================================ |
---|
428 | computes a list of critical pairs for the next reduction process |
---|
429 | the first element is always "useful" thus the critical pair |
---|
430 | computed is either "useful" or "useless" depending on the second |
---|
431 | element which generates the critical pair. |
---|
432 | first element in gPrev is always the newest element which must |
---|
433 | build critical pairs with all other elements in gPrev |
---|
434 | ================================================================ |
---|
435 | */ |
---|
436 | inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList, int plus) { |
---|
437 | //Print("IN CRITPAIRS\n"); |
---|
438 | // initialization for usage in pLcm() |
---|
439 | number nOne = nInit(1); |
---|
440 | LNode* newElement = gPrev->getLast(); |
---|
441 | LNode* temp = gPrev->getFirst(); |
---|
442 | poly u1 = pOne(); |
---|
443 | poly u2 = pOne(); |
---|
444 | poly lcm = pOne(); |
---|
445 | poly t = pHead(newElement->getPoly()); |
---|
446 | RuleOld* testedRuleOld = NULL; |
---|
447 | //Print("NEW: "); |
---|
448 | //pWrite(newElement->getPoly()); |
---|
449 | //Print("ADDRESS: %p",newElement); |
---|
450 | if(NULL != rules->getFirst()) { |
---|
451 | testedRuleOld = rules->getFirst()->getRuleOld(); |
---|
452 | } |
---|
453 | // computation of critical pairs |
---|
454 | while( gPrev->getLast() != temp) { |
---|
455 | //Print("TEMP: "); |
---|
456 | //pWrite(pHead(temp->getPoly())); |
---|
457 | //Print("ADDRESS: %p",temp); |
---|
458 | pLcm(newElement->getPoly(), temp->getPoly(), lcm); |
---|
459 | pSetCoeff(lcm,nOne); |
---|
460 | // computing factors u2 for new labels |
---|
461 | u1 = pDivide(lcm,t); |
---|
462 | if(NULL == u1) { |
---|
463 | break; |
---|
464 | } |
---|
465 | pSetCoeff(u1,nOne); |
---|
466 | u2 = pDivide(lcm,pHead(temp->getPoly())); |
---|
467 | pSetCoeff(u2,nOne); |
---|
468 | int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly()))); |
---|
469 | // testing both new labels by the F5 Criterion |
---|
470 | if(!temp->getDel()) { |
---|
471 | if(plus && highestDegreeGBCriticalPair < degree) { |
---|
472 | highestDegreeGBCriticalPair = degree; |
---|
473 | } |
---|
474 | if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag) |
---|
475 | && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) |
---|
476 | && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { |
---|
477 | // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater |
---|
478 | // label as first element in the CPairOld |
---|
479 | if(newElement->getIndex() == temp->getIndex() && |
---|
480 | -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { |
---|
481 | CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, |
---|
482 | temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld); |
---|
483 | critPairs->insert(cp); |
---|
484 | // counting the number of useful pairs |
---|
485 | numberUsefulPairs++; |
---|
486 | } |
---|
487 | else { |
---|
488 | CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, |
---|
489 | newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld); |
---|
490 | critPairs->insert(cp); |
---|
491 | // counting the number of useful pairs |
---|
492 | numberUsefulPairs++; |
---|
493 | } |
---|
494 | } |
---|
495 | else { |
---|
496 | // TODO: generate a list of lcms of rejected GB critical pairs and |
---|
497 | // check F5 critical pairs with it at their creation |
---|
498 | //Print("--------------------------------------------------------------------\n"); |
---|
499 | //Print("--------------------------------------------------------------------\n"); |
---|
500 | pSetm(lcm); |
---|
501 | rejectedGBList->insert(lcm); |
---|
502 | //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n"); |
---|
503 | //pWrite(lcm); |
---|
504 | //Print("--------------------------------------------------------------------\n"); |
---|
505 | //rejectedGBList->print(); |
---|
506 | } |
---|
507 | } |
---|
508 | else { |
---|
509 | //Print("LABEL: "); |
---|
510 | //pWrite(ppMult_qq(u1,newElement->getTerm())); |
---|
511 | //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair |
---|
512 | if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag) |
---|
513 | && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) |
---|
514 | && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { |
---|
515 | // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater |
---|
516 | // label as first element in the CPairOld |
---|
517 | if(newElement->getIndex() == temp->getIndex() && |
---|
518 | -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { |
---|
519 | CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, |
---|
520 | temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld); |
---|
521 | critPairs->insert(cp); |
---|
522 | numberUselessPairs++; |
---|
523 | } |
---|
524 | else { |
---|
525 | CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, |
---|
526 | newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld); |
---|
527 | critPairs->insert(cp); |
---|
528 | numberUselessPairs++; |
---|
529 | } |
---|
530 | } |
---|
531 | //} |
---|
532 | } |
---|
533 | temp = temp->getNext(); |
---|
534 | } |
---|
535 | } |
---|
536 | |
---|
537 | |
---|
538 | |
---|
539 | /* |
---|
540 | ================================================================ |
---|
541 | computes a list of critical pairs for the next reduction process |
---|
542 | the first element is always "useless" thus the critical pair |
---|
543 | computed is "useless". |
---|
544 | first element in gPrev is always the newest element which must |
---|
545 | build critical pairs with all other elements in gPrev |
---|
546 | ================================================================ |
---|
547 | */ |
---|
548 | inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList) { |
---|
549 | //Print("IN CRITPAIRS\n"); |
---|
550 | // initialization for usage in pLcm() |
---|
551 | number nOne = nInit(1); |
---|
552 | LNode* newElement = gPrev->getLast(); |
---|
553 | LNode* temp = gPrev->getFirst(); |
---|
554 | poly u1 = pOne(); |
---|
555 | poly u2 = pOne(); |
---|
556 | poly lcm = pOne(); |
---|
557 | poly t = pHead(newElement->getPoly()); |
---|
558 | RuleOld* testedRuleOld = NULL; |
---|
559 | if(NULL != rules->getFirst()) { |
---|
560 | testedRuleOld = rules->getFirst()->getRuleOld(); |
---|
561 | } |
---|
562 | // computation of critical pairs |
---|
563 | while( gPrev->getLast() != temp) { |
---|
564 | pLcm(newElement->getPoly(), temp->getPoly(), lcm); |
---|
565 | pSetCoeff(lcm,nOne); |
---|
566 | // computing factors u2 for new labels |
---|
567 | u1 = pDivide(lcm,t); |
---|
568 | if(NULL == u1) { |
---|
569 | break; |
---|
570 | } |
---|
571 | pSetCoeff(u1,nOne); |
---|
572 | u2 = pDivide(lcm,pHead(temp->getPoly())); |
---|
573 | pSetCoeff(u2,nOne); |
---|
574 | // testing both new labels by the F5 Criterion |
---|
575 | //Print("LABEL: "); |
---|
576 | //pWrite(ppMult_qq(u1,newElement->getTerm())); |
---|
577 | //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair |
---|
578 | if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag) |
---|
579 | && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) |
---|
580 | && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { |
---|
581 | // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater |
---|
582 | // label as first element in the CPairOld |
---|
583 | if(newElement->getIndex() == temp->getIndex() && |
---|
584 | -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { |
---|
585 | CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, |
---|
586 | temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld); |
---|
587 | critPairs->insert(cp); |
---|
588 | numberUselessPairs++; |
---|
589 | } |
---|
590 | else { |
---|
591 | CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, |
---|
592 | newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld); |
---|
593 | critPairs->insert(cp); |
---|
594 | numberUselessPairs++; |
---|
595 | } |
---|
596 | } |
---|
597 | //} |
---|
598 | temp = temp->getNext(); |
---|
599 | } |
---|
600 | } |
---|
601 | |
---|
602 | |
---|
603 | |
---|
604 | /* |
---|
605 | ======================================== |
---|
606 | Criterion 1, i.e. Faugere's F5 Criterion |
---|
607 | ======================================== |
---|
608 | */ |
---|
609 | inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) { |
---|
610 | // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag |
---|
611 | int idx = l->getIndex(); |
---|
612 | int i; |
---|
613 | if(idx == 1) { |
---|
614 | //Print("HIER\n"); |
---|
615 | return false; |
---|
616 | } |
---|
617 | else { |
---|
618 | LNode* testNode = gPrev->getFirst(); |
---|
619 | // save the monom t1*label_term(l) as it is tested various times in the following |
---|
620 | poly u1 = ppMult_qq(t,l->getTerm()); |
---|
621 | //Print("------------------------------IN CRITERION 1-----------------------------------------\n"); |
---|
622 | //Print("TESTED ELEMENT: "); |
---|
623 | //pWrite(l->getPoly()); |
---|
624 | //pWrite(l->getTerm()); |
---|
625 | //pWrite(ppMult_qq(t,l->getTerm())); |
---|
626 | //Print("%d\n\n",l->getIndex()); |
---|
627 | while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) { |
---|
628 | //pWrite(testNode->getPoly()); |
---|
629 | //Print("%d\n",testNode->getIndex()); |
---|
630 | if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) { |
---|
631 | //Print("Criterion 1 NOT passed!\n"); |
---|
632 | if(idx != gPrev->getLast()->getIndex()) { |
---|
633 | //Print("DOCH!\n"); |
---|
634 | } |
---|
635 | return true; |
---|
636 | } |
---|
637 | //pWrite(testNode->getNext()->getPoly()); |
---|
638 | testNode = testNode->getNext(); |
---|
639 | } |
---|
640 | /* |
---|
641 | ideal testId = idInit(idx-1,1); |
---|
642 | for(i=0;i<idx-1;i++) { |
---|
643 | testId->m[i] = pHead(testNode->getPoly()); |
---|
644 | testNode = testNode->getNext(); |
---|
645 | } |
---|
646 | poly temp = kNF(testId,currQuotient,u1); |
---|
647 | //pWrite(temp); |
---|
648 | for(i=0;i<IDELEMS(testId);i++) { |
---|
649 | testId->m[i] = NULL; |
---|
650 | } |
---|
651 | idDelete(&testId); |
---|
652 | if(NULL == temp) { |
---|
653 | //if(l->getIndex() != gPrev->getFirst()->getIndex()) { |
---|
654 | // Print("----------------------------Criterion1 not passed----------------------------------\n"); |
---|
655 | //} |
---|
656 | return true; |
---|
657 | } |
---|
658 | */ |
---|
659 | return false; |
---|
660 | } |
---|
661 | } |
---|
662 | |
---|
663 | |
---|
664 | |
---|
665 | /* |
---|
666 | ===================================== |
---|
667 | Criterion 2, i.e. Rewritten Criterion |
---|
668 | ===================================== |
---|
669 | */ |
---|
670 | inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) { |
---|
671 | //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n"); |
---|
672 | /* |
---|
673 | Print("RULES: \n"); |
---|
674 | RNode* tempR = rules->getFirst(); |
---|
675 | Print("%p\n",tempR); |
---|
676 | int i = 1; |
---|
677 | while(NULL != tempR) { |
---|
678 | Print("ADDRESS OF %d RNODE: %p\n",i,tempR); |
---|
679 | Print("ADDRESS OF RULE: %p\n",tempR->getRule()); |
---|
680 | pWrite(tempR->getRuleTerm()); |
---|
681 | Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm()); |
---|
682 | Print("%d\n\n",tempR->getRuleIndex()); |
---|
683 | tempR = tempR->getNext(); |
---|
684 | i++; |
---|
685 | } |
---|
686 | //Print("TESTED ELEMENT: "); |
---|
687 | //pWrite(l->getPoly()); |
---|
688 | //pWrite(l->getTerm()); |
---|
689 | //pWrite(ppMult_qq(t,l->getTerm())); |
---|
690 | //Print("%d\n\n",l->getIndex()); |
---|
691 | */ |
---|
692 | // start at the previously added element to gPrev, as all other elements will have the same index for sure |
---|
693 | if(idx > l->getIndex()) { |
---|
694 | return false; |
---|
695 | } |
---|
696 | |
---|
697 | RNode* testNode; // = new RNode(); |
---|
698 | testNode = rules->getFirst(); |
---|
699 | /* |
---|
700 | if(NULL == rTag->getFirst()) { |
---|
701 | if(NULL != rules->getFirst()) { |
---|
702 | testNode = rules->getFirst(); |
---|
703 | } |
---|
704 | else { |
---|
705 | return false; |
---|
706 | } |
---|
707 | } |
---|
708 | |
---|
709 | else { |
---|
710 | |
---|
711 | if(l->getIndex() > rTag->getFirst()->getRuleIndex()) { |
---|
712 | testNode = rules->getFirst(); |
---|
713 | } |
---|
714 | else { |
---|
715 | //Print("HIER\n"); |
---|
716 | //Print("DEBUG\n"); |
---|
717 | //Print("L INDEX: %d\n",l->getIndex()); |
---|
718 | *------------------------------------- |
---|
719 | * TODO: WHEN INTERREDUCING THE GB THE |
---|
720 | * INDEX OF THE PREVIOUS ELEMENTS |
---|
721 | * GETS HIGHER! |
---|
722 | *-----------------------------------* |
---|
723 | //testNode = rules->getFirst(); |
---|
724 | testNode = rTag->get(l->getIndex()); |
---|
725 | if(NULL == testNode) { |
---|
726 | testNode = rules->getFirst(); |
---|
727 | } |
---|
728 | //Print("TESTNODE ADDRESS: %p\n",testNode); |
---|
729 | } |
---|
730 | } |
---|
731 | */ |
---|
732 | //testNode = rules->getFirst(); |
---|
733 | // save the monom t1*label_term(l) as it is tested various times in the following |
---|
734 | poly u1 = ppMult_qq(t,l->getTerm()); |
---|
735 | // first element added to rTag was NULL, check for this |
---|
736 | //Print("%p\n",testNode->getRule()); |
---|
737 | // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1! |
---|
738 | //Print("TESTNODE: %p\n",testNode); |
---|
739 | //pWrite(testNode->getRuleTerm()); |
---|
740 | if(NULL != testNode ) { |
---|
741 | //pWrite(testNode->getRuleTerm()); |
---|
742 | } |
---|
743 | if(NULL != testNode) { |
---|
744 | if(testNode->getRuleOld() == l->getRuleOld()) { |
---|
745 | //Print("%p\n%p\n",testNode->getRule(),l->getRule()); |
---|
746 | //Print("EQUAL\n"); |
---|
747 | } |
---|
748 | else { |
---|
749 | //Print("NOT EQUAL\n"); |
---|
750 | } |
---|
751 | } |
---|
752 | while(NULL != testNode && testNode->getRuleOld() != l->getRuleOld() |
---|
753 | && l->getIndex() == testNode->getRuleOldIndex()) { |
---|
754 | //Print("%p\n",testNode); |
---|
755 | //pWrite(testNode->getRuleTerm()); |
---|
756 | //pWrite(t); |
---|
757 | //pWrite(l->getTerm()); |
---|
758 | //pWrite(u1); |
---|
759 | //Print("%d\n",testNode->getRuleIndex()); |
---|
760 | if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) { |
---|
761 | //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n"); |
---|
762 | //Print("INDEX: %d\n",l->getIndex()); |
---|
763 | pDelete(&u1); |
---|
764 | //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n"); |
---|
765 | return true; |
---|
766 | } |
---|
767 | testNode = testNode->getNext(); |
---|
768 | } |
---|
769 | //delete testNode; |
---|
770 | pDelete(&u1); |
---|
771 | //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n"); |
---|
772 | return false; |
---|
773 | } |
---|
774 | |
---|
775 | |
---|
776 | |
---|
777 | /* |
---|
778 | ================================================================================================================= |
---|
779 | Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter |
---|
780 | ================================================================================================================= |
---|
781 | */ |
---|
782 | inline bool criterion2(poly t, LPolyOld* l, RList* rules, RuleOld* testedRuleOld) { |
---|
783 | //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n"); |
---|
784 | //Print("LAST RuleOld TESTED: %p",testedRuleOld); |
---|
785 | /* |
---|
786 | Print("RULES: \n"); |
---|
787 | RNode* tempR = rules->getFirst(); |
---|
788 | while(NULL != tempR) { |
---|
789 | pWrite(tempR->getRuleTerm()); |
---|
790 | Print("%d\n\n",tempR->getRuleIndex()); |
---|
791 | tempR = tempR->getNext(); |
---|
792 | } |
---|
793 | //Print("TESTED ELEMENT: "); |
---|
794 | //pWrite(l->getPoly()); |
---|
795 | //pWrite(l->getTerm()); |
---|
796 | //pWrite(ppMult_qq(t,l->getTerm())); |
---|
797 | //Print("%d\n\n",l->getIndex()); |
---|
798 | */ |
---|
799 | // start at the previously added element to gPrev, as all other elements will have the same index for sure |
---|
800 | RNode* testNode = rules->getFirst(); |
---|
801 | // save the monom t1*label_term(l) as it is tested various times in the following |
---|
802 | poly u1 = ppMult_qq(t,l->getTerm()); |
---|
803 | // first element added to rTag was NULL, check for this |
---|
804 | while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) { |
---|
805 | //pWrite(testNode->getRuleTerm()); |
---|
806 | if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) { |
---|
807 | //Print("--------------------------Criterion 2 NOT passed!------------------------------\n"); |
---|
808 | //Print("INDEX: %d\n",l->getIndex()); |
---|
809 | pDelete(&u1); |
---|
810 | //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n"); |
---|
811 | return true; |
---|
812 | } |
---|
813 | testNode = testNode->getNext(); |
---|
814 | } |
---|
815 | pDelete(&u1); |
---|
816 | //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n"); |
---|
817 | return false; |
---|
818 | } |
---|
819 | |
---|
820 | /* |
---|
821 | * check for useful pairs in the given subset of critical pairs |
---|
822 | */ |
---|
823 | int computeUsefulMinDeg(CNode* first) { |
---|
824 | CNode* temp = first; |
---|
825 | int numberUsefulPairsMinDeg = 0; |
---|
826 | while(NULL != temp) { |
---|
827 | if(!temp->getDel()) { |
---|
828 | numberUsefulPairsMinDeg++; |
---|
829 | } |
---|
830 | temp = temp->getNext(); |
---|
831 | } |
---|
832 | return numberUsefulPairsMinDeg; |
---|
833 | } |
---|
834 | /* |
---|
835 | ================================== |
---|
836 | Computation of S-Polynomials in F5 |
---|
837 | ================================== |
---|
838 | */ |
---|
839 | void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, PList* rejectedGBList) { |
---|
840 | CNode* temp = first; |
---|
841 | //Print("\nDegree: %d\n",temp->getData()->getDeg()); |
---|
842 | // only GB-critical pairs are computed |
---|
843 | //while(NULL != temp && temp->getDel()) { |
---|
844 | // temp = temp->getNext(); |
---|
845 | //} |
---|
846 | //if(temp->getData()->getDeg() == 11) { |
---|
847 | // Print("PAIRS OF DEG 11:\n"); |
---|
848 | //} |
---|
849 | RList* f5rules = new RList(); |
---|
850 | CListOld* f5pairs = new CListOld(); |
---|
851 | poly sp = pInit(); |
---|
852 | number sign = nInit(-1); |
---|
853 | //Print("###############################IN SPOLS##############################\n"); |
---|
854 | //first->print(); |
---|
855 | /* |
---|
856 | * first of all: do everything for GB critical pairs |
---|
857 | */ |
---|
858 | while(NULL != temp) { |
---|
859 | // if(temp->getData()->getDeg() == 11) { |
---|
860 | //Print("--------------------------\n"); |
---|
861 | //Print("redundant? %d\n",temp->getDel()); |
---|
862 | //pWrite(pHead(temp->getLp1Poly())); |
---|
863 | //Print("redundant: %d\n",temp->getAdLp1()->getDel()); |
---|
864 | //pWrite(pHead(temp->getLp2Poly())); |
---|
865 | //Print("redundant: %d\n",temp->getAdLp2()->getDel()); |
---|
866 | //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); |
---|
867 | // sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
868 | // ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
869 | //Print("BEGIN SPOLY2\n====================\n"); |
---|
870 | // pNorm(sp); |
---|
871 | // pWrite(pHead(sp)); |
---|
872 | //Print("--------------------------\n"); |
---|
873 | //} |
---|
874 | if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { |
---|
875 | //if(temp->getDel() == 0 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { |
---|
876 | if(temp->getLp2Index() == temp->getLp1Index()) { |
---|
877 | if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) { |
---|
878 | sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
879 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
880 | pNorm(sp); |
---|
881 | if(NULL == sp) { |
---|
882 | reductionsToZero++; |
---|
883 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
884 | numberOfRules++; |
---|
885 | pDelete(&sp); |
---|
886 | } |
---|
887 | else { |
---|
888 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
889 | numberOfRules++; |
---|
890 | sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); |
---|
891 | //Print("INSERTED\n"); |
---|
892 | numberOfSpolys++; |
---|
893 | } |
---|
894 | } |
---|
895 | else { |
---|
896 | if(highestDegreeGBCriticalPair < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { |
---|
897 | highestDegreeGBCriticalPair = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly())); |
---|
898 | } |
---|
899 | rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); |
---|
900 | //Print("rejected!\n"); |
---|
901 | |
---|
902 | //Print("CRITERION 2 in SPOLS 2nd generator\n"); |
---|
903 | } |
---|
904 | } |
---|
905 | else { |
---|
906 | sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
907 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
908 | //Print("BEGIN SPOLY2\n====================\n"); |
---|
909 | pNorm(sp); |
---|
910 | //pWrite(sp); |
---|
911 | //Print("END SPOLY2\n====================\n"); |
---|
912 | if(NULL == sp) { |
---|
913 | reductionsToZero++; |
---|
914 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
915 | numberOfRules++; |
---|
916 | pDelete(&sp); |
---|
917 | } |
---|
918 | else { |
---|
919 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
920 | numberOfRules++; |
---|
921 | sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); |
---|
922 | //Print("INSERTED\n"); |
---|
923 | numberOfSpolys++; |
---|
924 | } |
---|
925 | } |
---|
926 | } |
---|
927 | /* |
---|
928 | if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { |
---|
929 | //Print("rejected!\n"); |
---|
930 | rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); |
---|
931 | } |
---|
932 | |
---|
933 | |
---|
934 | if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { |
---|
935 | if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { |
---|
936 | highestDegree = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly())); |
---|
937 | } |
---|
938 | if(temp->getLp2Index() == temp->getLp1Index()) { |
---|
939 | if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) { |
---|
940 | sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
941 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
942 | pNorm(sp); |
---|
943 | if(NULL == sp) { |
---|
944 | reductionsToZero++; |
---|
945 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
946 | numberOfRules++; |
---|
947 | pDelete(&sp); |
---|
948 | } |
---|
949 | else { |
---|
950 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
951 | numberOfRules++; |
---|
952 | |
---|
953 | |
---|
954 | // save the address of the rule again in a different |
---|
955 | // list |
---|
956 | |
---|
957 | f5rules->insert(rules->getFirst()->getRuleOld()); |
---|
958 | f5pairs->insertWithoutSort(temp->getData()); |
---|
959 | /////////////////////////////////////// |
---|
960 | |
---|
961 | //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); |
---|
962 | } |
---|
963 | } |
---|
964 | } |
---|
965 | else { |
---|
966 | sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
967 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
968 | //Print("BEGIN SPOLY2\n====================\n"); |
---|
969 | pNorm(sp); |
---|
970 | //pWrite(sp); |
---|
971 | //Print("END SPOLY2\n====================\n"); |
---|
972 | if(NULL == sp) { |
---|
973 | reductionsToZero++; |
---|
974 | //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
975 | numberOfRules++; |
---|
976 | pDelete(&sp); |
---|
977 | } |
---|
978 | else { |
---|
979 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
980 | numberOfRules++; |
---|
981 | // save the address of the rule again in a different |
---|
982 | // list |
---|
983 | |
---|
984 | f5rules->insert(rules->getFirst()->getRuleOld()); |
---|
985 | f5pairs->insertWithoutSort(temp->getData()); |
---|
986 | /////////////////////////////////////// |
---|
987 | //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); |
---|
988 | // numberOfSpolys++; |
---|
989 | } |
---|
990 | } |
---|
991 | } |
---|
992 | // the following else is not needed at all as we are checking |
---|
993 | // F5-critical pairs in this step |
---|
994 | /* |
---|
995 | else { |
---|
996 | if(!temp->getDel()) { |
---|
997 | rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); |
---|
998 | } |
---|
999 | |
---|
1000 | } |
---|
1001 | */ |
---|
1002 | |
---|
1003 | temp = temp->getNext(); |
---|
1004 | |
---|
1005 | } |
---|
1006 | |
---|
1007 | /* |
---|
1008 | temp = f5pairs->getFirst(); |
---|
1009 | RNode* tempRule = f5rules->getFirst(); |
---|
1010 | int howmany = 1; |
---|
1011 | while(NULL != temp) { |
---|
1012 | //Print("RULE: "); |
---|
1013 | //pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
1014 | sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
1015 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
1016 | pNorm(sp); |
---|
1017 | if(rejectedGBList->check(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())))) { //|| (temp->getData()->getDeg() == 10 && howmany == 2)) { |
---|
1018 | if((temp->getData()->getDeg() == 10) && (howmany == 2)) { |
---|
1019 | //Print("HIER DRIN IM SAFTLADEN\n"); |
---|
1020 | } |
---|
1021 | sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld()); |
---|
1022 | numberOfSpolys++; |
---|
1023 | howmany++; |
---|
1024 | } |
---|
1025 | else { |
---|
1026 | numberRejectedF5CriticalPairs++; |
---|
1027 | howmany++; |
---|
1028 | if(numberRejectedF5CriticalPairs < -1) { // || |
---|
1029 | } |
---|
1030 | else { |
---|
1031 | //numberRejectedF5CriticalPairs == 7) { |
---|
1032 | /* |
---|
1033 | Print("--------------------------------- rejected F5-critical pair-------------------------------------\n"); |
---|
1034 | pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); |
---|
1035 | Print("Label: "); |
---|
1036 | pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
1037 | Print("%d\n",temp->getDel()); |
---|
1038 | Print("Comes from:\n "); |
---|
1039 | pWrite(pHead(temp->getLp1Poly())); |
---|
1040 | Print("Label: "); |
---|
1041 | pWrite(temp->getLp1Term()); |
---|
1042 | Print("%d\n",temp->getLp1Index()); |
---|
1043 | pWrite(pHead(temp->getLp2Poly())); |
---|
1044 | Print("Label: "); |
---|
1045 | pWrite(temp->getLp2Term()); |
---|
1046 | Print("%d\n",temp->getLp2Index()); |
---|
1047 | //Print("--------------------------------------LIST OF GB PAIRS REJECTED-----------------------------------------\n"); |
---|
1048 | //rejectedGBList->print(); |
---|
1049 | Print("--------------------------------------------------------------------------------------------------------\n"); |
---|
1050 | //if(temp->getLp1Index() < 7) { |
---|
1051 | sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld()); |
---|
1052 | |
---|
1053 | //} |
---|
1054 | //numberOfSpolys++; |
---|
1055 | } |
---|
1056 | //pSetExp(tempRule->getRuleOld()->getTerm(),1,1000); |
---|
1057 | } |
---|
1058 | temp = temp->getNext(); |
---|
1059 | tempRule = tempRule->getNext(); |
---|
1060 | |
---|
1061 | } |
---|
1062 | */ |
---|
1063 | // these critical pairs can be deleted now as they are either useless for further computations or |
---|
1064 | // already saved as an S-polynomial to be reduced in the following |
---|
1065 | delete first; |
---|
1066 | //Print("NUMBER SPOLYS: %d\n", numberOfSpolys); |
---|
1067 | //Print("SPOLY LIST: \n"); |
---|
1068 | //LNode* tempSpoly = sPolyList->getFirst(); |
---|
1069 | //if(NULL != tempSpoly) { |
---|
1070 | // pWrite(pHead(tempSpoly->getPoly())); |
---|
1071 | // tempSpoly = tempSpoly->getNext(); |
---|
1072 | //} |
---|
1073 | //Print("-----SP------\n"); |
---|
1074 | //else { |
---|
1075 | // Print("EMPTY SPOLYLIST!\n"); |
---|
1076 | //} |
---|
1077 | } |
---|
1078 | |
---|
1079 | /* |
---|
1080 | ======================================================================== |
---|
1081 | reduction including subalgorithm topReduction() using Faugere's criteria |
---|
1082 | ======================================================================== |
---|
1083 | */ |
---|
1084 | void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, |
---|
1085 | ideal gbPrev, PList* rejectedGBList, int plus) { |
---|
1086 | //Print("##########################################In REDUCTION!########################################\n"); |
---|
1087 | // check if sPolyList has any elements |
---|
1088 | // NOTE: due to initialization sPolyList always has a default NULL element |
---|
1089 | LNode* temp = sPolyList->getFirst(); |
---|
1090 | while(NULL != temp) { |
---|
1091 | // temp is the first element in the sPolyList which should be reduced |
---|
1092 | // due to earlier sorting this is the element of minimal degree AND |
---|
1093 | // minimal label |
---|
1094 | // delete the above first element from sPolyList, temp will be either reduced to |
---|
1095 | // zero or added to gPrev, but never come back to sPolyList |
---|
1096 | //pWrite(sPolyList->getFirst()->getPoly()); |
---|
1097 | //Print("LIST OF SPOLYNOMIALS!\n"); |
---|
1098 | //sPolyList->print(); |
---|
1099 | sPolyList->setFirst(temp->getNext()); |
---|
1100 | poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly()); |
---|
1101 | if(NULL != tempNF) { |
---|
1102 | pNorm(tempNF); |
---|
1103 | temp->setPoly(tempNF); |
---|
1104 | // try further reductions of temp with polynomials in gPrev |
---|
1105 | // with label index = current label index: this is done such that there |
---|
1106 | // is no label corruption during the reduction process |
---|
1107 | //Print("lower label reduction: "); |
---|
1108 | //pWrite(tempNF); |
---|
1109 | topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus); |
---|
1110 | |
---|
1111 | } |
---|
1112 | else { |
---|
1113 | reductionsToZero++; |
---|
1114 | delete temp; |
---|
1115 | } |
---|
1116 | //if(NULL != temp->getPoly()) { |
---|
1117 | // criticalPair(gPrev,critPairs,lTag,rTag,rules); |
---|
1118 | //} |
---|
1119 | temp = sPolyList->getFirst(); |
---|
1120 | } |
---|
1121 | //sPolyList->print(); |
---|
1122 | //delete sPolyList; |
---|
1123 | } |
---|
1124 | |
---|
1125 | /* |
---|
1126 | ======================================================================== |
---|
1127 | reduction including subalgorithm topReduction() using Faugere's criteria |
---|
1128 | ======================================================================== |
---|
1129 | */ |
---|
1130 | void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, |
---|
1131 | ideal gbPrev, int termination, PList* rejectedGBList, int plus) { |
---|
1132 | //Print("##########################################In REDUCTION!########################################\n"); |
---|
1133 | // check if sPolyList has any elements |
---|
1134 | // NOTE: due to initialization sPolyList always has a default NULL element |
---|
1135 | //Print("--1--\n"); |
---|
1136 | LNode* temp = sPolyList->getFirst(); |
---|
1137 | //Print("START OF REDUCTION: "); |
---|
1138 | while(NULL != temp) { |
---|
1139 | numberOfReductions++; |
---|
1140 | // temp is the first element in the sPolyList which should be reduced |
---|
1141 | // due to earlier sorting this is the element of minimal degree AND |
---|
1142 | // minimal label |
---|
1143 | // delete the above first element from sPolyList, temp will be either reduced to |
---|
1144 | // zero or added to gPrev, but never come back to sPolyList |
---|
1145 | //Print("LIST OF SPOLYNOMIALS!\n"); |
---|
1146 | //sPolyList->print(); |
---|
1147 | //pWrite(sPolyList->getFirst()->getPoly()); |
---|
1148 | sPolyList->setFirst(temp->getNext()); |
---|
1149 | //if(pDeg(temp->getPoly()) > 11) { |
---|
1150 | // Print("YES!!!!!!!!!!!!!!!!\n"); |
---|
1151 | //} |
---|
1152 | //pWrite(temp->getPoly()); |
---|
1153 | //poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly()); |
---|
1154 | //Print("!!!\n"); |
---|
1155 | //if(NULL != tempNF) { |
---|
1156 | //pNorm(tempNF); |
---|
1157 | //temp->setPoly(tempNF); |
---|
1158 | //Print("lower label reduction: "); |
---|
1159 | //pWrite(tempNF); |
---|
1160 | // try further reductions of temp with polynomials in gPrev |
---|
1161 | // with label index = current label index: this is done such that there |
---|
1162 | // is no label corruption during the reduction process |
---|
1163 | findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus); |
---|
1164 | //} |
---|
1165 | //else { |
---|
1166 | // reductionsToZero++; |
---|
1167 | // delete temp; |
---|
1168 | //} |
---|
1169 | //if(NULL != temp->getPoly()) { |
---|
1170 | // criticalPair(gPrev,critPairs,lTag,rTag,rules); |
---|
1171 | //} |
---|
1172 | //Print("HIER AUCH ?\n"); |
---|
1173 | //Print("--2--\n"); |
---|
1174 | //sPolyList->print(); |
---|
1175 | //critPairs->print(); |
---|
1176 | temp = sPolyList->getFirst(); |
---|
1177 | //Print("%p\n",temp); |
---|
1178 | } |
---|
1179 | //sPolyList->print(); |
---|
1180 | //delete sPolyList; |
---|
1181 | //Print("REDUCTION FERTIG\n"); |
---|
1182 | } |
---|
1183 | |
---|
1184 | |
---|
1185 | /*! |
---|
1186 | * ================================================================================ |
---|
1187 | * searches for reducers of temp similar to the symbolic preprocessing of F4 and |
---|
1188 | * divides them into a "good" and "bad" part: |
---|
1189 | * |
---|
1190 | * the "good" ones are the reducers which do not corrupt the label of temp, with |
---|
1191 | * these the normal form of temp is computed |
---|
1192 | * |
---|
1193 | * the "bad" ones are the reducers which corrupt the label of temp, they are tested |
---|
1194 | * later on for possible new rules and S-polynomials to be added to the algorithm |
---|
1195 | * ================================================================================ |
---|
1196 | */ |
---|
1197 | void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus) { |
---|
1198 | int canonicalize = 0; |
---|
1199 | //int timerRed = 0; |
---|
1200 | bool addToG = 1; |
---|
1201 | number sign = nInit(-1); |
---|
1202 | LList* good = new LList(); |
---|
1203 | LList* bad = new LList(); |
---|
1204 | LList* monomials = new LList(l->getLPolyOld()); |
---|
1205 | poly u = pOne(); |
---|
1206 | number nOne = nInit(1); |
---|
1207 | LNode* tempRed = lTag->getFirstCurrentIdx(); |
---|
1208 | LNode* tempMon = monomials->getFirst(); |
---|
1209 | poly tempPoly = pInit(); |
---|
1210 | poly redPoly = NULL; |
---|
1211 | int idx = l->getIndex(); |
---|
1212 | //Print("IN FIND REDUCERS: "); |
---|
1213 | //pWrite(l->getPoly()); |
---|
1214 | tempPoly = pCopy(l->getPoly()); |
---|
1215 | //tempMon->setPoly(tempPoly); |
---|
1216 | //while(NULL != tempMon) { |
---|
1217 | // iteration over all monomials in tempMon |
---|
1218 | kBucket* bucket = kBucketCreate(currRing); |
---|
1219 | kBucketInit(bucket,tempPoly,0); |
---|
1220 | tempPoly = kBucketGetLm(bucket); |
---|
1221 | //Print("\n\n\nTO BE REDUCED: "); |
---|
1222 | //pWrite(l->getPoly()); |
---|
1223 | //pWrite(l->getTerm()); |
---|
1224 | //pWrite(tempPoly); |
---|
1225 | while(NULL != tempPoly) { |
---|
1226 | // iteration of all elements in gPrev of the current index |
---|
1227 | tempRed = gPrev->getFirst(); |
---|
1228 | while(NULL != tempRed) { |
---|
1229 | //Print("TEMPREDPOLY: "); |
---|
1230 | //pWrite(tempRed->getPoly()); |
---|
1231 | if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) { |
---|
1232 | u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly())); |
---|
1233 | //Print("U: "); |
---|
1234 | //pWrite(u); |
---|
1235 | if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done! |
---|
1236 | if(tempRed->getIndex() != idx) { |
---|
1237 | // passing criterion1 ? |
---|
1238 | if(!criterion1(gPrev,u,tempRed,lTag)) { |
---|
1239 | poly tempRedPoly = tempRed->getPoly(); |
---|
1240 | //Print("REDUCER: "); |
---|
1241 | //pWrite(tempRedPoly); |
---|
1242 | pIter(tempRedPoly); |
---|
1243 | int lTempRedPoly = pLength(tempRedPoly); |
---|
1244 | kBucketExtractLm(bucket); |
---|
1245 | kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); |
---|
1246 | canonicalize++; |
---|
1247 | //Print("Reduction\n"); |
---|
1248 | if(!(canonicalize % 50)) { |
---|
1249 | kBucketCanonicalize(bucket); |
---|
1250 | } |
---|
1251 | tempPoly = kBucketGetLm(bucket); |
---|
1252 | //Print("TEMPPOLY: "); |
---|
1253 | //pWrite(tempPoly); |
---|
1254 | if(NULL != tempPoly) { |
---|
1255 | tempRed = gPrev->getFirst(); |
---|
1256 | continue; |
---|
1257 | } |
---|
1258 | else { |
---|
1259 | break; |
---|
1260 | } |
---|
1261 | } |
---|
1262 | |
---|
1263 | } |
---|
1264 | else { |
---|
1265 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) { |
---|
1266 | //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n"); |
---|
1267 | //pWrite(u); |
---|
1268 | //pWrite(tempRed->getTerm()); |
---|
1269 | //pWrite(pHead(tempRed->getPoly())); |
---|
1270 | addToG = 0; |
---|
1271 | } |
---|
1272 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) { |
---|
1273 | // passing criterion2 ? |
---|
1274 | if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) { |
---|
1275 | // passing criterion1 ? |
---|
1276 | if(!criterion1(gPrev,u,tempRed,lTag)) { |
---|
1277 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { |
---|
1278 | if(NULL == redPoly) { |
---|
1279 | bad->insert(tempRed->getLPolyOld()); |
---|
1280 | addToG = 1; |
---|
1281 | //poly tempRedPoly = tempRed->getPoly(); |
---|
1282 | //break; |
---|
1283 | } |
---|
1284 | } |
---|
1285 | else { |
---|
1286 | poly tempRedPoly = tempRed->getPoly(); |
---|
1287 | //Print("REDUCER: "); |
---|
1288 | //pWrite(tempRedPoly); |
---|
1289 | pIter(tempRedPoly); |
---|
1290 | int lTempRedPoly = pLength(tempRedPoly); |
---|
1291 | //Print("HEAD MONOMIAL KBUCKET: "); |
---|
1292 | //pWrite(kBucketGetLm(bucket)); |
---|
1293 | kBucketExtractLm(bucket); |
---|
1294 | kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); |
---|
1295 | canonicalize++; |
---|
1296 | //Print("REDUCTION\n"); |
---|
1297 | addToG = 1; |
---|
1298 | if(!(canonicalize % 50)) { |
---|
1299 | kBucketCanonicalize(bucket); |
---|
1300 | } |
---|
1301 | //Print("HEAD MONOMIAL KBUCKET: "); |
---|
1302 | //pWrite(kBucketGetLm(bucket)); |
---|
1303 | tempPoly = kBucketGetLm(bucket); |
---|
1304 | //Print("TEMPPOLY: "); |
---|
1305 | //pWrite(tempPoly); |
---|
1306 | if(NULL != tempPoly) { |
---|
1307 | tempRed = gPrev->getFirst(); |
---|
1308 | continue; |
---|
1309 | } |
---|
1310 | else { |
---|
1311 | break; |
---|
1312 | } |
---|
1313 | } |
---|
1314 | } |
---|
1315 | } |
---|
1316 | else { |
---|
1317 | //Print("CRIT 1 "); |
---|
1318 | |
---|
1319 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) { |
---|
1320 | //Print("NOT ALLOWED REDUCER, CRIT 1:\n"); |
---|
1321 | //pWrite(u); |
---|
1322 | //pWrite(tempRed->getTerm()); |
---|
1323 | //pWrite(tempRed->getPoly()); |
---|
1324 | if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { |
---|
1325 | //Print("REDUCER LABEL: "); |
---|
1326 | //pWrite(tempRed->getTerm()); |
---|
1327 | addToG = 0; |
---|
1328 | } |
---|
1329 | } |
---|
1330 | } |
---|
1331 | } |
---|
1332 | else { |
---|
1333 | //Print("CRIT 2 "); |
---|
1334 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { |
---|
1335 | //Print("NOT ALLOWED REDUCER, CRIT 2:\n"); |
---|
1336 | //pWrite(u); |
---|
1337 | //pWrite(tempRed->getTerm()); |
---|
1338 | //pWrite(tempRed->getPoly()); |
---|
1339 | if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { |
---|
1340 | //Print("REDUCER LABEL: "); |
---|
1341 | //pWrite(tempRed->getTerm()); |
---|
1342 | addToG = 0; |
---|
1343 | } |
---|
1344 | } |
---|
1345 | } |
---|
1346 | } |
---|
1347 | } |
---|
1348 | else { // u = 1 => reduce without checking criteria |
---|
1349 | poly tempRedPoly = tempRed->getPoly(); |
---|
1350 | //Print("REDUCER: "); |
---|
1351 | //pWrite(tempRedPoly); |
---|
1352 | pIter(tempRedPoly); |
---|
1353 | int lTempRedPoly = pLength(tempRedPoly); |
---|
1354 | kBucketExtractLm(bucket); |
---|
1355 | kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); |
---|
1356 | canonicalize++; |
---|
1357 | //Print("Reduction\n"); |
---|
1358 | if(!(canonicalize % 50)) { |
---|
1359 | kBucketCanonicalize(bucket); |
---|
1360 | } |
---|
1361 | tempPoly = kBucketGetLm(bucket); |
---|
1362 | //Print("TEMPPOLY: "); |
---|
1363 | //pWrite(tempPoly); |
---|
1364 | if(NULL != tempPoly) { |
---|
1365 | tempRed = gPrev->getFirst(); |
---|
1366 | continue; |
---|
1367 | } |
---|
1368 | else { |
---|
1369 | break; |
---|
1370 | } |
---|
1371 | |
---|
1372 | } |
---|
1373 | } |
---|
1374 | tempRed = tempRed->getNext(); |
---|
1375 | } |
---|
1376 | // reduction process with elements in LList* reducers |
---|
1377 | if(NULL != tempPoly) { |
---|
1378 | //Print("HERE\n"); |
---|
1379 | tempRed = reducers->getFirst(); |
---|
1380 | while(NULL != tempRed) { |
---|
1381 | //Print("TEMPREDPOLY: "); |
---|
1382 | //pWrite(tempRed->getPoly()); |
---|
1383 | //pWrite(tempPoly); |
---|
1384 | if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) { |
---|
1385 | //Print("A\n"); |
---|
1386 | u = pDivideM(pHead(tempPoly),pHead(tempRed->getPoly())); |
---|
1387 | //Print("U: "); |
---|
1388 | //pWrite(u); |
---|
1389 | if(tempRed->getIndex() != idx) { |
---|
1390 | // passing criterion1 ? |
---|
1391 | if(!criterion1(gPrev,u,tempRed,lTag)) { |
---|
1392 | poly tempRedPoly = tempRed->getPoly(); |
---|
1393 | //Print("REDUCER: "); |
---|
1394 | //pWrite(ppMult_qq(u,tempRedPoly)); |
---|
1395 | pIter(tempRedPoly); |
---|
1396 | int lTempRedPoly = pLength(tempRedPoly); |
---|
1397 | kBucketExtractLm(bucket); |
---|
1398 | kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); |
---|
1399 | canonicalize++; |
---|
1400 | //Print("Reduction\n"); |
---|
1401 | if(!(canonicalize % 50)) { |
---|
1402 | kBucketCanonicalize(bucket); |
---|
1403 | } |
---|
1404 | tempPoly = kBucketGetLm(bucket); |
---|
1405 | //Print("TEMPPOLY: "); |
---|
1406 | //pWrite(tempPoly); |
---|
1407 | if(NULL != tempPoly) { |
---|
1408 | tempRed = gPrev->getFirst(); |
---|
1409 | continue; |
---|
1410 | } |
---|
1411 | else { |
---|
1412 | break; |
---|
1413 | } |
---|
1414 | } |
---|
1415 | |
---|
1416 | } |
---|
1417 | else { |
---|
1418 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) { |
---|
1419 | //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n"); |
---|
1420 | //pWrite(u); |
---|
1421 | //pWrite(tempRed->getTerm()); |
---|
1422 | //pWrite(pHead(tempRed->getPoly())); |
---|
1423 | //addToG = 0; |
---|
1424 | } |
---|
1425 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) { |
---|
1426 | // passing criterion2 ? |
---|
1427 | if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) { |
---|
1428 | // passing criterion1 ? |
---|
1429 | if(!criterion1(gPrev,u,tempRed,lTag)) { |
---|
1430 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { |
---|
1431 | if(NULL == redPoly) { |
---|
1432 | bad->insert(tempRed->getLPolyOld()); |
---|
1433 | addToG = 1; |
---|
1434 | //poly tempRedPoly = tempRed->getPoly(); |
---|
1435 | //break; |
---|
1436 | } |
---|
1437 | } |
---|
1438 | else { |
---|
1439 | poly tempRedPoly = tempRed->getPoly(); |
---|
1440 | //Print("REDUCER: "); |
---|
1441 | //pWrite(ppMult_qq(u,tempRedPoly)); |
---|
1442 | pIter(tempRedPoly); |
---|
1443 | int lTempRedPoly = pLength(tempRedPoly); |
---|
1444 | //Print("HEAD MONOMIAL KBUCKET: "); |
---|
1445 | //pWrite(kBucketGetLm(bucket)); |
---|
1446 | kBucketExtractLm(bucket); |
---|
1447 | kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); |
---|
1448 | canonicalize++; |
---|
1449 | //Print("REDUCTION\n"); |
---|
1450 | addToG = 1; |
---|
1451 | if(!(canonicalize % 50)) { |
---|
1452 | kBucketCanonicalize(bucket); |
---|
1453 | } |
---|
1454 | //Print("HEAD MONOMIAL KBUCKET: "); |
---|
1455 | //pWrite(kBucketGetLm(bucket)); |
---|
1456 | tempPoly = kBucketGetLm(bucket); |
---|
1457 | //Print("TEMPPOLY: "); |
---|
1458 | //pWrite(tempPoly); |
---|
1459 | if(NULL != tempPoly) { |
---|
1460 | tempRed = gPrev->getFirst(); |
---|
1461 | continue; |
---|
1462 | } |
---|
1463 | else { |
---|
1464 | break; |
---|
1465 | } |
---|
1466 | } |
---|
1467 | } |
---|
1468 | } |
---|
1469 | else { |
---|
1470 | //Print("CRIT 1 "); |
---|
1471 | |
---|
1472 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) { |
---|
1473 | //Print("NOT ALLOWED REDUCER, CRIT 1:\n"); |
---|
1474 | //pWrite(u); |
---|
1475 | //pWrite(tempRed->getTerm()); |
---|
1476 | //pWrite(tempRed->getPoly()); |
---|
1477 | if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { |
---|
1478 | //Print("REDUCER LABEL: "); |
---|
1479 | //pWrite(tempRed->getTerm()); |
---|
1480 | addToG = 0; |
---|
1481 | } |
---|
1482 | } |
---|
1483 | } |
---|
1484 | } |
---|
1485 | else { |
---|
1486 | //Print("CRIT 2 "); |
---|
1487 | if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { |
---|
1488 | //Print("NOT ALLOWED REDUCER, CRIT 2:\n"); |
---|
1489 | //pWrite(u); |
---|
1490 | //pWrite(tempRed->getTerm()); |
---|
1491 | //pWrite(tempRed->getPoly()); |
---|
1492 | if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { |
---|
1493 | //Print("REDUCER LABEL: "); |
---|
1494 | //pWrite(tempRed->getTerm()); |
---|
1495 | addToG = 0; |
---|
1496 | } |
---|
1497 | } |
---|
1498 | } |
---|
1499 | } |
---|
1500 | |
---|
1501 | } |
---|
1502 | tempRed = tempRed->getNext(); |
---|
1503 | } |
---|
1504 | } |
---|
1505 | if(NULL != tempPoly) { |
---|
1506 | if(NULL == redPoly) { |
---|
1507 | redPoly = kBucketExtractLm(bucket); |
---|
1508 | } |
---|
1509 | else { |
---|
1510 | redPoly = p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing); |
---|
1511 | } |
---|
1512 | // for top-reduction only |
---|
1513 | redPoly = p_Merge_q(redPoly,kBucketClear(bucket),currRing); |
---|
1514 | break; |
---|
1515 | // end for top-reduction only |
---|
1516 | tempPoly = kBucketGetLm(bucket); |
---|
1517 | |
---|
1518 | } |
---|
1519 | } |
---|
1520 | if(NULL == redPoly) { |
---|
1521 | reductionsToZero++; |
---|
1522 | //pDelete(&redPoly); |
---|
1523 | } |
---|
1524 | else { |
---|
1525 | Print("\nELEMENT ADDED TO GPREV: "); |
---|
1526 | pNorm(redPoly); |
---|
1527 | if(highestDegree < pDeg(redPoly)) { |
---|
1528 | highestDegree = pDeg(redPoly); |
---|
1529 | } |
---|
1530 | pWrite(pHead(redPoly)); |
---|
1531 | //pWrite(l->getTerm()); |
---|
1532 | //Print("%d\n",canonicalize); |
---|
1533 | l->setPoly(redPoly); |
---|
1534 | // give "l" the label if it is "useful" (addToG = 0) or "useless" |
---|
1535 | // (addToG = 1) |
---|
1536 | l->setDel(!addToG); |
---|
1537 | Print("redundant? %d\n\n",l->getDel()); |
---|
1538 | if(addToG == 0 && termination == 1) { |
---|
1539 | reducers->insert(l->getLPolyOld()); |
---|
1540 | } |
---|
1541 | else { |
---|
1542 | gPrev->insert(l->getLPolyOld()); |
---|
1543 | } |
---|
1544 | //Print("%d\n\n",termination); |
---|
1545 | if(termination == 1) { |
---|
1546 | if(addToG) { |
---|
1547 | //Print("----------------HERE?-----------------\n"); |
---|
1548 | criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus); |
---|
1549 | } |
---|
1550 | else { |
---|
1551 | notInG++; |
---|
1552 | //Print("\nNONONO"); |
---|
1553 | //pWrite(pHead(l->getPoly())); |
---|
1554 | //pWrite(l->getTerm()); |
---|
1555 | } |
---|
1556 | } |
---|
1557 | // case in which all new elements are added to gPrev! |
---|
1558 | // using boolean "addToG" to know if the element is "useful" (0) or |
---|
1559 | // "useless" (1) |
---|
1560 | else { |
---|
1561 | if(!l->getDel()) { |
---|
1562 | criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus); |
---|
1563 | } |
---|
1564 | else { |
---|
1565 | criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList); |
---|
1566 | } |
---|
1567 | } |
---|
1568 | } |
---|
1569 | |
---|
1570 | // if there are "bad" reducers than try to compute new S-polynomials and rules |
---|
1571 | |
---|
1572 | if(NULL != bad->getFirst()) { |
---|
1573 | //Print("BAD STUFF LIST:\n"); |
---|
1574 | //bad->print(); |
---|
1575 | LNode* tempBad = bad->getFirst(); |
---|
1576 | //pWrite(l->getPoly()); |
---|
1577 | while(NULL != tempBad) { |
---|
1578 | if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) { |
---|
1579 | //Print("BAD STUFF\n"); |
---|
1580 | //pWrite(l->getPoly()); |
---|
1581 | //pWrite(tempBad->getPoly()); |
---|
1582 | u = pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly())); |
---|
1583 | //Print("MULTIPLIER: "); |
---|
1584 | //pWrite(u); |
---|
1585 | pSetCoeff(u,nOne); |
---|
1586 | if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) { |
---|
1587 | // passing criterion2 ? |
---|
1588 | if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) { |
---|
1589 | // passing criterion1 ? |
---|
1590 | if(!criterion1(gPrev,u,tempBad,lTag)) { |
---|
1591 | //Print("HIERHIERHIERHIERHIERHIER\n"); |
---|
1592 | rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm())); |
---|
1593 | numberOfRules++; |
---|
1594 | //gPrev->print(); |
---|
1595 | //pWrite(l->getPoly()); |
---|
1596 | poly temp = ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly()); |
---|
1597 | //pWrite(l->getPoly()); |
---|
1598 | //Print("%p\n",temp); |
---|
1599 | //gPrev->print(); |
---|
1600 | if(NULL != temp) { |
---|
1601 | pNorm(temp); |
---|
1602 | LNode* tempBadNew = new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld()); |
---|
1603 | //pWrite(temp); |
---|
1604 | //pWrite(tempBadNew->getPoly()); |
---|
1605 | //pWrite(tempBadNew->getTerm()); |
---|
1606 | //pWrite(pHead(tempBadNew->getPoly())); |
---|
1607 | //Print("%p\n",tempBadNew->getPoly()); |
---|
1608 | //tempRed->getLPoly()->setRule(rules->getFirst()->getRule()); |
---|
1609 | tempBadNew->setDel(1); |
---|
1610 | |
---|
1611 | sPolyList->insertByLabel(tempBadNew); |
---|
1612 | //Print("BAD SPOLYLIST: \n"); |
---|
1613 | //sPolyList->print(); |
---|
1614 | } |
---|
1615 | } |
---|
1616 | } |
---|
1617 | } |
---|
1618 | } |
---|
1619 | //Print("HIER\n"); |
---|
1620 | tempBad = tempBad->getNext(); |
---|
1621 | //Print("%p\n",tempBad); |
---|
1622 | } |
---|
1623 | // Print("-------------------BAD STUFF LIST-----------------------------\n"); |
---|
1624 | } |
---|
1625 | //Print("HIER AUCH\n"); |
---|
1626 | //Print("SPOLYLIST IN BAD: \n"); |
---|
1627 | //sPolyList->print(); |
---|
1628 | //Print("END FIND REDUCERS\n"); |
---|
1629 | } |
---|
1630 | |
---|
1631 | /* |
---|
1632 | ======================================================================================= |
---|
1633 | merging 2 polynomials p & q without requiring that all monomials of p & q are different |
---|
1634 | if there are equal monomials in p & q only one of these monomials (always that of p!) |
---|
1635 | is taken into account |
---|
1636 | ======================================================================================= |
---|
1637 | |
---|
1638 | poly p_MergeEq_q(poly p, poly q, const ring r) { |
---|
1639 | assume(p != NULL && q != NULL); |
---|
1640 | p_Test(p, r); |
---|
1641 | p_Test(q, r); |
---|
1642 | #if PDEBUG > 0 |
---|
1643 | int l = pLength(p) + pLength(q); |
---|
1644 | #endif |
---|
1645 | |
---|
1646 | spolyrec rp; |
---|
1647 | poly a = &rp; |
---|
1648 | DECLARE_LENGTH(const unsigned long length = r->CmpL_Size); |
---|
1649 | DECLARE_ORDSGN(const long* ordsgn = r->ordsgn); |
---|
1650 | |
---|
1651 | Top: // compare p and q w.r.t. monomial ordering |
---|
1652 | p_MemCmp(p->exp, q->exp, length, ordsgn, goto Equal, goto Greater , goto Smaller); |
---|
1653 | |
---|
1654 | Equal: |
---|
1655 | a = pNext(a) = p; |
---|
1656 | pIter(p); |
---|
1657 | pIter(q); |
---|
1658 | if(NULL == p) { |
---|
1659 | if(NULL == q) { |
---|
1660 | goto Finish; |
---|
1661 | } |
---|
1662 | else { |
---|
1663 | pNext(a) = q; |
---|
1664 | goto Finish; |
---|
1665 | } |
---|
1666 | } |
---|
1667 | goto Top; |
---|
1668 | |
---|
1669 | Greater: |
---|
1670 | a = pNext(a) = p; |
---|
1671 | pIter(p); |
---|
1672 | if (p==NULL) { pNext(a) = q; goto Finish;} |
---|
1673 | goto Top; |
---|
1674 | |
---|
1675 | Smaller: |
---|
1676 | a = pNext(a) = q; |
---|
1677 | pIter(q); |
---|
1678 | if (q==NULL) { pNext(a) = p; goto Finish;} |
---|
1679 | goto Top; |
---|
1680 | |
---|
1681 | Finish: |
---|
1682 | |
---|
1683 | p_Test(pNext(&rp), r); |
---|
1684 | #if PDEBUG > 0 |
---|
1685 | pAssume1(l - pLength(pNext(&rp)) == 0); |
---|
1686 | #endif |
---|
1687 | return pNext(&rp); |
---|
1688 | } |
---|
1689 | */ |
---|
1690 | |
---|
1691 | /* |
---|
1692 | ===================================================================================== |
---|
1693 | top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of |
---|
1694 | the same index whereas the labels are taken into account |
---|
1695 | ===================================================================================== |
---|
1696 | */ |
---|
1697 | void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) { |
---|
1698 | //Print("##########################################In topREDUCTION!########################################\n"); |
---|
1699 | // try l as long as there are reductors found by findReductor() |
---|
1700 | LNode* gPrevRedCheck = lTag->getFirstCurrentIdx(); |
---|
1701 | LNode* tempRed; |
---|
1702 | poly pOne = pOne(); |
---|
1703 | do { |
---|
1704 | //int timer5 = initTimer(); |
---|
1705 | //startTimer(); |
---|
1706 | //Print("TOP REDUCTION: "); |
---|
1707 | //pWrite(l->getPoly()); |
---|
1708 | tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag); |
---|
1709 | //timer5 = getTimer(); |
---|
1710 | //reductionTime = reductionTime + timer5; |
---|
1711 | // if a reductor for l is found and saved in tempRed |
---|
1712 | if(NULL != tempRed) { |
---|
1713 | // if label of reductor is greater than the label of l we have to built a new element |
---|
1714 | // and add it to sPolyList |
---|
1715 | |
---|
1716 | if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) { |
---|
1717 | // needed sinc pSub destroys the arguments! |
---|
1718 | //poly temp_poly_l = pInit(); |
---|
1719 | //temp_poly_l = pCopy(l->getPoly()); |
---|
1720 | //Print("VORHER: "); |
---|
1721 | //pWrite(tempRed->getPoly()); |
---|
1722 | //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly()); |
---|
1723 | poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly()); |
---|
1724 | rules->insert(tempRed->getIndex(),tempRed->getTerm()); |
---|
1725 | //Print("NACHHER: "); |
---|
1726 | //pWrite(tempRed->getPoly()); |
---|
1727 | //Print("TEMP: "); |
---|
1728 | //pWrite(temp); |
---|
1729 | if(NULL != temp) { |
---|
1730 | pNorm(temp); |
---|
1731 | //tempRed->setPoly(temp); |
---|
1732 | //tempRed->setDel(1); |
---|
1733 | //rules->insert(tempRed->getIndex(),tempRed->getTerm()); |
---|
1734 | LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld()); |
---|
1735 | //tempRed->getLPoly()->setRule(rules->getFirst()->getRule()); |
---|
1736 | tempRedNew->setDel(1); |
---|
1737 | sPolyList->insertByLabel(tempRedNew); |
---|
1738 | } |
---|
1739 | else { |
---|
1740 | pDelete(&temp); |
---|
1741 | reductionsToZero++; |
---|
1742 | //delete tempRed; |
---|
1743 | } |
---|
1744 | } |
---|
1745 | |
---|
1746 | // label of reductor is smaller than the label of l, subtract reductor from l and delete the |
---|
1747 | // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes |
---|
1748 | // after subtraction |
---|
1749 | else { |
---|
1750 | |
---|
1751 | //poly temp_poly_l = pInit(); |
---|
1752 | //temp_poly_l = pCopy(l->getPoly()); |
---|
1753 | //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly()); |
---|
1754 | //Print("REDUCER: "); |
---|
1755 | //pWrite(tempRed->getPoly()); |
---|
1756 | //pWrite(tempRed->getTerm()); |
---|
1757 | poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly()); |
---|
1758 | //Print("REDUCED ELEMENT: "); |
---|
1759 | if(NULL != temp) { |
---|
1760 | pNorm(temp); |
---|
1761 | //pWrite(temp); |
---|
1762 | poly tempNF = kNF(gbPrev,currQuotient,temp); |
---|
1763 | pNorm(tempNF); |
---|
1764 | if(NULL == tempNF) { |
---|
1765 | reductionsToZero++; |
---|
1766 | pDelete(&tempNF); |
---|
1767 | l->setPoly(NULL); |
---|
1768 | break; |
---|
1769 | } |
---|
1770 | l->setPoly(tempNF); |
---|
1771 | |
---|
1772 | gPrevRedCheck = lTag->getFirstCurrentIdx(); |
---|
1773 | } |
---|
1774 | else { |
---|
1775 | reductionsToZero++; |
---|
1776 | pDelete(&temp); |
---|
1777 | l->setPoly(NULL); |
---|
1778 | break; |
---|
1779 | } |
---|
1780 | } |
---|
1781 | } |
---|
1782 | else { |
---|
1783 | if(NULL != l->getPoly()) { |
---|
1784 | pNorm(l->getPoly()); |
---|
1785 | //Print("ELEMENT ADDED TO GPREV: "); |
---|
1786 | //pWrite(l->getPoly()); |
---|
1787 | gPrev->insert(l->getLPolyOld()); |
---|
1788 | //Print("TEMP RED == 0 "); |
---|
1789 | //pWrite(l->getPoly()); |
---|
1790 | //pWrite(l->getTerm()); |
---|
1791 | //rules->print(); |
---|
1792 | criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus); |
---|
1793 | //Print("LIST OF CRITICAL PAIRS: \n"); |
---|
1794 | //critPairs->print(); |
---|
1795 | } |
---|
1796 | break; |
---|
1797 | } |
---|
1798 | } while(1); |
---|
1799 | } |
---|
1800 | |
---|
1801 | |
---|
1802 | /* |
---|
1803 | ===================================================================== |
---|
1804 | subalgorithm to find a possible reductor for the labeled polynomial l |
---|
1805 | ===================================================================== |
---|
1806 | */ |
---|
1807 | LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag, PList* rejectedGBList) { |
---|
1808 | // allociation of memory for the possible reductor |
---|
1809 | //Print("LPOLY: "); |
---|
1810 | //pWrite(l->getPoly()); |
---|
1811 | poly u = pOne(); |
---|
1812 | poly red; |
---|
1813 | number nOne = nInit(1); |
---|
1814 | LNode* temp; |
---|
1815 | // head term of actual element such that we do not have to call pHead at each new reductor test |
---|
1816 | poly t = pHead(l->getPoly()); |
---|
1817 | // if l was already checked use the information in gPrevRedCheck such |
---|
1818 | // that we can start searching for new reducers from this point and |
---|
1819 | // not from the first element of gPrev with the current index |
---|
1820 | temp = gPrevRedCheck; |
---|
1821 | // search for reductors until we are at the end of gPrev resp. at the |
---|
1822 | // end of the elements of the current index |
---|
1823 | while(NULL != temp && temp->getIndex() == l->getIndex()) { |
---|
1824 | // does the head of the element of gPrev divides the head of |
---|
1825 | // the to be reduced element? |
---|
1826 | if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) { |
---|
1827 | // get all the information needed for the following tests |
---|
1828 | // of the criteria |
---|
1829 | u = pDivide(t,pHead(temp->getPoly())); |
---|
1830 | pSetCoeff(u,nOne); |
---|
1831 | red = ppMult_qq(u,temp->getPoly()); |
---|
1832 | pNorm(red); |
---|
1833 | // check if both have the same label |
---|
1834 | if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) { |
---|
1835 | // passing criterion2 ? |
---|
1836 | if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) { |
---|
1837 | // passing criterion1 ? |
---|
1838 | if(!criterion1(gPrev,u,temp,lTag)) { |
---|
1839 | gPrevRedCheck = temp->getNext(); |
---|
1840 | LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL); |
---|
1841 | return redNode; |
---|
1842 | } |
---|
1843 | } |
---|
1844 | } |
---|
1845 | if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == 1) { |
---|
1846 | // passing criterion2 ? |
---|
1847 | if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) { |
---|
1848 | // passing criterion1 ? |
---|
1849 | if(!criterion1(gPrev,u,temp,lTag)) { |
---|
1850 | poly tempSpoly = ksOldSpolyRedNew(red,l->getPoly()); |
---|
1851 | rules->insert(temp->getIndex(),ppMult_qq(u,temp->getTerm())); |
---|
1852 | gPrevRedCheck = temp->getNext(); |
---|
1853 | if(NULL != tempSpoly) { |
---|
1854 | pNorm(tempSpoly); |
---|
1855 | sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld()); |
---|
1856 | //Print("NEW ONE: "); |
---|
1857 | //pWrite(tempSpoly); |
---|
1858 | //Print("HIER\n"); |
---|
1859 | //sPolyList->print(); |
---|
1860 | //sleep(5); |
---|
1861 | } |
---|
1862 | } |
---|
1863 | } |
---|
1864 | } |
---|
1865 | } |
---|
1866 | //Print("AUCH HIER\n"); |
---|
1867 | temp = temp->getNext(); |
---|
1868 | } |
---|
1869 | |
---|
1870 | // delete temp; |
---|
1871 | return NULL; |
---|
1872 | } |
---|
1873 | |
---|
1874 | |
---|
1875 | |
---|
1876 | /* |
---|
1877 | ========================================================================== |
---|
1878 | MAIN:computes a gb of the ideal i in the ring r with our F5 implementation |
---|
1879 | OPTIONS: INTEGER "opt" is to be set "0" for F5, "1" for F5R, "2" for F5C |
---|
1880 | ========================================================================== |
---|
1881 | */ |
---|
1882 | ideal F5main(ideal id, ring r, int opt, int plus, int termination) { |
---|
1883 | switch(opt) { |
---|
1884 | case 0: |
---|
1885 | Print("\nComputations are done by the standard F5 Algorithm"); |
---|
1886 | break; |
---|
1887 | case 1: |
---|
1888 | Print("\nComputations are done by the variant F5R of the F5 Algorithm"); |
---|
1889 | break; |
---|
1890 | case 2: |
---|
1891 | Print("\nComputations are done by the variant F5C of the F5 Algorithm"); |
---|
1892 | break; |
---|
1893 | default: |
---|
1894 | WerrorS("\nThe option can only be set to \"0\", \"1\" or \"2\":\n\"0\": standard F5 Algorithm\n\"1\": variant F5R\n\"2\": variant F5C\nComputations are aborted!\n"); |
---|
1895 | return id; |
---|
1896 | } |
---|
1897 | |
---|
1898 | int timer = initTimer(); |
---|
1899 | startTimer(); |
---|
1900 | int i,j,k,l; |
---|
1901 | int gbLength; |
---|
1902 | // 1 polynomial for defining initial labels & further tests |
---|
1903 | poly ONE = pOne(); |
---|
1904 | poly pOne = pOne(); |
---|
1905 | number nOne = nInit(1); |
---|
1906 | // tag the first element of index i-1 for criterion 1 |
---|
1907 | //Print("LTAG BEGINNING: %p\n",lTag); |
---|
1908 | |
---|
1909 | // DEBUGGING STUFF START |
---|
1910 | //Print("NUMBER: %d\n",r->N); |
---|
1911 | /* |
---|
1912 | int* ev = new int[r->N +1]; |
---|
1913 | for(i=0;i<IDELEMS(id);i++) { |
---|
1914 | pGetExpV(id->m[i],ev); |
---|
1915 | //ev2 = pGetExp(id->m[i],1); |
---|
1916 | pWrite(id->m[i]); |
---|
1917 | Print("EXP1: %d\n",ev[1]); |
---|
1918 | Print("EXP2: %d\n",ev[2]); |
---|
1919 | Print("EXP3: %d\n\n",ev[3]); |
---|
1920 | Print("SUM: %ld\n\n\n",sumVector(ev,r->N)); |
---|
1921 | } |
---|
1922 | delete ev; |
---|
1923 | */ |
---|
1924 | /*DEBUGGING STUFF END */ |
---|
1925 | |
---|
1926 | // first element in rTag is first element of rules which is NULL RNode, |
---|
1927 | // this must be done due to possible later improvements |
---|
1928 | RList* rules = new RList(); |
---|
1929 | //Print("RULES FIRST: %p\n",rules->getFirst()); |
---|
1930 | //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule()); |
---|
1931 | //RTagList* rTag = new RTagList(rules->getFirst()); |
---|
1932 | RTagList* rTag = NULL; |
---|
1933 | i = 1; |
---|
1934 | /*for(j=0; j<IDELEMS(id); j++) { |
---|
1935 | if(NULL != id->m[j]) { |
---|
1936 | if(pComparePolys(id->m[j],ONE)) { |
---|
1937 | Print("One Polynomial in Input => Computations stopped\n"); |
---|
1938 | ideal idNew = idInit(1,1); |
---|
1939 | idNew->m[0] = ONE; |
---|
1940 | return(idNew); |
---|
1941 | } |
---|
1942 | } |
---|
1943 | }*/ |
---|
1944 | ideal idNew = kInterRed(id); |
---|
1945 | id = idNew; |
---|
1946 | //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]); |
---|
1947 | //idShow(id); |
---|
1948 | LList* gPrev = new LList(ONE, i, id->m[0]); |
---|
1949 | LList* reducers = new LList(); |
---|
1950 | //idShow(id); |
---|
1951 | //Print("%p\n",id->m[0]); |
---|
1952 | //pWrite(id->m[0]); |
---|
1953 | //Print("%p\n",gPrev->getFirst()->getPoly()); |
---|
1954 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
1955 | |
---|
1956 | LTagList* lTag = new LTagList(gPrev->getFirst()); |
---|
1957 | //lTag->insert(gPrev->getFirst()); |
---|
1958 | lTag->setFirstCurrentIdx(gPrev->getFirst()); |
---|
1959 | // computing the groebner basis of the elements of index < actual index |
---|
1960 | gbLength = gPrev->getLength(); |
---|
1961 | //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength()); |
---|
1962 | ideal gbPrev = idInit(gbLength,1); |
---|
1963 | // initializing the groebner basis of elements of index < actual index |
---|
1964 | gbPrev->m[0] = gPrev->getFirst()->getPoly(); |
---|
1965 | //idShow(gbPrev); |
---|
1966 | //idShow(currQuotient); |
---|
1967 | for(i=2; i<=IDELEMS(id); i++) { |
---|
1968 | LNode* gPrevTag = gPrev->getLast(); |
---|
1969 | //Print("Last POlynomial in GPREV: "); |
---|
1970 | //Print("%p\n",gPrevTag); |
---|
1971 | //pWrite(gPrevTag->getPoly()); |
---|
1972 | Print("Iteration: %d\n\n",i); |
---|
1973 | gPrev = F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination); |
---|
1974 | //Print("%d\n",gPrev->count(gPrevTag->getNext())); |
---|
1975 | //Print("%d\n",gPrev->getLength()); |
---|
1976 | //Print("____________________________________ITERATION STEP DONE________________________________________\n"); |
---|
1977 | |
---|
1978 | // DEBUGGING STUFF |
---|
1979 | LNode* temp = gPrev->getFirst(); |
---|
1980 | |
---|
1981 | |
---|
1982 | ///////////////////////////////////////////////////////////////////////////////// |
---|
1983 | // // |
---|
1984 | // one needs to choose one of the following 3 implementations of the algorithm // |
---|
1985 | // F5,F5R or F5C // |
---|
1986 | // // |
---|
1987 | ///////////////////////////////////////////////////////////////////////////////// |
---|
1988 | |
---|
1989 | |
---|
1990 | // |
---|
1991 | // standard "F5" |
---|
1992 | // |
---|
1993 | if(0 == opt) { |
---|
1994 | if(gPrev->getLength() > gbLength) { |
---|
1995 | if(i < IDELEMS(id)) { |
---|
1996 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
1997 | LNode* temp = gPrevTag; |
---|
1998 | int counter = 0; |
---|
1999 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
2000 | temp = temp->getNext(); |
---|
2001 | if(0 == temp->getDel()) { |
---|
2002 | counter++; |
---|
2003 | gbAdd->m[j] = temp->getPoly(); |
---|
2004 | } |
---|
2005 | } |
---|
2006 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
2007 | } |
---|
2008 | else { |
---|
2009 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
2010 | LNode* temp = gPrevTag; |
---|
2011 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
2012 | temp = temp->getNext(); |
---|
2013 | gbAdd->m[j] = temp->getPoly(); |
---|
2014 | } |
---|
2015 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
2016 | } |
---|
2017 | //if(i == IDELEMS(id)) { |
---|
2018 | // ideal tempId = kInterRed(gbPrev); |
---|
2019 | // gbPrev = tempId; |
---|
2020 | //} |
---|
2021 | } |
---|
2022 | gbLength = gPrev->getLength(); |
---|
2023 | } |
---|
2024 | |
---|
2025 | |
---|
2026 | // |
---|
2027 | // "F5R" |
---|
2028 | // |
---|
2029 | if(1 == opt) { |
---|
2030 | if(gPrev->getLength() > gbLength) { |
---|
2031 | if(i < IDELEMS(id)) { |
---|
2032 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
2033 | LNode* temp = gPrevTag; |
---|
2034 | int counter = 0; |
---|
2035 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
2036 | temp = temp->getNext(); |
---|
2037 | if(0 == temp->getDel()) { |
---|
2038 | counter++; |
---|
2039 | gbAdd->m[j] = temp->getPoly(); |
---|
2040 | } |
---|
2041 | } |
---|
2042 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
2043 | } |
---|
2044 | else { |
---|
2045 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
2046 | LNode* temp = gPrevTag; |
---|
2047 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
2048 | temp = temp->getNext(); |
---|
2049 | gbAdd->m[j] = temp->getPoly(); |
---|
2050 | } |
---|
2051 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
2052 | } |
---|
2053 | // interreduction stuff |
---|
2054 | // comment this out if you want F5 instead of F5R |
---|
2055 | if(i<IDELEMS(id)) { |
---|
2056 | ideal tempId = kInterRed(gbPrev); |
---|
2057 | gbPrev = tempId; |
---|
2058 | } |
---|
2059 | } |
---|
2060 | gbLength = gPrev->getLength(); |
---|
2061 | } |
---|
2062 | |
---|
2063 | |
---|
2064 | // |
---|
2065 | // "F5C" |
---|
2066 | // |
---|
2067 | if(2 == opt) { |
---|
2068 | if(gPrev->getLength() > gbLength) { |
---|
2069 | if(i < IDELEMS(id)) { |
---|
2070 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
2071 | LNode* temp = gPrevTag; |
---|
2072 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
2073 | temp = temp->getNext(); |
---|
2074 | gbAdd->m[j] = temp->getPoly(); |
---|
2075 | } |
---|
2076 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
2077 | } |
---|
2078 | else { |
---|
2079 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
2080 | LNode* temp = gPrevTag; |
---|
2081 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
2082 | temp = temp->getNext(); |
---|
2083 | gbAdd->m[j] = temp->getPoly(); |
---|
2084 | } |
---|
2085 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
2086 | } |
---|
2087 | if(i<IDELEMS(id)) { |
---|
2088 | ideal tempId = kInterRed(gbPrev); |
---|
2089 | gbPrev = tempId; |
---|
2090 | delete gPrev; |
---|
2091 | delete rules; |
---|
2092 | gPrev = new LList(pOne,1,gbPrev->m[0]); |
---|
2093 | gPrev->insert(pOne,1,gbPrev->m[1]); |
---|
2094 | rules = new RList(); |
---|
2095 | //rTag = new RTagList(rules->getFirst()); |
---|
2096 | for(k=2; k<IDELEMS(gbPrev); k++) { |
---|
2097 | gPrev->insert(pOne,k+1,gbPrev->m[k]); |
---|
2098 | /* |
---|
2099 | for(l=0; l<k; l++) { |
---|
2100 | } |
---|
2101 | rTag->insert(rules->getFirst()); |
---|
2102 | */ |
---|
2103 | } |
---|
2104 | } |
---|
2105 | gbLength = gPrev->getLength(); |
---|
2106 | } |
---|
2107 | } |
---|
2108 | |
---|
2109 | |
---|
2110 | } |
---|
2111 | timer = getTimer(); |
---|
2112 | //Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime); |
---|
2113 | Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero); |
---|
2114 | Print("Number of rules: %d\n",numberOfRules); |
---|
2115 | Print("Number of rejected F5-critical pairs:%d\n",numberRejectedF5CriticalPairs); |
---|
2116 | Print("Number of reductions: %d\n",numberOfReductions); |
---|
2117 | Print("Elements not added to G: %d\n",notInG); |
---|
2118 | Print("Highest Degree during computations: %d\n",highestDegree); |
---|
2119 | Print("Degree d_0 in F5+: %d\n",highestDegreeGBCriticalPair); |
---|
2120 | Print("Time for computations: %d/1000 seconds\n",timer); |
---|
2121 | Print("Number of elements in gb: %d\n",IDELEMS(gbPrev)); |
---|
2122 | //LNode* temp = gPrev->getFirst(); |
---|
2123 | //while(NULL != temp) { |
---|
2124 | // pWrite(temp->getPoly()); |
---|
2125 | // temp = temp->getNext(); |
---|
2126 | // } |
---|
2127 | //gPrev->print(); |
---|
2128 | //delete lTag; |
---|
2129 | delete rTag; |
---|
2130 | delete gPrev; |
---|
2131 | notInG = 0; |
---|
2132 | numberOfRules = 0; |
---|
2133 | reductionsToZero = 0; |
---|
2134 | highestDegree = 0; |
---|
2135 | highestDegreeGBCriticalPair = 0; |
---|
2136 | reductionTime = 0; |
---|
2137 | spolsTime = 0; |
---|
2138 | numberUselessPairs = 0; |
---|
2139 | numberUsefulPairs = 0; |
---|
2140 | numberRejectedF5CriticalPairs = 0; |
---|
2141 | numberOfReductions = 0; |
---|
2142 | numberOfSpolys = 0; |
---|
2143 | return(gbPrev); |
---|
2144 | |
---|
2145 | |
---|
2146 | } |
---|
2147 | |
---|
2148 | #endif |
---|