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