[35aab3] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
[85e68dd] | 4 | /* $Id: syz1.cc,v 1.13 2008-03-19 17:44:12 Singular Exp $ */ |
---|
[35aab3] | 5 | /* |
---|
| 6 | * ABSTRACT: resolutions |
---|
| 7 | */ |
---|
| 8 | |
---|
| 9 | #include "mod2.h" |
---|
| 10 | #include <mylimits.h> |
---|
| 11 | #include "structs.h" |
---|
| 12 | #include "omalloc.h" |
---|
| 13 | #include "polys.h" |
---|
| 14 | #include "febase.h" |
---|
| 15 | #include "kstd1.h" |
---|
| 16 | #include "kutil.h" |
---|
| 17 | #include "stairc.h" |
---|
[f599636] | 18 | //#include "cntrlc.h" |
---|
[35aab3] | 19 | #include "intvec.h" |
---|
| 20 | #include "numbers.h" |
---|
| 21 | #include "modulop.h" |
---|
| 22 | #include "ideals.h" |
---|
| 23 | #include "intvec.h" |
---|
| 24 | #include "ring.h" |
---|
| 25 | #include "syz.h" |
---|
| 26 | #include "kbuckets.h" |
---|
| 27 | #include "prCopy.h" |
---|
| 28 | |
---|
| 29 | extern void p_Setm_Syz(poly p, ring r, |
---|
| 30 | int* Components, long* ShiftedComponents); |
---|
| 31 | |
---|
| 32 | /*--------------static variables------------------------*/ |
---|
| 33 | /*---points to the real components, shifted of the actual module-*/ |
---|
| 34 | int * currcomponents=NULL; |
---|
| 35 | long * currShiftedComponents=NULL; |
---|
| 36 | |
---|
| 37 | |
---|
| 38 | /*---head-term-polynomials for the reduction------------*/ |
---|
| 39 | static poly redpol=NULL; |
---|
| 40 | /*---counts number of applications of GM-criteria-------*/ |
---|
| 41 | //static int crit; |
---|
| 42 | //static int euler; |
---|
| 43 | |
---|
| 44 | /*3 |
---|
| 45 | * deletes all entres of a pair |
---|
| 46 | */ |
---|
| 47 | void syDeletePair(SObject * so) |
---|
| 48 | { |
---|
| 49 | pDelete(&(*so).p); |
---|
| 50 | pDelete(&(*so).lcm); |
---|
| 51 | pDelete(&(*so).syz); |
---|
| 52 | (*so).p1 = NULL; |
---|
| 53 | (*so).p2 = NULL; |
---|
| 54 | (*so).ind1 = 0; |
---|
| 55 | (*so).ind2 = 0; |
---|
| 56 | (*so).syzind = -1; |
---|
| 57 | (*so).order = 0; |
---|
| 58 | (*so).isNotMinimal = NULL; |
---|
| 59 | (*so).length = -1; |
---|
| 60 | (*so).reference = -1; |
---|
| 61 | } |
---|
| 62 | |
---|
| 63 | /*3 |
---|
| 64 | * initializes all entres of a pair |
---|
| 65 | */ |
---|
| 66 | void syInitializePair(SObject * so) |
---|
| 67 | { |
---|
| 68 | (*so).p = NULL; |
---|
| 69 | (*so).lcm = NULL; |
---|
| 70 | (*so).syz = NULL; |
---|
| 71 | (*so).p1 = NULL; |
---|
| 72 | (*so).p2 = NULL; |
---|
| 73 | (*so).ind1 = 0; |
---|
| 74 | (*so).ind2 = 0; |
---|
| 75 | (*so).syzind = -1; |
---|
| 76 | (*so).order = 0; |
---|
| 77 | (*so).isNotMinimal = NULL; |
---|
| 78 | (*so).length = -1; |
---|
| 79 | (*so).reference = -1; |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | /*3 |
---|
| 83 | * puts all entres of a pair to another |
---|
| 84 | */ |
---|
| 85 | void syCopyPair(SObject * argso, SObject * imso) |
---|
| 86 | { |
---|
| 87 | *imso=*argso; |
---|
| 88 | (*argso).p = NULL; |
---|
| 89 | (*argso).p1 = NULL; |
---|
| 90 | (*argso).p2 = NULL; |
---|
| 91 | (*argso).lcm = NULL; |
---|
| 92 | (*argso).syz = NULL; |
---|
| 93 | (*argso).ind1 = 0; |
---|
| 94 | (*argso).ind2 = 0; |
---|
| 95 | (*argso).syzind = -1; |
---|
| 96 | (*argso).order = 0; |
---|
| 97 | (*argso).isNotMinimal = NULL; |
---|
| 98 | (*argso).length = -1; |
---|
| 99 | (*argso).reference = -1; |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | /*3 |
---|
| 103 | * deletes empty objects from a pair set beginning with |
---|
| 104 | * pair first |
---|
| 105 | * assumes a pair to be empty if .lcm does so |
---|
| 106 | */ |
---|
| 107 | void syCompactifyPairSet(SSet sPairs, int sPlength, int first) |
---|
| 108 | { |
---|
| 109 | int k=first,kk=0; |
---|
| 110 | |
---|
| 111 | while (k+kk<sPlength) |
---|
| 112 | { |
---|
| 113 | if (sPairs[k+kk].lcm!=NULL) |
---|
| 114 | { |
---|
| 115 | if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]); |
---|
| 116 | k++; |
---|
| 117 | } |
---|
| 118 | else |
---|
| 119 | { |
---|
| 120 | kk++; |
---|
| 121 | } |
---|
| 122 | } |
---|
| 123 | while (k<sPlength) |
---|
| 124 | { |
---|
| 125 | syInitializePair(&sPairs[k]); |
---|
| 126 | k++; |
---|
| 127 | } |
---|
| 128 | } |
---|
| 129 | |
---|
| 130 | /*3 |
---|
| 131 | * deletes empty objects from a pair set beginning with |
---|
| 132 | * pair first |
---|
| 133 | * assumes a pair to be empty if .lcm does so |
---|
| 134 | */ |
---|
| 135 | void syCompactify1(SSet sPairs, int* sPlength, int first) |
---|
| 136 | { |
---|
| 137 | int k=first,kk=0; |
---|
| 138 | |
---|
| 139 | while (k+kk<*sPlength) |
---|
| 140 | { |
---|
| 141 | if (sPairs[k+kk].lcm!=NULL) |
---|
| 142 | { |
---|
| 143 | if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]); |
---|
| 144 | k++; |
---|
| 145 | } |
---|
| 146 | else |
---|
| 147 | { |
---|
| 148 | kk++; |
---|
| 149 | } |
---|
| 150 | } |
---|
| 151 | while (k<*sPlength) |
---|
| 152 | { |
---|
| 153 | syInitializePair(&sPairs[k]); |
---|
| 154 | k++; |
---|
| 155 | } |
---|
| 156 | *sPlength -= kk; |
---|
| 157 | } |
---|
| 158 | |
---|
| 159 | /*3 |
---|
| 160 | * replaces comp1dpc during homogeneous syzygy-computations |
---|
| 161 | * compares with components of currcomponents instead of the |
---|
| 162 | * exp[0] |
---|
| 163 | */ |
---|
| 164 | static int syzcomp0dpc(poly p1, poly p2) |
---|
| 165 | { |
---|
| 166 | /*4 compare monomials by order then revlex*/ |
---|
| 167 | int i = pVariables; |
---|
| 168 | if ((pGetExp(p1,i) == pGetExp(p2,i))) |
---|
| 169 | { |
---|
| 170 | do |
---|
| 171 | { |
---|
| 172 | i--; |
---|
| 173 | if (i <= 1) |
---|
| 174 | { |
---|
| 175 | /*4 handle module case:*/ |
---|
| 176 | if (pGetComp(p1)==pGetComp(p2)) return 0; |
---|
| 177 | else if |
---|
| 178 | (currcomponents[pGetComp(p1)]>currcomponents[pGetComp(p2)]) |
---|
| 179 | return 1; |
---|
| 180 | else return -1; |
---|
| 181 | } |
---|
| 182 | } while ((pGetExp(p1,i) == pGetExp(p2,i))); |
---|
| 183 | } |
---|
| 184 | if (pGetExp(p1,i) < pGetExp(p2,i)) return 1; |
---|
| 185 | return -1; |
---|
| 186 | } |
---|
| 187 | |
---|
| 188 | /*3 |
---|
| 189 | * replaces comp1dpc during homogeneous syzygy-computations |
---|
| 190 | * compares with components of currcomponents instead of the |
---|
| 191 | * exp[0] |
---|
| 192 | */ |
---|
| 193 | int syzcomp1dpc(poly p1, poly p2) |
---|
| 194 | { |
---|
| 195 | int i = pVariables; |
---|
| 196 | while ((i>1) && (pGetExp(p1,i)==pGetExp(p2,i))) |
---|
| 197 | i--; |
---|
| 198 | if (i>1) |
---|
| 199 | { |
---|
| 200 | if (pGetExp(p1,i) < pGetExp(p2,i)) return 1; |
---|
| 201 | return -1; |
---|
| 202 | } |
---|
| 203 | int o1=pGetComp(p1); |
---|
| 204 | int o2=pGetComp(p2); |
---|
| 205 | if (o1==o2/*pGetComp(p1)==pGetComp(p2)*/) return 0; |
---|
| 206 | if (currcomponents[o1]>currcomponents[o2]) return 1; |
---|
| 207 | return -1; |
---|
| 208 | |
---|
| 209 | } |
---|
| 210 | |
---|
| 211 | /*3 |
---|
| 212 | * replaces comp1dpc during homogeneous syzygy-computations |
---|
| 213 | * compares with components of currcomponents instead of the |
---|
| 214 | * exp[0] |
---|
| 215 | */ |
---|
| 216 | |
---|
| 217 | #ifdef PDEBUG |
---|
| 218 | static int syzcomp2dpc_test(poly p1, poly p2) |
---|
| 219 | { |
---|
| 220 | long c1, c2, cc1, cc2, ccc1, ccc2, ec1, ec2; |
---|
| 221 | c1 = pGetComp(p1); |
---|
| 222 | c2 = pGetComp(p2); |
---|
| 223 | cc1 = currcomponents[c1]; |
---|
| 224 | cc2 = currcomponents[c2]; |
---|
| 225 | ccc1 = currShiftedComponents[cc1]; |
---|
| 226 | ccc2 = currShiftedComponents[cc2]; |
---|
| 227 | ec1 = p1->exp[currRing->typ[1].data.syzcomp.place]; |
---|
| 228 | ec2 = p2->exp[currRing->typ[1].data.syzcomp.place]; |
---|
| 229 | |
---|
| 230 | if (ec1 != ccc1) |
---|
| 231 | { |
---|
| 232 | Warn("Shifted comp of p1 out of sync. should %d, is %d", ccc1, ec1); |
---|
| 233 | //mmDBInfoBlock(p1); |
---|
| 234 | } |
---|
| 235 | if (ec2 != ccc2) |
---|
| 236 | { |
---|
| 237 | Warn("Shifted comp of p2 out of sync. should %d, is %d", ccc2, ec2); |
---|
| 238 | //mmDBInfoBlock(p2); |
---|
| 239 | } |
---|
| 240 | |
---|
| 241 | if (c1 == c2) |
---|
| 242 | { |
---|
| 243 | assume(ccc1 == ccc2); |
---|
| 244 | } |
---|
| 245 | else if (cc1 > cc2) |
---|
| 246 | { |
---|
| 247 | assume(ccc1 > ccc2); |
---|
| 248 | } |
---|
| 249 | else |
---|
| 250 | { |
---|
| 251 | assume (cc1 < cc2); |
---|
| 252 | assume (ccc1 < ccc2); |
---|
| 253 | } |
---|
| 254 | int o1=pGetOrder(p1), o2=pGetOrder(p2); |
---|
| 255 | if (o1 > o2) return 1; |
---|
| 256 | if (o1 < o2) return -1; |
---|
| 257 | |
---|
| 258 | //if (o1>0) |
---|
| 259 | { |
---|
| 260 | int i = pVariables; |
---|
| 261 | while ((i>1) && (pGetExp(p1,i)==pGetExp(p2,i))) |
---|
| 262 | i--; |
---|
| 263 | //(*orderingdepth)[pVariables-i]++; |
---|
| 264 | if (i>1) |
---|
| 265 | { |
---|
| 266 | if (pGetExp(p1,i) < pGetExp(p2,i)) return 1; |
---|
| 267 | return -1; |
---|
| 268 | } |
---|
| 269 | } |
---|
| 270 | o1=pGetComp(p1); |
---|
| 271 | o2=pGetComp(p2); |
---|
| 272 | if (o1==o2/*pGetComp(p1)==pGetComp(p2)*/) return 0; |
---|
| 273 | if (currcomponents[o1]>currcomponents[o2]) return 1; |
---|
| 274 | return -1; |
---|
| 275 | } |
---|
| 276 | #endif // PDEBUG |
---|
| 277 | |
---|
| 278 | /*3 |
---|
| 279 | * compares only the monomial without component |
---|
| 280 | */ |
---|
| 281 | static int syzcompmonomdp(poly p1, poly p2) |
---|
| 282 | { |
---|
| 283 | int i; |
---|
| 284 | |
---|
| 285 | /*4 compare monomials by order then revlex*/ |
---|
| 286 | if (pGetOrder(p1) == pGetOrder(p2)) |
---|
| 287 | { |
---|
| 288 | i = pVariables; |
---|
| 289 | if ((pGetExp(p1,i) == pGetExp(p2,i))) |
---|
| 290 | { |
---|
| 291 | do |
---|
| 292 | { |
---|
| 293 | i--; |
---|
| 294 | if (i <= 1) |
---|
| 295 | return 0; |
---|
| 296 | } while ((pGetExp(p1,i) == pGetExp(p2,i))); |
---|
| 297 | } |
---|
| 298 | if (pGetExp(p1,i) < pGetExp(p2,i)) return 1; |
---|
| 299 | return -1; |
---|
| 300 | } |
---|
| 301 | else if (pGetOrder(p1) > pGetOrder(p2)) return 1; |
---|
| 302 | return -1; |
---|
| 303 | } |
---|
| 304 | |
---|
| 305 | poly syRedtail (poly p, syStrategy syzstr, int index) |
---|
| 306 | { |
---|
| 307 | poly h, hn; |
---|
| 308 | int j,pos; |
---|
| 309 | ideal redWith=syzstr->orderedRes[index]; |
---|
| 310 | |
---|
| 311 | h = p; |
---|
| 312 | hn = pNext(h); |
---|
| 313 | while(hn != NULL) |
---|
| 314 | { |
---|
| 315 | j = syzstr->Firstelem[index-1][pGetComp(hn)]-1; |
---|
| 316 | if (j>=0) |
---|
| 317 | { |
---|
| 318 | pos = j+syzstr->Howmuch[index-1][pGetComp(hn)]; |
---|
| 319 | while (j < pos) |
---|
| 320 | { |
---|
| 321 | if (pLmDivisibleByNoComp(redWith->m[j], hn)) |
---|
| 322 | { |
---|
| 323 | //hn = sySPolyRed(hn,redWith->m[j]); |
---|
| 324 | hn = ksOldSpolyRed(redWith->m[j],hn); |
---|
| 325 | if (hn == NULL) |
---|
| 326 | { |
---|
| 327 | pNext(h) = NULL; |
---|
| 328 | return p; |
---|
| 329 | } |
---|
| 330 | j = syzstr->Firstelem[index-1][pGetComp(hn)]-1; |
---|
| 331 | pos = j+syzstr->Howmuch[index-1][pGetComp(hn)]; |
---|
| 332 | } |
---|
| 333 | else |
---|
| 334 | { |
---|
| 335 | j++; |
---|
| 336 | } |
---|
| 337 | } |
---|
| 338 | } |
---|
| 339 | h = pNext(h) = hn; |
---|
| 340 | hn = pNext(h); |
---|
| 341 | } |
---|
| 342 | return p; |
---|
| 343 | } |
---|
| 344 | |
---|
| 345 | |
---|
| 346 | /*3 |
---|
| 347 | * local procedure for of syInitRes for the module case |
---|
| 348 | */ |
---|
| 349 | static int syChMin(intvec * iv) |
---|
| 350 | { |
---|
| 351 | int i,j=-1,r=-1; |
---|
| 352 | |
---|
| 353 | for (i=iv->length()-1;i>=0;i--) |
---|
| 354 | { |
---|
| 355 | if ((*iv)[i]>=0) |
---|
| 356 | { |
---|
| 357 | if ((j<0) || ((*iv)[i]<j)) |
---|
| 358 | { |
---|
| 359 | j = (*iv)[i]; |
---|
| 360 | r = i; |
---|
| 361 | } |
---|
| 362 | } |
---|
| 363 | } |
---|
| 364 | return r; |
---|
| 365 | } |
---|
| 366 | |
---|
| 367 | /*3 |
---|
| 368 | * initialize the resolution and puts in the argument as |
---|
| 369 | * zeroth entre, length must be > 0 |
---|
| 370 | * assumes that the basering is degree-compatible |
---|
| 371 | */ |
---|
| 372 | SRes syInitRes(ideal arg,int * length, intvec * Tl, intvec * cw) |
---|
| 373 | { |
---|
| 374 | if (idIs0(arg)) return NULL; |
---|
| 375 | SRes resPairs = (SRes)omAlloc0(*length*sizeof(SSet)); |
---|
| 376 | resPairs[0] = (SSet)omAlloc0(IDELEMS(arg)*sizeof(SObject)); |
---|
| 377 | intvec * iv=NULL; |
---|
| 378 | int i,j; |
---|
| 379 | |
---|
| 380 | if (idRankFreeModule(arg)==0) |
---|
| 381 | { |
---|
| 382 | iv = idSort(arg); |
---|
| 383 | for (i=0;i<IDELEMS(arg);i++) |
---|
| 384 | { |
---|
| 385 | (resPairs[0])[i].syz = /*pCopy*/(arg->m[(*iv)[i]-1]); |
---|
| 386 | arg->m[(*iv)[i]-1] = NULL; |
---|
| 387 | (resPairs[0])[i].order = pTotaldegree((resPairs[0])[i].syz); |
---|
| 388 | } |
---|
| 389 | } |
---|
| 390 | else |
---|
| 391 | { |
---|
| 392 | iv = new intvec(IDELEMS(arg),1,-1); |
---|
| 393 | for (i=0;i<IDELEMS(arg);i++) |
---|
| 394 | { |
---|
| 395 | (*iv)[i] = pTotaldegree(arg->m[i])+(*cw)[pGetComp(arg->m[i])-1]; |
---|
| 396 | } |
---|
| 397 | for (i=0;i<IDELEMS(arg);i++) |
---|
| 398 | { |
---|
| 399 | j = syChMin(iv); |
---|
| 400 | if (j<0) break; |
---|
| 401 | (resPairs[0])[i].syz = arg->m[j]; |
---|
| 402 | arg->m[j] = NULL; |
---|
| 403 | (resPairs[0])[i].order = (*iv)[j]; |
---|
| 404 | (*iv)[j] = -1; |
---|
| 405 | } |
---|
| 406 | } |
---|
| 407 | if (iv!=NULL) delete iv; |
---|
| 408 | (*Tl)[0] = IDELEMS(arg); |
---|
| 409 | return resPairs; |
---|
| 410 | } |
---|
| 411 | |
---|
| 412 | // rearrange shifted components |
---|
| 413 | long syReorderShiftedComponents(long * sc, int n) |
---|
| 414 | { |
---|
| 415 | long holes = 0; |
---|
| 416 | int i; |
---|
| 417 | long new_comps = 0, new_space, max; |
---|
| 418 | |
---|
| 419 | // count number of holes |
---|
| 420 | for (i=1; i<n; i++) |
---|
| 421 | { |
---|
| 422 | if (sc[i-1] + 1 < sc[i]) holes++; |
---|
| 423 | } |
---|
| 424 | |
---|
| 425 | if (LONG_MAX - SYZ_SHIFT_BASE <= sc[n-1]) |
---|
| 426 | { |
---|
| 427 | // need new components |
---|
| 428 | new_comps = (((long) 1) << SYZ_SHIFT_MAX_NEW_COMP_ESTIMATE) - 1; |
---|
| 429 | max = LONG_MAX; |
---|
| 430 | } |
---|
| 431 | else |
---|
| 432 | { |
---|
| 433 | max = sc[n-1] + SYZ_SHIFT_BASE; |
---|
| 434 | } |
---|
| 435 | |
---|
| 436 | // no we arrange things such that |
---|
| 437 | // (n - holes) + holes*new_space + new_comps*SYZ_SHIFT_BASE= LONG_MAX |
---|
| 438 | new_space = (max - n + holes - new_comps*SYZ_SHIFT_BASE) / holes; |
---|
| 439 | |
---|
| 440 | assume(new_space < SYZ_SHIFT_BASE && new_space >= 4); |
---|
| 441 | |
---|
| 442 | long* tc = ( long*) omAlloc(n*sizeof(long)); |
---|
| 443 | tc[0] = sc[0]; |
---|
| 444 | // rearrange things |
---|
| 445 | for (i=1; i<n; i++) |
---|
| 446 | { |
---|
| 447 | if (sc[i-1] + 1 < sc[i]) |
---|
| 448 | { |
---|
| 449 | tc[i] = tc[i-1] + new_space; |
---|
| 450 | } |
---|
| 451 | else |
---|
| 452 | { |
---|
| 453 | tc[i] = tc[i-1] + 1; |
---|
| 454 | } |
---|
| 455 | assume(tc[i] > tc[i-1]); |
---|
| 456 | } |
---|
| 457 | |
---|
| 458 | assume(LONG_MAX - SYZ_SHIFT_BASE > tc[n-1]); |
---|
| 459 | #ifdef HAVE_ASSUME |
---|
| 460 | for (i=1; i<n; i++) |
---|
| 461 | { |
---|
| 462 | assume(tc[i] >= 0); |
---|
| 463 | assume(tc[i-1] + 1 <= tc[i]); |
---|
| 464 | } |
---|
| 465 | #endif |
---|
| 466 | |
---|
| 467 | omMemcpyW(sc, tc, n); |
---|
| 468 | omFreeSize(tc, n*sizeof(long)); |
---|
| 469 | return new_space; |
---|
| 470 | } |
---|
| 471 | |
---|
| 472 | // this make a Setm on p |
---|
| 473 | static void pResetSetm(poly p) |
---|
| 474 | { |
---|
| 475 | #ifdef PDEBUG |
---|
| 476 | poly q = p; |
---|
| 477 | #endif |
---|
| 478 | while (p!= NULL) |
---|
| 479 | { |
---|
| 480 | pSetm(p); |
---|
| 481 | pIter(p); |
---|
| 482 | } |
---|
| 483 | #ifdef PDEBUG |
---|
[025942] | 484 | pTest(q); |
---|
[35aab3] | 485 | #endif |
---|
| 486 | } |
---|
| 487 | |
---|
| 488 | void syResetShiftedComponents(syStrategy syzstr, int index,int hilb) |
---|
| 489 | { |
---|
| 490 | assume(index > 0); |
---|
| 491 | int i; |
---|
| 492 | if (syzstr->res[index] != NULL) |
---|
| 493 | { |
---|
| 494 | long * prev_s; |
---|
| 495 | int* prev_c; |
---|
| 496 | int p_length; |
---|
| 497 | rGetSComps(&prev_c, &prev_s, &p_length); |
---|
| 498 | currcomponents = syzstr->truecomponents[index-1]; |
---|
| 499 | currShiftedComponents = syzstr->ShiftedComponents[index-1]; |
---|
| 500 | rChangeSComps(currcomponents, |
---|
| 501 | currShiftedComponents, |
---|
| 502 | IDELEMS(syzstr->res[index-1])); |
---|
| 503 | if (hilb==0) |
---|
| 504 | { |
---|
| 505 | ideal id = syzstr->res[index]; |
---|
| 506 | for (i=0; i<IDELEMS(id); i++) |
---|
| 507 | { |
---|
| 508 | pResetSetm(id->m[i]); |
---|
| 509 | } |
---|
| 510 | } |
---|
| 511 | else if (hilb==1) |
---|
| 512 | { |
---|
| 513 | assume (index>1); |
---|
| 514 | assume (syzstr->resPairs[index-1]!=NULL); |
---|
| 515 | SSet Pairs=syzstr->resPairs[index-1]; |
---|
| 516 | SSet Pairs1=syzstr->resPairs[index]; |
---|
| 517 | int till=(*syzstr->Tl)[index-1]; |
---|
| 518 | for (i=0;i<till;i++) |
---|
| 519 | { |
---|
| 520 | if (Pairs[i].syz!=NULL) |
---|
| 521 | pResetSetm(Pairs[i].syz); |
---|
| 522 | } |
---|
| 523 | till=(*syzstr->Tl)[index]; |
---|
| 524 | for (i=0;i<till;i++) |
---|
| 525 | { |
---|
| 526 | if (Pairs1[i].p!=NULL) |
---|
| 527 | pResetSetm(Pairs1[i].p); |
---|
| 528 | } |
---|
| 529 | } |
---|
| 530 | currcomponents = prev_c; |
---|
| 531 | currShiftedComponents = prev_s; |
---|
| 532 | rChangeSComps(prev_c, prev_s, p_length); |
---|
| 533 | } |
---|
| 534 | } |
---|
| 535 | |
---|
| 536 | /*3 |
---|
| 537 | * determines the place of a polynomial in the right ordered resolution |
---|
| 538 | * set the vectors of truecomponents |
---|
| 539 | */ |
---|
| 540 | static BOOLEAN syOrder(poly p,syStrategy syzstr,int index, |
---|
| 541 | int realcomp) |
---|
| 542 | { |
---|
| 543 | int i=IDELEMS(syzstr->res[index-1])+1,j=0,k,tc,orc,ie=realcomp-1; |
---|
| 544 | int *trind1=syzstr->truecomponents[index-1]; |
---|
| 545 | int *trind=syzstr->truecomponents[index]; |
---|
| 546 | long *shind=syzstr->ShiftedComponents[index]; |
---|
| 547 | int *bc=syzstr->backcomponents[index]; |
---|
| 548 | int *F1=syzstr->Firstelem[index-1]; |
---|
| 549 | int *H1=syzstr->Howmuch[index-1]; |
---|
| 550 | poly pp; |
---|
| 551 | polyset o_r=syzstr->orderedRes[index]->m; |
---|
| 552 | polyset or1=syzstr->orderedRes[index-1]->m; |
---|
| 553 | BOOLEAN ret = FALSE; |
---|
| 554 | |
---|
| 555 | // if != 0, then new element can go into same component |
---|
| 556 | // i.e., we do not need to leave space in shifted components |
---|
| 557 | long same_comp = 0; |
---|
| 558 | |
---|
| 559 | if (p==NULL) return FALSE; |
---|
| 560 | if (realcomp==0) realcomp=1; |
---|
| 561 | |
---|
| 562 | if (index>1) |
---|
| 563 | tc = trind1[pGetComp(p)]-1; |
---|
| 564 | else |
---|
| 565 | tc = pGetComp(p)-1; |
---|
| 566 | loop //while ((j<ie) && (trind1[orc]<=tc+1)) |
---|
| 567 | { |
---|
| 568 | if (j>=ie) |
---|
| 569 | break; |
---|
| 570 | else |
---|
| 571 | { |
---|
| 572 | orc = pGetComp(o_r[j]); |
---|
| 573 | if (trind1[orc]>tc+1) break; |
---|
| 574 | else if (trind1[orc] == tc+1) |
---|
| 575 | { |
---|
| 576 | same_comp = 1; |
---|
| 577 | } |
---|
| 578 | else |
---|
| 579 | { |
---|
| 580 | assume(same_comp == 0); |
---|
| 581 | } |
---|
| 582 | j += H1[orc]; |
---|
| 583 | } |
---|
| 584 | } |
---|
| 585 | if (j>ie) |
---|
| 586 | { |
---|
| 587 | WerrorS("orderedRes to small"); |
---|
| 588 | return FALSE; |
---|
| 589 | } |
---|
| 590 | ie++; |
---|
| 591 | if (j == (ie -1)) |
---|
| 592 | { |
---|
| 593 | // new element is the last in ordered module |
---|
| 594 | if (same_comp == 0) |
---|
| 595 | same_comp = SYZ_SHIFT_BASE; |
---|
| 596 | |
---|
| 597 | // test wheter we have enough space for new shifted component |
---|
| 598 | if ((LONG_MAX - same_comp) <= shind[ie-1]) |
---|
| 599 | { |
---|
| 600 | long new_space = syReorderShiftedComponents(shind, ie); |
---|
| 601 | assume((LONG_MAX - same_comp) > shind[ie-1]); |
---|
| 602 | ret = TRUE; |
---|
| 603 | if (TEST_OPT_PROT) Print("(T%u)", new_space); |
---|
| 604 | } |
---|
| 605 | |
---|
| 606 | // yes, then set new shifted component |
---|
| 607 | assume(ie == 1 || shind[ie-1] > 0); |
---|
| 608 | shind[ie] = shind[ie-1] + same_comp; |
---|
| 609 | } |
---|
| 610 | else |
---|
| 611 | { |
---|
| 612 | // new element must come in between |
---|
| 613 | // i.e. at place j+1 |
---|
| 614 | long prev, next; |
---|
| 615 | |
---|
| 616 | // test whether new component can get shifted value |
---|
| 617 | prev = shind[j]; |
---|
| 618 | next = shind[j+1]; |
---|
| 619 | assume(next > prev); |
---|
| 620 | if ((same_comp && prev + 2 >= next) || (!same_comp && next - prev < 4)) |
---|
| 621 | { |
---|
| 622 | long new_space = syReorderShiftedComponents(shind, ie); |
---|
| 623 | prev = shind[j]; |
---|
| 624 | next = shind[j+1]; |
---|
| 625 | assume((same_comp && prev + 2 < next) || (!same_comp && next - prev >= 4)); |
---|
| 626 | ret = TRUE; |
---|
| 627 | if (TEST_OPT_PROT) Print("(B%u)", new_space); |
---|
| 628 | } |
---|
| 629 | |
---|
| 630 | // make room for insertion of j+1 shifted component |
---|
| 631 | for (k=ie; k > j+1; k--) shind[k] = shind[k-1]; |
---|
| 632 | |
---|
| 633 | if (same_comp) |
---|
| 634 | { |
---|
| 635 | // can simply add one |
---|
| 636 | shind[j+1] = prev + 1; |
---|
| 637 | assume(shind[j+1] + 1 < shind[j+2]); |
---|
| 638 | } |
---|
| 639 | else |
---|
| 640 | { |
---|
| 641 | // need to leave more breathing room - i.e. value goes in |
---|
| 642 | // between |
---|
| 643 | shind[j+1] = prev + ((next - prev) >> 1); |
---|
| 644 | assume (shind[j] + 1 < shind[j+1] && shind[j+1] + 1 < shind[j+2]); |
---|
| 645 | } |
---|
| 646 | } |
---|
| 647 | |
---|
| 648 | if (o_r[j]!=NULL) |
---|
| 649 | { |
---|
| 650 | for (k=ie-1;k>j;k--) |
---|
| 651 | { |
---|
| 652 | o_r[k] = o_r[k-1]; |
---|
| 653 | bc[k] = bc[k-1]; |
---|
| 654 | } |
---|
| 655 | } |
---|
| 656 | o_r[j] = p; |
---|
| 657 | bc[j] = realcomp-1; |
---|
| 658 | (H1[pGetComp(p)])++; |
---|
| 659 | for (k=0;k<i;k++) |
---|
| 660 | { |
---|
| 661 | if (F1[k]>j) |
---|
| 662 | (F1[k])++; |
---|
| 663 | } |
---|
| 664 | if (F1[pGetComp(p)]==0) |
---|
| 665 | F1[pGetComp(p)]=j+1; |
---|
| 666 | for (k=0;k<IDELEMS((syzstr->res)[index]);k++) |
---|
| 667 | { |
---|
| 668 | if (trind[k]>j) |
---|
| 669 | trind[k] += 1; |
---|
| 670 | } |
---|
| 671 | for (k=IDELEMS((syzstr->res)[index])-1;k>realcomp;k--) |
---|
| 672 | trind[k] = trind[k-1]; |
---|
| 673 | trind[realcomp] = j+1; |
---|
| 674 | return ret; |
---|
| 675 | } |
---|
| 676 | |
---|
| 677 | //#define OLD_PAIR_ORDER |
---|
| 678 | #ifdef OLD_PAIR_ORDER |
---|
| 679 | static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr, |
---|
| 680 | int howmuch, int index) |
---|
| 681 | { |
---|
| 682 | int i=howmuch-1,i1=0,l,ll; |
---|
| 683 | int ** Fin=syzstr->Firstelem; |
---|
| 684 | int ** Hin=syzstr->Howmuch; |
---|
| 685 | int ** bin=syzstr->backcomponents; |
---|
| 686 | ideal o_r=syzstr->orderedRes[index+1]; |
---|
| 687 | intvec *result=new intvec(howmuch+1); |
---|
| 688 | BOOLEAN isDivisible; |
---|
| 689 | SObject tso; |
---|
| 690 | |
---|
| 691 | while (i>=0) |
---|
| 692 | { |
---|
| 693 | tso = nextPairs[i]; |
---|
| 694 | isDivisible = FALSE; |
---|
| 695 | if (syzstr->res[index+1]!=NULL) |
---|
| 696 | { |
---|
| 697 | l = Fin[index][pGetComp(tso.lcm)]-1; |
---|
| 698 | if (l>=0) |
---|
| 699 | { |
---|
| 700 | ll = l+Hin[index][pGetComp(tso.lcm)]; |
---|
| 701 | while ((l<ll) && (!isDivisible)) |
---|
| 702 | { |
---|
| 703 | if (o_r->m[l]!=NULL) |
---|
| 704 | { |
---|
| 705 | isDivisible = isDivisible || |
---|
| 706 | pLmDivisibleByNoComp(o_r->m[l],tso.lcm); |
---|
| 707 | } |
---|
| 708 | l++; |
---|
| 709 | } |
---|
| 710 | } |
---|
| 711 | } |
---|
| 712 | if (isDivisible) |
---|
| 713 | { |
---|
| 714 | syDeletePair(&nextPairs[i]); |
---|
| 715 | //crit++; |
---|
| 716 | } |
---|
| 717 | else |
---|
| 718 | { |
---|
| 719 | nextPairs[i].p = |
---|
| 720 | //sySPoly(tso.p1, tso.p2,tso.lcm); |
---|
| 721 | spSpolyCreate(tso.p2, tso.p1,NULL,spSpolyLoop_General); |
---|
| 722 | (*result)[i1] = i+1; |
---|
| 723 | i1++; |
---|
| 724 | } |
---|
| 725 | i--; |
---|
| 726 | } |
---|
| 727 | return result; |
---|
| 728 | } |
---|
| 729 | #else |
---|
| 730 | static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr, |
---|
| 731 | int howmuch, int index) |
---|
| 732 | { |
---|
| 733 | int i=howmuch-1,i1=0,i2,i3,l,ll; |
---|
| 734 | int ** Fin=syzstr->Firstelem; |
---|
| 735 | int ** Hin=syzstr->Howmuch; |
---|
| 736 | int ** bin=syzstr->backcomponents; |
---|
| 737 | ideal o_r=syzstr->orderedRes[index+1]; |
---|
| 738 | intvec *result=new intvec(howmuch+1); |
---|
| 739 | intvec *spl=new intvec(howmuch,1,-1); |
---|
| 740 | BOOLEAN isDivisible; |
---|
| 741 | SObject tso; |
---|
| 742 | |
---|
| 743 | while (i>=0) |
---|
| 744 | { |
---|
| 745 | tso = nextPairs[i]; |
---|
| 746 | isDivisible = FALSE; |
---|
| 747 | if (syzstr->res[index+1]!=NULL) |
---|
| 748 | { |
---|
| 749 | l = Fin[index][pGetComp(tso.lcm)]-1; |
---|
| 750 | if (l>=0) |
---|
| 751 | { |
---|
| 752 | ll = l+Hin[index][pGetComp(tso.lcm)]; |
---|
| 753 | while ((l<ll) && (!isDivisible)) |
---|
| 754 | { |
---|
| 755 | if (o_r->m[l]!=NULL) |
---|
| 756 | { |
---|
| 757 | isDivisible = isDivisible || |
---|
| 758 | pLmDivisibleByNoComp(o_r->m[l],tso.lcm); |
---|
| 759 | } |
---|
| 760 | l++; |
---|
| 761 | } |
---|
| 762 | } |
---|
| 763 | } |
---|
| 764 | if (isDivisible) |
---|
| 765 | { |
---|
| 766 | syDeletePair(&nextPairs[i]); |
---|
| 767 | //crit++; |
---|
| 768 | } |
---|
| 769 | else |
---|
| 770 | { |
---|
| 771 | pTest(tso.p2); |
---|
| 772 | pTest(tso.p1); |
---|
| 773 | nextPairs[i].p = |
---|
| 774 | ksOldCreateSpoly(tso.p2, tso.p1,NULL); |
---|
| 775 | (*spl)[i] = pLength(nextPairs[i].p); |
---|
| 776 | } |
---|
| 777 | i--; |
---|
| 778 | } |
---|
| 779 | i3 = 0; |
---|
| 780 | loop |
---|
| 781 | { |
---|
| 782 | i2 = -1; |
---|
| 783 | for (i1=0;i1<howmuch;i1++) |
---|
| 784 | { |
---|
| 785 | if (i2==-1) |
---|
| 786 | { |
---|
| 787 | if ((*spl)[i1]!=-1) |
---|
| 788 | { |
---|
| 789 | i2 = i1; |
---|
| 790 | } |
---|
| 791 | } |
---|
| 792 | else |
---|
| 793 | { |
---|
| 794 | if (((*spl)[i1]>=0) && ((*spl)[i1]<(*spl)[i2])) |
---|
| 795 | { |
---|
| 796 | i2 = i1; |
---|
| 797 | } |
---|
| 798 | } |
---|
| 799 | } |
---|
| 800 | if (i2>=0) |
---|
| 801 | { |
---|
| 802 | (*result)[i3] = i2+1; |
---|
| 803 | (*spl)[i2] = -1; |
---|
| 804 | i3++; |
---|
| 805 | } |
---|
| 806 | else |
---|
| 807 | { |
---|
| 808 | break; |
---|
| 809 | } |
---|
| 810 | } |
---|
| 811 | delete spl; |
---|
| 812 | return result; |
---|
| 813 | } |
---|
| 814 | #endif |
---|
| 815 | |
---|
| 816 | void syEnlargeFields(syStrategy syzstr,int index) |
---|
| 817 | { |
---|
| 818 | pEnlargeSet(&(syzstr->res[index]->m),IDELEMS(syzstr->res[index]),16); |
---|
| 819 | syzstr->truecomponents[index]=(int*)omRealloc0Size((ADDRESS)syzstr->truecomponents[index], |
---|
| 820 | (IDELEMS(syzstr->res[index])+1)*sizeof(int), |
---|
| 821 | (IDELEMS(syzstr->res[index])+17)*sizeof(int)); |
---|
| 822 | syzstr->ShiftedComponents[index] |
---|
| 823 | =(long*)omRealloc0Size((ADDRESS)syzstr->ShiftedComponents[index], |
---|
| 824 | (IDELEMS(syzstr->res[index])+1)*sizeof(long), |
---|
| 825 | (IDELEMS(syzstr->res[index])+17)*sizeof(long)); |
---|
| 826 | syzstr->backcomponents[index]=(int*)omRealloc0Size((ADDRESS)syzstr->backcomponents[index], |
---|
| 827 | (IDELEMS(syzstr->res[index])+1)*sizeof(int), |
---|
| 828 | (IDELEMS(syzstr->res[index])+17)*sizeof(int)); |
---|
| 829 | syzstr->Howmuch[index]=(int*)omRealloc0Size((ADDRESS)syzstr->Howmuch[index], |
---|
| 830 | (IDELEMS(syzstr->res[index])+1)*sizeof(int), |
---|
| 831 | (IDELEMS(syzstr->res[index])+17)*sizeof(int)); |
---|
| 832 | syzstr->Firstelem[index]=(int*)omRealloc0Size((ADDRESS)syzstr->Firstelem[index], |
---|
| 833 | (IDELEMS(syzstr->res[index])+1)*sizeof(int), |
---|
| 834 | (IDELEMS(syzstr->res[index])+17)*sizeof(int)); |
---|
| 835 | syzstr->elemLength[index]=(int*)omRealloc0Size((ADDRESS)syzstr->elemLength[index], |
---|
| 836 | (IDELEMS(syzstr->res[index])+1)*sizeof(int), |
---|
| 837 | (IDELEMS(syzstr->res[index])+17)*sizeof(int)); |
---|
| 838 | syzstr->sev[index]=(unsigned long*)omRealloc0Size((ADDRESS)syzstr->sev[index], |
---|
| 839 | (IDELEMS(syzstr->res[index])+1)*sizeof(unsigned long), |
---|
| 840 | (IDELEMS(syzstr->res[index])+17)*sizeof(unsigned long)); |
---|
| 841 | IDELEMS(syzstr->res[index]) += 16; |
---|
| 842 | pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16); |
---|
| 843 | IDELEMS(syzstr->orderedRes[index]) += 16; |
---|
| 844 | } |
---|
| 845 | /*3 |
---|
| 846 | * reduces all pairs of degree deg in the module index |
---|
| 847 | * put the reduced generators to the resolvente which contains |
---|
| 848 | * the truncated kStd |
---|
| 849 | */ |
---|
| 850 | static void syRedNextPairs(SSet nextPairs, syStrategy syzstr, |
---|
| 851 | int howmuch, int index) |
---|
| 852 | { |
---|
| 853 | int i,j,k=IDELEMS(syzstr->res[index]); |
---|
| 854 | int ks=IDELEMS(syzstr->res[index+1]),kk,l,ll; |
---|
| 855 | int * Fin=syzstr->Firstelem[index-1]; |
---|
| 856 | int * Hin=syzstr->Howmuch[index-1]; |
---|
| 857 | int * bin=syzstr->backcomponents[index]; |
---|
| 858 | int * elL=syzstr->elemLength[index]; |
---|
| 859 | number coefgcd,n; |
---|
| 860 | polyset redset=syzstr->orderedRes[index]->m; |
---|
| 861 | poly p=NULL,q; |
---|
| 862 | intvec *spl1; |
---|
| 863 | SObject tso; |
---|
| 864 | long * ShiftedComponents = syzstr->ShiftedComponents[index]; |
---|
| 865 | int* Components = syzstr->truecomponents[index]; |
---|
| 866 | assume(Components != NULL && ShiftedComponents != NULL); |
---|
| 867 | BOOLEAN need_reset; |
---|
| 868 | |
---|
| 869 | if ((nextPairs==NULL) || (howmuch==0)) return; |
---|
| 870 | while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--; |
---|
| 871 | while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--; |
---|
| 872 | spl1 = syLinStrat(nextPairs,syzstr,howmuch,index); |
---|
| 873 | i=0; |
---|
| 874 | while ((*spl1)[i]>0) |
---|
| 875 | { |
---|
| 876 | need_reset = FALSE; |
---|
| 877 | tso = nextPairs[(*spl1)[i]-1]; |
---|
| 878 | if ((tso.p1!=NULL) && (tso.p2!=NULL)) |
---|
| 879 | { |
---|
| 880 | nNormalize(pGetCoeff(tso.p1)); |
---|
| 881 | nNormalize(pGetCoeff(tso.p2)); |
---|
| 882 | coefgcd = |
---|
| 883 | nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing); |
---|
| 884 | tso.syz = pHead(tso.lcm); |
---|
| 885 | p = tso.syz; |
---|
| 886 | pSetCoeff(p,nDiv(pGetCoeff(tso.p1),coefgcd)); |
---|
| 887 | pGetCoeff(p) = nNeg(pGetCoeff(p)); |
---|
| 888 | pSetComp(p,tso.ind2+1); |
---|
| 889 | p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index |
---|
| 890 | pNext(p) = pHead(tso.lcm); |
---|
| 891 | pIter(p); |
---|
| 892 | pSetComp(p,tso.ind1+1); |
---|
| 893 | p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index |
---|
| 894 | pSetCoeff(p,nDiv(pGetCoeff(tso.p2),coefgcd)); |
---|
| 895 | nDelete(&coefgcd); |
---|
| 896 | if (tso.p != NULL) |
---|
| 897 | { |
---|
| 898 | kBucketInit(syzstr->bucket,tso.p,-1); |
---|
| 899 | q = kBucketGetLm(syzstr->bucket); |
---|
| 900 | j = Fin[pGetComp(q)]-1; |
---|
| 901 | int pos = j+Hin[pGetComp(q)]; |
---|
| 902 | loop |
---|
| 903 | { |
---|
| 904 | if (j<0) break; |
---|
| 905 | if (pLmDivisibleByNoComp(redset[j],q)) |
---|
| 906 | { |
---|
| 907 | pNext(p) = pHead(q); |
---|
| 908 | pIter(p); |
---|
| 909 | pSetComp(p,bin[j]+1); |
---|
| 910 | p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index |
---|
| 911 | //if (pLength(redset[j])!=syzstr->elemLength[index][bin[j]]) |
---|
| 912 | //Print("Halt"); |
---|
| 913 | //if (pLength(redset[j])!=syzstr->elemLength[index][bin[j]]) |
---|
| 914 | //Print("Halt"); |
---|
| 915 | pGetCoeff(p) = nNeg(pGetCoeff(p)); |
---|
| 916 | number up = kBucketPolyRed(syzstr->bucket,redset[j],elL[bin[j]], |
---|
| 917 | NULL); |
---|
| 918 | // Thomas: Check whether you need number here |
---|
| 919 | nDelete(&up); |
---|
| 920 | q = kBucketGetLm(syzstr->bucket); |
---|
| 921 | if (q==NULL) break; |
---|
| 922 | j = Fin[pGetComp(q)]-1; |
---|
| 923 | pos = j+Hin[pGetComp(q)]; |
---|
| 924 | } |
---|
| 925 | else |
---|
| 926 | { |
---|
| 927 | j++; |
---|
| 928 | if (j==pos) break; |
---|
| 929 | } |
---|
| 930 | } |
---|
| 931 | int lb; |
---|
| 932 | kBucketClear(syzstr->bucket,&tso.p,&lb); |
---|
| 933 | } |
---|
| 934 | if (tso.p != NULL) |
---|
| 935 | { |
---|
| 936 | if (TEST_OPT_PROT) PrintS("g"); |
---|
| 937 | if (k==IDELEMS((syzstr->res)[index])) |
---|
| 938 | { |
---|
| 939 | syEnlargeFields(syzstr,index); |
---|
| 940 | bin=syzstr->backcomponents[index]; |
---|
| 941 | elL=syzstr->elemLength[index]; |
---|
| 942 | redset=syzstr->orderedRes[index]->m; |
---|
| 943 | Components = syzstr->truecomponents[index]; |
---|
| 944 | ShiftedComponents = syzstr->ShiftedComponents[index]; |
---|
| 945 | } |
---|
| 946 | pNext(p) = pHead(tso.p); |
---|
| 947 | pIter(p); |
---|
| 948 | |
---|
| 949 | assume(p!= NULL); |
---|
| 950 | k++; |
---|
| 951 | syzstr->res[index]->m[k-1] = tso.p; |
---|
| 952 | syzstr->elemLength[index][k-1] = pLength(tso.p); |
---|
| 953 | pNorm(syzstr->res[index]->m[k-1]); |
---|
| 954 | need_reset = syOrder(syzstr->res[index]->m[k-1],syzstr,index,k); |
---|
| 955 | pSetComp(p,k); // actueller index |
---|
| 956 | p_Setm_Syz(p, currRing, Components, ShiftedComponents); |
---|
| 957 | pGetCoeff(p) = nNeg(pGetCoeff(p)); |
---|
| 958 | |
---|
| 959 | tso.isNotMinimal = p; |
---|
| 960 | tso.p = NULL; |
---|
| 961 | } |
---|
| 962 | else |
---|
| 963 | { |
---|
| 964 | if (TEST_OPT_PROT) PrintS("."); |
---|
| 965 | //if (index % 2==0) |
---|
| 966 | //euler++; |
---|
| 967 | //else |
---|
| 968 | //euler--; |
---|
| 969 | } |
---|
| 970 | if (ks==IDELEMS(syzstr->res[index+1])) |
---|
| 971 | { |
---|
| 972 | syEnlargeFields(syzstr,index+1); |
---|
| 973 | } |
---|
| 974 | syzstr->res[index+1]->m[ks] = tso.syz; |
---|
| 975 | syzstr->elemLength[index+1][ks] = pLength(tso.syz); |
---|
| 976 | pNorm(syzstr->res[index+1]->m[ks]); |
---|
| 977 | tso.syz =NULL; |
---|
| 978 | tso.syzind = ks; |
---|
| 979 | if (need_reset) |
---|
| 980 | syResetShiftedComponents(syzstr, index+1); |
---|
| 981 | if (syOrder(syzstr->res[index+1]->m[ks],syzstr,index+1,ks+1)) |
---|
| 982 | syResetShiftedComponents(syzstr, index+2); |
---|
| 983 | ks++; |
---|
| 984 | p = NULL; |
---|
| 985 | nextPairs[(*spl1)[i]-1] = tso; |
---|
| 986 | } |
---|
| 987 | i++; |
---|
| 988 | } |
---|
| 989 | delete spl1; |
---|
| 990 | } |
---|
| 991 | |
---|
| 992 | /*3 |
---|
| 993 | * reduces the generators of the module index in degree deg |
---|
| 994 | * (which are actual syzygies of the module index-1) |
---|
| 995 | * wrt. the ideal generated by elements of lower degrees |
---|
| 996 | */ |
---|
| 997 | static void syRedGenerOfCurrDeg(syStrategy syzstr, int deg, int index) |
---|
| 998 | { |
---|
| 999 | ideal res=syzstr->res[index]; |
---|
| 1000 | int i=0,j,k=IDELEMS(res),kk; |
---|
| 1001 | SSet sPairs=syzstr->resPairs[index-1]; |
---|
| 1002 | |
---|
| 1003 | while ((k>0) && (res->m[k-1]==NULL)) k--; |
---|
| 1004 | while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) || |
---|
| 1005 | ((sPairs)[i].order<deg))) |
---|
| 1006 | i++; |
---|
| 1007 | if ((i>=(*syzstr->Tl)[index-1]) || ((sPairs)[i].order>deg)) return; |
---|
| 1008 | while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) || |
---|
| 1009 | ((sPairs)[i].order==deg))) |
---|
| 1010 | { |
---|
| 1011 | if ((sPairs)[i].syz!=NULL) |
---|
| 1012 | { |
---|
| 1013 | j = k-1; |
---|
| 1014 | while ((j>=0) && (res->m[j]!=NULL) && |
---|
| 1015 | ((sPairs)[i].syz!=NULL)) |
---|
| 1016 | { |
---|
| 1017 | if (pLmDivisibleBy(res->m[j],(sPairs)[i].syz)) |
---|
| 1018 | { |
---|
| 1019 | (sPairs)[i].syz = |
---|
| 1020 | ksOldSpolyRed(res->m[j],(sPairs)[i].syz); |
---|
| 1021 | //sySPolyRed((sPairs)[i].syz,res->m[j]); |
---|
| 1022 | j = k-1; |
---|
| 1023 | } |
---|
| 1024 | else |
---|
| 1025 | { |
---|
| 1026 | j--; |
---|
| 1027 | } |
---|
| 1028 | } |
---|
| 1029 | if ((sPairs)[i].syz != NULL) |
---|
| 1030 | { |
---|
| 1031 | if (k==IDELEMS(res)) |
---|
| 1032 | { |
---|
| 1033 | syEnlargeFields(syzstr,index); |
---|
| 1034 | res=syzstr->res[index]; |
---|
| 1035 | } |
---|
| 1036 | if (TEST_OPT_DEBUG) |
---|
| 1037 | { |
---|
| 1038 | if ((sPairs)[i].isNotMinimal==NULL) |
---|
| 1039 | { |
---|
| 1040 | PrintLn(); |
---|
| 1041 | PrintS("minimal generator: ");pWrite((syzstr->resPairs[index-1])[i].syz); |
---|
| 1042 | PrintS("comes from: ");pWrite((syzstr->resPairs[index-1])[i].p1); |
---|
| 1043 | PrintS("and: ");pWrite((syzstr->resPairs[index-1])[i].p2); |
---|
| 1044 | } |
---|
| 1045 | } |
---|
| 1046 | //res->m[k] = (sPairs)[i].syz; |
---|
| 1047 | res->m[k] = syRedtail((sPairs)[i].syz,syzstr,index); |
---|
| 1048 | (sPairs)[i].syzind = k; |
---|
| 1049 | syzstr->elemLength[index][k] = pLength((sPairs)[i].syz); |
---|
| 1050 | pNorm(res->m[k]); |
---|
| 1051 | // (sPairs)[i].syz = NULL; |
---|
| 1052 | k++; |
---|
| 1053 | if (syOrder(res->m[k-1],syzstr,index,k)) |
---|
| 1054 | syResetShiftedComponents(syzstr, index); |
---|
| 1055 | //euler++; |
---|
| 1056 | } |
---|
| 1057 | else |
---|
| 1058 | (sPairs)[i].syzind = -1; |
---|
| 1059 | } |
---|
| 1060 | i++; |
---|
| 1061 | } |
---|
| 1062 | } |
---|
| 1063 | |
---|
| 1064 | /*3 |
---|
| 1065 | * puts a pair into the right place in resPairs |
---|
| 1066 | */ |
---|
| 1067 | void syEnterPair(SSet sPairs, SObject * so, int * sPlength,int index) |
---|
| 1068 | { |
---|
| 1069 | int ll,k,no=(*so).order,sP=*sPlength,i; |
---|
| 1070 | poly p=(*so).lcm; |
---|
| 1071 | |
---|
| 1072 | if ((sP==0) || (sPairs[sP-1].order<=no)) |
---|
| 1073 | ll = sP; |
---|
| 1074 | else if (sP==1) |
---|
| 1075 | ll = 0; |
---|
| 1076 | else |
---|
| 1077 | { |
---|
| 1078 | int an=0,en=sP-1; |
---|
| 1079 | loop |
---|
| 1080 | { |
---|
| 1081 | if (an>=en-1) |
---|
| 1082 | { |
---|
| 1083 | if ((sPairs[an].order<=no) && (sPairs[an+1].order>no)) |
---|
| 1084 | { |
---|
| 1085 | ll = an+1; |
---|
| 1086 | break; |
---|
| 1087 | } |
---|
| 1088 | else if ((sPairs[en].order<=no) && (sPairs[en+1].order>no)) |
---|
| 1089 | { |
---|
| 1090 | ll = en+1; |
---|
| 1091 | break; |
---|
| 1092 | } |
---|
| 1093 | else if (sPairs[an].order>no) |
---|
| 1094 | { |
---|
| 1095 | ll = an; |
---|
| 1096 | break; |
---|
| 1097 | } |
---|
| 1098 | else |
---|
| 1099 | { |
---|
| 1100 | PrintS("Hier ist was faul!\n"); |
---|
| 1101 | break; |
---|
| 1102 | } |
---|
| 1103 | } |
---|
| 1104 | i=(an+en) / 2; |
---|
| 1105 | if (sPairs[i].order <= no) |
---|
| 1106 | an=i; |
---|
| 1107 | else |
---|
| 1108 | en=i; |
---|
| 1109 | } |
---|
| 1110 | } |
---|
| 1111 | for (k=(*sPlength);k>ll;k--) |
---|
| 1112 | { |
---|
| 1113 | syCopyPair(&sPairs[k-1],&sPairs[k]); |
---|
| 1114 | } |
---|
| 1115 | syCopyPair(so,&sPairs[ll]); |
---|
| 1116 | (*sPlength)++; |
---|
| 1117 | } |
---|
| 1118 | void syEnterPair(syStrategy syzstr, SObject * so, int * sPlength,int index) |
---|
| 1119 | { |
---|
| 1120 | int ll; |
---|
| 1121 | |
---|
| 1122 | if (*sPlength>=(*syzstr->Tl)[index]) |
---|
| 1123 | { |
---|
| 1124 | SSet temp = (SSet)omAlloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject)); |
---|
| 1125 | for (ll=0;ll<(*syzstr->Tl)[index];ll++) |
---|
| 1126 | { |
---|
| 1127 | temp[ll].p = (syzstr->resPairs[index])[ll].p; |
---|
| 1128 | temp[ll].p1 = (syzstr->resPairs[index])[ll].p1; |
---|
| 1129 | temp[ll].p2 = (syzstr->resPairs[index])[ll].p2; |
---|
| 1130 | temp[ll].syz = (syzstr->resPairs[index])[ll].syz; |
---|
| 1131 | temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm; |
---|
| 1132 | temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1; |
---|
| 1133 | temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2; |
---|
| 1134 | temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind; |
---|
| 1135 | temp[ll].order = (syzstr->resPairs[index])[ll].order; |
---|
| 1136 | temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal; |
---|
| 1137 | temp[ll].length = (syzstr->resPairs[index])[ll].length; |
---|
| 1138 | temp[ll].reference = (syzstr->resPairs[index])[ll].reference; |
---|
| 1139 | } |
---|
| 1140 | if (syzstr->resPairs[index] != NULL) // OB: ????? |
---|
| 1141 | omFreeSize((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject)); |
---|
| 1142 | (*syzstr->Tl)[index] += 16; |
---|
| 1143 | syzstr->resPairs[index] = temp; |
---|
| 1144 | } |
---|
| 1145 | syEnterPair(syzstr->resPairs[index],so,sPlength,index); |
---|
| 1146 | } |
---|
| 1147 | |
---|
| 1148 | /*3 |
---|
| 1149 | * computes pairs from the new elements (beginning with the element newEl) |
---|
| 1150 | * in the module index |
---|
| 1151 | */ |
---|
| 1152 | static void syCreateNewPairs(syStrategy syzstr, int index, int newEl) |
---|
| 1153 | { |
---|
| 1154 | SSet temp; |
---|
| 1155 | SObject tso; |
---|
| 1156 | int i,ii,j,k=IDELEMS(syzstr->res[index]),l=(*syzstr->Tl)[index],ll; |
---|
| 1157 | int qc,first,pos,jj,j1; |
---|
| 1158 | int * bci=syzstr->backcomponents[index]; |
---|
| 1159 | poly p,q; |
---|
| 1160 | polyset rs=syzstr->res[index]->m,nPm; |
---|
| 1161 | |
---|
| 1162 | |
---|
| 1163 | while ((k>0) && (rs[k-1]==NULL)) k--; |
---|
| 1164 | if (newEl>=k) return; |
---|
| 1165 | |
---|
| 1166 | long * ShiftedComponents = syzstr->ShiftedComponents[index]; |
---|
| 1167 | int* Components = syzstr->truecomponents[index]; |
---|
| 1168 | |
---|
| 1169 | ideal nP=idInit(k,syzstr->res[index]->rank); |
---|
| 1170 | nPm=nP->m; |
---|
| 1171 | while ((l>0) && ((syzstr->resPairs[index])[l-1].p1==NULL)) l--; |
---|
| 1172 | for (j=newEl;j<k;j++) |
---|
| 1173 | { |
---|
| 1174 | q = rs[j]; |
---|
| 1175 | qc = pGetComp(q); |
---|
| 1176 | first = syzstr->Firstelem[index-1][pGetComp(q)]-1; |
---|
| 1177 | pos = first+syzstr->Howmuch[index-1][pGetComp(q)]; |
---|
| 1178 | for (i=first;i<pos;i++) |
---|
| 1179 | { |
---|
| 1180 | jj = bci[i]; |
---|
| 1181 | if (jj>=j) break; |
---|
| 1182 | p = pOne(); |
---|
| 1183 | pLcm(rs[jj],q,p); |
---|
| 1184 | pSetComp(p,j+1); |
---|
| 1185 | p_Setm_Syz(p, currRing, Components, ShiftedComponents); |
---|
| 1186 | ii = first; |
---|
| 1187 | loop |
---|
| 1188 | { |
---|
| 1189 | j1 = bci[ii]; |
---|
| 1190 | if (nPm[j1]!=NULL) |
---|
| 1191 | { |
---|
| 1192 | if (pLmDivisibleByNoComp(nPm[j1],p)) |
---|
| 1193 | { |
---|
| 1194 | pDelete(&p); |
---|
| 1195 | break; |
---|
| 1196 | } |
---|
| 1197 | else if (pLmDivisibleByNoComp(p,nPm[j1])) |
---|
| 1198 | { |
---|
| 1199 | pDelete(&(nPm[j1])); |
---|
| 1200 | //break; |
---|
| 1201 | } |
---|
| 1202 | } |
---|
| 1203 | ii++; |
---|
| 1204 | if (ii>=pos) break; |
---|
| 1205 | } |
---|
| 1206 | if (p!=NULL) |
---|
| 1207 | { |
---|
| 1208 | nPm[jj] = p; |
---|
| 1209 | } |
---|
| 1210 | } |
---|
| 1211 | for (i=first;i<pos;i++) |
---|
| 1212 | { |
---|
| 1213 | ii = bci[i]; |
---|
| 1214 | if (nPm[ii]!=NULL) |
---|
| 1215 | { |
---|
| 1216 | if (l>=(*syzstr->Tl)[index]) |
---|
| 1217 | { |
---|
| 1218 | temp = (SSet)omAlloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject)); |
---|
| 1219 | for (ll=0;ll<(*syzstr->Tl)[index];ll++) |
---|
| 1220 | { |
---|
| 1221 | temp[ll].p = (syzstr->resPairs[index])[ll].p; |
---|
| 1222 | temp[ll].p1 = (syzstr->resPairs[index])[ll].p1; |
---|
| 1223 | temp[ll].p2 = (syzstr->resPairs[index])[ll].p2; |
---|
| 1224 | temp[ll].syz = (syzstr->resPairs[index])[ll].syz; |
---|
| 1225 | temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm; |
---|
| 1226 | temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1; |
---|
| 1227 | temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2; |
---|
| 1228 | temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind; |
---|
| 1229 | temp[ll].order = (syzstr->resPairs[index])[ll].order; |
---|
| 1230 | temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal; |
---|
| 1231 | } |
---|
| 1232 | if (syzstr->resPairs[index] != NULL) // OB: ???? |
---|
| 1233 | omFreeSize((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject)); |
---|
| 1234 | (*syzstr->Tl)[index] += 16; |
---|
| 1235 | syzstr->resPairs[index] = temp; |
---|
| 1236 | } |
---|
| 1237 | tso.lcm = p = nPm[ii]; |
---|
| 1238 | nPm[ii] = NULL; |
---|
| 1239 | //#ifdef HAVE_SHIFTED_EXPONENTS |
---|
| 1240 | //tso.order = pTotaldegree(p); |
---|
| 1241 | //p->exp[currRing->pOrdIndex]=tso.order+0x40000000; |
---|
| 1242 | //#else |
---|
| 1243 | tso.order = pTotaldegree(p); |
---|
| 1244 | pSetOrder(p, tso.order); |
---|
| 1245 | //#endif |
---|
| 1246 | if ((syzstr->cw!=NULL) && (index>0) && (pGetComp(q)>0)) |
---|
| 1247 | { |
---|
| 1248 | int ii=index-1,jj=pGetComp(q); |
---|
| 1249 | while (ii>0) |
---|
| 1250 | { |
---|
| 1251 | jj = pGetComp(syzstr->res[ii]->m[jj-1]); |
---|
| 1252 | ii--; |
---|
| 1253 | } |
---|
| 1254 | tso.order += (*syzstr->cw)[jj-1]; |
---|
| 1255 | } |
---|
| 1256 | tso.p1 = rs[ii]; |
---|
| 1257 | tso.p2 = q; |
---|
| 1258 | tso.ind1 = ii; |
---|
| 1259 | tso.ind2 = j; |
---|
| 1260 | tso.syzind = -1; |
---|
| 1261 | tso.isNotMinimal = NULL; |
---|
| 1262 | tso.p = NULL; |
---|
| 1263 | tso.syz = NULL; |
---|
| 1264 | syEnterPair(syzstr->resPairs[index],&tso,&l,index); |
---|
| 1265 | } |
---|
| 1266 | } |
---|
| 1267 | } |
---|
| 1268 | idDelete(&nP); |
---|
| 1269 | } |
---|
| 1270 | |
---|
| 1271 | static SSet syChosePairsPutIn(syStrategy syzstr, int *index, |
---|
| 1272 | int *howmuch, int * actdeg, int an, int en) |
---|
| 1273 | { |
---|
| 1274 | int newdeg=*actdeg,newindex=-1,i,t,sldeg; |
---|
| 1275 | poly p; |
---|
| 1276 | SSet result; |
---|
| 1277 | SRes resPairs=syzstr->resPairs; |
---|
| 1278 | |
---|
| 1279 | if (an>syzstr->length) return NULL; |
---|
| 1280 | if (en>syzstr->length) en=syzstr->length; |
---|
| 1281 | while (*index<en) |
---|
| 1282 | { |
---|
| 1283 | if (resPairs[*index]!=NULL) |
---|
| 1284 | { |
---|
| 1285 | sldeg = (*actdeg)+*index; |
---|
| 1286 | i = 0; |
---|
| 1287 | if (*index!=0) |
---|
| 1288 | { |
---|
| 1289 | while ((i<(*syzstr->Tl)[*index])) |
---|
| 1290 | { |
---|
| 1291 | if ((resPairs[*index])[i].lcm!=NULL) |
---|
| 1292 | { |
---|
| 1293 | if ((resPairs[*index])[i].order == sldeg) |
---|
| 1294 | { |
---|
| 1295 | result = &(resPairs[*index])[i]; |
---|
| 1296 | *howmuch =1; |
---|
| 1297 | i++; |
---|
| 1298 | while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL) |
---|
| 1299 | && ((resPairs[*index])[i].order == sldeg)) |
---|
| 1300 | { |
---|
| 1301 | i++; |
---|
| 1302 | (*howmuch)++; |
---|
| 1303 | } |
---|
| 1304 | return result; |
---|
| 1305 | } |
---|
| 1306 | } |
---|
| 1307 | i++; |
---|
| 1308 | } |
---|
| 1309 | } |
---|
| 1310 | else |
---|
| 1311 | { |
---|
| 1312 | while ((i<(*syzstr->Tl)[*index])) |
---|
| 1313 | { |
---|
| 1314 | if ((resPairs[*index])[i].syz!=NULL) |
---|
| 1315 | { |
---|
| 1316 | if ((resPairs[*index])[i].order == sldeg) |
---|
| 1317 | { |
---|
| 1318 | result = &(resPairs[*index])[i]; |
---|
| 1319 | (*howmuch) =1; |
---|
| 1320 | i++; |
---|
| 1321 | while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL) |
---|
| 1322 | && ((resPairs[*index])[i].order == *actdeg)) |
---|
| 1323 | { |
---|
| 1324 | i++; |
---|
| 1325 | (*howmuch)++; |
---|
| 1326 | } |
---|
| 1327 | return result; |
---|
| 1328 | } |
---|
| 1329 | } |
---|
| 1330 | i++; |
---|
| 1331 | } |
---|
| 1332 | } |
---|
| 1333 | } |
---|
| 1334 | (*index)++; |
---|
| 1335 | } |
---|
| 1336 | *index = an; |
---|
| 1337 | //if (TEST_OPT_PROT) Print("(Euler:%d)",euler); |
---|
| 1338 | while (*index<en) |
---|
| 1339 | { |
---|
| 1340 | if (resPairs[*index]!=NULL) |
---|
| 1341 | { |
---|
| 1342 | i = 0; |
---|
| 1343 | while ((i<(*syzstr->Tl)[*index])) |
---|
| 1344 | { |
---|
| 1345 | t = *actdeg+*index; |
---|
| 1346 | if (((resPairs[*index])[i].lcm!=NULL) || |
---|
| 1347 | ((resPairs[*index])[i].syz!=NULL)) |
---|
| 1348 | { |
---|
| 1349 | if ((resPairs[*index])[i].order > t) |
---|
| 1350 | t = (resPairs[*index])[i].order; |
---|
| 1351 | } |
---|
| 1352 | if ((t>*actdeg+*index) && ((newdeg==*actdeg) || (t<newdeg+*index))) |
---|
| 1353 | { |
---|
| 1354 | newdeg = t-*index; |
---|
| 1355 | newindex = *index; |
---|
| 1356 | break; |
---|
| 1357 | } |
---|
| 1358 | i++; |
---|
| 1359 | } |
---|
| 1360 | } |
---|
| 1361 | (*index)++; |
---|
| 1362 | } |
---|
| 1363 | if (newdeg>*actdeg) |
---|
| 1364 | { |
---|
| 1365 | *actdeg = newdeg; |
---|
| 1366 | *index = newindex; |
---|
| 1367 | return syChosePairsPutIn(syzstr,index,howmuch,actdeg,an,en); |
---|
| 1368 | } |
---|
| 1369 | else return NULL; |
---|
| 1370 | } |
---|
| 1371 | |
---|
| 1372 | /*3 |
---|
| 1373 | * FOR THE HOMOGENEOUS CASE ONLY! |
---|
| 1374 | * looks through the pair set and the given module for |
---|
| 1375 | * remaining pairs or generators to consider |
---|
| 1376 | * returns a pointer to the first pair and the number of them in the given module |
---|
| 1377 | * works with slanted degree (i.e. deg=realdeg-index) |
---|
| 1378 | */ |
---|
| 1379 | SSet syChosePairs(syStrategy syzstr, int *index, int *howmuch, int * actdeg) |
---|
| 1380 | { |
---|
| 1381 | return syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,syzstr->length); |
---|
| 1382 | } |
---|
| 1383 | |
---|
| 1384 | /*3 |
---|
| 1385 | * FOR THE INHOMOGENEOUS CASE ONLY! |
---|
| 1386 | * looks through the pair set and the given module for |
---|
| 1387 | * remaining pairs or generators to consider |
---|
| 1388 | * returns a pointer to the first pair and the number of them in the given module |
---|
| 1389 | * works with slanted degree (i.e. deg=realdeg-index) |
---|
| 1390 | * looks first through the 0 and 1 module then through the other |
---|
| 1391 | */ |
---|
| 1392 | static SSet syChosePairsIH(syStrategy syzstr, int *index, |
---|
| 1393 | int *howmuch, int * actdeg, int mindeg) |
---|
| 1394 | { |
---|
| 1395 | SSet result=NULL; |
---|
| 1396 | |
---|
| 1397 | result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,2); |
---|
| 1398 | if (result == NULL) |
---|
| 1399 | { |
---|
| 1400 | *actdeg = mindeg; |
---|
| 1401 | result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,2,syzstr->length); |
---|
| 1402 | } |
---|
| 1403 | return result; |
---|
| 1404 | } |
---|
| 1405 | |
---|
| 1406 | /*3 |
---|
| 1407 | * looks through the pair set and the given module for |
---|
| 1408 | * remaining pairs or generators to consider |
---|
| 1409 | * returns a pointer to the first pair and the number of them in the given module |
---|
| 1410 | * works deg by deg |
---|
| 1411 | */ |
---|
| 1412 | /* |
---|
| 1413 | *static SSet syChosePairs1(SRes resPairs,intvec * Tl, int *index, int *howmuch, |
---|
| 1414 | * int length,int * actdeg) |
---|
| 1415 | *{ |
---|
| 1416 | * int newdeg=*actdeg,newindex=-1,i,t; |
---|
| 1417 | * SSet result; |
---|
| 1418 | * |
---|
| 1419 | * while (*index>=0) |
---|
| 1420 | * { |
---|
| 1421 | * if (resPairs[*index]!=NULL) |
---|
| 1422 | * { |
---|
| 1423 | * i = 0; |
---|
| 1424 | * if (*index!=0) |
---|
| 1425 | * { |
---|
| 1426 | * while ((i<(*Tl)[*index])) |
---|
| 1427 | * { |
---|
| 1428 | * if ((resPairs[*index])[i].lcm!=NULL) |
---|
| 1429 | * { |
---|
| 1430 | * if (pGetOrder((resPairs[*index])[i].lcm) == *actdeg) |
---|
| 1431 | * { |
---|
| 1432 | * result = &(resPairs[*index])[i]; |
---|
| 1433 | * *howmuch =1; |
---|
| 1434 | * i++; |
---|
| 1435 | * while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL) |
---|
| 1436 | * && (pGetOrder((resPairs[*index])[i].lcm) == *actdeg)) |
---|
| 1437 | * { |
---|
| 1438 | * i++; |
---|
| 1439 | * (*howmuch)++; |
---|
| 1440 | * } |
---|
| 1441 | * return result; |
---|
| 1442 | * } |
---|
| 1443 | * } |
---|
| 1444 | * i++; |
---|
| 1445 | * } |
---|
| 1446 | * } |
---|
| 1447 | * else |
---|
| 1448 | * { |
---|
| 1449 | * while ((i<(*Tl)[*index])) |
---|
| 1450 | * { |
---|
| 1451 | * if ((resPairs[*index])[i].syz!=NULL) |
---|
| 1452 | * { |
---|
| 1453 | * if ((resPairs[*index])[i].order == *actdeg) |
---|
| 1454 | * { |
---|
| 1455 | * result = &(resPairs[*index])[i]; |
---|
| 1456 | * (*howmuch) =1; |
---|
| 1457 | * i++; |
---|
| 1458 | * while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL) |
---|
| 1459 | * && ((resPairs[*index])[i].order == *actdeg)) |
---|
| 1460 | * { |
---|
| 1461 | * i++; |
---|
| 1462 | * (*howmuch)++; |
---|
| 1463 | * } |
---|
| 1464 | * return result; |
---|
| 1465 | * } |
---|
| 1466 | * } |
---|
| 1467 | * i++; |
---|
| 1468 | * } |
---|
| 1469 | * } |
---|
| 1470 | * } |
---|
| 1471 | * (*index)--; |
---|
| 1472 | * } |
---|
| 1473 | * *index = length-1; |
---|
| 1474 | * while (*index>=0) |
---|
| 1475 | * { |
---|
| 1476 | * if (resPairs[*index]!=NULL) |
---|
| 1477 | * { |
---|
| 1478 | * i = 0; |
---|
| 1479 | * while ((i<(*Tl)[*index])) |
---|
| 1480 | * { |
---|
| 1481 | * t = *actdeg; |
---|
| 1482 | * if ((resPairs[*index])[i].lcm!=NULL) |
---|
| 1483 | * { |
---|
| 1484 | * if (pGetOrder((resPairs[*index])[i].lcm) > *actdeg) |
---|
| 1485 | * t = pGetOrder((resPairs[*index])[i].lcm); |
---|
| 1486 | * } |
---|
| 1487 | * else if ((resPairs[*index])[i].syz!=NULL) |
---|
| 1488 | * { |
---|
| 1489 | * if ((resPairs[*index])[i].order > *actdeg) |
---|
| 1490 | * t = (resPairs[*index])[i].order; |
---|
| 1491 | * } |
---|
| 1492 | * if ((t>*actdeg) && ((newdeg==*actdeg) || (t<newdeg))) |
---|
| 1493 | * { |
---|
| 1494 | * newdeg = t; |
---|
| 1495 | * newindex = *index; |
---|
| 1496 | * break; |
---|
| 1497 | * } |
---|
| 1498 | * i++; |
---|
| 1499 | * } |
---|
| 1500 | * } |
---|
| 1501 | * (*index)--; |
---|
| 1502 | * } |
---|
| 1503 | * if (newdeg>*actdeg) |
---|
| 1504 | * { |
---|
| 1505 | * *actdeg = newdeg; |
---|
| 1506 | * *index = newindex; |
---|
| 1507 | * return syChosePairs1(resPairs,Tl,index,howmuch,length,actdeg); |
---|
| 1508 | * } |
---|
| 1509 | * else return NULL; |
---|
| 1510 | *} |
---|
| 1511 | */ |
---|
| 1512 | /*3 |
---|
| 1513 | * statistics of the resolution |
---|
| 1514 | */ |
---|
| 1515 | static void syStatistics(resolvente res,int length) |
---|
| 1516 | { |
---|
| 1517 | int i,j=1,k; |
---|
| 1518 | Order_t deg = 0; |
---|
| 1519 | |
---|
| 1520 | PrintLn(); |
---|
| 1521 | while ((j<length) && (res[j]!=NULL)) |
---|
| 1522 | { |
---|
| 1523 | Print("In module %d: \n",j); |
---|
| 1524 | k = 0; |
---|
| 1525 | while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL)) |
---|
| 1526 | { |
---|
| 1527 | i = 1; |
---|
| 1528 | deg = pGetOrder(res[j]->m[k]); |
---|
| 1529 | k++; |
---|
| 1530 | while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL) && |
---|
| 1531 | (pGetOrder(res[j]->m[k])==deg)) |
---|
| 1532 | { |
---|
| 1533 | i++; |
---|
| 1534 | k++; |
---|
| 1535 | } |
---|
| 1536 | Print("%d elements of degree %d\n",i,deg); |
---|
| 1537 | } |
---|
| 1538 | j++; |
---|
| 1539 | } |
---|
| 1540 | } |
---|
| 1541 | |
---|
| 1542 | /*3 |
---|
| 1543 | * initialize a module |
---|
| 1544 | */ |
---|
| 1545 | int syInitSyzMod(syStrategy syzstr, int index, int init) |
---|
| 1546 | { |
---|
| 1547 | int result; |
---|
| 1548 | |
---|
| 1549 | if (syzstr->res[index]==NULL) |
---|
| 1550 | { |
---|
| 1551 | syzstr->res[index] = idInit(init-1,1); |
---|
| 1552 | syzstr->truecomponents[index] = (int*)omAlloc0(init*sizeof(int)); |
---|
| 1553 | syzstr->ShiftedComponents[index] = (long*)omAlloc0(init*sizeof(long)); |
---|
| 1554 | if (index==0) |
---|
| 1555 | { |
---|
| 1556 | for (int i=0;i<init;i++) |
---|
| 1557 | { |
---|
| 1558 | syzstr->truecomponents[0][i] = i; |
---|
| 1559 | syzstr->ShiftedComponents[0][i] = (i)*SYZ_SHIFT_BASE; |
---|
| 1560 | } |
---|
| 1561 | } |
---|
| 1562 | syzstr->backcomponents[index] = (int*)omAlloc0(init*sizeof(int)); |
---|
| 1563 | syzstr->Howmuch[index] = (int*)omAlloc0(init*sizeof(int)); |
---|
| 1564 | syzstr->Firstelem[index] = (int*)omAlloc0(init*sizeof(int)); |
---|
| 1565 | syzstr->elemLength[index] = (int*)omAlloc0(init*sizeof(int)); |
---|
| 1566 | syzstr->orderedRes[index] = idInit(init-1,1); |
---|
| 1567 | syzstr->sev[index] = (unsigned long*) omAlloc0(init*sizeof(unsigned long)); |
---|
| 1568 | result = 0; |
---|
| 1569 | } |
---|
| 1570 | else |
---|
| 1571 | { |
---|
| 1572 | result = IDELEMS(syzstr->res[index]); |
---|
| 1573 | while ((result>0) && (syzstr->res[index]->m[result-1]==NULL)) result--; |
---|
| 1574 | } |
---|
| 1575 | return result; |
---|
| 1576 | } |
---|
| 1577 | |
---|
| 1578 | /*3 |
---|
| 1579 | * deletes a resolution |
---|
| 1580 | */ |
---|
| 1581 | void syKillComputation(syStrategy syzstr, ring r) |
---|
| 1582 | { |
---|
| 1583 | if (syzstr->references>0) |
---|
| 1584 | { |
---|
| 1585 | (syzstr->references)--; |
---|
| 1586 | } |
---|
| 1587 | else |
---|
| 1588 | { |
---|
| 1589 | int i,j; |
---|
| 1590 | if (syzstr->minres!=NULL) |
---|
| 1591 | { |
---|
| 1592 | for (i=0;i<syzstr->length;i++) |
---|
| 1593 | { |
---|
| 1594 | if (syzstr->minres[i]!=NULL) |
---|
| 1595 | { |
---|
| 1596 | for (j=0;j<IDELEMS(syzstr->minres[i]);j++) |
---|
| 1597 | { |
---|
| 1598 | if (syzstr->minres[i]->m[j]!=NULL) |
---|
| 1599 | p_Delete(&(syzstr->minres[i]->m[j]),r); |
---|
| 1600 | } |
---|
| 1601 | } |
---|
| 1602 | id_Delete(&(syzstr->minres[i]),r); |
---|
| 1603 | } |
---|
| 1604 | omFreeSize((ADDRESS)syzstr->minres,(syzstr->length+1)*sizeof(ideal)); |
---|
| 1605 | } |
---|
| 1606 | if (syzstr->fullres!=NULL) |
---|
| 1607 | { |
---|
| 1608 | for (i=0;i<syzstr->length;i++) |
---|
| 1609 | { |
---|
| 1610 | if (syzstr->fullres[i]!=NULL) |
---|
| 1611 | { |
---|
| 1612 | for (j=0;j<IDELEMS(syzstr->fullres[i]);j++) |
---|
| 1613 | { |
---|
| 1614 | if (syzstr->fullres[i]->m[j]!=NULL) |
---|
| 1615 | p_Delete(&(syzstr->fullres[i]->m[j]),r); |
---|
| 1616 | } |
---|
| 1617 | } |
---|
| 1618 | id_Delete(&(syzstr->fullres[i]),r); |
---|
| 1619 | } |
---|
| 1620 | omFreeSize((ADDRESS)syzstr->fullres,(syzstr->length+1)*sizeof(ideal)); |
---|
| 1621 | } |
---|
| 1622 | if (syzstr->weights!=0) |
---|
| 1623 | { |
---|
| 1624 | for (i=0;i<syzstr->length;i++) |
---|
| 1625 | { |
---|
| 1626 | if (syzstr->weights[i]!=NULL) |
---|
| 1627 | { |
---|
| 1628 | delete syzstr->weights[i]; |
---|
| 1629 | } |
---|
| 1630 | } |
---|
| 1631 | omFreeSize((ADDRESS)syzstr->weights,syzstr->length*sizeof(intvec*)); |
---|
| 1632 | } |
---|
| 1633 | |
---|
| 1634 | ring sr=syzstr->syRing; |
---|
| 1635 | if (sr==NULL) sr=r; |
---|
| 1636 | |
---|
| 1637 | if (syzstr->resPairs!=NULL) |
---|
| 1638 | { |
---|
| 1639 | for (i=0;i<syzstr->length;i++) |
---|
| 1640 | { |
---|
| 1641 | for (j=0;j<(*syzstr->Tl)[i];j++) |
---|
| 1642 | { |
---|
| 1643 | if ((syzstr->resPairs[i])[j].lcm!=NULL) |
---|
| 1644 | p_Delete(&((syzstr->resPairs[i])[j].lcm),sr); |
---|
| 1645 | if ((i>0) && ((syzstr->resPairs[i])[j].syz!=NULL)) |
---|
| 1646 | p_Delete(&((syzstr->resPairs[i])[j].syz),sr); |
---|
| 1647 | } |
---|
| 1648 | if (syzstr->orderedRes[i]!=NULL) |
---|
| 1649 | { |
---|
| 1650 | for (j=0;j<IDELEMS(syzstr->orderedRes[i]);j++) |
---|
| 1651 | { |
---|
| 1652 | syzstr->orderedRes[i]->m[j] = NULL; |
---|
| 1653 | } |
---|
| 1654 | } |
---|
| 1655 | id_Delete(&(syzstr->orderedRes[i]),sr); |
---|
| 1656 | if (syzstr->truecomponents[i]!=NULL) |
---|
| 1657 | { |
---|
| 1658 | omFreeSize((ADDRESS)syzstr->truecomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int)); |
---|
| 1659 | syzstr->truecomponents[i]=NULL; |
---|
| 1660 | omFreeSize((ADDRESS)syzstr->ShiftedComponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(long)); |
---|
| 1661 | syzstr->ShiftedComponents[i]=NULL; |
---|
| 1662 | } |
---|
| 1663 | if (syzstr->backcomponents[i]!=NULL) |
---|
| 1664 | { |
---|
| 1665 | omFreeSize((ADDRESS)syzstr->backcomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int)); |
---|
| 1666 | syzstr->backcomponents[i]=NULL; |
---|
| 1667 | } |
---|
| 1668 | if (syzstr->Howmuch[i]!=NULL) |
---|
| 1669 | { |
---|
| 1670 | omFreeSize((ADDRESS)syzstr->Howmuch[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int)); |
---|
| 1671 | syzstr->Howmuch[i]=NULL; |
---|
| 1672 | } |
---|
| 1673 | if (syzstr->Firstelem[i]!=NULL) |
---|
| 1674 | { |
---|
| 1675 | omFreeSize((ADDRESS)syzstr->Firstelem[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int)); |
---|
| 1676 | syzstr->Firstelem[i]=NULL; |
---|
| 1677 | } |
---|
| 1678 | if (syzstr->elemLength[i]!=NULL) |
---|
| 1679 | { |
---|
| 1680 | omFreeSize((ADDRESS)syzstr->elemLength[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int)); |
---|
| 1681 | syzstr->elemLength[i]=NULL; |
---|
| 1682 | } |
---|
| 1683 | if (syzstr->res[i]!=NULL) |
---|
| 1684 | { |
---|
| 1685 | for (j=0;j<IDELEMS(syzstr->res[i]);j++) |
---|
| 1686 | { |
---|
| 1687 | if (syzstr->res[i]->m[j]!=NULL) |
---|
| 1688 | p_Delete(&(syzstr->res[i]->m[j]),sr); |
---|
| 1689 | } |
---|
| 1690 | } |
---|
| 1691 | if ((syzstr->hilb_coeffs!=NULL) |
---|
| 1692 | && (syzstr->hilb_coeffs[i]!=NULL)) |
---|
| 1693 | delete syzstr->hilb_coeffs[i]; |
---|
| 1694 | if (syzstr->sev[i] != NULL) |
---|
| 1695 | omFreeSize((ADDRESS)syzstr->sev[i], (IDELEMS(syzstr->res[i])+1)*sizeof(unsigned long)); |
---|
| 1696 | id_Delete(&(syzstr->res[i]),sr); |
---|
| 1697 | if (syzstr->resPairs[i] != NULL) // OB: ???? |
---|
| 1698 | omFreeSize((ADDRESS)syzstr->resPairs[i],(*syzstr->Tl)[i]*sizeof(SObject)); |
---|
| 1699 | } |
---|
| 1700 | omFreeSize((ADDRESS)syzstr->resPairs,syzstr->length*sizeof(SObject*)); |
---|
| 1701 | omFreeSize((ADDRESS)syzstr->res,(syzstr->length+1)*sizeof(ideal)); |
---|
| 1702 | omFreeSize((ADDRESS)syzstr->orderedRes,(syzstr->length+1)*sizeof(ideal)); |
---|
| 1703 | omFreeSize((ADDRESS)syzstr->elemLength,(syzstr->length+1)*sizeof(int*)); |
---|
| 1704 | omFreeSize((ADDRESS)syzstr->truecomponents,(syzstr->length+1)*sizeof(int*)); |
---|
| 1705 | omFreeSize((ADDRESS)syzstr->ShiftedComponents,(syzstr->length+1)*sizeof(long*)); |
---|
| 1706 | if (syzstr->sev != NULL) |
---|
| 1707 | omFreeSize(((ADDRESS)syzstr->sev), (syzstr->length+1)*sizeof(unsigned long*)); |
---|
| 1708 | omFreeSize((ADDRESS)syzstr->backcomponents,(syzstr->length+1)*sizeof(int*)); |
---|
| 1709 | omFreeSize((ADDRESS)syzstr->Howmuch,(syzstr->length+1)*sizeof(int*)); |
---|
| 1710 | omFreeSize((ADDRESS)syzstr->Firstelem,(syzstr->length+1)*sizeof(int*)); |
---|
| 1711 | if (syzstr->hilb_coeffs!=NULL) |
---|
| 1712 | omFreeSize((ADDRESS)syzstr->hilb_coeffs,(syzstr->length+1)*sizeof(intvec*)); |
---|
| 1713 | } |
---|
| 1714 | if (syzstr->cw!=NULL) |
---|
| 1715 | delete syzstr->cw; |
---|
| 1716 | if (syzstr->betti!=NULL) |
---|
| 1717 | delete syzstr->betti; |
---|
| 1718 | if (syzstr->resolution!=NULL) |
---|
| 1719 | delete syzstr->resolution; |
---|
| 1720 | if (syzstr->Tl!=NULL) |
---|
| 1721 | delete syzstr->Tl; |
---|
| 1722 | if ((syzstr->syRing != NULL) && (syzstr->syRing != r)) |
---|
| 1723 | { |
---|
| 1724 | rKill(syzstr->syRing); |
---|
| 1725 | } |
---|
| 1726 | omFreeSize((ADDRESS)syzstr, sizeof(ssyStrategy)); |
---|
| 1727 | } |
---|
| 1728 | } |
---|
| 1729 | |
---|
[30b8381] | 1730 | /*2 |
---|
| 1731 | * divides out the weight monomials (given by the Schreyer-ordering) |
---|
| 1732 | * from the LaScala-resolution |
---|
[35aab3] | 1733 | */ |
---|
[30b8381] | 1734 | resolvente syReorder(resolvente res,int length, |
---|
| 1735 | syStrategy syzstr,BOOLEAN toCopy,resolvente totake) |
---|
[35aab3] | 1736 | { |
---|
[30b8381] | 1737 | int i,j,l; |
---|
| 1738 | poly p,q,tq; |
---|
| 1739 | polyset ri1; |
---|
| 1740 | resolvente fullres; |
---|
| 1741 | ring origR=syzstr->syRing; |
---|
| 1742 | fullres = (resolvente)omAlloc0((length+1)*sizeof(ideal)); |
---|
| 1743 | if (totake==NULL) |
---|
| 1744 | totake = res; |
---|
| 1745 | for (i=length-1;i>0;i--) |
---|
[35aab3] | 1746 | { |
---|
[30b8381] | 1747 | if (res[i]!=NULL) |
---|
[35aab3] | 1748 | { |
---|
[30b8381] | 1749 | if (i>1) |
---|
| 1750 | { |
---|
| 1751 | j = IDELEMS(res[i-1]); |
---|
| 1752 | while ((j>0) && (res[i-1]->m[j-1]==NULL)) j--; |
---|
| 1753 | fullres[i-1] = idInit(IDELEMS(res[i]),j); |
---|
| 1754 | ri1 = totake[i-1]->m; |
---|
| 1755 | for (j=IDELEMS(res[i])-1;j>=0;j--) |
---|
| 1756 | { |
---|
| 1757 | p = res[i]->m[j]; |
---|
| 1758 | q = NULL; |
---|
| 1759 | while (p!=NULL) |
---|
| 1760 | { |
---|
| 1761 | if (toCopy) |
---|
| 1762 | { |
---|
| 1763 | if (origR!=NULL) |
---|
| 1764 | tq = prHeadR(p,origR); |
---|
| 1765 | else |
---|
| 1766 | tq = pHead(p); |
---|
| 1767 | pIter(p); |
---|
| 1768 | } |
---|
| 1769 | else |
---|
| 1770 | { |
---|
| 1771 | res[i]->m[j] = NULL; |
---|
| 1772 | if (origR!=NULL) |
---|
| 1773 | { |
---|
| 1774 | poly pp=p; |
---|
| 1775 | pIter(p); |
---|
| 1776 | pNext(pp)=NULL; |
---|
| 1777 | tq = prMoveR(pp, origR); |
---|
| 1778 | } |
---|
| 1779 | else |
---|
| 1780 | { |
---|
| 1781 | tq = p; |
---|
| 1782 | pIter(p); |
---|
| 1783 | pNext(tq) = NULL; |
---|
| 1784 | } |
---|
| 1785 | } |
---|
| 1786 | // pWrite(tq); |
---|
| 1787 | pTest(tq); |
---|
| 1788 | for (l=pVariables;l>0;l--) |
---|
| 1789 | { |
---|
| 1790 | if (origR!=NULL) |
---|
| 1791 | pSubExp(tq,l, p_GetExp(ri1[pGetComp(tq)-1],l,origR)); |
---|
| 1792 | else |
---|
| 1793 | pSubExp(tq,l, pGetExp(ri1[pGetComp(tq)-1],l)); |
---|
| 1794 | } |
---|
| 1795 | pSetm(tq); |
---|
| 1796 | pTest(tq); |
---|
| 1797 | q = pAdd(q,tq); |
---|
| 1798 | pTest(q); |
---|
| 1799 | } |
---|
| 1800 | fullres[i-1]->m[j] = q; |
---|
| 1801 | } |
---|
| 1802 | } |
---|
| 1803 | else |
---|
[35aab3] | 1804 | { |
---|
[30b8381] | 1805 | if (origR!=NULL) |
---|
[35aab3] | 1806 | { |
---|
[30b8381] | 1807 | fullres[i-1] = idInit(IDELEMS(res[i]),res[i]->rank); |
---|
| 1808 | for (j=IDELEMS(res[i])-1;j>=0;j--) |
---|
| 1809 | { |
---|
| 1810 | if (toCopy) |
---|
| 1811 | fullres[i-1]->m[j] = prCopyR(res[i]->m[j], origR); |
---|
| 1812 | else |
---|
| 1813 | { |
---|
| 1814 | fullres[i-1]->m[j] = prMoveR(res[i]->m[j], origR); |
---|
| 1815 | res[i]->m[j] = NULL; |
---|
| 1816 | } |
---|
| 1817 | } |
---|
[35aab3] | 1818 | } |
---|
[30b8381] | 1819 | else |
---|
| 1820 | { |
---|
| 1821 | if (toCopy) |
---|
| 1822 | fullres[i-1] = idCopy(res[i]); |
---|
| 1823 | else |
---|
| 1824 | { |
---|
| 1825 | fullres[i-1] = res[i]; |
---|
| 1826 | res[i] = NULL; |
---|
| 1827 | } |
---|
| 1828 | } |
---|
| 1829 | for (j=IDELEMS(fullres[i-1])-1;j>=0;j--) |
---|
| 1830 | fullres[i-1]->m[j] = pSortCompCorrect(fullres[i-1]->m[j]); |
---|
| 1831 | } |
---|
| 1832 | if (!toCopy) |
---|
| 1833 | { |
---|
| 1834 | if (res[i]!=NULL) idDelete(&res[i]); |
---|
[35aab3] | 1835 | } |
---|
| 1836 | } |
---|
[30b8381] | 1837 | } |
---|
| 1838 | if (!toCopy) |
---|
| 1839 | omFreeSize((ADDRESS)res,(length+1)*sizeof(ideal)); |
---|
| 1840 | //syzstr->length = length; |
---|
| 1841 | return fullres; |
---|
| 1842 | } |
---|
| 1843 | |
---|
| 1844 | /*3 |
---|
| 1845 | * read out the Betti numbers from resolution |
---|
| 1846 | * (if not LaScala calls the traditional Betti procedure) |
---|
| 1847 | */ |
---|
| 1848 | intvec * syBettiOfComputation(syStrategy syzstr, BOOLEAN minim,int * row_shift, |
---|
| 1849 | intvec* weights) |
---|
| 1850 | { |
---|
| 1851 | int dummy; |
---|
| 1852 | BOOLEAN std_weights=TRUE; |
---|
| 1853 | if ((weights!=NULL) |
---|
| 1854 | && (syzstr->betti!=NULL) |
---|
| 1855 | && (syzstr->weights!=NULL) && (syzstr->weights[0]!=NULL)) |
---|
| 1856 | { |
---|
| 1857 | int i; |
---|
| 1858 | for(i=weights->length()-1; i>=0; i--) |
---|
[35aab3] | 1859 | { |
---|
[30b8381] | 1860 | //Print("test %d: %d - %d\n",i,(*weights)[i], (*(syzstr->weights[0]))[i]); |
---|
| 1861 | if ((*weights)[i]!=(*(syzstr->weights[0]))[i]) |
---|
[35aab3] | 1862 | { |
---|
[30b8381] | 1863 | std_weights=FALSE; |
---|
| 1864 | break; |
---|
[35aab3] | 1865 | } |
---|
| 1866 | } |
---|
| 1867 | } |
---|
[30b8381] | 1868 | if ((syzstr->betti!=NULL) |
---|
| 1869 | && (std_weights)) |
---|
| 1870 | { |
---|
| 1871 | if (minim || (syzstr->resPairs!=NULL)) |
---|
| 1872 | return ivCopy(syzstr->betti); |
---|
| 1873 | } |
---|
| 1874 | if ((syzstr->fullres==NULL) && (syzstr->minres==NULL)) |
---|
| 1875 | { |
---|
| 1876 | if (syzstr->hilb_coeffs==NULL) |
---|
| 1877 | { |
---|
| 1878 | syzstr->fullres = syReorder(syzstr->res,syzstr->length,syzstr); |
---|
| 1879 | } |
---|
| 1880 | else |
---|
| 1881 | { |
---|
| 1882 | syzstr->minres = syReorder(syzstr->orderedRes,syzstr->length,syzstr); |
---|
| 1883 | syKillEmptyEntres(syzstr->minres,syzstr->length); |
---|
| 1884 | } |
---|
| 1885 | } |
---|
| 1886 | intvec *result=NULL; |
---|
| 1887 | if (syzstr->fullres!=NULL) |
---|
| 1888 | result = syBetti(syzstr->fullres,syzstr->length,&dummy,weights,minim,row_shift); |
---|
[35aab3] | 1889 | else |
---|
[30b8381] | 1890 | result = syBetti(syzstr->minres,syzstr->length,&dummy,weights,minim,row_shift); |
---|
| 1891 | if ((result!=NULL) |
---|
| 1892 | && ((minim) || (syzstr->resPairs!=NULL)) |
---|
| 1893 | && std_weights) |
---|
| 1894 | { |
---|
[35aab3] | 1895 | syzstr->betti = ivCopy(result); |
---|
[30b8381] | 1896 | } |
---|
[35aab3] | 1897 | return result; |
---|
| 1898 | } |
---|
| 1899 | |
---|
| 1900 | /*3 |
---|
| 1901 | * computes the allocated length of the resolution |
---|
| 1902 | */ |
---|
| 1903 | int syLength(syStrategy syzstr) |
---|
| 1904 | { |
---|
| 1905 | return syzstr->length; |
---|
| 1906 | } |
---|
| 1907 | |
---|
| 1908 | /*3 |
---|
| 1909 | * computes the real length of the resolution |
---|
| 1910 | */ |
---|
| 1911 | int sySize(syStrategy syzstr) |
---|
| 1912 | { |
---|
| 1913 | resolvente r=syzstr->res; |
---|
| 1914 | if (r==NULL) |
---|
| 1915 | r = syzstr->fullres; |
---|
| 1916 | if (r==NULL) |
---|
| 1917 | r = syzstr->minres; |
---|
| 1918 | if (r==NULL) |
---|
| 1919 | { |
---|
| 1920 | WerrorS("No resolution found"); |
---|
| 1921 | return 0; |
---|
| 1922 | } |
---|
| 1923 | int i=syzstr->length; |
---|
| 1924 | while ((i>0) && (r[i-1]==NULL)) i--; |
---|
| 1925 | return i; |
---|
| 1926 | } |
---|
| 1927 | |
---|
| 1928 | /*3 |
---|
| 1929 | * computes the cohomological dimension of res[1] |
---|
| 1930 | */ |
---|
| 1931 | int syDim(syStrategy syzstr) |
---|
| 1932 | { |
---|
| 1933 | int i,j=-1,l; |
---|
| 1934 | if (syzstr->resPairs!=NULL) |
---|
| 1935 | { |
---|
| 1936 | SRes rP=syzstr->resPairs; |
---|
| 1937 | |
---|
| 1938 | l = syzstr->length; |
---|
| 1939 | while ((l>0) && (rP[l-1]==NULL)) l--; |
---|
| 1940 | if (l==0) return -1; |
---|
| 1941 | l--; |
---|
| 1942 | while (l>=0) |
---|
| 1943 | { |
---|
| 1944 | i = 0; |
---|
| 1945 | while ((i<(*syzstr->Tl)[l]) && |
---|
| 1946 | ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) && |
---|
| 1947 | (rP[l][i].isNotMinimal!=NULL)) |
---|
| 1948 | { |
---|
| 1949 | i++; |
---|
| 1950 | } |
---|
| 1951 | if ((i<(*syzstr->Tl)[l]) && |
---|
| 1952 | ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) && |
---|
| 1953 | (rP[l][i].isNotMinimal==NULL)) |
---|
| 1954 | return l; |
---|
| 1955 | l--; |
---|
| 1956 | } |
---|
| 1957 | return l; |
---|
| 1958 | } |
---|
| 1959 | else |
---|
| 1960 | return sySize(syzstr); |
---|
| 1961 | } |
---|
| 1962 | |
---|
| 1963 | /*3 |
---|
| 1964 | * copies the resolution (by increment the reference counter) |
---|
| 1965 | */ |
---|
| 1966 | syStrategy syCopy(syStrategy syzstr) |
---|
| 1967 | { |
---|
| 1968 | syStrategy result=syzstr; |
---|
| 1969 | (result->references)++; |
---|
| 1970 | return result; |
---|
| 1971 | } |
---|
| 1972 | |
---|
| 1973 | /*2 |
---|
| 1974 | * local print procedure used in syPrint |
---|
| 1975 | */ |
---|
| 1976 | static void syPrintEmptySpaces(int i) |
---|
| 1977 | { |
---|
| 1978 | if (i!=0) |
---|
| 1979 | { |
---|
| 1980 | PrintS(" "); |
---|
| 1981 | syPrintEmptySpaces(i/10); |
---|
| 1982 | } |
---|
| 1983 | } |
---|
| 1984 | |
---|
| 1985 | /*2 |
---|
| 1986 | * local print procedure used in syPrint |
---|
| 1987 | */ |
---|
| 1988 | static void syPrintEmptySpaces1(int i) |
---|
| 1989 | { |
---|
| 1990 | if (i!=0) |
---|
| 1991 | { |
---|
| 1992 | PrintS(" "); |
---|
| 1993 | syPrintEmptySpaces1(i-1); |
---|
| 1994 | } |
---|
| 1995 | } |
---|
| 1996 | |
---|
| 1997 | /*2 |
---|
| 1998 | * local print procedure used in syPrint |
---|
| 1999 | */ |
---|
| 2000 | static int syLengthInt(int i) |
---|
| 2001 | { |
---|
| 2002 | int j=0; |
---|
| 2003 | |
---|
| 2004 | if (i==0) return 1; |
---|
| 2005 | while (i!=0) |
---|
| 2006 | { |
---|
| 2007 | j++; |
---|
| 2008 | i = i/10; |
---|
| 2009 | } |
---|
| 2010 | return j; |
---|
| 2011 | } |
---|
| 2012 | |
---|
| 2013 | /*3 |
---|
| 2014 | * prints the resolution as sequence of free modules |
---|
| 2015 | */ |
---|
| 2016 | void syPrint(syStrategy syzstr) |
---|
| 2017 | { |
---|
| 2018 | if ((syzstr->resPairs==NULL) && (syzstr->fullres==NULL) |
---|
| 2019 | && (syzstr->minres==NULL)) |
---|
| 2020 | { |
---|
| 2021 | PrintS("No resolution defined\n"); |
---|
| 2022 | return; |
---|
| 2023 | } |
---|
| 2024 | int l=0; |
---|
| 2025 | if (syzstr->resolution==NULL) |
---|
| 2026 | { |
---|
| 2027 | int j; |
---|
| 2028 | if (syzstr->resPairs!=NULL) |
---|
| 2029 | { |
---|
| 2030 | syzstr->resolution = new intvec(syzstr->length+1); |
---|
| 2031 | SRes rP=syzstr->resPairs; |
---|
[0ef842] | 2032 | assume(idRankFreeModule(syzstr->res[1], |
---|
| 2033 | (syzstr->syRing != NULL ? syzstr->syRing : currRing))==syzstr->res[1]->rank); |
---|
| 2034 | (*syzstr->resolution)[0] = syzstr->res[1]->rank; |
---|
[35aab3] | 2035 | while ((l<syzstr->length) && (rP[l]!=NULL)) |
---|
| 2036 | { |
---|
| 2037 | j=0; |
---|
| 2038 | while ((j<(*syzstr->Tl)[l]) && |
---|
| 2039 | ((rP[l][j].lcm!=NULL) || (rP[l][j].syz!=NULL))) |
---|
| 2040 | { |
---|
| 2041 | if (rP[l][j].isNotMinimal==NULL) |
---|
| 2042 | ((*syzstr->resolution)[l+1])++; |
---|
| 2043 | j++; |
---|
| 2044 | } |
---|
| 2045 | l++; |
---|
| 2046 | } |
---|
| 2047 | } |
---|
| 2048 | else |
---|
| 2049 | { |
---|
| 2050 | resolvente rr; |
---|
| 2051 | syzstr->resolution = new intvec(syzstr->length+2); |
---|
| 2052 | if (syzstr->minres!=NULL) |
---|
| 2053 | rr = syzstr->minres; |
---|
| 2054 | else |
---|
| 2055 | rr = syzstr->fullres; |
---|
| 2056 | (*syzstr->resolution)[0] |
---|
[62dd9b] | 2057 | = si_max(1,(int)idRankFreeModule(rr[0], |
---|
[35aab3] | 2058 | (syzstr->syRing != NULL ? syzstr->syRing : currRing))); |
---|
| 2059 | while ((l<syzstr->length) && (rr[l]!=NULL)) |
---|
| 2060 | { |
---|
| 2061 | j = IDELEMS(rr[l]); |
---|
| 2062 | while ((j>0) && (rr[l]->m[j-1]==NULL)) j--; |
---|
| 2063 | ((*syzstr->resolution)[l+1]) = j; |
---|
| 2064 | l++; |
---|
| 2065 | } |
---|
| 2066 | } |
---|
| 2067 | } |
---|
[85e68dd] | 2068 | const char *sn=currRingHdl->id; |
---|
[35aab3] | 2069 | int sl=strlen(sn); |
---|
| 2070 | syPrintEmptySpaces1(sl); |
---|
| 2071 | l = 0; |
---|
| 2072 | loop |
---|
| 2073 | { |
---|
| 2074 | if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0)) |
---|
| 2075 | break; |
---|
[c68d10] | 2076 | Print("%d",(*syzstr->resolution)[l]); |
---|
[35aab3] | 2077 | syPrintEmptySpaces1(sl+5); |
---|
| 2078 | l++; |
---|
| 2079 | } |
---|
| 2080 | PrintLn(); |
---|
| 2081 | l = 0; |
---|
| 2082 | loop |
---|
| 2083 | { |
---|
| 2084 | if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0)) |
---|
| 2085 | break; |
---|
[01d285] | 2086 | PrintS(sn); |
---|
[c68d10] | 2087 | if (((l+1)>=syzstr->resolution->length()) || ((*syzstr->resolution)[(l+1)]==0)) |
---|
| 2088 | break; |
---|
[35aab3] | 2089 | PrintS(" <-- "); |
---|
[01d285] | 2090 | syPrintEmptySpaces((*syzstr->resolution)[l]); |
---|
[35aab3] | 2091 | l++; |
---|
| 2092 | } |
---|
| 2093 | PrintLn(); |
---|
| 2094 | PrintLn(); |
---|
| 2095 | l = 0; |
---|
| 2096 | loop |
---|
| 2097 | { |
---|
| 2098 | if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0)) |
---|
| 2099 | break; |
---|
[01d285] | 2100 | Print("%d",l); |
---|
[35aab3] | 2101 | syPrintEmptySpaces1(sl+5+syLengthInt((*syzstr->resolution)[l])- |
---|
| 2102 | syLengthInt(l)); |
---|
| 2103 | l++; |
---|
| 2104 | } |
---|
| 2105 | PrintLn(); |
---|
| 2106 | if (syzstr->minres==NULL) |
---|
| 2107 | { |
---|
| 2108 | PrintS("resolution not minimized yet"); |
---|
| 2109 | PrintLn(); |
---|
| 2110 | } |
---|
| 2111 | } |
---|
| 2112 | |
---|
| 2113 | /*2 |
---|
| 2114 | * deleting all monomials the component of which correspond |
---|
| 2115 | * to non-minimal generators |
---|
| 2116 | */ |
---|
| 2117 | static poly syStripOut(poly p,intvec * toStrip) |
---|
| 2118 | { |
---|
| 2119 | if (toStrip==NULL) return p; |
---|
| 2120 | poly pp=p; |
---|
| 2121 | |
---|
| 2122 | while ((pp!=NULL) && ((*toStrip)[pGetComp(pp)]!=0)) |
---|
| 2123 | pDeleteLm(&pp); |
---|
| 2124 | p = pp; |
---|
| 2125 | if (pp!=NULL) |
---|
| 2126 | { |
---|
| 2127 | while (pNext(pp)!=NULL) |
---|
| 2128 | { |
---|
| 2129 | if ((*toStrip)[pGetComp(pNext(pp))]!=0) |
---|
| 2130 | pDeleteLm(&pNext(pp)); |
---|
| 2131 | else |
---|
| 2132 | pIter(pp); |
---|
| 2133 | } |
---|
| 2134 | } |
---|
| 2135 | return p; |
---|
| 2136 | } |
---|
| 2137 | |
---|
| 2138 | /*2 |
---|
| 2139 | * copies only those monomials the component of which correspond |
---|
| 2140 | * to minimal generators |
---|
| 2141 | */ |
---|
| 2142 | static poly syStripOutCopy(poly p,intvec * toStrip) |
---|
| 2143 | { |
---|
| 2144 | if (toStrip==NULL) return pCopy(p); |
---|
| 2145 | poly result=NULL,pp; |
---|
| 2146 | |
---|
| 2147 | while (p!=NULL) |
---|
| 2148 | { |
---|
| 2149 | if ((*toStrip)[pGetComp(p)]==0) |
---|
| 2150 | { |
---|
| 2151 | if (result==NULL) |
---|
| 2152 | { |
---|
| 2153 | result = pp = pHead(p); |
---|
| 2154 | } |
---|
| 2155 | else |
---|
| 2156 | { |
---|
| 2157 | pNext(pp) = pHead(p); |
---|
| 2158 | pIter(pp); |
---|
| 2159 | } |
---|
| 2160 | } |
---|
| 2161 | pIter(p); |
---|
| 2162 | } |
---|
| 2163 | return result; |
---|
| 2164 | } |
---|
| 2165 | |
---|
| 2166 | /*2 |
---|
| 2167 | * minimizes toMin |
---|
| 2168 | */ |
---|
| 2169 | static poly syMinimizeP(int toMin,syStrategy syzstr,intvec * ordn,int index, |
---|
| 2170 | intvec * toStrip) |
---|
| 2171 | { |
---|
| 2172 | int ii=0,i,j,tc; |
---|
| 2173 | poly p,pp,q=NULL,tq,pisN; |
---|
| 2174 | SSet sPairs=syzstr->resPairs[index]; |
---|
| 2175 | poly tempStripped=NULL; |
---|
| 2176 | |
---|
| 2177 | //pp=pCopy(syzstr->res[index+1]->m[toMin]); |
---|
| 2178 | pp = syStripOutCopy(syzstr->res[index+1]->m[toMin],toStrip); |
---|
| 2179 | while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) && |
---|
| 2180 | (sPairs[(*ordn)[ii]].syzind!=toMin)) |
---|
| 2181 | { |
---|
| 2182 | ii++; |
---|
| 2183 | } |
---|
| 2184 | while (ii>=0) |
---|
| 2185 | { |
---|
| 2186 | i = (*ordn)[ii]; |
---|
| 2187 | if (sPairs[i].isNotMinimal!=NULL) |
---|
| 2188 | { |
---|
| 2189 | tempStripped = |
---|
| 2190 | syStripOutCopy(syzstr->res[index+1]->m[sPairs[i].syzind],toStrip); |
---|
| 2191 | pisN = sPairs[i].isNotMinimal; |
---|
| 2192 | tc = pGetComp(pisN); |
---|
| 2193 | p = pp; |
---|
| 2194 | while (p!=NULL) |
---|
| 2195 | { |
---|
| 2196 | if (pGetComp(p)==tc) |
---|
| 2197 | { |
---|
| 2198 | tq = pInit(); |
---|
| 2199 | for(j=pVariables; j>0; j--) |
---|
| 2200 | pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j)); |
---|
| 2201 | pSetComp(tq, 0); |
---|
| 2202 | pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN))); |
---|
| 2203 | pGetCoeff(tq) = nNeg(pGetCoeff(tq)); |
---|
| 2204 | pSetm(tq); |
---|
| 2205 | q = pAdd(q,pMult_mm(pCopy(tempStripped),tq)); |
---|
| 2206 | pDelete(&tq); |
---|
| 2207 | } |
---|
| 2208 | pIter(p); |
---|
| 2209 | } |
---|
| 2210 | if (q!=NULL) |
---|
| 2211 | { |
---|
| 2212 | pp = pAdd(pp,q); |
---|
| 2213 | q = NULL; |
---|
| 2214 | } |
---|
| 2215 | pDelete(&tempStripped); |
---|
| 2216 | } |
---|
| 2217 | ii--; |
---|
| 2218 | } |
---|
| 2219 | return pp; |
---|
| 2220 | } |
---|
| 2221 | |
---|
| 2222 | /*2 |
---|
| 2223 | * minimizes toMin |
---|
| 2224 | */ |
---|
| 2225 | static poly syMinimizeP1(int toMin,syStrategy syzstr,intvec * ordn,int index, |
---|
| 2226 | intvec * toStrip) |
---|
| 2227 | { |
---|
| 2228 | int ii=0,i,j,tc,lp,ltS=-1; |
---|
| 2229 | poly p,mp=NULL,pp,q=NULL,tq,pisN; |
---|
| 2230 | SSet sPairs=syzstr->resPairs[index]; |
---|
| 2231 | poly tempStripped=NULL; |
---|
| 2232 | |
---|
| 2233 | pp = syStripOutCopy(syzstr->res[index+1]->m[toMin],toStrip); |
---|
| 2234 | kBucketInit(syzstr->bucket,pp,-1); |
---|
| 2235 | while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) && |
---|
| 2236 | (sPairs[(*ordn)[ii]].syzind!=toMin)) |
---|
| 2237 | { |
---|
| 2238 | ii++; |
---|
| 2239 | } |
---|
| 2240 | while (ii>=0) |
---|
| 2241 | { |
---|
| 2242 | i = (*ordn)[ii]; |
---|
| 2243 | if (sPairs[i].isNotMinimal!=NULL) |
---|
| 2244 | { |
---|
| 2245 | tempStripped = |
---|
| 2246 | syStripOutCopy(syzstr->res[index+1]->m[sPairs[i].syzind],toStrip); |
---|
| 2247 | tc = pGetComp(sPairs[i].isNotMinimal); |
---|
| 2248 | //p = pTakeOutComp1(&tempStripped,tc); |
---|
| 2249 | int lu; |
---|
| 2250 | pTakeOutComp(&tempStripped,tc,&p,&lu); |
---|
| 2251 | kBucketTakeOutComp(syzstr->bucket,tc,&mp,&lp); |
---|
| 2252 | mp = pDivideM(mp,p); |
---|
| 2253 | while (mp!=NULL) |
---|
| 2254 | { |
---|
| 2255 | p = pNext(mp); |
---|
| 2256 | pNext(mp) = NULL; |
---|
| 2257 | ltS = -1; |
---|
| 2258 | kBucket_Minus_m_Mult_p(syzstr->bucket,mp,tempStripped,<S); |
---|
| 2259 | mp = p; |
---|
| 2260 | } |
---|
| 2261 | pDelete(&mp); |
---|
| 2262 | pDelete(&tempStripped); |
---|
| 2263 | } |
---|
| 2264 | ii--; |
---|
| 2265 | } |
---|
| 2266 | kBucketClear(syzstr->bucket,&pp,&lp); |
---|
| 2267 | return pp; |
---|
| 2268 | } |
---|
| 2269 | |
---|
| 2270 | /*2 |
---|
| 2271 | * deletes empty components after minimization |
---|
| 2272 | */ |
---|
| 2273 | void syKillEmptyEntres(resolvente res,int length) |
---|
| 2274 | { |
---|
| 2275 | int i,j,jj,k,rj; |
---|
| 2276 | intvec * changes; |
---|
| 2277 | poly p; |
---|
| 2278 | ideal ri; |
---|
| 2279 | |
---|
| 2280 | for (i=0;i<length;i++) |
---|
| 2281 | { |
---|
| 2282 | ri = res[i]; |
---|
| 2283 | if (ri!=NULL) |
---|
| 2284 | { |
---|
| 2285 | rj = IDELEMS(ri); |
---|
| 2286 | changes = new intvec(rj+1,1,-1); |
---|
| 2287 | while ((rj>0) && (ri->m[rj-1]==NULL)) rj--; |
---|
| 2288 | j = k = 0; |
---|
| 2289 | while (j+k<rj) |
---|
| 2290 | { |
---|
| 2291 | if (ri->m[j+k]!=NULL) |
---|
| 2292 | { |
---|
| 2293 | ri->m[j] = ri->m[j+k]; |
---|
| 2294 | (*changes)[j+k+1] = j+1; |
---|
| 2295 | j++; |
---|
| 2296 | } |
---|
| 2297 | else |
---|
| 2298 | { |
---|
| 2299 | k++; |
---|
| 2300 | } |
---|
| 2301 | } |
---|
| 2302 | for (jj=j;jj<rj;jj++) |
---|
| 2303 | ri->m[jj] = NULL; |
---|
| 2304 | if (res[i+1]!=NULL) |
---|
| 2305 | { |
---|
| 2306 | ri = res[i+1]; |
---|
| 2307 | for (j=IDELEMS(ri)-1;j>=0;j--) |
---|
| 2308 | { |
---|
| 2309 | p = ri->m[j]; |
---|
| 2310 | while (p!=NULL) |
---|
| 2311 | { |
---|
| 2312 | pSetComp(p,(*changes)[pGetComp(p)]); |
---|
| 2313 | pSetm(p); |
---|
| 2314 | pIter(p); |
---|
| 2315 | } |
---|
| 2316 | } |
---|
| 2317 | } |
---|
| 2318 | delete changes; |
---|
| 2319 | } |
---|
| 2320 | } |
---|
| 2321 | } |
---|
| 2322 | |
---|
| 2323 | /*2 |
---|
| 2324 | * determines the components for minimization |
---|
| 2325 | */ |
---|
| 2326 | static intvec * syToStrip(syStrategy syzstr, int index) |
---|
| 2327 | { |
---|
| 2328 | intvec * result=NULL; |
---|
| 2329 | |
---|
| 2330 | if ((syzstr->resPairs[index-1]!=NULL) && (!idIs0(syzstr->res[index]))) |
---|
| 2331 | { |
---|
| 2332 | result=new intvec(IDELEMS(syzstr->res[index])+1); |
---|
| 2333 | for (int i=(*syzstr->Tl)[index-1]-1;i>=0;i--) |
---|
| 2334 | { |
---|
| 2335 | if (syzstr->resPairs[index-1][i].isNotMinimal!=NULL) |
---|
| 2336 | { |
---|
| 2337 | (*result)[syzstr->resPairs[index-1][i].syzind+1] = 1; |
---|
| 2338 | } |
---|
| 2339 | } |
---|
| 2340 | } |
---|
| 2341 | return result; |
---|
| 2342 | } |
---|
| 2343 | |
---|
| 2344 | /*2 |
---|
| 2345 | * re-computes the order of pairs during the algorithm |
---|
| 2346 | * this ensures to procede with a triangular matrix |
---|
| 2347 | */ |
---|
| 2348 | static intvec * syOrdPairs(SSet sPairs, int length) |
---|
| 2349 | { |
---|
| 2350 | intvec * result=new intvec(length,1,-1); |
---|
| 2351 | int i,j=0,k=-1,l,ii; |
---|
| 2352 | |
---|
| 2353 | loop |
---|
| 2354 | { |
---|
| 2355 | l = -1; |
---|
| 2356 | for(i=0;i<length;i++) |
---|
| 2357 | { |
---|
| 2358 | if (sPairs[i].syzind>k) |
---|
| 2359 | { |
---|
| 2360 | if (l==-1) |
---|
| 2361 | { |
---|
| 2362 | l = sPairs[i].syzind; |
---|
| 2363 | ii = i; |
---|
| 2364 | } |
---|
| 2365 | else |
---|
| 2366 | { |
---|
| 2367 | if (sPairs[i].syzind<l) |
---|
| 2368 | { |
---|
| 2369 | l = sPairs[i].syzind; |
---|
| 2370 | ii = i; |
---|
| 2371 | } |
---|
| 2372 | } |
---|
| 2373 | } |
---|
| 2374 | } |
---|
| 2375 | if (l==-1) break; |
---|
| 2376 | (*result)[j] = ii; |
---|
| 2377 | j++; |
---|
| 2378 | k = l; |
---|
| 2379 | } |
---|
| 2380 | return result; |
---|
| 2381 | } |
---|
| 2382 | |
---|
| 2383 | /*2 |
---|
| 2384 | * minimizes the output of LaScala |
---|
| 2385 | */ |
---|
| 2386 | static resolvente syReadOutMinimalRes(syStrategy syzstr, |
---|
| 2387 | BOOLEAN computeStd=FALSE) |
---|
| 2388 | { |
---|
| 2389 | intvec * Strip, * ordn; |
---|
| 2390 | resolvente tres=(resolvente)omAlloc0((syzstr->length+1)*sizeof(ideal)); |
---|
| 2391 | ring tmpR = NULL; |
---|
| 2392 | ring origR = currRing; |
---|
| 2393 | |
---|
| 2394 | //Print("Hier "); |
---|
| 2395 | if (computeStd) |
---|
| 2396 | { |
---|
| 2397 | tres[0] = syzstr->res[1]; |
---|
| 2398 | syzstr->res[1] = idInit(IDELEMS(tres[0]),tres[0]->rank); |
---|
| 2399 | return tres; |
---|
| 2400 | } |
---|
| 2401 | int i,j,l,index,ii,i1; |
---|
| 2402 | poly p; |
---|
| 2403 | ideal rs; |
---|
| 2404 | SSet sPairs; |
---|
| 2405 | int * ord,*b0,*b1; |
---|
| 2406 | |
---|
| 2407 | assume(syzstr->syRing != NULL); |
---|
| 2408 | rChangeCurrRing(syzstr->syRing); |
---|
| 2409 | //Print("laeufts "); |
---|
| 2410 | syzstr->bucket = kBucketCreate(); |
---|
| 2411 | for (index=syzstr->length-1;index>0;index--) |
---|
| 2412 | { |
---|
| 2413 | if (syzstr->resPairs[index]!=NULL) |
---|
| 2414 | { |
---|
| 2415 | //Print("ideal %d: \n",index); |
---|
| 2416 | currcomponents = syzstr->truecomponents[index]; |
---|
| 2417 | currShiftedComponents = syzstr->ShiftedComponents[index]; |
---|
| 2418 | rChangeSComps(currcomponents, currShiftedComponents, |
---|
| 2419 | IDELEMS(syzstr->res[index])); |
---|
| 2420 | sPairs = syzstr->resPairs[index]; |
---|
| 2421 | Strip = syToStrip(syzstr,index); |
---|
| 2422 | tres[index+1] = idInit(IDELEMS(syzstr->res[index+1]),syzstr->res[index+1]->rank); |
---|
| 2423 | i1 = (*syzstr->Tl)[index]; |
---|
| 2424 | //Print("i1= %d\n",i1); |
---|
| 2425 | ordn = syOrdPairs(sPairs,i1); |
---|
| 2426 | for (i=0;i<i1;i++) |
---|
| 2427 | { |
---|
| 2428 | if ((sPairs[i].isNotMinimal==NULL) && (sPairs[i].lcm!=NULL)) |
---|
| 2429 | { |
---|
| 2430 | l = sPairs[i].syzind; |
---|
| 2431 | //Print("Minimiere Poly %d: ",l);pWrite(syzstr->res[index+1]->m[l]); |
---|
| 2432 | tres[index+1]->m[l] = |
---|
| 2433 | syMinimizeP1(l,syzstr,ordn,index,Strip); |
---|
| 2434 | } |
---|
| 2435 | } |
---|
| 2436 | delete Strip; |
---|
| 2437 | Strip = NULL; |
---|
| 2438 | } |
---|
| 2439 | } |
---|
| 2440 | currcomponents = syzstr->truecomponents[0]; |
---|
| 2441 | currShiftedComponents = syzstr->ShiftedComponents[0]; |
---|
| 2442 | rChangeSComps( currcomponents, currShiftedComponents, |
---|
| 2443 | IDELEMS(syzstr->res[0])); |
---|
| 2444 | tres[1] = idInit(IDELEMS(syzstr->res[1]),syzstr->res[1]->rank); |
---|
| 2445 | sPairs = syzstr->resPairs[0]; |
---|
| 2446 | for (i=(*syzstr->Tl)[0]-1;i>=0;i--) |
---|
| 2447 | { |
---|
| 2448 | if (sPairs[i].syzind>=0) |
---|
| 2449 | { |
---|
| 2450 | tres[1]->m[sPairs[i].syzind] = pCopy(syzstr->res[1]->m[sPairs[i].syzind]); |
---|
| 2451 | } |
---|
| 2452 | } |
---|
| 2453 | /*--- changes to the original ring------------------*/ |
---|
| 2454 | kBucketDestroy(&syzstr->bucket); |
---|
| 2455 | if (syzstr->syRing != NULL) |
---|
| 2456 | { |
---|
| 2457 | rChangeCurrRing(origR); |
---|
| 2458 | // Thomas: now make sure that all data which you need is pFetchCopied |
---|
| 2459 | // maybe incoporate it into syReorder ?? |
---|
| 2460 | } |
---|
| 2461 | tres = syReorder(tres,syzstr->length,syzstr,FALSE,syzstr->res); |
---|
| 2462 | syKillEmptyEntres(tres,syzstr->length); |
---|
| 2463 | idSkipZeroes(tres[0]); |
---|
| 2464 | return tres; |
---|
| 2465 | } |
---|
| 2466 | |
---|
| 2467 | /*3 |
---|
| 2468 | * minimizes any kind of resolution |
---|
| 2469 | */ |
---|
| 2470 | syStrategy syMinimize(syStrategy syzstr) |
---|
| 2471 | { |
---|
| 2472 | if (syzstr->minres==NULL) |
---|
| 2473 | { |
---|
| 2474 | if (syzstr->resPairs!=NULL) |
---|
| 2475 | { |
---|
| 2476 | if (syzstr->hilb_coeffs==NULL) |
---|
| 2477 | { |
---|
| 2478 | syzstr->minres = syReadOutMinimalRes(syzstr); |
---|
| 2479 | } |
---|
| 2480 | else |
---|
| 2481 | { |
---|
| 2482 | syzstr->minres = syReorder(syzstr->orderedRes,syzstr->length,syzstr); |
---|
| 2483 | } |
---|
| 2484 | } |
---|
| 2485 | else if (syzstr->fullres!=NULL) |
---|
| 2486 | { |
---|
| 2487 | syMinimizeResolvente(syzstr->fullres,syzstr->length,1); |
---|
| 2488 | syzstr->minres = syzstr->fullres; |
---|
| 2489 | syzstr->fullres = NULL; |
---|
| 2490 | } |
---|
| 2491 | } |
---|
| 2492 | (syzstr->references)++; |
---|
| 2493 | return syzstr; |
---|
| 2494 | } |
---|
| 2495 | |
---|
| 2496 | /*2 |
---|
| 2497 | * implementation of LaScala's algorithm |
---|
| 2498 | * assumes that the given module is homogeneous |
---|
| 2499 | * works with slanted degree, uses syChosePairs |
---|
| 2500 | */ |
---|
| 2501 | syStrategy syLaScala3(ideal arg,int * length) |
---|
| 2502 | { |
---|
| 2503 | BOOLEAN noPair=FALSE; |
---|
| 2504 | int i,j,actdeg=32000,index=0,reg=-1; |
---|
| 2505 | int startdeg,howmuch; |
---|
| 2506 | poly p; |
---|
| 2507 | ideal temp; |
---|
| 2508 | SSet nextPairs; |
---|
| 2509 | syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy)); |
---|
| 2510 | ring origR = currRing; |
---|
| 2511 | |
---|
| 2512 | if ((idIs0(arg)) || |
---|
| 2513 | ((idRankFreeModule(arg)>0) && (!idHomModule(arg,NULL,&(syzstr->cw))))) |
---|
| 2514 | { |
---|
| 2515 | syzstr->minres = (resolvente)omAlloc0Bin(ideal_bin); |
---|
| 2516 | syzstr->length = 1; |
---|
| 2517 | syzstr->minres[0] = idInit(1,arg->rank); |
---|
| 2518 | return syzstr; |
---|
| 2519 | } |
---|
| 2520 | |
---|
| 2521 | //crit = 0; |
---|
| 2522 | //euler = -1; |
---|
| 2523 | redpol = pInit(); |
---|
| 2524 | syzstr->length = *length = pVariables+2; |
---|
| 2525 | |
---|
| 2526 | // Creare dp,S ring and change to it |
---|
| 2527 | syzstr->syRing = rCurrRingAssure_dp_S(); |
---|
| 2528 | assume(syzstr->syRing != origR); |
---|
| 2529 | |
---|
| 2530 | // set initial ShiftedComps |
---|
| 2531 | currcomponents = (int*)omAlloc0((arg->rank+1)*sizeof(int)); |
---|
| 2532 | currShiftedComponents = (long*)omAlloc0((arg->rank+1)*sizeof(long)); |
---|
| 2533 | for (i=0;i<=arg->rank;i++) |
---|
| 2534 | { |
---|
| 2535 | currShiftedComponents[i] = (i)*SYZ_SHIFT_BASE; |
---|
| 2536 | currcomponents[i] = i; |
---|
| 2537 | } |
---|
| 2538 | rChangeSComps(currcomponents, currShiftedComponents, arg->rank); |
---|
| 2539 | /*--- initializes the data structures---------------*/ |
---|
| 2540 | syzstr->Tl = new intvec(*length); |
---|
| 2541 | temp = idInit(IDELEMS(arg),arg->rank); |
---|
| 2542 | for (i=0;i<IDELEMS(arg);i++) |
---|
| 2543 | { |
---|
| 2544 | temp->m[i] = prCopyR( arg->m[i], origR); |
---|
| 2545 | if (temp->m[i]!=NULL) |
---|
| 2546 | { |
---|
| 2547 | j = pTotaldegree(temp->m[i]); |
---|
| 2548 | if (j<actdeg) actdeg = j; |
---|
| 2549 | } |
---|
| 2550 | } |
---|
| 2551 | idTest(temp); |
---|
| 2552 | idSkipZeroes(temp); |
---|
| 2553 | idTest(temp); |
---|
| 2554 | syzstr->resPairs = syInitRes(temp,length,syzstr->Tl,syzstr->cw); |
---|
| 2555 | omFreeSize((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int)); |
---|
| 2556 | omFreeSize((ADDRESS)currShiftedComponents,(arg->rank+1)*sizeof(long)); |
---|
| 2557 | syzstr->res = (resolvente)omAlloc0((*length+1)*sizeof(ideal)); |
---|
| 2558 | syzstr->orderedRes = (resolvente)omAlloc0((*length+1)*sizeof(ideal)); |
---|
| 2559 | syzstr->elemLength = (int**)omAlloc0((*length+1)*sizeof(int*)); |
---|
| 2560 | syzstr->truecomponents = (int**)omAlloc0((*length+1)*sizeof(int*)); |
---|
| 2561 | syzstr->ShiftedComponents = (long**)omAlloc0((*length+1)*sizeof(long*)); |
---|
| 2562 | syzstr->backcomponents = (int**)omAlloc0((*length+1)*sizeof(int*)); |
---|
| 2563 | syzstr->Howmuch = (int**)omAlloc0((*length+1)*sizeof(int*)); |
---|
| 2564 | syzstr->Firstelem = (int**)omAlloc0((*length+1)*sizeof(int*)); |
---|
| 2565 | syzstr->sev = (unsigned long **) omAlloc0((*length+1)*sizeof(unsigned long *)); |
---|
| 2566 | syzstr->bucket = kBucketCreate(); |
---|
| 2567 | int len0=idRankFreeModule(temp)+1; |
---|
| 2568 | |
---|
| 2569 | startdeg = actdeg; |
---|
| 2570 | nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg); |
---|
| 2571 | //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index); |
---|
| 2572 | /*--- computes the resolution ----------------------*/ |
---|
| 2573 | while (nextPairs!=NULL) |
---|
| 2574 | { |
---|
| 2575 | if (TEST_OPT_PROT) Print("%d",actdeg); |
---|
| 2576 | if (TEST_OPT_PROT) Print("(m%d)",index); |
---|
| 2577 | if (index==0) |
---|
| 2578 | i = syInitSyzMod(syzstr,index,len0); |
---|
| 2579 | else |
---|
| 2580 | i = syInitSyzMod(syzstr,index); |
---|
| 2581 | currcomponents = syzstr->truecomponents[si_max(index-1,0)]; |
---|
| 2582 | currShiftedComponents = syzstr->ShiftedComponents[si_max(index-1,0)]; |
---|
| 2583 | rChangeSComps(currcomponents, currShiftedComponents, |
---|
| 2584 | IDELEMS(syzstr->res[si_max(index-1,0)])); |
---|
| 2585 | j = syInitSyzMod(syzstr,index+1); |
---|
| 2586 | if (index>0) |
---|
| 2587 | { |
---|
| 2588 | syRedNextPairs(nextPairs,syzstr,howmuch,index); |
---|
| 2589 | syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0); |
---|
| 2590 | } |
---|
| 2591 | else |
---|
| 2592 | syRedGenerOfCurrDeg(syzstr,actdeg,index+1); |
---|
| 2593 | /*--- creates new pairs -----------------------------*/ |
---|
| 2594 | syCreateNewPairs(syzstr,index,i); |
---|
| 2595 | if (index<(*length)-1) |
---|
| 2596 | { |
---|
| 2597 | syCreateNewPairs(syzstr,index+1,j); |
---|
| 2598 | } |
---|
| 2599 | index++; |
---|
| 2600 | nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg); |
---|
| 2601 | //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index); |
---|
| 2602 | } |
---|
| 2603 | if (temp!=NULL) idDelete(&temp); |
---|
| 2604 | kBucketDestroy(&(syzstr->bucket)); |
---|
| 2605 | if (origR != syzstr->syRing) |
---|
| 2606 | rChangeCurrRing(origR); |
---|
| 2607 | pDeleteLm(&redpol); |
---|
| 2608 | if (TEST_OPT_PROT) PrintLn(); |
---|
| 2609 | return syzstr; |
---|
| 2610 | } |
---|
| 2611 | |
---|
[50d54f8] | 2612 | |
---|
| 2613 | |
---|
| 2614 | /*2 |
---|
| 2615 | * more general implementation of LaScala's algorithm |
---|
| 2616 | * assumes that the given module is (quasi-)homogeneous |
---|
| 2617 | * works with slanted degree, uses syChosePairs |
---|
| 2618 | */ |
---|
| 2619 | syStrategy syLaScala(ideal arg, int& maxlength, intvec* weights) |
---|
| 2620 | { |
---|
| 2621 | BOOLEAN noPair=FALSE; |
---|
| 2622 | int i,j,actdeg=32000,index=0,reg=-1; |
---|
| 2623 | int startdeg,howmuch; |
---|
| 2624 | poly p; |
---|
| 2625 | ideal temp; |
---|
| 2626 | SSet nextPairs; |
---|
| 2627 | syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy)); |
---|
| 2628 | ring origR = currRing; |
---|
| 2629 | |
---|
| 2630 | if(weights!= NULL) |
---|
| 2631 | syzstr->cw = new intvec(weights); |
---|
| 2632 | else |
---|
| 2633 | syzstr->cw = NULL; |
---|
| 2634 | |
---|
| 2635 | if ((idIs0(arg)) || |
---|
| 2636 | ((idRankFreeModule(arg)>0) && (!idTestHomModule(arg, NULL, syzstr->cw)))) |
---|
| 2637 | { |
---|
| 2638 | syzstr->minres = (resolvente)omAlloc0Bin(ideal_bin); |
---|
| 2639 | syzstr->length = 1; |
---|
| 2640 | syzstr->minres[0] = idInit(1,arg->rank); |
---|
| 2641 | return syzstr; |
---|
| 2642 | } |
---|
| 2643 | |
---|
| 2644 | |
---|
| 2645 | //crit = 0; |
---|
| 2646 | //euler = -1; |
---|
| 2647 | redpol = pInit(); |
---|
| 2648 | |
---|
| 2649 | if( maxlength > 0 ) |
---|
| 2650 | syzstr->length = maxlength; // = pVariables+2; |
---|
| 2651 | else |
---|
| 2652 | syzstr->length = maxlength = pVariables+2; |
---|
| 2653 | |
---|
| 2654 | // Creare dp,S ring and change to it |
---|
| 2655 | syzstr->syRing = rCurrRingAssure_dp_S(); |
---|
| 2656 | assume(syzstr->syRing != origR); |
---|
| 2657 | |
---|
| 2658 | // set initial ShiftedComps |
---|
| 2659 | currcomponents = (int*)omAlloc0((arg->rank+1)*sizeof(int)); |
---|
| 2660 | currShiftedComponents = (long*)omAlloc0((arg->rank+1)*sizeof(long)); |
---|
| 2661 | for (i=0;i<=arg->rank;i++) |
---|
| 2662 | { |
---|
| 2663 | currShiftedComponents[i] = (i)*SYZ_SHIFT_BASE; |
---|
| 2664 | currcomponents[i] = i; |
---|
| 2665 | } |
---|
| 2666 | rChangeSComps(currcomponents, currShiftedComponents, arg->rank); |
---|
| 2667 | /*--- initializes the data structures---------------*/ |
---|
| 2668 | syzstr->Tl = new intvec(maxlength); |
---|
| 2669 | temp = idInit(IDELEMS(arg),arg->rank); |
---|
| 2670 | for (i=0;i<IDELEMS(arg);i++) |
---|
| 2671 | { |
---|
| 2672 | temp->m[i] = prCopyR( arg->m[i], origR); |
---|
| 2673 | if (temp->m[i]!=NULL) |
---|
| 2674 | { |
---|
| 2675 | j = pTotaldegree(temp->m[i]); |
---|
| 2676 | if (j<actdeg) actdeg = j; |
---|
| 2677 | } |
---|
| 2678 | } |
---|
| 2679 | idTest(temp); |
---|
| 2680 | idSkipZeroes(temp); |
---|
| 2681 | idTest(temp); |
---|
| 2682 | syzstr->resPairs = syInitRes(temp,&maxlength,syzstr->Tl,syzstr->cw); |
---|
| 2683 | omFreeSize((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int)); |
---|
| 2684 | omFreeSize((ADDRESS)currShiftedComponents,(arg->rank+1)*sizeof(long)); |
---|
| 2685 | syzstr->res = (resolvente)omAlloc0((maxlength+1)*sizeof(ideal)); |
---|
| 2686 | syzstr->orderedRes = (resolvente)omAlloc0((maxlength+1)*sizeof(ideal)); |
---|
| 2687 | syzstr->elemLength = (int**)omAlloc0((maxlength+1)*sizeof(int*)); |
---|
| 2688 | syzstr->truecomponents = (int**)omAlloc0((maxlength+1)*sizeof(int*)); |
---|
| 2689 | syzstr->ShiftedComponents = (long**)omAlloc0((maxlength+1)*sizeof(long*)); |
---|
| 2690 | syzstr->backcomponents = (int**)omAlloc0((maxlength+1)*sizeof(int*)); |
---|
| 2691 | syzstr->Howmuch = (int**)omAlloc0((maxlength+1)*sizeof(int*)); |
---|
| 2692 | syzstr->Firstelem = (int**)omAlloc0((maxlength+1)*sizeof(int*)); |
---|
| 2693 | syzstr->sev = (unsigned long **) omAlloc0((maxlength+1)*sizeof(unsigned long *)); |
---|
| 2694 | syzstr->bucket = kBucketCreate(); |
---|
| 2695 | int len0=idRankFreeModule(temp)+1; |
---|
| 2696 | |
---|
| 2697 | startdeg = actdeg; |
---|
| 2698 | nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg); |
---|
| 2699 | //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index); |
---|
| 2700 | /*--- computes the resolution ----------------------*/ |
---|
| 2701 | while (nextPairs!=NULL) |
---|
| 2702 | { |
---|
| 2703 | if (TEST_OPT_PROT) Print("%d",actdeg); |
---|
| 2704 | if (TEST_OPT_PROT) Print("(m%d)",index); |
---|
| 2705 | if (index==0) |
---|
| 2706 | i = syInitSyzMod(syzstr,index,len0); |
---|
| 2707 | else |
---|
| 2708 | i = syInitSyzMod(syzstr,index); |
---|
| 2709 | currcomponents = syzstr->truecomponents[si_max(index-1,0)]; |
---|
| 2710 | currShiftedComponents = syzstr->ShiftedComponents[si_max(index-1,0)]; |
---|
| 2711 | rChangeSComps(currcomponents, currShiftedComponents, |
---|
| 2712 | IDELEMS(syzstr->res[si_max(index-1,0)])); |
---|
| 2713 | j = syInitSyzMod(syzstr,index+1); |
---|
| 2714 | if (index>0) |
---|
| 2715 | { |
---|
| 2716 | syRedNextPairs(nextPairs,syzstr,howmuch,index); |
---|
| 2717 | syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0); |
---|
| 2718 | } |
---|
| 2719 | else |
---|
| 2720 | syRedGenerOfCurrDeg(syzstr,actdeg,index+1); |
---|
| 2721 | /*--- creates new pairs -----------------------------*/ |
---|
| 2722 | syCreateNewPairs(syzstr,index,i); |
---|
| 2723 | if (index<(maxlength-1)) |
---|
| 2724 | { |
---|
| 2725 | syCreateNewPairs(syzstr,index+1,j); |
---|
| 2726 | } |
---|
| 2727 | index++; |
---|
| 2728 | nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg); |
---|
| 2729 | //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index); |
---|
| 2730 | } |
---|
| 2731 | if (temp!=NULL) idDelete(&temp); |
---|
| 2732 | kBucketDestroy(&(syzstr->bucket)); |
---|
| 2733 | if (origR != syzstr->syRing) |
---|
| 2734 | rChangeCurrRing(origR); |
---|
| 2735 | pDeleteLm(&redpol); |
---|
| 2736 | if (TEST_OPT_PROT) PrintLn(); |
---|
| 2737 | return syzstr; |
---|
| 2738 | } |
---|
| 2739 | |
---|