1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* |
---|
5 | * ABSTRACT: resolutions |
---|
6 | */ |
---|
7 | |
---|
8 | #include "config.h" |
---|
9 | #include <kernel/mod2.h> |
---|
10 | #include <misc/mylimits.h> |
---|
11 | #include <misc/options.h> |
---|
12 | #include <omalloc/omalloc.h> |
---|
13 | #include <kernel/polys.h> |
---|
14 | #include <kernel/febase.h> |
---|
15 | #include <kernel/kstd1.h> |
---|
16 | #include <kernel/kutil.h> |
---|
17 | #include <kernel/stairc.h> |
---|
18 | //#include "cntrlc.h" |
---|
19 | #include <misc/intvec.h> |
---|
20 | #include <coeffs/numbers.h> |
---|
21 | #include <kernel/modulop.h> |
---|
22 | #include <kernel/ideals.h> |
---|
23 | #include <misc/intvec.h> |
---|
24 | #include <polys/monomials/ring.h> |
---|
25 | #include <kernel/syz.h> |
---|
26 | #include <polys/kbuckets.h> |
---|
27 | #include <polys/prCopy.h> |
---|
28 | #include <kernel/timer.h> |
---|
29 | #include <polys/matpol.h> |
---|
30 | |
---|
31 | //#define SHOW_PROT |
---|
32 | //#define SHOW_RED |
---|
33 | //#define SHOW_Kosz |
---|
34 | //#define SHOW_RESULT |
---|
35 | //#define INVERT_PAIRS |
---|
36 | //#define ONLY_STD |
---|
37 | //#define EXPERIMENT1 //Hier stimmt was mit der Anzahl der Erzeuger in xyz11 nicht!! |
---|
38 | #define EXPERIMENT2 |
---|
39 | #define EXPERIMENT3 |
---|
40 | #define WITH_BUCKET //Use of buckets in EXPERIMENT3 (Product criterion) |
---|
41 | #define WITH_SCHREYER_ORD |
---|
42 | #define USE_CHAINCRIT |
---|
43 | #define USE_CHAINCRIT0 |
---|
44 | #define USE_PROD_CRIT |
---|
45 | #define USE_REGULARITY |
---|
46 | #define WITH_SORT |
---|
47 | //#define FULL_TOTAKE |
---|
48 | int discard_pairs; |
---|
49 | int short_pairs; |
---|
50 | |
---|
51 | /*3 |
---|
52 | * assumes the ideals old_ideal and new_ideal to be homogeneous |
---|
53 | * tests wether the new_ideal is a regular extension of the old_ideal |
---|
54 | */ |
---|
55 | static BOOLEAN syIsRegular(ideal old_ideal,ideal new_ideal,int deg) |
---|
56 | { |
---|
57 | intvec * old_hilbs=hHstdSeries(old_ideal,NULL,NULL,NULL); |
---|
58 | intvec * new_hilbs=hHstdSeries(new_ideal,NULL,NULL,NULL); |
---|
59 | int biggest_length=si_max(old_hilbs->length()+deg,new_hilbs->length()); |
---|
60 | intvec * shifted_old_hilbs=new intvec(biggest_length); |
---|
61 | intvec * old_hilb1=new intvec(biggest_length); |
---|
62 | intvec * new_hilb1=new intvec(biggest_length); |
---|
63 | int i; |
---|
64 | BOOLEAN isRegular=TRUE; |
---|
65 | |
---|
66 | for (i=old_hilbs->length()+deg-1;i>=deg;i--) |
---|
67 | (*shifted_old_hilbs)[i] = (*old_hilbs)[i-deg]; |
---|
68 | for (i=old_hilbs->length()-1;i>=0;i--) |
---|
69 | (*old_hilb1)[i] = (*old_hilbs)[i]-(*shifted_old_hilbs)[i]; |
---|
70 | for (i=old_hilbs->length()+deg-1;i>=old_hilbs->length();i--) |
---|
71 | (*old_hilb1)[i] = -(*shifted_old_hilbs)[i]; |
---|
72 | for (i=new_hilbs->length()-1;i>=0;i--) |
---|
73 | (*new_hilb1)[i] = (*new_hilbs)[i]; |
---|
74 | i = 0; |
---|
75 | while ((i<biggest_length) && isRegular) |
---|
76 | { |
---|
77 | isRegular = isRegular && ((*old_hilb1)[i] == (*new_hilb1)[i]); |
---|
78 | i++; |
---|
79 | } |
---|
80 | delete old_hilbs; |
---|
81 | delete new_hilbs; |
---|
82 | delete old_hilb1; |
---|
83 | delete new_hilb1; |
---|
84 | delete shifted_old_hilbs; |
---|
85 | return isRegular; |
---|
86 | } |
---|
87 | |
---|
88 | /*3 |
---|
89 | * shows the resolution stored in syzstr->orderedRes |
---|
90 | */ |
---|
91 | #if 0 /* unused*/ |
---|
92 | static void syShowRes(syStrategy syzstr) |
---|
93 | { |
---|
94 | int i=0; |
---|
95 | |
---|
96 | while ((i<syzstr->length) && (!idIs0(syzstr->res[i]))) |
---|
97 | { |
---|
98 | Print("aktueller hoechster index ist: %d\n",(*syzstr->Tl)[i]); |
---|
99 | Print("der %d-te modul ist:\n",i); |
---|
100 | idPrint(syzstr->res[i]); |
---|
101 | PrintS("Seine Darstellung:\n"); |
---|
102 | idPrint(syzstr->orderedRes[i]); |
---|
103 | i++; |
---|
104 | } |
---|
105 | } |
---|
106 | #endif |
---|
107 | |
---|
108 | /*3 |
---|
109 | * produces the next subresolution for a regular extension |
---|
110 | */ |
---|
111 | static void syCreateRegularExtension(syStrategy syzstr,ideal old_ideal, |
---|
112 | ideal old_repr,int old_tl, poly next_generator,resolvente totake) |
---|
113 | { |
---|
114 | int index=syzstr->length-1,i,j,start,start_ttk,new_tl; |
---|
115 | poly gen=pCopy(next_generator),p; |
---|
116 | poly neg_gen=pCopy(next_generator); |
---|
117 | ideal current_ideal,current_repr; |
---|
118 | int current_tl; |
---|
119 | poly w_gen=pHead(next_generator); |
---|
120 | pSetComp(w_gen,0); |
---|
121 | pSetmComp(w_gen); |
---|
122 | |
---|
123 | //syShowRes(syzstr); |
---|
124 | neg_gen = pNeg(neg_gen); |
---|
125 | if (pGetComp(gen)>0) |
---|
126 | { |
---|
127 | p_Shift(&gen,-1,currRing); |
---|
128 | p_Shift(&neg_gen,-1,currRing); |
---|
129 | } |
---|
130 | while (index>0) |
---|
131 | { |
---|
132 | if (index%2==0) |
---|
133 | p = gen; |
---|
134 | else |
---|
135 | p = neg_gen; |
---|
136 | if (index>1) |
---|
137 | { |
---|
138 | current_ideal = syzstr->res[index-1]; |
---|
139 | current_repr = syzstr->orderedRes[index-1]; |
---|
140 | current_tl = (*syzstr->Tl)[index-1]; |
---|
141 | } |
---|
142 | else |
---|
143 | { |
---|
144 | current_ideal = old_ideal; |
---|
145 | current_repr = old_repr; |
---|
146 | current_tl = old_tl; |
---|
147 | } |
---|
148 | if (!idIs0(current_ideal)) |
---|
149 | { |
---|
150 | if (idIs0(syzstr->res[index])) |
---|
151 | { |
---|
152 | syzstr->res[index] = idInit(IDELEMS(current_ideal), |
---|
153 | current_ideal->rank+current_tl); |
---|
154 | syzstr->orderedRes[index] = idInit(IDELEMS(current_ideal), |
---|
155 | current_ideal->rank); |
---|
156 | start = 0; |
---|
157 | } |
---|
158 | else |
---|
159 | { |
---|
160 | start = IDELEMS(syzstr->res[index]); |
---|
161 | while ((start>0) && (syzstr->res[index]->m[start-1]==NULL)) start--; |
---|
162 | if (IDELEMS(syzstr->res[index])<start+IDELEMS(current_ideal)) |
---|
163 | { |
---|
164 | pEnlargeSet(&syzstr->res[index]->m,IDELEMS(syzstr->res[index]), |
---|
165 | IDELEMS(current_ideal)); |
---|
166 | IDELEMS(syzstr->res[index]) += IDELEMS(current_ideal); |
---|
167 | pEnlargeSet(&syzstr->orderedRes[index]->m,IDELEMS(syzstr->orderedRes[index]), |
---|
168 | IDELEMS(current_ideal)); |
---|
169 | IDELEMS(syzstr->orderedRes[index]) += IDELEMS(current_ideal); |
---|
170 | } |
---|
171 | } |
---|
172 | if (idIs0(totake[index])) |
---|
173 | { |
---|
174 | totake[index] = idInit(IDELEMS(current_ideal), |
---|
175 | current_ideal->rank+current_tl); |
---|
176 | start_ttk = 0; |
---|
177 | } |
---|
178 | else |
---|
179 | { |
---|
180 | start_ttk = IDELEMS(totake[index]); |
---|
181 | while ((start_ttk>0) && (totake[index]->m[start_ttk-1]==NULL)) start_ttk--; |
---|
182 | if (IDELEMS(totake[index])<start_ttk+IDELEMS(current_ideal)) |
---|
183 | { |
---|
184 | pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]), |
---|
185 | IDELEMS(current_ideal)); |
---|
186 | for (j=IDELEMS(totake[index]);j<IDELEMS(totake[index])+ |
---|
187 | IDELEMS(current_ideal);j++) |
---|
188 | totake[index]->m[j] = NULL; |
---|
189 | IDELEMS(totake[index]) += IDELEMS(current_ideal); |
---|
190 | } |
---|
191 | } |
---|
192 | for (i=0;i<IDELEMS(current_ideal);i++) |
---|
193 | { |
---|
194 | if (current_ideal->m[i]!=NULL) |
---|
195 | { |
---|
196 | syzstr->res[index]->m[i+start] = pCopy(current_ideal->m[i]); |
---|
197 | syzstr->res[index]->m[i+start] = pMult_mm(syzstr->res[index]->m[i+start],w_gen); |
---|
198 | p_Shift(&syzstr->res[index]->m[i+start],current_tl,currRing); |
---|
199 | syzstr->res[index]->m[i+start] = pAdd(syzstr->res[index]->m[i+start], |
---|
200 | ppMult_qq(current_repr->m[i],p)); |
---|
201 | syzstr->orderedRes[index]->m[i+start] = pCopy(current_repr->m[i]); |
---|
202 | syzstr->orderedRes[index]->m[i+start] = |
---|
203 | pMult_mm(syzstr->orderedRes[index]->m[i+start],w_gen); |
---|
204 | if ((*syzstr->Tl)[index]!=0) |
---|
205 | p_Shift(&syzstr->orderedRes[index]->m[i+start],(*syzstr->Tl)[index],currRing); |
---|
206 | } |
---|
207 | } |
---|
208 | for (i=0;i<IDELEMS(totake[index-1]);i++) |
---|
209 | { |
---|
210 | if (totake[index-1]->m[i]!=NULL) |
---|
211 | { |
---|
212 | if ((index==1) && ((i==IDELEMS(current_ideal) || |
---|
213 | (totake[index-1]->m[i+1]==NULL)))) break; |
---|
214 | totake[index]->m[i+start_ttk] = |
---|
215 | pMult_mm(pCopy(totake[index-1]->m[i]),w_gen); |
---|
216 | p_Shift(&totake[index]->m[i+start_ttk],current_tl,currRing); |
---|
217 | #ifdef FULL_TOTAKE |
---|
218 | poly pp=pCopy(p); |
---|
219 | p_Shift(&pp,i+1,currRing); |
---|
220 | totake[index]->m[i+start_ttk] = pAdd(totake[index]->m[i+start_ttk],pp); |
---|
221 | #endif |
---|
222 | } |
---|
223 | } |
---|
224 | (*syzstr->Tl)[index] += current_tl; |
---|
225 | } |
---|
226 | index--; |
---|
227 | } |
---|
228 | pDelete(&gen); |
---|
229 | pDelete(&neg_gen); |
---|
230 | pDelete(&w_gen); |
---|
231 | //syShowRes(syzstr); |
---|
232 | } |
---|
233 | |
---|
234 | /*3 |
---|
235 | * proves the consistence of the pairset resPairs with the corresponding |
---|
236 | * set of generators; |
---|
237 | * only for tests |
---|
238 | */ |
---|
239 | static void syTestPairs(SSet resPairs,int length,ideal old_generators) |
---|
240 | { |
---|
241 | int i=0; |
---|
242 | |
---|
243 | while (i<length) |
---|
244 | { |
---|
245 | if (resPairs[i].lcm!=NULL) |
---|
246 | { |
---|
247 | if (resPairs[i].p1!=NULL) |
---|
248 | assume(resPairs[i].p1==old_generators->m[resPairs[i].ind1]); |
---|
249 | if (resPairs[i].p2!=NULL) |
---|
250 | assume(resPairs[i].p2==old_generators->m[resPairs[i].ind2]); |
---|
251 | } |
---|
252 | i++; |
---|
253 | } |
---|
254 | } |
---|
255 | |
---|
256 | /*3 |
---|
257 | * cancels the weight monomials given by the leading terms of totake |
---|
258 | * from the resolution res; |
---|
259 | * works in place on res, but reads only from totake |
---|
260 | */ |
---|
261 | void syReorder_Kosz(syStrategy syzstr) |
---|
262 | { |
---|
263 | int length=syzstr->length; |
---|
264 | int syzIndex=length-1,i,j; |
---|
265 | resolvente res=syzstr->fullres; |
---|
266 | poly p; |
---|
267 | |
---|
268 | while ((syzIndex!=0) && (res[syzIndex]==NULL)) syzIndex--; |
---|
269 | while (syzIndex>0) |
---|
270 | { |
---|
271 | for(i=0;i<IDELEMS(res[syzIndex]);i++) |
---|
272 | { |
---|
273 | #ifdef USE_REGULARITY |
---|
274 | if ((syzstr->regularity>0) && (res[syzIndex]->m[i]!=NULL)) |
---|
275 | { |
---|
276 | if (p_FDeg(res[syzIndex]->m[i],currRing)>=syzstr->regularity+syzIndex) |
---|
277 | pDelete(&res[syzIndex]->m[i]); |
---|
278 | } |
---|
279 | #endif |
---|
280 | p = res[syzIndex]->m[i]; |
---|
281 | while (p!=NULL) |
---|
282 | { |
---|
283 | if (res[syzIndex-1]->m[pGetComp(p)-1]!=NULL) |
---|
284 | { |
---|
285 | for(j=1;j<=(currRing->N);j++) |
---|
286 | { |
---|
287 | pSetExp(p,j,pGetExp(p,j) |
---|
288 | -pGetExp(res[syzIndex-1]->m[pGetComp(p)-1],j)); |
---|
289 | } |
---|
290 | } |
---|
291 | else |
---|
292 | PrintS("error in the resolvent\n"); |
---|
293 | pSetm(p); |
---|
294 | pIter(p); |
---|
295 | } |
---|
296 | } |
---|
297 | syzIndex--; |
---|
298 | } |
---|
299 | } |
---|
300 | |
---|
301 | /*3 |
---|
302 | * updates the pairset resPairs by generating all pairs including the |
---|
303 | * new_generators in the 0-th modul; |
---|
304 | * the new_generators are inserted in the old_generators; |
---|
305 | * new_generators is empty after the procedure; |
---|
306 | */ |
---|
307 | static void updatePairs(SSet *resPairs,int *l_pairs,syStrategy syzstr, |
---|
308 | int index,ideal new_generators,ideal new_repr,int crit_comp) |
---|
309 | { |
---|
310 | if (idIs0(new_generators)) return; |
---|
311 | ideal old_generators=syzstr->res[index]; |
---|
312 | ideal old_repr=syzstr->orderedRes[index]; |
---|
313 | int i=0,j,k,kk,og_elem=0,og_idel=IDELEMS(old_generators),l=*l_pairs,jj,ll,j1; |
---|
314 | int og_ini=0; |
---|
315 | ideal pairs=idInit(og_idel+IDELEMS(new_generators),old_generators->rank); |
---|
316 | polyset prs=pairs->m; |
---|
317 | poly p=NULL; |
---|
318 | SObject tso; |
---|
319 | |
---|
320 | syInitializePair(&tso); |
---|
321 | while ((og_elem<og_idel) && (old_generators->m[og_elem]!=NULL)) |
---|
322 | { |
---|
323 | if ((index>0) && (pGetComp(old_generators->m[og_elem])<=crit_comp)) |
---|
324 | og_ini = og_elem; |
---|
325 | og_elem++; |
---|
326 | } |
---|
327 | while ((l>0) && ((*resPairs)[l-1].lcm==NULL)) l--; |
---|
328 | while ((i<IDELEMS(new_generators)) && (new_generators->m[i]!=NULL)) |
---|
329 | { |
---|
330 | syTestPairs(*resPairs,*l_pairs,old_generators); |
---|
331 | if (IDELEMS(old_generators)==og_elem) |
---|
332 | { |
---|
333 | pEnlargeSet(&old_generators->m,IDELEMS(old_generators),16); |
---|
334 | IDELEMS(old_generators) += 16; |
---|
335 | pEnlargeSet(&old_repr->m,IDELEMS(old_repr),16); |
---|
336 | IDELEMS(old_repr) += 16; |
---|
337 | } |
---|
338 | k = p_FDeg(new_generators->m[i],currRing); |
---|
339 | kk = pGetComp(new_generators->m[i]); |
---|
340 | j = og_ini; |
---|
341 | while ((j<og_elem) && (old_generators->m[j]!=NULL) && |
---|
342 | (pGetComp(old_generators->m[j])<kk)) j++; |
---|
343 | while ((j<og_elem) && (old_generators->m[j]!=NULL) && |
---|
344 | (p_FDeg(old_generators->m[j],currRing)<=k)) j++; |
---|
345 | for (jj=og_elem;jj>j;jj--) |
---|
346 | { |
---|
347 | old_generators->m[jj] = old_generators->m[jj-1]; |
---|
348 | old_repr->m[jj] = old_repr->m[jj-1]; |
---|
349 | } |
---|
350 | old_generators->m[j] = new_generators->m[i]; |
---|
351 | new_generators->m[i] = NULL; |
---|
352 | old_repr->m[j] = new_repr->m[i]; |
---|
353 | new_repr->m[i] = NULL; |
---|
354 | og_elem++; |
---|
355 | for (jj=0;jj<*l_pairs;jj++) |
---|
356 | { |
---|
357 | if ((*resPairs)[jj].lcm!=NULL) |
---|
358 | { |
---|
359 | if ((*resPairs)[jj].ind1>=j) (*resPairs)[jj].ind1++; |
---|
360 | if ((*resPairs)[jj].ind2>=j) (*resPairs)[jj].ind2++; |
---|
361 | } |
---|
362 | } |
---|
363 | syTestPairs(*resPairs,*l_pairs,old_generators); |
---|
364 | for (jj=og_ini;jj<og_elem;jj++) |
---|
365 | { |
---|
366 | if ((j!=jj) && (pGetComp(old_generators->m[jj])==pGetComp(old_generators->m[j]))) |
---|
367 | { |
---|
368 | p = pOne(); |
---|
369 | pLcm(old_generators->m[jj],old_generators->m[j],p); |
---|
370 | pSetComp(p,j+1); |
---|
371 | pSetm(p); |
---|
372 | j1 = 0; |
---|
373 | while (j1<jj) |
---|
374 | { |
---|
375 | if (prs[j1]!=NULL) |
---|
376 | { |
---|
377 | if (pLmDivisibleByNoComp(prs[j1],p)) |
---|
378 | { |
---|
379 | pDelete(&p); |
---|
380 | break; |
---|
381 | } |
---|
382 | else if (pLmDivisibleByNoComp(p,prs[j1])) |
---|
383 | { |
---|
384 | pDelete(&(prs[j1])); |
---|
385 | } |
---|
386 | #ifdef USE_CHAINCRIT0 |
---|
387 | else |
---|
388 | { |
---|
389 | poly p1,p2; |
---|
390 | int ip=(currRing->N); |
---|
391 | p1 = pDivide(p,old_generators->m[jj]); |
---|
392 | p2 = pDivide(prs[j1],old_generators->m[j1]); |
---|
393 | while ((ip>0) && (pGetExp(p1,ip)*pGetExp(p2,ip)==0)) ip--; |
---|
394 | if (ip==0) |
---|
395 | { |
---|
396 | int ti=0; |
---|
397 | while ((ti<l) && (((*resPairs)[ti].ind1!=j1)|| ((*resPairs)[ti].ind2!=jj))) ti++; |
---|
398 | if (ti<l) |
---|
399 | { |
---|
400 | if (TEST_OPT_PROT) PrintS("cc"); |
---|
401 | syDeletePair(&(*resPairs)[ti]); |
---|
402 | syCompactifyPairSet(*resPairs,*l_pairs,ti); |
---|
403 | l--; |
---|
404 | } |
---|
405 | } |
---|
406 | pDelete(&p1); |
---|
407 | pDelete(&p2); |
---|
408 | } |
---|
409 | #endif |
---|
410 | } |
---|
411 | j1++; |
---|
412 | } |
---|
413 | if (p!=NULL) |
---|
414 | prs[jj] = p; |
---|
415 | } |
---|
416 | } |
---|
417 | for (jj=og_ini;jj<og_elem;jj++) |
---|
418 | { |
---|
419 | if (prs[jj] !=NULL) |
---|
420 | { |
---|
421 | if (l>=*l_pairs) |
---|
422 | { |
---|
423 | SSet temp = (SSet)omAlloc0((*l_pairs+16)*sizeof(SObject)); |
---|
424 | for (ll=0;ll<*l_pairs;ll++) |
---|
425 | { |
---|
426 | temp[ll].p = (*resPairs)[ll].p; |
---|
427 | temp[ll].p1 = (*resPairs)[ll].p1; |
---|
428 | temp[ll].p2 = (*resPairs)[ll].p2; |
---|
429 | temp[ll].syz = (*resPairs)[ll].syz; |
---|
430 | temp[ll].lcm = (*resPairs)[ll].lcm; |
---|
431 | temp[ll].ind1 = (*resPairs)[ll].ind1; |
---|
432 | temp[ll].ind2 = (*resPairs)[ll].ind2; |
---|
433 | temp[ll].syzind = (*resPairs)[ll].syzind; |
---|
434 | temp[ll].order = (*resPairs)[ll].order; |
---|
435 | temp[ll].isNotMinimal = (*resPairs)[ll].isNotMinimal; |
---|
436 | } |
---|
437 | omFreeSize((ADDRESS)(*resPairs),*l_pairs*sizeof(SObject)); |
---|
438 | *l_pairs += 16; |
---|
439 | (*resPairs) = temp; |
---|
440 | } |
---|
441 | tso.lcm = prs[jj]; |
---|
442 | prs[jj] = NULL; |
---|
443 | tso.order = p_FDeg(tso.lcm,currRing); |
---|
444 | tso.p1 = old_generators->m[jj]; |
---|
445 | tso.p2 = old_generators->m[j]; |
---|
446 | tso.ind1 = jj; |
---|
447 | tso.ind2 = j; |
---|
448 | tso.syzind = -1; |
---|
449 | tso.isNotMinimal = NULL; |
---|
450 | tso.p = NULL; |
---|
451 | tso.syz = NULL; |
---|
452 | SSet rP=*resPairs; |
---|
453 | #ifdef SHOW_PROT |
---|
454 | Print("erzeuge Paar im Modul %d,%d mit: \n",index,tso.order); |
---|
455 | PrintS("poly1: ");pWrite(tso.p1); |
---|
456 | PrintS("poly2: ");pWrite(tso.p2); |
---|
457 | PrintS("syz: ");pWrite(tso.syz); |
---|
458 | PrintS("sPoly: ");pWrite(tso.p); |
---|
459 | PrintLn(); |
---|
460 | #endif |
---|
461 | syEnterPair(rP,&tso,&l,index); |
---|
462 | syInitializePair(&tso); |
---|
463 | } |
---|
464 | } |
---|
465 | i++; |
---|
466 | } |
---|
467 | idDelete(&pairs); |
---|
468 | } |
---|
469 | |
---|
470 | /*3 |
---|
471 | * performs the modification of a single reduction on the syzygy-level |
---|
472 | */ |
---|
473 | inline void sySPRedSyz_Kosz(syStrategy syzstr,poly redWith,poly syz,poly q=NULL,int l_syz=-1) |
---|
474 | { |
---|
475 | poly p=pDivide(q,redWith); |
---|
476 | pSetCoeff(p,nDiv(pGetCoeff(q),pGetCoeff(redWith))); |
---|
477 | kBucket_Minus_m_Mult_p(syzstr->syz_bucket,p,syz,&l_syz,NULL); |
---|
478 | pDelete(&p); |
---|
479 | } |
---|
480 | |
---|
481 | /*3 |
---|
482 | * normalizes the poly bucket by the ideal; |
---|
483 | * stops the reduction whenever the leading component is less than the |
---|
484 | * crit_comp; |
---|
485 | * returns the changing status |
---|
486 | */ |
---|
487 | static BOOLEAN syRedSyz(kBucket_pt bucket,ideal red,int crit_comp,int* g_l) |
---|
488 | { |
---|
489 | poly p = kBucketGetLm(bucket); |
---|
490 | int j = 0,i=IDELEMS(red)-1; |
---|
491 | number n; |
---|
492 | BOOLEAN isChanged=FALSE; |
---|
493 | |
---|
494 | loop |
---|
495 | { |
---|
496 | if ((j>=i) || (p==NULL) || (pGetComp(p)<=crit_comp)) break; |
---|
497 | if ((red->m[j]!=NULL) && (pDivisibleBy(red->m[j],p))) |
---|
498 | { |
---|
499 | n = kBucketPolyRed(bucket,red->m[j], g_l[j], NULL); |
---|
500 | nDelete(&n); |
---|
501 | p = kBucketGetLm(bucket); |
---|
502 | isChanged = TRUE; |
---|
503 | j = 0; |
---|
504 | } |
---|
505 | else |
---|
506 | j++; |
---|
507 | } |
---|
508 | return isChanged; |
---|
509 | } |
---|
510 | |
---|
511 | /*3 |
---|
512 | * a tail reduction for the syzygies yielding new generators |
---|
513 | */ |
---|
514 | static poly syRedTailSyz(poly tored,ideal red,ideal sec_red,int crit_comp,syStrategy syzstr, |
---|
515 | int * gen_length,int * secgen_length,int * tored_length) |
---|
516 | { |
---|
517 | int i=IDELEMS(red)-1,num_mon,num_tail; |
---|
518 | poly h,hn; |
---|
519 | BOOLEAN dummy; |
---|
520 | |
---|
521 | while ((i>0) && (red->m[i-1]==NULL)) i--; |
---|
522 | i--; |
---|
523 | h = tored; |
---|
524 | if ((h!=NULL) && (pGetComp(h)>crit_comp)) |
---|
525 | { |
---|
526 | num_mon = 1; |
---|
527 | hn = pNext(h); |
---|
528 | num_tail = *tored_length-1; |
---|
529 | while (hn!=NULL) |
---|
530 | { |
---|
531 | kBucketInit(syzstr->syz_bucket,hn,num_tail); |
---|
532 | dummy = syRedSyz(syzstr->syz_bucket,red,crit_comp,gen_length); |
---|
533 | kBucketClear(syzstr->syz_bucket,&hn,&num_tail); |
---|
534 | pNext(h) = hn; |
---|
535 | if ((hn==NULL) || (pGetComp(hn)<=crit_comp)) |
---|
536 | break; |
---|
537 | else |
---|
538 | { |
---|
539 | pIter(h); |
---|
540 | pIter(hn); |
---|
541 | num_mon++; |
---|
542 | num_tail--; |
---|
543 | } |
---|
544 | } |
---|
545 | if (sec_red!=NULL) |
---|
546 | { |
---|
547 | while (hn!=NULL) |
---|
548 | { |
---|
549 | kBucketInit(syzstr->syz_bucket,hn,num_tail); |
---|
550 | dummy = syRedSyz(syzstr->syz_bucket,sec_red,crit_comp,secgen_length); |
---|
551 | kBucketClear(syzstr->syz_bucket,&hn,&num_tail); |
---|
552 | pNext(h) = hn; |
---|
553 | if (hn==NULL) |
---|
554 | break; |
---|
555 | else |
---|
556 | { |
---|
557 | pIter(h); |
---|
558 | pIter(hn); |
---|
559 | num_mon++; |
---|
560 | num_tail--; |
---|
561 | } |
---|
562 | } |
---|
563 | } |
---|
564 | *tored_length = num_mon+num_tail; |
---|
565 | } |
---|
566 | assume(pLength(tored)==*tored_length); |
---|
567 | return tored; |
---|
568 | } |
---|
569 | |
---|
570 | /*3 |
---|
571 | * the complete reduction of a single pair which is just stored |
---|
572 | * in bucket and syz_bucket |
---|
573 | */ |
---|
574 | static BOOLEAN syRedSyzPair(syStrategy syzstr,int index,int* g_l,int* orp_l) |
---|
575 | { |
---|
576 | kBucket_pt bucket=syzstr->bucket; |
---|
577 | poly p = kBucketGetLm(bucket); |
---|
578 | ideal red=syzstr->res[index],repr=syzstr->orderedRes[index]; |
---|
579 | int j = 0,i=IDELEMS(red)-1; |
---|
580 | number n; |
---|
581 | BOOLEAN isChanged=FALSE; |
---|
582 | |
---|
583 | loop |
---|
584 | { |
---|
585 | if ((j>=i) || (p==NULL)) break; |
---|
586 | if ((red->m[j]!=NULL) && (pDivisibleBy(red->m[j],p))) |
---|
587 | { |
---|
588 | sySPRedSyz_Kosz(syzstr,red->m[j],repr->m[j],p,orp_l[j]); |
---|
589 | n = kBucketPolyRed(bucket,red->m[j], g_l[j], NULL); |
---|
590 | nDelete(&n); |
---|
591 | p = kBucketGetLm(bucket); |
---|
592 | isChanged = TRUE; |
---|
593 | j = 0; |
---|
594 | } |
---|
595 | else |
---|
596 | j++; |
---|
597 | } |
---|
598 | return isChanged; |
---|
599 | } |
---|
600 | |
---|
601 | /*3 |
---|
602 | * the tailreduction for generators (which includes the correction of |
---|
603 | * the corresponding representation) |
---|
604 | */ |
---|
605 | #if 0 /*unused*/ |
---|
606 | static void syRedTailSyzPair(SObject tso,syStrategy syzstr,int index, |
---|
607 | int * gen_length,int* orp_l,int * tored_l,int * syzred_l) |
---|
608 | { |
---|
609 | int num_mon,num_tail,syz_l; |
---|
610 | poly h,hn; |
---|
611 | BOOLEAN dummy; |
---|
612 | |
---|
613 | h = tso.p; |
---|
614 | kBucketInit(syzstr->syz_bucket,tso.syz,*syzred_l); |
---|
615 | if (h!=NULL) |
---|
616 | { |
---|
617 | num_mon = 1; |
---|
618 | hn = pNext(h); |
---|
619 | num_tail = *tored_l-1; |
---|
620 | while (hn!=NULL) |
---|
621 | { |
---|
622 | kBucketInit(syzstr->bucket,hn,num_tail); |
---|
623 | dummy = syRedSyzPair(syzstr,index,gen_length,orp_l); |
---|
624 | kBucketClear(syzstr->bucket,&hn,&num_tail); |
---|
625 | pNext(h) = hn; |
---|
626 | if (hn==NULL) |
---|
627 | break; |
---|
628 | else |
---|
629 | { |
---|
630 | pIter(h); |
---|
631 | pIter(hn); |
---|
632 | num_mon++; |
---|
633 | num_tail--; |
---|
634 | } |
---|
635 | } |
---|
636 | *tored_l = num_mon+num_tail; |
---|
637 | } |
---|
638 | kBucketClear(syzstr->syz_bucket,&tso.syz,&syz_l); |
---|
639 | assume(pLength(tso.syz)==syz_l); |
---|
640 | assume(pLength(tso.p)==*tored_l); |
---|
641 | } |
---|
642 | #endif |
---|
643 | |
---|
644 | /*3 |
---|
645 | * the reduction of a pair in the 0-th module |
---|
646 | */ |
---|
647 | static void redOnePair(SSet resPairs,int itso,int l, ideal syzygies, |
---|
648 | int crit_comp, syStrategy syzstr,int index,ideal new_generators, |
---|
649 | ideal new_repr,int * ogm_l,int * orp_l) |
---|
650 | { |
---|
651 | SObject tso = resPairs[itso]; |
---|
652 | assume (tso.lcm!=NULL); |
---|
653 | ideal old_generators=syzstr->res[index]; |
---|
654 | ideal old_repr=syzstr->orderedRes[index]; |
---|
655 | int og_idel=IDELEMS(old_generators),ng_place=IDELEMS(new_generators); |
---|
656 | int toReplace=0; |
---|
657 | int i,j,syz_l; |
---|
658 | number coefgcd,n; |
---|
659 | polyset ogm=old_generators->m; |
---|
660 | poly p; |
---|
661 | BOOLEAN deleteP=FALSE; |
---|
662 | #ifdef EXPERIMENT1 |
---|
663 | poly syzp; |
---|
664 | #endif |
---|
665 | int syz_place=IDELEMS(syzygies); |
---|
666 | |
---|
667 | while ((syz_place>0) && (syzygies->m[syz_place-1]==NULL)) syz_place--; |
---|
668 | while ((ng_place>0) && (new_generators->m[ng_place-1]==NULL)) ng_place--; |
---|
669 | while ((og_idel>0) && (old_generators->m[og_idel-1]==NULL)) og_idel--; |
---|
670 | assume (tso.ind1<og_idel); |
---|
671 | assume (tso.ind2<og_idel); |
---|
672 | assume (tso.ind1!=tso.ind2); |
---|
673 | assume (tso.p1 == old_generators->m[tso.ind1]); |
---|
674 | assume (tso.p2 == old_generators->m[tso.ind2]); |
---|
675 | tso.p1 = old_generators->m[tso.ind1]; |
---|
676 | tso.p2 = old_generators->m[tso.ind2]; |
---|
677 | if ((tso.p1!=NULL) && (tso.p2!=NULL)) |
---|
678 | { |
---|
679 | if (TEST_OPT_PROT) |
---|
680 | PrintS("."); |
---|
681 | if (index==0) |
---|
682 | { |
---|
683 | /*--- tests wether a generator must be replaced (lt(f1)|lt(f2)!)--*/ |
---|
684 | if (p_FDeg(tso.p1,currRing)==p_FDeg(tso.lcm,currRing)) |
---|
685 | toReplace = tso.ind1+1; |
---|
686 | else if (p_FDeg(tso.p2,currRing)==p_FDeg(tso.lcm,currRing)) |
---|
687 | toReplace = tso.ind2+1; |
---|
688 | } |
---|
689 | #ifdef EXPERIMENT3 |
---|
690 | /*--- tests wether the product criterion applies --------------*/ |
---|
691 | if ((index==0) && (old_generators->rank==1) && |
---|
692 | (p_FDeg(tso.p1,currRing)+p_FDeg(tso.p2,currRing)==tso.order)) |
---|
693 | { |
---|
694 | tso.p = NULL; |
---|
695 | p = pCopy(tso.p1); |
---|
696 | p_Shift(&p,-1,currRing); |
---|
697 | #ifdef WITH_BUCKET |
---|
698 | poly pp; |
---|
699 | pp = pMult_mm(pCopy(old_repr->m[tso.ind2]),p); |
---|
700 | kBucketInit(syzstr->syz_bucket,pp,-1); |
---|
701 | pLmDelete(&p); |
---|
702 | p = pNeg(p); |
---|
703 | pp = pCopy(old_repr->m[tso.ind2]); |
---|
704 | int il=-1; |
---|
705 | while (p!=NULL) |
---|
706 | { |
---|
707 | kBucket_Minus_m_Mult_p(syzstr->syz_bucket,p,pp,&il,NULL); |
---|
708 | pLmDelete(&p); |
---|
709 | } |
---|
710 | pDelete(&pp); |
---|
711 | p = pCopy(tso.p2); |
---|
712 | p_Shift(&p,-1,currRing); |
---|
713 | pp = pCopy(old_repr->m[tso.ind1]); |
---|
714 | il=-1; |
---|
715 | while (p!=NULL) |
---|
716 | { |
---|
717 | kBucket_Minus_m_Mult_p(syzstr->syz_bucket,p,pp,&il,NULL); |
---|
718 | pLmDelete(&p); |
---|
719 | } |
---|
720 | pDelete(&pp); |
---|
721 | kBucketClear(syzstr->syz_bucket,&tso.syz,&j); |
---|
722 | #else |
---|
723 | tso.syz = pMult(p,pCopy(old_repr->m[tso.ind2])); |
---|
724 | p = pCopy(tso.p2); |
---|
725 | p_Shift(&p,-1,currRing); |
---|
726 | tso.syz = pSub(tso.syz,pMult(p,pCopy(old_repr->m[tso.ind1]))); |
---|
727 | #endif |
---|
728 | } |
---|
729 | else |
---|
730 | #endif |
---|
731 | /*--- the product criterion does not apply --------------------*/ |
---|
732 | { |
---|
733 | tso.p = ksOldCreateSpoly(tso.p2,tso.p1); |
---|
734 | number coefgcd = nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing); |
---|
735 | assume (old_repr->m[tso.ind1]!=NULL); |
---|
736 | tso.syz = pCopy(old_repr->m[tso.ind1]); |
---|
737 | poly tt = pDivide(tso.lcm,tso.p1); |
---|
738 | pSetComp(tt,0); |
---|
739 | pSetmComp(tt); |
---|
740 | pSetCoeff(tt,nDiv(pGetCoeff(tso.p1),coefgcd)); |
---|
741 | tso.syz = pMult_mm(tso.syz,tt); |
---|
742 | pDelete(&tt); |
---|
743 | coefgcd = nNeg(coefgcd); |
---|
744 | assume (old_repr->m[tso.ind2]!=NULL); |
---|
745 | p = pCopy(old_repr->m[tso.ind2]); |
---|
746 | tt = pDivide(tso.lcm,tso.p2); |
---|
747 | pSetComp(tt,0); |
---|
748 | pSetmComp(tt); |
---|
749 | pSetCoeff(tt,nDiv(pGetCoeff(tso.p2),coefgcd)); |
---|
750 | p = pMult_mm(p,tt); |
---|
751 | pDelete(&tt); |
---|
752 | tso.syz = pAdd(p,tso.syz); |
---|
753 | #ifdef EXPERIMENT2 |
---|
754 | if ((tso.syz!=NULL) && (pGetComp(tso.syz)<=crit_comp)) |
---|
755 | { |
---|
756 | /*--- breaks when the leading component is less than crit_comp ------*/ |
---|
757 | deleteP = TRUE; |
---|
758 | discard_pairs++; |
---|
759 | } |
---|
760 | #endif |
---|
761 | nDelete(&coefgcd); |
---|
762 | } //End of the else-part of EXPERIMENT3 |
---|
763 | #ifdef SHOW_PROT |
---|
764 | Print("reduziere Paar im Module %d mit: \n",index); |
---|
765 | PrintS("poly1: ");pWrite(tso.p1); |
---|
766 | PrintS("poly2: ");pWrite(tso.p2); |
---|
767 | PrintS("syz: ");pWrite(tso.syz); |
---|
768 | PrintS("sPoly: ");pWrite(tso.p); |
---|
769 | #endif |
---|
770 | assume(tso.syz!=NULL); |
---|
771 | kBucketInit(syzstr->syz_bucket,tso.syz,-1); |
---|
772 | if ((tso.p!=NULL) && (!deleteP)) |
---|
773 | { |
---|
774 | kBucketInit(syzstr->bucket,tso.p,-1); |
---|
775 | p = kBucketGetLm(syzstr->bucket); |
---|
776 | j = 0; |
---|
777 | loop |
---|
778 | { |
---|
779 | if (j>=og_idel) |
---|
780 | { |
---|
781 | /*--- reduction with generators computed in this procedure ---*/ |
---|
782 | j = 0; |
---|
783 | while ((j<ng_place) && (!pDivisibleBy(new_generators->m[j],p))) j++; |
---|
784 | if (j>=ng_place) break; |
---|
785 | assume (new_repr->m[j]!=NULL); |
---|
786 | sySPRedSyz_Kosz(syzstr,new_generators->m[j],new_repr->m[j],p); |
---|
787 | n = kBucketPolyRed(syzstr->bucket,new_generators->m[j],pLength(new_generators->m[j]), NULL); |
---|
788 | p = kBucketGetLm(syzstr->bucket); |
---|
789 | #ifdef EXPERIMENT1 |
---|
790 | syzp = kBucketGetLm(syzstr->syz_bucket); |
---|
791 | if ((syzp!=NULL) && (pGetComp(syzp)<=crit_comp)) |
---|
792 | { |
---|
793 | deleteP =TRUE; |
---|
794 | break; |
---|
795 | } |
---|
796 | //if (syzp==NULL) |
---|
797 | //assume(p==NULL); |
---|
798 | //else |
---|
799 | //if (pGetComp(syzp)<=crit_comp) short_pairs++; |
---|
800 | #endif |
---|
801 | if (p==NULL) break; |
---|
802 | j = 0; |
---|
803 | } |
---|
804 | if (pDivisibleBy(ogm[j],p)) |
---|
805 | { |
---|
806 | /*--- reduction with general old generators ---------------------*/ |
---|
807 | assume (old_repr->m[j]!=NULL); |
---|
808 | sySPRedSyz_Kosz(syzstr,ogm[j],old_repr->m[j],p,orp_l[j]); |
---|
809 | n = kBucketPolyRed(syzstr->bucket,ogm[j],ogm_l[j], NULL); |
---|
810 | p = kBucketGetLm(syzstr->bucket); |
---|
811 | #ifdef EXPERIMENT1 |
---|
812 | syzp = kBucketGetLm(syzstr->syz_bucket); |
---|
813 | if ((syzp!=NULL) && (pGetComp(syzp)<=crit_comp)) |
---|
814 | { |
---|
815 | break; |
---|
816 | deleteP =TRUE; |
---|
817 | } |
---|
818 | //if (syzp==NULL) |
---|
819 | //assume(p==NULL); |
---|
820 | //else |
---|
821 | //if ((pGetComp(syzp)<=crit_comp) && (p!=NULL)) short_pairs++; |
---|
822 | #endif |
---|
823 | if (p==NULL) break; |
---|
824 | j = 0; |
---|
825 | } |
---|
826 | else |
---|
827 | j++; |
---|
828 | } |
---|
829 | kBucketClear(syzstr->bucket,&tso.p,&tso.length); |
---|
830 | } |
---|
831 | kBucketClear(syzstr->syz_bucket,&tso.syz,&syz_l); |
---|
832 | if (deleteP) |
---|
833 | { |
---|
834 | pDelete(&tso.p); |
---|
835 | pDelete(&tso.syz); |
---|
836 | } |
---|
837 | } |
---|
838 | else |
---|
839 | { |
---|
840 | PrintS("Shit happens!\n"); |
---|
841 | } |
---|
842 | #ifdef SHOW_PROT |
---|
843 | Print("erhalte Paar im Module %d mit: \n",index); |
---|
844 | PrintS("syz: ");pWrite(tso.syz); |
---|
845 | PrintS("sPoly: ");pWrite(tso.p); |
---|
846 | PrintLn(); |
---|
847 | #endif |
---|
848 | if (toReplace) |
---|
849 | { |
---|
850 | /*-- replaces the generator if neccesary ------------------*/ |
---|
851 | pDelete(&old_generators->m[toReplace-1]); |
---|
852 | pDelete(&old_repr->m[toReplace-1]); |
---|
853 | for (i=toReplace-1;i<og_idel-1;i++) |
---|
854 | { |
---|
855 | old_generators->m[i] = old_generators->m[i+1]; |
---|
856 | old_repr->m[i] = old_repr->m[i+1]; |
---|
857 | } |
---|
858 | old_generators->m[og_idel-1] = NULL; |
---|
859 | old_repr->m[og_idel-1] = NULL; |
---|
860 | for (i=itso+1;i<l;i++) |
---|
861 | { |
---|
862 | if (resPairs[i].lcm!=NULL) |
---|
863 | { |
---|
864 | if ((resPairs[i].ind1==toReplace-1)||(resPairs[i].ind2==toReplace-1)) |
---|
865 | syDeletePair(&resPairs[i]); |
---|
866 | else |
---|
867 | { |
---|
868 | if (resPairs[i].ind1>=toReplace) |
---|
869 | (resPairs[i].ind1)--; |
---|
870 | if (resPairs[i].ind2>=toReplace) |
---|
871 | (resPairs[i].ind2)--; |
---|
872 | } |
---|
873 | } |
---|
874 | } |
---|
875 | syCompactifyPairSet(resPairs,l,itso+1); |
---|
876 | } |
---|
877 | if (tso.p!=NULL) |
---|
878 | { |
---|
879 | /*-- stores the new generator ---------------------------------*/ |
---|
880 | //syRedTailSyzPair(tso,syzstr,index,ogm_l,orp_l,&tso.length,&syz_l); |
---|
881 | if (ng_place>=IDELEMS(new_generators)) |
---|
882 | { |
---|
883 | pEnlargeSet(&new_generators->m,IDELEMS(new_generators),16); |
---|
884 | IDELEMS(new_generators) += 16; |
---|
885 | pEnlargeSet(&new_repr->m,IDELEMS(new_repr),16); |
---|
886 | IDELEMS(new_repr) += 16; |
---|
887 | } |
---|
888 | if (!nIsOne(pGetCoeff(tso.p))) |
---|
889 | { |
---|
890 | n=nInvers(pGetCoeff(tso.p)); |
---|
891 | pNorm(tso.p); |
---|
892 | pMult_nn(tso.syz,n); |
---|
893 | nDelete(&n); |
---|
894 | } |
---|
895 | new_generators->m[ng_place] = tso.p; |
---|
896 | tso.p = NULL; |
---|
897 | new_repr->m[ng_place] = tso.syz; |
---|
898 | tso.syz = NULL; |
---|
899 | } |
---|
900 | else |
---|
901 | { |
---|
902 | /*--- takes the syzygy as new generator of the next module ---*/ |
---|
903 | if (tso.syz==NULL) |
---|
904 | { |
---|
905 | #ifndef EXPERIMENT2 |
---|
906 | #ifdef EXPERIMENT3 |
---|
907 | short_pairs++; |
---|
908 | #endif |
---|
909 | #endif |
---|
910 | } |
---|
911 | else if (pGetComp(tso.syz)<=crit_comp) |
---|
912 | { |
---|
913 | pDelete(&tso.syz); |
---|
914 | } |
---|
915 | else |
---|
916 | { |
---|
917 | if (syz_place>=IDELEMS(syzygies)) |
---|
918 | { |
---|
919 | pEnlargeSet(&syzygies->m,IDELEMS(syzygies),16); |
---|
920 | IDELEMS(syzygies) += 16; |
---|
921 | } |
---|
922 | syzygies->m[syz_place] = tso.syz; |
---|
923 | tso.syz = NULL; |
---|
924 | pNorm(syzygies->m[syz_place]); |
---|
925 | } |
---|
926 | } |
---|
927 | resPairs[itso] = tso; |
---|
928 | syDeletePair(&resPairs[itso]); |
---|
929 | syTestPairs(resPairs,l,old_generators); |
---|
930 | } |
---|
931 | |
---|
932 | /*3 |
---|
933 | * reduction of all pairs of a fixed degree of the 0-th module |
---|
934 | */ |
---|
935 | static BOOLEAN redPairs(SSet resPairs,int l_pairs, ideal syzygies, |
---|
936 | ideal new_generators,ideal new_repr, int crit_comp,syStrategy syzstr, |
---|
937 | int index) |
---|
938 | { |
---|
939 | if (resPairs[0].lcm==NULL) return TRUE; |
---|
940 | int i,j,actdeg=resPairs[0].order; |
---|
941 | int * ogm_l=(int*)omAlloc0(IDELEMS(syzstr->res[index])*sizeof(int)); |
---|
942 | int * orp_l=(int*)omAlloc0(IDELEMS(syzstr->orderedRes[index])*sizeof(int)); |
---|
943 | int t1=IDELEMS(syzstr->res[index]),t2=IDELEMS(syzstr->orderedRes[index]); |
---|
944 | |
---|
945 | for (j=IDELEMS(syzstr->res[index])-1;j>=0;j--) |
---|
946 | { |
---|
947 | if (syzstr->res[index]->m[j]!=NULL) |
---|
948 | ogm_l[j] = pLength(syzstr->res[index]->m[j]); |
---|
949 | } |
---|
950 | for (j=IDELEMS(syzstr->orderedRes[index])-1;j>=0;j--) |
---|
951 | { |
---|
952 | if (syzstr->orderedRes[index]->m[j]!=NULL) |
---|
953 | orp_l[j] = pLength(syzstr->orderedRes[index]->m[j]); |
---|
954 | } |
---|
955 | loop |
---|
956 | { |
---|
957 | i = 0; |
---|
958 | if (TEST_OPT_PROT) |
---|
959 | Print("(%d,%d)",index,resPairs[0].order); |
---|
960 | while (resPairs[i].order==actdeg) |
---|
961 | { |
---|
962 | syTestPairs(resPairs,l_pairs,syzstr->res[index]); |
---|
963 | redOnePair(resPairs,i,l_pairs,syzygies,crit_comp,syzstr,index, |
---|
964 | new_generators, new_repr,ogm_l,orp_l); |
---|
965 | i++; |
---|
966 | syTestPairs(resPairs,l_pairs,syzstr->res[index]); |
---|
967 | } |
---|
968 | syTestPairs(resPairs,l_pairs,syzstr->res[index]); |
---|
969 | syCompactifyPairSet(resPairs,l_pairs,0); |
---|
970 | syTestPairs(resPairs,l_pairs,syzstr->res[index]); |
---|
971 | if (!idIs0(new_generators)) |
---|
972 | break; |
---|
973 | else if (resPairs[0].lcm==NULL) //there are no pairs left and no new_gens |
---|
974 | { |
---|
975 | omFreeSize((ADDRESS)ogm_l,IDELEMS(syzstr->res[index])*sizeof(int)); |
---|
976 | omFreeSize((ADDRESS)orp_l,IDELEMS(syzstr->orderedRes[index])*sizeof(int)); |
---|
977 | return TRUE; |
---|
978 | } |
---|
979 | else |
---|
980 | actdeg = resPairs[0].order; |
---|
981 | } |
---|
982 | syTestPairs(resPairs,l_pairs,syzstr->res[index]); |
---|
983 | omFreeSize((ADDRESS)ogm_l,IDELEMS(syzstr->res[index])*sizeof(int)); |
---|
984 | omFreeSize((ADDRESS)orp_l,IDELEMS(syzstr->orderedRes[index])*sizeof(int)); |
---|
985 | return FALSE; |
---|
986 | } |
---|
987 | |
---|
988 | /*3 |
---|
989 | * extends the standard basis old_generators with new_generators; |
---|
990 | * returns the syzygies which involve the new elements; |
---|
991 | * assumes that the components of the new_generators are sperated |
---|
992 | * from those of old_generators, i.e. whenever the leading term |
---|
993 | * of a syzygy lies in the part of the old_generators, the syzygy |
---|
994 | * lie just in the module old_generators |
---|
995 | * assumes that the new_generators are reduced w.r.t. old_generators |
---|
996 | */ |
---|
997 | static ideal kosz_std(ideal new_generators,ideal new_repr,syStrategy syzstr, |
---|
998 | int index,int next_comp) |
---|
999 | { |
---|
1000 | int og_idel=IDELEMS(syzstr->res[index]); |
---|
1001 | int l_pairs=2*og_idel; |
---|
1002 | ideal syzygies=idInit(16,syzstr->res[index]->rank+1); |
---|
1003 | if ((idIs0(new_generators)) || (new_generators->m[0]==NULL)) |
---|
1004 | { |
---|
1005 | Werror("Hier ist was faul!\n"); |
---|
1006 | return NULL; |
---|
1007 | } |
---|
1008 | SSet resPairs=(SSet)omAlloc0(l_pairs*sizeof(SObject)); |
---|
1009 | loop |
---|
1010 | { |
---|
1011 | updatePairs(&resPairs,&l_pairs,syzstr,index, |
---|
1012 | new_generators,new_repr,next_comp); |
---|
1013 | if (redPairs(resPairs,l_pairs,syzygies, new_generators,new_repr, |
---|
1014 | next_comp,syzstr,index)) break; |
---|
1015 | } |
---|
1016 | omFreeSize((SSet)resPairs,l_pairs*sizeof(SObject)); |
---|
1017 | return syzygies; |
---|
1018 | } |
---|
1019 | |
---|
1020 | /*3 |
---|
1021 | * normalizes the incoming generators |
---|
1022 | */ |
---|
1023 | static poly normalize(poly next_p,ideal add_generators, syStrategy syzstr, |
---|
1024 | int * g_l,int * p_l,int crit_comp) |
---|
1025 | { |
---|
1026 | int j=0,i=IDELEMS(add_generators); |
---|
1027 | kBucketInit(syzstr->bucket,next_p,pLength(next_p)); |
---|
1028 | poly p = kBucketGetLm(syzstr->bucket),result; |
---|
1029 | number n; |
---|
1030 | |
---|
1031 | loop |
---|
1032 | { |
---|
1033 | if ((j>=i) || (p==NULL) || (pGetComp(p)<=crit_comp)) break; |
---|
1034 | if ((add_generators->m[j]!=NULL) && (pDivisibleBy(add_generators->m[j],p))) |
---|
1035 | { |
---|
1036 | n = kBucketPolyRed(syzstr->bucket,add_generators->m[j], g_l[j], NULL); |
---|
1037 | nDelete(&n); |
---|
1038 | p = kBucketGetLm(syzstr->bucket); |
---|
1039 | j = 0; |
---|
1040 | } |
---|
1041 | else |
---|
1042 | j++; |
---|
1043 | } |
---|
1044 | kBucketClear(syzstr->bucket,&result,p_l); |
---|
1045 | return result; |
---|
1046 | } |
---|
1047 | |
---|
1048 | /*3 |
---|
1049 | * updates the pairs inthe higher modules |
---|
1050 | */ |
---|
1051 | static void updatePairsHIndex(SSet *resPairs,int *l_pairs,syStrategy syzstr, |
---|
1052 | int index,ideal add_generators,ideal add_repr,ideal new_generators, |
---|
1053 | ideal new_repr,int crit_comp,int* first_new) |
---|
1054 | { |
---|
1055 | int i=*first_new,l=*l_pairs,j,ll,j1,add_idel=IDELEMS(add_generators); |
---|
1056 | ideal pairs=idInit(add_idel,add_generators->rank); |
---|
1057 | polyset prs=pairs->m; |
---|
1058 | poly p=NULL; |
---|
1059 | SObject tso; |
---|
1060 | |
---|
1061 | syInitializePair(&tso); |
---|
1062 | while ((l>0) && ((*resPairs)[l-1].lcm==NULL)) l--; |
---|
1063 | while ((i<add_idel) && (add_generators->m[i]!=NULL)) |
---|
1064 | { |
---|
1065 | for (j=0;j<i;j++) |
---|
1066 | { |
---|
1067 | if ((pGetComp(add_generators->m[j])==pGetComp(add_generators->m[i]))) |
---|
1068 | { |
---|
1069 | p = pOne(); |
---|
1070 | pLcm(add_generators->m[j],add_generators->m[i],p); |
---|
1071 | pSetComp(p,i+1); |
---|
1072 | pSetm(p); |
---|
1073 | j1 = 0; |
---|
1074 | while (j1<j) |
---|
1075 | { |
---|
1076 | if (prs[j1]!=NULL) |
---|
1077 | { |
---|
1078 | if (pLmDivisibleByNoComp(prs[j1],p)) |
---|
1079 | { |
---|
1080 | pDelete(&p); |
---|
1081 | break; |
---|
1082 | } |
---|
1083 | else if (pLmDivisibleByNoComp(p,prs[j1])) |
---|
1084 | { |
---|
1085 | pDelete(&(prs[j1])); |
---|
1086 | } |
---|
1087 | #ifdef USE_CHAINCRIT |
---|
1088 | else |
---|
1089 | { |
---|
1090 | poly p1,p2; |
---|
1091 | int ip=(currRing->N); |
---|
1092 | p1 = pDivide(p,add_generators->m[j]); |
---|
1093 | p2 = pDivide(prs[j1],add_generators->m[j1]); |
---|
1094 | while ((ip>0) && (pGetExp(p1,ip)*pGetExp(p2,ip)==0)) ip--; |
---|
1095 | if (ip==0) |
---|
1096 | { |
---|
1097 | int ti=0; |
---|
1098 | while ((ti<l) && (((*resPairs)[ti].ind1!=j1)|| ((*resPairs)[ti].ind2!=j))) ti++; |
---|
1099 | if (ti<l) |
---|
1100 | { |
---|
1101 | if (TEST_OPT_PROT) PrintS("cc"); |
---|
1102 | syDeletePair(&(*resPairs)[ti]); |
---|
1103 | syCompactifyPairSet(*resPairs,*l_pairs,ti); |
---|
1104 | l--; |
---|
1105 | } |
---|
1106 | } |
---|
1107 | pDelete(&p1); |
---|
1108 | pDelete(&p2); |
---|
1109 | } |
---|
1110 | #endif |
---|
1111 | } |
---|
1112 | j1++; |
---|
1113 | } |
---|
1114 | if (p!=NULL) |
---|
1115 | prs[j] = p; |
---|
1116 | } |
---|
1117 | } |
---|
1118 | for (j=0;j<i;j++) |
---|
1119 | { |
---|
1120 | if (prs[j] !=NULL) |
---|
1121 | { |
---|
1122 | if (l>=*l_pairs) |
---|
1123 | { |
---|
1124 | SSet temp = (SSet)omAlloc0((*l_pairs+16)*sizeof(SObject)); |
---|
1125 | for (ll=0;ll<*l_pairs;ll++) |
---|
1126 | { |
---|
1127 | temp[ll].p = (*resPairs)[ll].p; |
---|
1128 | temp[ll].p1 = (*resPairs)[ll].p1; |
---|
1129 | temp[ll].p2 = (*resPairs)[ll].p2; |
---|
1130 | temp[ll].syz = (*resPairs)[ll].syz; |
---|
1131 | temp[ll].lcm = (*resPairs)[ll].lcm; |
---|
1132 | temp[ll].ind1 = (*resPairs)[ll].ind1; |
---|
1133 | temp[ll].ind2 = (*resPairs)[ll].ind2; |
---|
1134 | temp[ll].syzind = (*resPairs)[ll].syzind; |
---|
1135 | temp[ll].order = (*resPairs)[ll].order; |
---|
1136 | temp[ll].isNotMinimal = (*resPairs)[ll].isNotMinimal; |
---|
1137 | } |
---|
1138 | omFreeSize((ADDRESS)(*resPairs),*l_pairs*sizeof(SObject)); |
---|
1139 | *l_pairs += 16; |
---|
1140 | (*resPairs) = temp; |
---|
1141 | } |
---|
1142 | tso.lcm = prs[j]; |
---|
1143 | prs[j] = NULL; |
---|
1144 | tso.order = p_FDeg(tso.lcm,currRing); |
---|
1145 | tso.p1 = add_generators->m[j]; |
---|
1146 | tso.p2 = add_generators->m[i]; |
---|
1147 | tso.ind1 = j; |
---|
1148 | tso.ind2 = i; |
---|
1149 | tso.syzind = -1; |
---|
1150 | tso.isNotMinimal = NULL; |
---|
1151 | tso.p = NULL; |
---|
1152 | tso.syz = NULL; |
---|
1153 | SSet rP=*resPairs; |
---|
1154 | #ifdef SHOW_PROT |
---|
1155 | Print("erzeuge Paar im Modul %d,%d mit: \n",index,tso.order); |
---|
1156 | PrintS("poly1: ");pWrite(tso.p1); |
---|
1157 | PrintS("poly2: ");pWrite(tso.p2); |
---|
1158 | PrintS("syz: ");pWrite(tso.syz); |
---|
1159 | PrintS("sPoly: ");pWrite(tso.p); |
---|
1160 | PrintLn(); |
---|
1161 | #endif |
---|
1162 | syEnterPair(rP,&tso,&l,index); |
---|
1163 | syInitializePair(&tso); |
---|
1164 | } |
---|
1165 | } |
---|
1166 | i++; |
---|
1167 | } |
---|
1168 | *first_new = i; |
---|
1169 | idDelete(&pairs); |
---|
1170 | } |
---|
1171 | |
---|
1172 | /*3 |
---|
1173 | * reduction of a single pair in the higher moduls |
---|
1174 | */ |
---|
1175 | static void redOnePairHIndex(SSet resPairs,int itso, int crit_comp, |
---|
1176 | syStrategy syzstr,int index,ideal add_generators, ideal add_repr, |
---|
1177 | ideal new_generators, ideal new_repr,int * next_place_add,int ** g_l, |
---|
1178 | poly deg_soc) |
---|
1179 | { |
---|
1180 | SObject tso = resPairs[itso]; |
---|
1181 | assume (tso.lcm!=NULL); |
---|
1182 | int ng_place=IDELEMS(new_generators); |
---|
1183 | int i,j; |
---|
1184 | number n; |
---|
1185 | poly p; |
---|
1186 | #ifdef EXPERIMENT1 |
---|
1187 | poly syzp; |
---|
1188 | #endif |
---|
1189 | |
---|
1190 | assume (tso.ind1<*next_place_add); |
---|
1191 | assume (tso.ind2<*next_place_add); |
---|
1192 | assume (tso.ind1!=tso.ind2); |
---|
1193 | assume (tso.p1 == add_generators->m[tso.ind1]); |
---|
1194 | assume (tso.p2 == add_generators->m[tso.ind2]); |
---|
1195 | tso.p1 = add_generators->m[tso.ind1]; |
---|
1196 | tso.p2 = add_generators->m[tso.ind2]; |
---|
1197 | if ((tso.p1!=NULL) && (tso.p2!=NULL)) |
---|
1198 | { |
---|
1199 | if (TEST_OPT_PROT) |
---|
1200 | PrintS("."); |
---|
1201 | #ifdef USE_PROD_CRIT |
---|
1202 | if (p_FDeg(tso.p1,currRing)+p_FDeg(tso.p2,currRing)==tso.order+p_FDeg(deg_soc,currRing)) |
---|
1203 | { |
---|
1204 | if (TEST_OPT_PROT) PrintS("pc"); |
---|
1205 | int ac=pGetComp(tso.p1); |
---|
1206 | assume(ac=pGetComp(tso.p2)); |
---|
1207 | poly p1=pCopy(tso.p1); |
---|
1208 | poly p2=pCopy(tso.p2); |
---|
1209 | poly pp1,pp2,tp1,tp2; |
---|
1210 | poly sp1=pCopy(add_repr->m[tso.ind1]),sp2=pCopy(add_repr->m[tso.ind2]); |
---|
1211 | pp1 = p1; |
---|
1212 | pp2 = p2; |
---|
1213 | loop |
---|
1214 | { |
---|
1215 | assume(pp1!=NULL); |
---|
1216 | for(i=(int)(currRing->N); i; i--) |
---|
1217 | pSetExp(pp1,i, pGetExp(pp1,i)- pGetExp(deg_soc,i)); |
---|
1218 | pSetComp(pp1, 0); |
---|
1219 | pSetm(pp1); |
---|
1220 | if ((pNext(pp1)!=NULL) && (pGetComp(pNext(pp1))!=ac)) break; |
---|
1221 | pIter(pp1); |
---|
1222 | } |
---|
1223 | loop |
---|
1224 | { |
---|
1225 | assume(pp2!=NULL); |
---|
1226 | for(i=(int)(currRing->N); i; i--) |
---|
1227 | pSetExp(pp2,i, pGetExp(pp2,i)- pGetExp(deg_soc,i)); |
---|
1228 | pSetComp(pp2, 0); |
---|
1229 | pSetm(pp2); |
---|
1230 | if ((pNext(pp2)!=NULL) && (pGetComp(pNext(pp2))!=ac)) break; |
---|
1231 | pIter(pp2); |
---|
1232 | } |
---|
1233 | tp1 = pNext(pp1); |
---|
1234 | tp2 = pNext(pp2); |
---|
1235 | pNext(pp1) = NULL; |
---|
1236 | pNext(pp2) = NULL; |
---|
1237 | //p_Shift(&p1,-ac,currRing); |
---|
1238 | //p_Shift(&p2,-ac,currRing); |
---|
1239 | tp1 = pMult(tp1,pCopy(p2)); |
---|
1240 | tp2 = pMult(tp2,pCopy(p1)); |
---|
1241 | sp1 = pMult(p2,sp1); |
---|
1242 | sp2 = pMult(p1,sp2); |
---|
1243 | tso.p = pSub(tp1,tp2); |
---|
1244 | tso.syz = pSub(sp1,sp2); |
---|
1245 | } |
---|
1246 | else |
---|
1247 | #endif |
---|
1248 | { |
---|
1249 | tso.p = ksOldCreateSpoly(tso.p2,tso.p1); |
---|
1250 | number coefgcd = nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing); |
---|
1251 | assume (add_repr->m[tso.ind1]!=NULL); |
---|
1252 | tso.syz = pCopy(add_repr->m[tso.ind1]); |
---|
1253 | poly tt = pDivide(tso.lcm,tso.p1); |
---|
1254 | pSetComp(tt,0); |
---|
1255 | pSetmComp(tt); |
---|
1256 | pSetCoeff(tt,nDiv(pGetCoeff(tso.p1),coefgcd)); |
---|
1257 | tso.syz = pMult_mm(tso.syz,tt); |
---|
1258 | pDelete(&tt); |
---|
1259 | coefgcd = nNeg(coefgcd); |
---|
1260 | assume (add_repr->m[tso.ind2]!=NULL); |
---|
1261 | p = pCopy(add_repr->m[tso.ind2]); |
---|
1262 | tt = pDivide(tso.lcm,tso.p2); |
---|
1263 | pSetComp(tt,0); |
---|
1264 | pSetmComp(tt); |
---|
1265 | pSetCoeff(tt,nDiv(pGetCoeff(tso.p2),coefgcd)); |
---|
1266 | p = pMult_mm(p,tt); |
---|
1267 | pDelete(&tt); |
---|
1268 | tso.syz = pAdd(p,tso.syz); |
---|
1269 | nDelete(&coefgcd); |
---|
1270 | } |
---|
1271 | #ifdef SHOW_PROT |
---|
1272 | Print("reduziere Paar im Module %d mit: \n",index); |
---|
1273 | PrintS("poly1: ");pWrite(tso.p1); |
---|
1274 | PrintS("poly2: ");pWrite(tso.p2); |
---|
1275 | PrintS("syz: ");pWrite(tso.syz); |
---|
1276 | PrintS("sPoly: ");pWrite(tso.p); |
---|
1277 | #endif |
---|
1278 | assume(tso.syz!=NULL); |
---|
1279 | kBucketInit(syzstr->syz_bucket,tso.syz,-1); |
---|
1280 | if (tso.p!=NULL) |
---|
1281 | { |
---|
1282 | kBucketInit(syzstr->bucket,tso.p,-1); |
---|
1283 | p = kBucketGetLm(syzstr->bucket); |
---|
1284 | j = 0; |
---|
1285 | loop |
---|
1286 | { |
---|
1287 | if (j>=*next_place_add) break; |
---|
1288 | if (pDivisibleBy(add_generators->m[j],p)) |
---|
1289 | { |
---|
1290 | assume (add_repr->m[j]!=NULL); |
---|
1291 | sySPRedSyz_Kosz(syzstr,add_generators->m[j],add_repr->m[j],p); |
---|
1292 | n = kBucketPolyRed(syzstr->bucket,add_generators->m[j], |
---|
1293 | pLength(add_generators->m[j]), NULL); |
---|
1294 | p = kBucketGetLm(syzstr->bucket); |
---|
1295 | if ((p==NULL) || (pGetComp(p)<=crit_comp)) break; |
---|
1296 | j = 0; |
---|
1297 | } |
---|
1298 | else |
---|
1299 | j++; |
---|
1300 | } |
---|
1301 | kBucketClear(syzstr->bucket,&tso.p,&tso.length); |
---|
1302 | } |
---|
1303 | kBucketClear(syzstr->syz_bucket,&tso.syz,&j); |
---|
1304 | } |
---|
1305 | else |
---|
1306 | { |
---|
1307 | PrintS("Shit happens!\n"); |
---|
1308 | } |
---|
1309 | #ifdef SHOW_PROT |
---|
1310 | Print("erhalte Paar im Module %d mit: \n",index); |
---|
1311 | PrintS("syz: ");pWrite(tso.syz); |
---|
1312 | PrintS("sPoly: ");pWrite(tso.p); |
---|
1313 | PrintLn(); |
---|
1314 | #endif |
---|
1315 | if (tso.p!=NULL) |
---|
1316 | { |
---|
1317 | if (!nIsOne(pGetCoeff(tso.p))) |
---|
1318 | { |
---|
1319 | n=nInvers(pGetCoeff(tso.p)); |
---|
1320 | pNorm(tso.p); |
---|
1321 | pMult_nn(tso.syz,n); |
---|
1322 | nDelete(&n); |
---|
1323 | } |
---|
1324 | } |
---|
1325 | if ((TEST_OPT_PROT) && (tso.syz==NULL)) PrintS("null"); |
---|
1326 | if ((tso.p!=NULL) && (pGetComp(tso.p)>crit_comp)) |
---|
1327 | { |
---|
1328 | if (*next_place_add>=IDELEMS(add_generators)) |
---|
1329 | { |
---|
1330 | pEnlargeSet(&add_generators->m,IDELEMS(add_generators),16); |
---|
1331 | pEnlargeSet(&add_repr->m,IDELEMS(add_repr),16); |
---|
1332 | *g_l = (int*)omRealloc0Size((ADDRESS)*g_l, IDELEMS(add_generators)*sizeof(int), |
---|
1333 | (IDELEMS(add_generators)+16)*sizeof(int)); |
---|
1334 | IDELEMS(add_generators) += 16; |
---|
1335 | IDELEMS(add_repr) += 16; |
---|
1336 | } |
---|
1337 | assume(add_repr->m[*next_place_add]==NULL); |
---|
1338 | add_generators->m[*next_place_add] = tso.p; |
---|
1339 | add_repr->m[*next_place_add] = tso.syz; |
---|
1340 | (*g_l)[*next_place_add] = tso.length; |
---|
1341 | (*next_place_add)++; |
---|
1342 | } |
---|
1343 | else |
---|
1344 | { |
---|
1345 | while ((ng_place>0) && (new_generators->m[ng_place-1]==NULL) && |
---|
1346 | (new_repr->m[ng_place-1]==NULL)) ng_place--; |
---|
1347 | if (ng_place>=IDELEMS(new_generators)) |
---|
1348 | { |
---|
1349 | pEnlargeSet(&new_generators->m,IDELEMS(new_generators),16); |
---|
1350 | IDELEMS(new_generators) += 16; |
---|
1351 | pEnlargeSet(&new_repr->m,IDELEMS(new_repr),16); |
---|
1352 | IDELEMS(new_repr) += 16; |
---|
1353 | } |
---|
1354 | new_generators->m[ng_place] = tso.p; |
---|
1355 | new_repr->m[ng_place] = tso.syz; |
---|
1356 | } |
---|
1357 | tso.p = NULL; |
---|
1358 | tso.syz = NULL; |
---|
1359 | resPairs[itso] = tso; |
---|
1360 | syDeletePair(&resPairs[itso]); |
---|
1361 | } |
---|
1362 | |
---|
1363 | /*3 |
---|
1364 | * reduction of all pairs of a fixed degree of a fixed module |
---|
1365 | */ |
---|
1366 | static BOOLEAN reducePairsHIndex(SSet resPairs,int l_pairs,syStrategy syzstr, |
---|
1367 | int index,ideal add_generators,ideal add_repr,ideal new_generators, |
---|
1368 | ideal new_repr,int crit_comp,int * red_deg,int * next_place_add,int **g_l, |
---|
1369 | resolvente totake) |
---|
1370 | { |
---|
1371 | if (resPairs[0].lcm==NULL) return FALSE; |
---|
1372 | int i=0; |
---|
1373 | poly deg_soc; |
---|
1374 | |
---|
1375 | if (TEST_OPT_PROT) |
---|
1376 | Print("(%d,%d)",index,resPairs[0].order); |
---|
1377 | while ((i<l_pairs) && (resPairs[i].order==*red_deg)) |
---|
1378 | { |
---|
1379 | assume(totake[index-1]!=NULL); |
---|
1380 | assume(pGetComp(resPairs[i].p1)<=IDELEMS(totake[index-1])); |
---|
1381 | assume(totake[index-1]->m[pGetComp(resPairs[i].p1)-1]!=NULL); |
---|
1382 | deg_soc = totake[index-1]->m[pGetComp(resPairs[i].p1)-1]; |
---|
1383 | redOnePairHIndex(resPairs,i,crit_comp,syzstr,index, add_generators,add_repr, |
---|
1384 | new_generators, new_repr,next_place_add,g_l,deg_soc); |
---|
1385 | i++; |
---|
1386 | } |
---|
1387 | syCompactifyPairSet(resPairs,l_pairs,0); |
---|
1388 | if (resPairs[0].lcm==NULL) //there are no pairs left and no new_gens |
---|
1389 | return FALSE; |
---|
1390 | else |
---|
1391 | *red_deg = resPairs[0].order; |
---|
1392 | return TRUE; |
---|
1393 | } |
---|
1394 | |
---|
1395 | /*3 |
---|
1396 | * we proceed the generators of the next module; |
---|
1397 | * they are stored in add_generators and add_repr; |
---|
1398 | * if the normal form of a new genrators w.r.t. add_generators has |
---|
1399 | * pGetComp<crit_comp it is skipped from the reduction; |
---|
1400 | * new_generators and new_repr (which are empty) stores the result of the |
---|
1401 | * reduction which is normalized afterwards |
---|
1402 | */ |
---|
1403 | static void procedeNextGenerators(ideal temp_generators,ideal temp_repr, |
---|
1404 | ideal new_generators, ideal new_repr, ideal add_generators, |
---|
1405 | ideal add_repr, syStrategy syzstr,int index, int crit_comp, |
---|
1406 | resolvente totake) |
---|
1407 | { |
---|
1408 | int i=0,j,next_new_el; |
---|
1409 | int idel_temp=IDELEMS(temp_generators); |
---|
1410 | int next_place_add; |
---|
1411 | int p_length,red_deg,l_pairs=IDELEMS(add_generators); |
---|
1412 | poly next_p; |
---|
1413 | int * gen_length=(int*)omAlloc0(IDELEMS(add_generators)*sizeof(int)); |
---|
1414 | int * secgen_length=(int*)omAlloc0(IDELEMS(syzstr->res[index])*sizeof(int)); |
---|
1415 | BOOLEAN pairs_left; |
---|
1416 | SSet resPairs=(SSet)omAlloc0(l_pairs*sizeof(SObject)); |
---|
1417 | |
---|
1418 | for (j=IDELEMS(syzstr->res[index])-1;j>=0;j--) |
---|
1419 | { |
---|
1420 | if (syzstr->res[index]->m[j]!=NULL) |
---|
1421 | secgen_length[j] = pLength(syzstr->res[index]->m[j]); |
---|
1422 | } |
---|
1423 | assume(idIs0(new_generators)); |
---|
1424 | next_place_add = IDELEMS(add_generators); |
---|
1425 | while ((next_place_add>0) && (add_generators->m[next_place_add-1]==NULL)) |
---|
1426 | next_place_add--; |
---|
1427 | int next_deg = p_FDeg(temp_generators->m[i],currRing); |
---|
1428 | next_new_el = next_place_add; |
---|
1429 | /*--- loop about all all elements-----------------------------------*/ |
---|
1430 | while ((i<idel_temp) && (temp_generators->m[i]!=NULL)) |
---|
1431 | { |
---|
1432 | /*--- separates elements of equal degree----------------------------*/ |
---|
1433 | #ifdef USE_REGULARITY |
---|
1434 | if (syzstr->regularity>0) |
---|
1435 | { |
---|
1436 | if (next_deg >= syzstr->regularity+index) |
---|
1437 | { |
---|
1438 | while ((i<idel_temp) && (temp_generators->m[i]!=NULL)) |
---|
1439 | { |
---|
1440 | pDelete(&temp_generators->m[i]); |
---|
1441 | i++; |
---|
1442 | } |
---|
1443 | break; |
---|
1444 | } |
---|
1445 | } |
---|
1446 | #endif |
---|
1447 | while ((i<idel_temp) && (p_FDeg(temp_generators->m[i],currRing)==next_deg)) |
---|
1448 | { |
---|
1449 | next_p = temp_generators->m[i]; |
---|
1450 | temp_generators->m[i] = NULL; |
---|
1451 | next_p = normalize(next_p,add_generators,syzstr,gen_length,&p_length, |
---|
1452 | crit_comp); |
---|
1453 | if (next_p!=NULL) |
---|
1454 | { |
---|
1455 | if (pGetComp(next_p)<=(unsigned)crit_comp) |
---|
1456 | { |
---|
1457 | pDelete(&next_p); |
---|
1458 | //if (TEST_OPT_PROT) Print("u(%d)",index); |
---|
1459 | } |
---|
1460 | else |
---|
1461 | { |
---|
1462 | next_p = syRedTailSyz(next_p,add_generators,syzstr->res[index],crit_comp,syzstr, |
---|
1463 | gen_length,secgen_length,&p_length); |
---|
1464 | if (!nIsOne(pGetCoeff(next_p))) |
---|
1465 | pNorm(next_p); |
---|
1466 | if (next_place_add>=IDELEMS(add_generators)) |
---|
1467 | { |
---|
1468 | pEnlargeSet(&add_generators->m,IDELEMS(add_generators),16); |
---|
1469 | pEnlargeSet(&add_repr->m,IDELEMS(add_repr),16); |
---|
1470 | gen_length = (int*)omRealloc0Size((ADDRESS)gen_length, IDELEMS(add_generators)*sizeof(int), |
---|
1471 | (IDELEMS(add_generators)+16)*sizeof(int)); |
---|
1472 | IDELEMS(add_generators) += 16; |
---|
1473 | IDELEMS(add_repr) += 16; |
---|
1474 | } |
---|
1475 | add_generators->m[next_place_add] = next_p; |
---|
1476 | if (totake[index]==NULL) |
---|
1477 | totake[index] = idInit(16,new_generators->rank); |
---|
1478 | if ((*syzstr->Tl)[index]==IDELEMS(totake[index])) |
---|
1479 | { |
---|
1480 | pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]), |
---|
1481 | (*syzstr->Tl)[index]+16-IDELEMS(totake[index])); |
---|
1482 | for (j=IDELEMS(totake[index]);j<(*syzstr->Tl)[index]+16;j++) |
---|
1483 | totake[index]->m[j] = NULL; |
---|
1484 | IDELEMS(totake[index]) = (*syzstr->Tl)[index]+16; |
---|
1485 | } |
---|
1486 | #ifdef FULL_TOTAKE |
---|
1487 | totake[index]->m[(*syzstr->Tl)[index]] = pCopy(next_p); |
---|
1488 | #else |
---|
1489 | totake[index]->m[(*syzstr->Tl)[index]] = pHead(next_p); |
---|
1490 | #endif |
---|
1491 | assume(add_repr->m[next_place_add]==NULL); |
---|
1492 | #ifdef WITH_SCHREYER_ORD |
---|
1493 | add_repr->m[next_place_add] = pHead(add_generators->m[next_place_add]); |
---|
1494 | #else |
---|
1495 | add_repr->m[next_place_add] = pOne(); |
---|
1496 | #endif |
---|
1497 | ((*syzstr->Tl)[index])++; |
---|
1498 | pSetComp(add_repr->m[next_place_add],(*syzstr->Tl)[index]); |
---|
1499 | pSetmComp(add_repr->m[next_place_add]); |
---|
1500 | gen_length[next_place_add] = p_length; |
---|
1501 | next_place_add++; |
---|
1502 | } |
---|
1503 | } |
---|
1504 | i++; |
---|
1505 | } //end inner loop |
---|
1506 | red_deg = next_deg; |
---|
1507 | if (i<idel_temp) |
---|
1508 | next_deg = p_FDeg(temp_generators->m[i],currRing); |
---|
1509 | else |
---|
1510 | next_deg = -1; |
---|
1511 | if ((next_place_add>next_new_el) || (next_deg<0)) //there are new generators or pairs |
---|
1512 | { |
---|
1513 | /*-reducing and generating pairs untill the degree of the next generators-*/ |
---|
1514 | pairs_left = TRUE; |
---|
1515 | while (pairs_left && ((next_deg<0) || (red_deg<= next_deg))) |
---|
1516 | { |
---|
1517 | updatePairsHIndex(&resPairs,&l_pairs,syzstr,index,add_generators, |
---|
1518 | add_repr,new_generators,new_repr,crit_comp,&next_new_el); |
---|
1519 | pairs_left = reducePairsHIndex(resPairs,l_pairs,syzstr,index,add_generators, |
---|
1520 | add_repr,new_generators,new_repr,crit_comp,&red_deg,&next_place_add,&gen_length, |
---|
1521 | totake); |
---|
1522 | } |
---|
1523 | } |
---|
1524 | } |
---|
1525 | omFreeSize((SSet)resPairs,l_pairs*sizeof(SObject)); |
---|
1526 | omFreeSize((ADDRESS)gen_length,IDELEMS(add_generators)*sizeof(int)); |
---|
1527 | omFreeSize((ADDRESS)secgen_length,IDELEMS(syzstr->res[index])*sizeof(int)); |
---|
1528 | } |
---|
1529 | |
---|
1530 | /*3 |
---|
1531 | * normalizes the part of the next reduction lying within the block |
---|
1532 | * of former generators (old_generators); |
---|
1533 | */ |
---|
1534 | static ideal normalizeOldPart(ideal new_generators,ideal new_repr, |
---|
1535 | syStrategy syzstr,int index,int crit_comp) |
---|
1536 | { |
---|
1537 | ideal old_generators= syzstr->res[index]; |
---|
1538 | ideal old_repr= syzstr->orderedRes[index]; |
---|
1539 | int i,j=0,ii=IDELEMS(old_generators)-1,dummy; |
---|
1540 | poly p; |
---|
1541 | number n; |
---|
1542 | int * g_l=(int*)omAlloc0(IDELEMS(old_generators)*sizeof(int)); |
---|
1543 | |
---|
1544 | for (i=0;i<IDELEMS(old_generators);i++) |
---|
1545 | { |
---|
1546 | if (old_generators->m[i]!=NULL) |
---|
1547 | { |
---|
1548 | g_l[i] = pLength(old_generators->m[i]); |
---|
1549 | } |
---|
1550 | } |
---|
1551 | for (i=IDELEMS(new_generators)-1;i>=0;i--) |
---|
1552 | { |
---|
1553 | if (new_generators->m[i]!=NULL) |
---|
1554 | { |
---|
1555 | kBucketInit(syzstr->bucket,new_generators->m[i], |
---|
1556 | pLength(new_generators->m[i])); |
---|
1557 | kBucketInit(syzstr->syz_bucket,new_repr->m[i], |
---|
1558 | pLength(new_repr->m[i])); |
---|
1559 | p = kBucketGetLm(syzstr->bucket); |
---|
1560 | loop |
---|
1561 | { |
---|
1562 | if ((j>=ii) || (p==NULL)) break; |
---|
1563 | if ((old_generators->m[j]!=NULL) && |
---|
1564 | (pDivisibleBy(old_generators->m[j],p))) |
---|
1565 | { |
---|
1566 | sySPRedSyz_Kosz(syzstr,old_generators->m[j],old_repr->m[j],p); |
---|
1567 | n = kBucketPolyRed(syzstr->bucket,old_generators->m[j], g_l[j], NULL); |
---|
1568 | nDelete(&n); |
---|
1569 | p = kBucketGetLm(syzstr->bucket); |
---|
1570 | j = 0; |
---|
1571 | } |
---|
1572 | else |
---|
1573 | j++; |
---|
1574 | } |
---|
1575 | assume (p==NULL); |
---|
1576 | kBucketClear(syzstr->bucket,&new_generators->m[i],&dummy); |
---|
1577 | kBucketClear(syzstr->syz_bucket,&new_repr->m[i],&dummy); |
---|
1578 | } |
---|
1579 | } |
---|
1580 | ideal result=idInit(IDELEMS(new_repr),new_repr->rank); |
---|
1581 | for (j=IDELEMS(new_repr)-1;j>=0;j--) |
---|
1582 | { |
---|
1583 | result->m[j] = new_repr->m[j]; |
---|
1584 | if ((result->m[j]!=NULL) && (!nIsOne(pGetCoeff(result->m[j])))) |
---|
1585 | pNorm(result->m[j]); |
---|
1586 | new_repr->m[j] = NULL; |
---|
1587 | } |
---|
1588 | omFreeSize((ADDRESS)g_l,IDELEMS(old_generators)*sizeof(int)); |
---|
1589 | return result; |
---|
1590 | } |
---|
1591 | |
---|
1592 | /*3 |
---|
1593 | * constructs the new subresolution for a nonregular extension |
---|
1594 | */ |
---|
1595 | static ideal kosz_ext(ideal new_generators,ideal new_repr,syStrategy syzstr, |
---|
1596 | int index,int next_comp,resolvente totake) |
---|
1597 | { |
---|
1598 | ideal temp_generators =idInit(IDELEMS(new_generators),new_generators->rank); |
---|
1599 | ideal temp_repr=idInit(IDELEMS(new_repr),new_repr->rank); |
---|
1600 | ideal add_generators =idInit(IDELEMS(new_generators),new_generators->rank); |
---|
1601 | ideal add_repr=idInit(IDELEMS(new_repr),new_repr->rank); |
---|
1602 | int min_deg=-1; |
---|
1603 | int j,jj,k,deg_p,idel_temp=IDELEMS(temp_generators); |
---|
1604 | poly p; |
---|
1605 | /*--reorder w.r.t. the degree----------------------------------------*/ |
---|
1606 | for (j=IDELEMS(new_generators)-1;j>=0;j--) |
---|
1607 | { |
---|
1608 | if (new_generators->m[j]!=NULL) |
---|
1609 | { |
---|
1610 | p = new_generators->m[j]; |
---|
1611 | new_generators->m[j] = NULL; |
---|
1612 | deg_p = p_FDeg(p,currRing); |
---|
1613 | if (min_deg<0) |
---|
1614 | { |
---|
1615 | min_deg = deg_p; |
---|
1616 | } |
---|
1617 | else |
---|
1618 | { |
---|
1619 | if (deg_p<min_deg) min_deg = deg_p; |
---|
1620 | } |
---|
1621 | k = 0; |
---|
1622 | while ((k<idel_temp) && (temp_generators->m[k]!=NULL) && |
---|
1623 | (p_FDeg(temp_generators->m[k],currRing)<=deg_p)) k++; |
---|
1624 | for (jj=idel_temp-1;jj>k;jj--) |
---|
1625 | { |
---|
1626 | temp_generators->m[jj] = temp_generators->m[jj-1]; |
---|
1627 | } |
---|
1628 | temp_generators->m[k] = p; |
---|
1629 | } |
---|
1630 | } |
---|
1631 | /*--- computing the standard basis in the resolution of the extension -*/ |
---|
1632 | procedeNextGenerators(temp_generators,temp_repr,new_generators,new_repr, |
---|
1633 | add_generators,add_repr,syzstr,index,next_comp,totake); |
---|
1634 | j = IDELEMS(syzstr->res[index]); |
---|
1635 | while ((j>0) && (syzstr->res[index]->m[j-1]==NULL)) j--; |
---|
1636 | jj = IDELEMS(add_generators); |
---|
1637 | while ((jj>0) && (add_generators->m[jj-1]==NULL)) jj--; |
---|
1638 | if (j+jj>=IDELEMS(syzstr->res[index])) |
---|
1639 | { |
---|
1640 | pEnlargeSet(&syzstr->res[index]->m,IDELEMS(syzstr->res[index]), |
---|
1641 | j+jj+1-IDELEMS(syzstr->res[index])); |
---|
1642 | IDELEMS(syzstr->res[index]) = j+jj+1; |
---|
1643 | pEnlargeSet(&syzstr->orderedRes[index]->m,IDELEMS(syzstr->orderedRes[index]), |
---|
1644 | j+jj+1-IDELEMS(syzstr->orderedRes[index])); |
---|
1645 | IDELEMS(syzstr->orderedRes[index]) = j+jj+1; |
---|
1646 | } |
---|
1647 | for (k=0;k<jj;k++) |
---|
1648 | { |
---|
1649 | syzstr->res[index]->m[j+k] = add_generators->m[k]; |
---|
1650 | syzstr->orderedRes[index]->m[j+k] = add_repr->m[k]; |
---|
1651 | add_generators->m[k] = NULL; |
---|
1652 | add_repr->m[k] = NULL; |
---|
1653 | } |
---|
1654 | assume(idIs0(add_generators)); |
---|
1655 | assume(idIs0(add_repr)); |
---|
1656 | idDelete(&add_generators); |
---|
1657 | idDelete(&add_repr); |
---|
1658 | idDelete(&temp_generators); |
---|
1659 | idDelete(&temp_repr); |
---|
1660 | /*--- normalizing the rest to get the syzygies ------------------------*/ |
---|
1661 | return normalizeOldPart(new_generators,new_repr,syzstr,index,next_comp); |
---|
1662 | } |
---|
1663 | |
---|
1664 | /* |
---|
1665 | * this procedure assumes that the first order is C !!! |
---|
1666 | * INPUT: old_generators - the generators of the actual module |
---|
1667 | * computed so far (they are mixed vectors) |
---|
1668 | * old_repr - the representations of the old generators |
---|
1669 | * new_generators - generators coming from reductions below, |
---|
1670 | * they must have leading terms in new components |
---|
1671 | * (they live only in the module part) |
---|
1672 | * (*syzstr->Tl)[index] - the last used component in the syzygy |
---|
1673 | * OUTPUT: old_generators is updated |
---|
1674 | * new_generators is empty |
---|
1675 | * the return value is a set of new generators for the syzygies, |
---|
1676 | */ |
---|
1677 | static ideal syAppendSyz(ideal new_generators, syStrategy syzstr,int index,int crit_comp, |
---|
1678 | resolvente totake) |
---|
1679 | { |
---|
1680 | int i,j; |
---|
1681 | ideal result; |
---|
1682 | int rk_new_gens = id_RankFreeModule(new_generators,currRing); |
---|
1683 | if (syzstr->res[index]==NULL) |
---|
1684 | { |
---|
1685 | syzstr->res[index] = idInit(1,si_max(rk_new_gens,1)); |
---|
1686 | syzstr->orderedRes[index] = idInit(1,si_max(rk_new_gens,1)); |
---|
1687 | } |
---|
1688 | int ng_idel=IDELEMS(new_generators); |
---|
1689 | ideal new_repr =idInit(ng_idel, crit_comp+ng_idel); |
---|
1690 | |
---|
1691 | if (index==0) |
---|
1692 | { |
---|
1693 | //int * og_l=(int*)omAlloc0(IDELEMS(syzstr->res[0])*sizeof(int)); |
---|
1694 | //for (i=IDELEMS(syzstr->res[0])-1;i>=0;i--) |
---|
1695 | //{ |
---|
1696 | //if (syzstr->res[0]->m[i]!=NULL) |
---|
1697 | //og_l[i] = pLength(syzstr->res[0]->m[i]); |
---|
1698 | //} |
---|
1699 | for (i=0;i<ng_idel;i++) |
---|
1700 | { |
---|
1701 | if (new_generators->m[i]!=NULL) |
---|
1702 | { |
---|
1703 | //int ng_l=pLength(new_generators->m[i]); |
---|
1704 | //new_generators->m[i] = syRedTailSyz(new_generators->m[i],syzstr->res[0],NULL,0,syzstr, |
---|
1705 | //og_l,NULL,&ng_l); |
---|
1706 | if (totake[index]==NULL) |
---|
1707 | totake[index] = idInit(16,new_generators->rank); |
---|
1708 | if ((*syzstr->Tl)[index]>=IDELEMS(totake[index])) |
---|
1709 | { |
---|
1710 | pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]), |
---|
1711 | (*syzstr->Tl)[index]+16-IDELEMS(totake[index])); |
---|
1712 | for (j=IDELEMS(totake[index]);j<(*syzstr->Tl)[index]+16;j++) |
---|
1713 | totake[index]->m[j] = NULL; |
---|
1714 | IDELEMS(totake[index]) = (*syzstr->Tl)[index]+16; |
---|
1715 | } |
---|
1716 | #ifdef FULL_TOTAKE |
---|
1717 | totake[index]->m[(*syzstr->Tl)[index]] = pCopy(new_generators->m[i]); |
---|
1718 | #else |
---|
1719 | totake[index]->m[(*syzstr->Tl)[index]] = pHead(new_generators->m[i]); |
---|
1720 | #endif |
---|
1721 | #ifdef WITH_SCHREYER_ORD |
---|
1722 | new_repr->m[i] = pHead(new_generators->m[i]); |
---|
1723 | #else |
---|
1724 | new_repr->m[i] = pOne(); |
---|
1725 | #endif |
---|
1726 | ((*syzstr->Tl)[index])++; |
---|
1727 | pSetComp(new_repr->m[i],(*syzstr->Tl)[index]); |
---|
1728 | pSetmComp(new_repr->m[i]); |
---|
1729 | } |
---|
1730 | } |
---|
1731 | //omFreeSize((ADDRESS)og_l,IDELEMS(syzstr->res[0])*sizeof(int)); |
---|
1732 | #ifdef SHOW_PROT |
---|
1733 | PrintS("Add new generators:\n"); |
---|
1734 | idPrint(new_generators); |
---|
1735 | PrintS("with representaions:\n"); |
---|
1736 | idPrint(new_repr); |
---|
1737 | #endif |
---|
1738 | result = kosz_std(new_generators,new_repr,syzstr,index,crit_comp); |
---|
1739 | } |
---|
1740 | else |
---|
1741 | { |
---|
1742 | result = kosz_ext(new_generators,new_repr,syzstr,index,crit_comp,totake); |
---|
1743 | } |
---|
1744 | idSkipZeroes(result); |
---|
1745 | assume(idIs0(new_repr)); |
---|
1746 | idDelete(&new_repr); |
---|
1747 | return result; |
---|
1748 | } |
---|
1749 | |
---|
1750 | /* |
---|
1751 | * main call of the extended Koszul-resolution |
---|
1752 | */ |
---|
1753 | syStrategy syKosz(ideal arg,int * length) |
---|
1754 | { |
---|
1755 | int i,j,jj,k=0,index=0,rk_arg,next_syz=0; |
---|
1756 | int crit_comp,t_comp,next_deg,old_tl; |
---|
1757 | ideal temp=NULL,old_ideal,old_repr; |
---|
1758 | ring origR = currRing; |
---|
1759 | poly next_gen; |
---|
1760 | BOOLEAN isRegular; |
---|
1761 | |
---|
1762 | discard_pairs = 0; |
---|
1763 | short_pairs = 0; |
---|
1764 | if (idIs0(arg)) return NULL; |
---|
1765 | rk_arg = id_RankFreeModule(arg,currRing); |
---|
1766 | syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy)); |
---|
1767 | /*--- changes to a Cdp-ring ----------------------------*/ |
---|
1768 | syzstr->syRing = rAssure_C_dp(origR); rChangeCurrRing(syzstr->syRing); |
---|
1769 | /*--- initializes the data structures---------------*/ |
---|
1770 | syzstr->length = *length = (syzstr->syRing->N)+2; |
---|
1771 | syzstr->regularity = -1; |
---|
1772 | if (origR!=syzstr->syRing) |
---|
1773 | temp = idrCopyR(arg, origR, syzstr->syRing); |
---|
1774 | else |
---|
1775 | temp = idCopy(arg); |
---|
1776 | if (rk_arg==0) |
---|
1777 | { |
---|
1778 | for (j=0;j<IDELEMS(temp);j++) |
---|
1779 | { |
---|
1780 | if (temp->m[j]!=NULL) |
---|
1781 | p_Shift(&temp->m[j],1,currRing); |
---|
1782 | } |
---|
1783 | } |
---|
1784 | idSkipZeroes(temp); |
---|
1785 | #ifdef WITH_SORT |
---|
1786 | if (temp->m[0]!=NULL) |
---|
1787 | { |
---|
1788 | int md; |
---|
1789 | int maxdeg=p_FDeg(temp->m[IDELEMS(temp)-1],currRing); |
---|
1790 | ideal temp1=idInit(IDELEMS(temp),temp->rank); |
---|
1791 | for (j=IDELEMS(temp)-2;j>=0;j--) |
---|
1792 | { |
---|
1793 | jj = p_FDeg(temp->m[j],currRing); |
---|
1794 | if (jj>maxdeg) maxdeg = jj; |
---|
1795 | } |
---|
1796 | while (!idIs0(temp)) |
---|
1797 | { |
---|
1798 | md = maxdeg; |
---|
1799 | for (j=IDELEMS(temp)-1;j>=0;j--) |
---|
1800 | { |
---|
1801 | if (temp->m[j]!=NULL) |
---|
1802 | { |
---|
1803 | jj = p_FDeg(temp->m[j],currRing); |
---|
1804 | if (jj<md) md = jj; |
---|
1805 | } |
---|
1806 | } |
---|
1807 | for (j=0;j<IDELEMS(temp);j++) |
---|
1808 | { |
---|
1809 | if ((temp->m[j]!=NULL) && (p_FDeg(temp->m[j],currRing)==md)) |
---|
1810 | { |
---|
1811 | temp1->m[k] = temp->m[j]; |
---|
1812 | temp->m[j] = NULL; |
---|
1813 | k++; |
---|
1814 | } |
---|
1815 | } |
---|
1816 | } |
---|
1817 | idDelete(&temp); |
---|
1818 | temp = temp1; |
---|
1819 | temp1 = NULL; |
---|
1820 | } |
---|
1821 | #endif |
---|
1822 | #ifdef USE_REGULARITY |
---|
1823 | int last_generator=IDELEMS(temp)-1; |
---|
1824 | while ((last_generator>=0) && (temp->m[last_generator]==NULL)) |
---|
1825 | last_generator--; |
---|
1826 | #endif |
---|
1827 | syzstr->res = (resolvente)omAlloc0((*length+1)*sizeof(ideal)); |
---|
1828 | syzstr->orderedRes = (resolvente)omAlloc0((*length+1)*sizeof(ideal)); |
---|
1829 | resolvente totake=(resolvente)omAlloc0((*length+1)*sizeof(ideal)); |
---|
1830 | syzstr->Tl = new intvec(*length+1); |
---|
1831 | syzstr->bucket = kBucketCreate(currRing); |
---|
1832 | syzstr->syz_bucket = kBucketCreate(currRing); |
---|
1833 | ideal new_generators=idInit(1,si_max(rk_arg,1)); |
---|
1834 | ideal temp_gens,old_std; |
---|
1835 | syzstr->res[0] = idInit(1,1); |
---|
1836 | if (rk_arg>1) syzstr->res[0]->rank = rk_arg; |
---|
1837 | syzstr->orderedRes[0] = idInit(1,1); |
---|
1838 | /*--- computes the resolution ----------------------*/ |
---|
1839 | i = 0; |
---|
1840 | while (i<IDELEMS(temp)) |
---|
1841 | { |
---|
1842 | if (temp->m[i]!=NULL) |
---|
1843 | { |
---|
1844 | new_generators->m[0] = kNF(syzstr->res[0],currQuotient,temp->m[i]); |
---|
1845 | if (!nIsOne(pGetCoeff(new_generators->m[0]))) |
---|
1846 | pNorm(new_generators->m[0]); |
---|
1847 | next_deg = p_FDeg(new_generators->m[0],currRing); |
---|
1848 | next_gen = pCopy(new_generators->m[0]); |
---|
1849 | } |
---|
1850 | if (!idIs0(new_generators)) |
---|
1851 | { |
---|
1852 | index = 0; |
---|
1853 | while (index<=*length) |
---|
1854 | { |
---|
1855 | if (index==0) |
---|
1856 | { |
---|
1857 | old_ideal = idCopy(syzstr->res[0]); |
---|
1858 | old_repr = idCopy(syzstr->orderedRes[0]); |
---|
1859 | old_tl = (*syzstr->Tl)[0]; |
---|
1860 | old_std = id_Head(syzstr->res[0],currRing); |
---|
1861 | } |
---|
1862 | t_comp = (*syzstr->Tl)[index]; |
---|
1863 | if (index==0) crit_comp = t_comp; |
---|
1864 | temp_gens = syAppendSyz(new_generators,syzstr, index,crit_comp,totake); |
---|
1865 | crit_comp = t_comp; |
---|
1866 | if (index==0) |
---|
1867 | { |
---|
1868 | isRegular = syIsRegular(old_std,syzstr->res[0],next_deg); |
---|
1869 | #ifndef ONLY_STD |
---|
1870 | if (isRegular) |
---|
1871 | syCreateRegularExtension(syzstr,old_ideal,old_repr,old_tl,next_gen, |
---|
1872 | totake); |
---|
1873 | #ifdef USE_REGULARITY |
---|
1874 | if ((index==0) && (!isRegular) && (i==last_generator)) |
---|
1875 | { |
---|
1876 | /*----------- we are computing the regularity -----------------------*/ |
---|
1877 | ideal initial=id_Head(syzstr->res[0],currRing); |
---|
1878 | int len=0,reg=0; |
---|
1879 | intvec *w=NULL; |
---|
1880 | ring dp_C_ring = rAssure_dp_C(currRing); rChangeCurrRing(dp_C_ring); |
---|
1881 | initial = idrMoveR_NoSort(initial, syzstr->syRing, dp_C_ring); |
---|
1882 | resolvente res = sySchreyerResolvente(initial,-1,&len,TRUE, TRUE); |
---|
1883 | intvec * dummy = syBetti(res,len,®, w); |
---|
1884 | syzstr->regularity = reg+2; |
---|
1885 | delete dummy; |
---|
1886 | delete w; |
---|
1887 | for (j=0;j<len;j++) |
---|
1888 | { |
---|
1889 | if (res[j]!=NULL) idDelete(&(res[j])); |
---|
1890 | } |
---|
1891 | omFreeSize((ADDRESS)res,len*sizeof(ideal)); |
---|
1892 | idDelete(&initial); |
---|
1893 | rChangeCurrRing(syzstr->syRing); |
---|
1894 | rDelete(dp_C_ring); |
---|
1895 | } |
---|
1896 | #endif |
---|
1897 | #endif |
---|
1898 | idDelete(&old_ideal); |
---|
1899 | idDelete(&old_repr); |
---|
1900 | idDelete(&old_std); |
---|
1901 | if (TEST_OPT_PROT) |
---|
1902 | { |
---|
1903 | if (isRegular) |
---|
1904 | PrintS("\n regular\n"); |
---|
1905 | else |
---|
1906 | PrintS("\n not regular\n"); |
---|
1907 | } |
---|
1908 | if (next_gen!=NULL) |
---|
1909 | pDelete(&next_gen); |
---|
1910 | if (isRegular) |
---|
1911 | { |
---|
1912 | idDelete(&temp_gens); |
---|
1913 | break; |
---|
1914 | } |
---|
1915 | } |
---|
1916 | idDelete(&new_generators); |
---|
1917 | new_generators = temp_gens; |
---|
1918 | #ifdef ONLY_STD |
---|
1919 | break; |
---|
1920 | #endif |
---|
1921 | if (idIs0(new_generators)) break; |
---|
1922 | index++; |
---|
1923 | } |
---|
1924 | if (!idIs0(new_generators)) |
---|
1925 | { |
---|
1926 | for (j=0;j<IDELEMS(new_generators);j++) |
---|
1927 | { |
---|
1928 | if (new_generators->m[j]!=NULL) |
---|
1929 | { |
---|
1930 | pDelete(&new_generators->m[j]); |
---|
1931 | new_generators->m[j] = NULL; |
---|
1932 | } |
---|
1933 | } |
---|
1934 | } |
---|
1935 | } |
---|
1936 | i++; |
---|
1937 | } |
---|
1938 | if (idIs0(new_generators) && new_generators!=NULL) idDelete(&new_generators); |
---|
1939 | if (temp!=NULL) idDelete(&temp); |
---|
1940 | kBucketDestroy(&(syzstr->bucket)); |
---|
1941 | kBucketDestroy(&(syzstr->syz_bucket)); |
---|
1942 | index = 0; |
---|
1943 | syzstr->fullres = syzstr->res; |
---|
1944 | syzstr->res = NULL; |
---|
1945 | index = 0; |
---|
1946 | while ((index<=*length) && (syzstr->fullres[index]!=NULL)) |
---|
1947 | { |
---|
1948 | #ifdef SHOW_RESULT |
---|
1949 | Print("The %d-th syzygy-module is now:\n",index); |
---|
1950 | ideal ttt=id_Head(syzstr->fullres[index],currRing); |
---|
1951 | idShow(ttt); |
---|
1952 | idDelete(&ttt); |
---|
1953 | //if (index>0) |
---|
1954 | //{ |
---|
1955 | //Print("The related module is: \n"); |
---|
1956 | //idPrint(totake[index-1]); |
---|
1957 | //} |
---|
1958 | //Print("The %d-th module of the minimal resolution is:\n",index); |
---|
1959 | if (!idIs0(totake[index])) |
---|
1960 | idShow(totake[index]); |
---|
1961 | //Print("with standard basis:\n"); |
---|
1962 | //idPrint(syzstr->fullres[index]); |
---|
1963 | //if ((index<*length) && (totake[index+1]!=NULL)) |
---|
1964 | //{ |
---|
1965 | //Print("The %d-th syzygy-module is now:\n",index+1); |
---|
1966 | //idPrint(totake[index+1]); |
---|
1967 | //matrix m1=idModule2Matrix(totake[index]); |
---|
1968 | //matrix m2=idModule2Matrix(totake[index+1]); |
---|
1969 | //matrix m3=mpMult(m1,m2); |
---|
1970 | //idPrint((ideal)m3); |
---|
1971 | //} |
---|
1972 | #endif |
---|
1973 | if (!idIs0(totake[index])) |
---|
1974 | { |
---|
1975 | for(i=0;i<IDELEMS(totake[index]);i++) |
---|
1976 | { |
---|
1977 | if (totake[index]->m[i]!=NULL) |
---|
1978 | { |
---|
1979 | j=0; |
---|
1980 | while ((j<IDELEMS(syzstr->fullres[index])) && |
---|
1981 | ((syzstr->fullres[index]->m[j]==NULL) || |
---|
1982 | (!pLmEqual(syzstr->fullres[index]->m[j],totake[index]->m[i])))) j++; |
---|
1983 | if (j<IDELEMS(syzstr->fullres[index])) |
---|
1984 | { |
---|
1985 | pDelete(&totake[index]->m[i]); |
---|
1986 | totake[index]->m[i] = syzstr->fullres[index]->m[j]; |
---|
1987 | syzstr->fullres[index]->m[j] = NULL; |
---|
1988 | } |
---|
1989 | else |
---|
1990 | { |
---|
1991 | PrintS("Da ist was faul!!!\n"); |
---|
1992 | Print("Aber: Regularitaet %d, Grad %ld\n", |
---|
1993 | syzstr->regularity,p_FDeg(totake[index]->m[i],currRing)); |
---|
1994 | } |
---|
1995 | } |
---|
1996 | } |
---|
1997 | idDelete(&syzstr->fullres[index]); |
---|
1998 | syzstr->fullres[index] = totake[index]; |
---|
1999 | } |
---|
2000 | #ifdef SHOW_RESULT |
---|
2001 | idShow(syzstr->fullres[index]); |
---|
2002 | #endif |
---|
2003 | index++; |
---|
2004 | } |
---|
2005 | syReorder_Kosz(syzstr); |
---|
2006 | index = 0; |
---|
2007 | while ((index<=*length) && (syzstr->orderedRes[index]!=NULL)) |
---|
2008 | { |
---|
2009 | idDelete(&(syzstr->orderedRes[index])); |
---|
2010 | index++; |
---|
2011 | } |
---|
2012 | if (origR!=syzstr->syRing) |
---|
2013 | { |
---|
2014 | rChangeCurrRing(origR); |
---|
2015 | index = 0; |
---|
2016 | while ((index<=*length) && (syzstr->fullres[index]!=NULL)) |
---|
2017 | { |
---|
2018 | syzstr->fullres[index] = idrMoveR(syzstr->fullres[index],syzstr->syRing, origR); |
---|
2019 | index++; |
---|
2020 | } |
---|
2021 | } |
---|
2022 | delete syzstr->Tl; |
---|
2023 | syzstr->Tl = NULL; |
---|
2024 | rDelete(syzstr->syRing); |
---|
2025 | syzstr->syRing = NULL; |
---|
2026 | omFreeSize((ADDRESS)totake,(*length+1)*sizeof(ideal)); |
---|
2027 | omFreeSize((ADDRESS)syzstr->orderedRes,(*length+1)*sizeof(ideal)); |
---|
2028 | //Print("Pairs to discard: %d\n",discard_pairs); |
---|
2029 | //Print("Pairs shorter reduced: %d\n",short_pairs); |
---|
2030 | //discard_pairs = 0; |
---|
2031 | //short_pairs = 0; |
---|
2032 | return syzstr; |
---|
2033 | } |
---|
2034 | |
---|