Changeset 410ea0f in git
 Timestamp:
 May 27, 2011, 4:18:06 PM (12 years ago)
 Branches:
 (u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')
 Children:
 db83bf13b62d944de021f52de5ae04b7ffd0390e
 Parents:
 a41623dd1e56318466dc81751481d37d19489c7b
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

kernel/tgb.cc
ra41623 r410ea0f 32 32 #define BUCKETS_FOR_NORO_RED 1 33 33 #define SR_HDL(A) ((long)(A)) 34 static const int bundle_size =100;35 static const int bundle_size_noro =10000;36 static const int delay_factor =3;37 int QlogSize (number n);34 static const int bundle_size = 100; 35 static const int bundle_size_noro = 10000; 36 static const int delay_factor = 3; 37 int QlogSize (number n); 38 38 #define ADD_LATER_SIZE 500 39 39 #if 1 40 static omBin lm_bin=NULL; 41 42 static void simplify_poly(poly p, ring r) 43 { 44 assume(r==currRing); 45 if (!rField_is_Zp(r)) 46 { 47 p_Cleardenom(p,r); 48 //p_Content(p,r); //is a duplicate call, but belongs here 49 } 50 else 51 pNorm(p); 52 } 40 static omBin lm_bin = NULL; 41 42 static void 43 simplify_poly (poly p, ring r) 44 { 45 assume (r == currRing); 46 if (!rField_is_Zp (r)) 47 { 48 p_Cleardenom (p, r); 49 //p_Content(p,r); //is a duplicate call, but belongs here 50 } 51 else 52 pNorm (p); 53 } 54 53 55 //static const BOOLEAN up_to_radical=TRUE; 54 56 55 int slim_nsize(number n, ring r) 56 { 57 if (rField_is_Zp(r)) 57 int 58 slim_nsize (number n, ring r) 59 { 60 if (rField_is_Zp (r)) 58 61 { 59 62 return 1; 60 63 } 61 if (rField_is_Q (r))62 { 63 return QlogSize (n);64 if (rField_is_Q (r)) 65 { 66 return QlogSize (n); 64 67 } 65 68 else 66 69 { 67 return n_Size(n,r); 68 } 69 } 70 static BOOLEAN monomial_root(poly m, ring r) 71 { 72 BOOLEAN changed=FALSE; 73 int i; 74 for(i=1;i<=rVar(r);i++) 75 { 76 int e=p_GetExp(m,i,r); 77 if (e>1) 78 { 79 p_SetExp(m,i,1,r); 80 changed=TRUE; 81 } 82 } 83 if (changed) { 84 p_Setm(m,r); 85 } 86 return changed; 87 } 88 static BOOLEAN polynomial_root(poly h, ring r) 89 { 90 poly got=gcd_of_terms(h,r); 91 BOOLEAN changed=FALSE; 92 if((got!=NULL) &&(TEST_V_UPTORADICAL)) { 93 poly copy=p_Copy(got,r); 70 return n_Size (n, r); 71 } 72 } 73 74 static BOOLEAN 75 monomial_root (poly m, ring r) 76 { 77 BOOLEAN changed = FALSE; 78 int i; 79 for (i = 1; i <= rVar (r); i++) 80 { 81 int e = p_GetExp (m, i, r); 82 if (e > 1) 83 { 84 p_SetExp (m, i, 1, r); 85 changed = TRUE; 86 } 87 } 88 if (changed) 89 { 90 p_Setm (m, r); 91 } 92 return changed; 93 } 94 95 static BOOLEAN 96 polynomial_root (poly h, ring r) 97 { 98 poly got = gcd_of_terms (h, r); 99 BOOLEAN changed = FALSE; 100 if ((got != NULL) && (TEST_V_UPTORADICAL)) 101 { 102 poly copy = p_Copy (got, r); 94 103 //p_wrp(got,c>r); 95 changed =monomial_root(got,r);104 changed = monomial_root (got, r); 96 105 if (changed) 97 106 { 98 poly div_by=pDivide(copy, got);99 poly iter=h;100 while(iter)101 102 pExpVectorSub(iter,div_by);103 pIter(iter);104 105 p_Delete(&div_by, r);106 107 PrintS("U");108 } 109 p_Delete (©,r);110 } 111 p_Delete (&got,r);107 poly div_by = pDivide (copy, got); 108 poly iter = h; 109 while (iter) 110 { 111 pExpVectorSub (iter, div_by); 112 pIter (iter); 113 } 114 p_Delete (&div_by, r); 115 if (TEST_OPT_PROT) 116 PrintS ("U"); 117 } 118 p_Delete (©, r); 119 } 120 p_Delete (&got, r); 112 121 return changed; 113 122 } 114 static inline poly p_Init_Special(const ring r) 115 { 116 return p_Init(r,lm_bin); 117 } 118 static inline poly pOne_Special(const ring r=currRing) 119 { 120 poly rc = p_Init_Special(r); 121 pSetCoeff0(rc,n_Init(1,r)); 123 124 static inline poly 125 p_Init_Special (const ring r) 126 { 127 return p_Init (r, lm_bin); 128 } 129 130 static inline poly 131 pOne_Special (const ring r = currRing) 132 { 133 poly rc = p_Init_Special (r); 134 pSetCoeff0 (rc, n_Init (1, r)); 122 135 return rc; 123 136 } 137 124 138 // zum Initialiseren: in t_rep_gb plazieren: 125 139 … … 133 147 #ifdef LEN_VAR1 134 148 // erste Variante: Laenge: Anzahl der Monome 135 static inline int pSLength(poly p, int l) { return l; } 136 static inline int kSBucketLength(kBucket* bucket, poly lm) 137 {return bucket_guess(bucket);} 149 static inline int 150 pSLength (poly p, int l) 151 { 152 return l; 153 } 154 155 static inline int 156 kSBucketLength (kBucket * bucket, poly lm) 157 { 158 return bucket_guess (bucket); 159 } 138 160 #endif 139 161 140 162 #ifdef LEN_VAR2 141 163 // 2. Variante: Laenge: Platz fuer die Koeff. 142 int pSLength(poly p,int l) 143 { 144 int s=0; 145 while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } 164 int 165 pSLength (poly p, int l) 166 { 167 int s = 0; 168 while (p != NULL) 169 { 170 s += nSize (pGetCoeff (p)); 171 pIter (p); 172 } 146 173 return s; 147 174 } 148 int kSBucketLength(kBucket* b, poly lm) 149 { 150 int s=0; 175 176 int 177 kSBucketLength (kBucket * b, poly lm) 178 { 179 int s = 0; 151 180 int i; 152 for (i =MAX_BUCKET;i>=0;i)153 { 154 s +=pSLength(b>buckets[i],0);181 for (i = MAX_BUCKET; i >= 0; i) 182 { 183 s += pSLength (b>buckets[i], 0); 155 184 } 156 185 return s; … … 158 187 #endif 159 188 160 int QlogSize(number n) 161 { 162 if (SR_HDL(n) & SR_INT) 163 { 164 long i=SR_TO_INT(n); 165 if (i==0) return 0; 166 167 unsigned long v; 168 v=(i>=0)?i:i; 169 int r = 0; 170 171 while (v >>= 1) 172 { 173 r++; 174 } 175 return r+1; 176 } 177 //assume denominator is 0 178 return mpz_sizeinbase(n>z,2); 189 int 190 QlogSize (number n) 191 { 192 if (SR_HDL (n) & SR_INT) 193 { 194 long i = SR_TO_INT (n); 195 if (i == 0) 196 return 0; 197 198 unsigned long v; 199 v = (i >= 0) ? i : i; 200 int r = 0; 201 202 while (v >>= 1) 203 { 204 r++; 205 } 206 return r + 1; 207 } 208 //assume denominator is 0 209 return mpz_sizeinbase (n>z, 2); 179 210 } 180 211 181 212 #ifdef LEN_VAR3 182 static inline wlen_type pSLength(poly p,int l) 213 static inline wlen_type 214 pSLength (poly p, int l) 183 215 { 184 216 wlen_type c; 185 number coef =pGetCoeff(p);186 if (rField_is_Q (currRing))187 { 188 c =QlogSize(coef);217 number coef = pGetCoeff (p); 218 if (rField_is_Q (currRing)) 219 { 220 c = QlogSize (coef); 189 221 } 190 222 else 191 c =nSize(coef);223 c = nSize (coef); 192 224 if (!(TEST_V_COEFSTRAT)) 193 return (wlen_type)c*(wlen_type)l /*pLength(p)*/;225 return (wlen_type) c *(wlen_type) l /*pLength(p) */ ; 194 226 else 195 227 { 196 wlen_type res =l;197 res *=c;198 res *=c;228 wlen_type res = l; 229 res *= c; 230 res *= c; 199 231 return res; 200 232 } 201 233 } 234 202 235 //! TODO CoefBuckets bercksichtigen 203 wlen_type kSBucketLength(kBucket* b, poly lm=NULL) 204 { 205 int s=0; 236 wlen_type 237 kSBucketLength (kBucket * b, poly lm = NULL) 238 { 239 int s = 0; 206 240 wlen_type c; 207 241 number coef; 208 if (lm==NULL)209 coef =pGetCoeff(kBucketGetLm(b));210 242 if (lm == NULL) 243 coef = pGetCoeff (kBucketGetLm (b)); 244 //c=nSize(pGetCoeff(kBucketGetLm(b))); 211 245 else 212 coef =pGetCoeff(lm);213 214 if (rField_is_Q (currRing))215 { 216 c =QlogSize(coef);246 coef = pGetCoeff (lm); 247 //c=nSize(pGetCoeff(lm)); 248 if (rField_is_Q (currRing)) 249 { 250 c = QlogSize (coef); 217 251 } 218 252 else 219 c =nSize(coef);253 c = nSize (coef); 220 254 221 255 int i; 222 for (i =b>buckets_used;i>=0;i)223 { 224 assume ((b>buckets_length[i]==0)(b>buckets[i]!=NULL));225 s +=b>buckets_length[i] /*pLength(b>buckets[i])*/;226 } 227 228 assume (b>buckets[0]==kBucketGetLm(b));229 if (b>coef[0] !=NULL)230 { 231 if (rField_is_Q (currRing))232 { 233 int modifier =QlogSize(pGetCoeff(b>coef[0]));234 c +=modifier;256 for (i = b>buckets_used; i >= 0; i) 257 { 258 assume ((b>buckets_length[i] == 0)  (b>buckets[i] != NULL)); 259 s += b>buckets_length[i] /*pLength(b>buckets[i]) */ ; 260 } 261 #ifdef HAVE_COEF_BUCKETS 262 assume (b>buckets[0] == kBucketGetLm (b)); 263 if (b>coef[0] != NULL) 264 { 265 if (rField_is_Q (currRing)) 266 { 267 int modifier = QlogSize (pGetCoeff (b>coef[0])); 268 c += modifier; 235 269 } 236 270 else 237 271 { 238 int modifier =nSize(pGetCoeff(b>coef[0]));239 c *=modifier;240 } 241 } 242 272 int modifier = nSize (pGetCoeff (b>coef[0])); 273 c *= modifier; 274 } 275 } 276 #endif 243 277 if (!(TEST_V_COEFSTRAT)) 244 278 { 245 return s *c;279 return s * c; 246 280 } 247 281 else 248 282 { 249 wlen_type res =s;250 res *=c;251 res *=c;283 wlen_type res = s; 284 res *= c; 285 res *= c; 252 286 return res; 253 287 } … … 255 289 #endif 256 290 #ifdef LEN_VAR5 257 static inline wlen_type pSLength(poly p,int l) 291 static inline wlen_type 292 pSLength (poly p, int l) 258 293 { 259 294 int c; 260 number coef =pGetCoeff(p);261 if (rField_is_Q (currRing))262 { 263 c =QlogSize(coef);295 number coef = pGetCoeff (p); 296 if (rField_is_Q (currRing)) 297 { 298 c = QlogSize (coef); 264 299 } 265 300 else 266 c =nSize(coef);267 wlen_type erg =l;268 erg *=c;269 erg *=c;301 c = nSize (coef); 302 wlen_type erg = l; 303 erg *= c; 304 erg *= c; 270 305 //PrintS("lenvar 5"); 271 assume(erg>=0); 272 return erg; /*pLength(p)*/; 273 } 306 assume (erg >= 0); 307 return erg; /*pLength(p) */ ; 308 } 309 274 310 //! TODO CoefBuckets bercksichtigen 275 wlen_type kSBucketLength(kBucket* b, poly lm=NULL) 276 { 277 wlen_type s=0; 311 wlen_type 312 kSBucketLength (kBucket * b, poly lm = NULL) 313 { 314 wlen_type s = 0; 278 315 int c; 279 316 number coef; 280 if (lm==NULL)281 coef =pGetCoeff(kBucketGetLm(b));282 317 if (lm == NULL) 318 coef = pGetCoeff (kBucketGetLm (b)); 319 //c=nSize(pGetCoeff(kBucketGetLm(b))); 283 320 else 284 coef =pGetCoeff(lm);285 286 if (rField_is_Q (currRing))287 { 288 c =QlogSize(coef);321 coef = pGetCoeff (lm); 322 //c=nSize(pGetCoeff(lm)); 323 if (rField_is_Q (currRing)) 324 { 325 c = QlogSize (coef); 289 326 } 290 327 else 291 c =nSize(coef);328 c = nSize (coef); 292 329 293 330 int i; 294 for (i =b>buckets_used;i>=0;i)295 { 296 assume ((b>buckets_length[i]==0)(b>buckets[i]!=NULL));297 s +=b>buckets_length[i] /*pLength(b>buckets[i])*/;298 } 299 300 assume (b>buckets[0]==kBucketGetLm(b));301 if (b>coef[0] !=NULL)302 { 303 if (rField_is_Q (currRing))304 { 305 int modifier =QlogSize(pGetCoeff(b>coef[0]));306 c +=modifier;331 for (i = b>buckets_used; i >= 0; i) 332 { 333 assume ((b>buckets_length[i] == 0)  (b>buckets[i] != NULL)); 334 s += b>buckets_length[i] /*pLength(b>buckets[i]) */ ; 335 } 336 #ifdef HAVE_COEF_BUCKETS 337 assume (b>buckets[0] == kBucketGetLm (b)); 338 if (b>coef[0] != NULL) 339 { 340 if (rField_is_Q (currRing)) 341 { 342 int modifier = QlogSize (pGetCoeff (b>coef[0])); 343 c += modifier; 307 344 } 308 345 else 309 346 { 310 int modifier=nSize(pGetCoeff(b>coef[0])); 311 c*=modifier;} 312 } 313 #endif 314 wlen_type erg=s; 315 erg*=c; 316 erg*=c; 347 int modifier = nSize (pGetCoeff (b>coef[0])); 348 c *= modifier; 349 } 350 } 351 #endif 352 wlen_type erg = s; 353 erg *= c; 354 erg *= c; 317 355 return erg; 318 356 } … … 321 359 #ifdef LEN_VAR4 322 360 // 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.) 323 int pSLength(poly p, int l) 324 { 325 int s=1; 326 int c=nSize(pGetCoeff(p)); 327 pIter(p); 328 while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } 329 return s*c; 330 } 331 int kSBucketLength(kBucket* b) 332 { 333 int s=1; 334 int c=nSize(pGetCoeff(kBucketGetLm(b))); 361 int 362 pSLength (poly p, int l) 363 { 364 int s = 1; 365 int c = nSize (pGetCoeff (p)); 366 pIter (p); 367 while (p != NULL) 368 { 369 s += nSize (pGetCoeff (p)); 370 pIter (p); 371 } 372 return s * c; 373 } 374 375 int 376 kSBucketLength (kBucket * b) 377 { 378 int s = 1; 379 int c = nSize (pGetCoeff (kBucketGetLm (b))); 335 380 int i; 336 for (i=MAX_BUCKET;i>0;i) 337 { 338 if(b>buckets[i]==NULL) continue; 339 s+=pSLength(b>buckets[i],0); 340 } 341 return s*c; 381 for (i = MAX_BUCKET; i > 0; i) 382 { 383 if (b>buckets[i] == NULL) 384 continue; 385 s += pSLength (b>buckets[i], 0); 386 } 387 return s * c; 342 388 } 343 389 #endif 344 390 //BUG/TODO this stuff will fail on internal Schreyer orderings 345 static BOOLEAN elength_is_normal_length(poly p, slimgb_alg* c) 346 { 347 ring r=c>r; 348 if (p_GetComp(p,r)!=0) return FALSE; 349 if (c>lastDpBlockStart<=pVariables) 350 { 351 int i; 352 for(i=1;i<c>lastDpBlockStart;i++) 353 { 354 if (p_GetExp(p,i,r)!=0) 355 { 356 break; 357 } 358 } 359 if (i>=c>lastDpBlockStart) { 360 //wrp(p); 361 //PrintS("\n"); 362 return TRUE; 363 } 364 else return FALSE; 391 static BOOLEAN 392 elength_is_normal_length (poly p, slimgb_alg * c) 393 { 394 ring r = c>r; 395 if (p_GetComp (p, r) != 0) 396 return FALSE; 397 if (c>lastDpBlockStart <= pVariables) 398 { 399 int i; 400 for (i = 1; i < c>lastDpBlockStart; i++) 401 { 402 if (p_GetExp (p, i, r) != 0) 403 { 404 break; 405 } 406 } 407 if (i >= c>lastDpBlockStart) 408 { 409 //wrp(p); 410 //PrintS("\n"); 411 return TRUE; 365 412 } 366 413 else 414 return FALSE; 415 } 416 else 367 417 return FALSE; 368 418 } 369 419 370 static BOOLEAN lies_in_last_dp_block(poly p, slimgb_alg* c) 371 { 372 ring r=c>r; 373 if (p_GetComp(p,r)!=0) return FALSE; 374 if (c>lastDpBlockStart<=pVariables) 375 { 376 int i; 377 for(i=1;i<c>lastDpBlockStart;i++) 378 { 379 if (p_GetExp(p,i,r)!=0) 380 { 381 break; 382 } 383 } 384 if (i>=c>lastDpBlockStart) { 385 //wrp(p); 386 //PrintS("\n"); 387 return TRUE; 388 } 389 else return FALSE; 420 static BOOLEAN 421 lies_in_last_dp_block (poly p, slimgb_alg * c) 422 { 423 ring r = c>r; 424 if (p_GetComp (p, r) != 0) 425 return FALSE; 426 if (c>lastDpBlockStart <= pVariables) 427 { 428 int i; 429 for (i = 1; i < c>lastDpBlockStart; i++) 430 { 431 if (p_GetExp (p, i, r) != 0) 432 { 433 break; 434 } 435 } 436 if (i >= c>lastDpBlockStart) 437 { 438 //wrp(p); 439 //PrintS("\n"); 440 return TRUE; 390 441 } 391 442 else 443 return FALSE; 444 } 445 else 392 446 return FALSE; 393 447 } 394 448 395 static int get_last_dp_block_start(ring r) 396 { 397 //ring r=c>r; 398 int last_block; 399 400 if (rRing_has_CompLastBlock(r)) 401 { 402 last_block=rBlocks(r)  3; 403 } 404 else 405 {last_block=rBlocks(r)2;} 406 assume(last_block>=0); 407 if (r>order[last_block]==ringorder_dp) 408 return r>block0[last_block]; 409 return pVariables+1; 410 } 411 412 static wlen_type do_pELength(poly p, slimgb_alg* c, int dlm=1) 413 { 414 if(p==NULL) return 0; 415 wlen_type s=0; 416 poly pi=p; 417 if(dlm<0) 418 { 419 dlm=c>pTotaldegree(p); 420 s=1; 421 pi=p>next; 422 } 423 424 while(pi) 425 { 426 int d=c>pTotaldegree(pi); 427 if(d>dlm) 428 s+=1+ddlm; 449 static int 450 get_last_dp_block_start (ring r) 451 { 452 //ring r=c>r; 453 int last_block; 454 455 if (rRing_has_CompLastBlock (r)) 456 { 457 last_block = rBlocks (r)  3; 458 } 459 else 460 { 461 last_block = rBlocks (r)  2; 462 } 463 assume (last_block >= 0); 464 if (r>order[last_block] == ringorder_dp) 465 return r>block0[last_block]; 466 return pVariables + 1; 467 } 468 469 static wlen_type 470 do_pELength (poly p, slimgb_alg * c, int dlm = 1) 471 { 472 if (p == NULL) 473 return 0; 474 wlen_type s = 0; 475 poly pi = p; 476 if (dlm < 0) 477 { 478 dlm = c>pTotaldegree (p); 479 s = 1; 480 pi = p>next; 481 } 482 483 while (pi) 484 { 485 int d = c>pTotaldegree (pi); 486 if (d > dlm) 487 s += 1 + d  dlm; 429 488 else 430 489 ++s; 431 pi =pi>next;490 pi = pi>next; 432 491 } 433 492 return s; 434 493 } 435 494 436 wlen_type pELength(poly p, slimgb_alg* c, ring r) 437 { 438 if(p==NULL) return 0; 439 wlen_type s=0; 440 poly pi=p; 495 wlen_type 496 pELength (poly p, slimgb_alg * c, ring r) 497 { 498 if (p == NULL) 499 return 0; 500 wlen_type s = 0; 501 poly pi = p; 441 502 int dlm; 442 dlm =c>pTotaldegree(p);443 s =1;444 pi =p>next;445 446 while (pi)447 { 448 int d =c>pTotaldegree(pi);449 if (d>dlm)450 s +=1+ddlm;503 dlm = c>pTotaldegree (p); 504 s = 1; 505 pi = p>next; 506 507 while (pi) 508 { 509 int d = c>pTotaldegree (pi); 510 if (d > dlm) 511 s += 1 + d  dlm; 451 512 else 452 513 ++s; 453 pi =pi>next;514 pi = pi>next; 454 515 } 455 516 return s; 456 517 } 457 518 458 wlen_type kEBucketLength(kBucket* b, poly lm,int sugar,slimgb_alg* ca) 459 { 460 wlen_type s=0; 461 if(lm==NULL) 462 { 463 lm=kBucketGetLm(b); 464 } 465 if(lm==NULL) return 0; 466 if(elength_is_normal_length(lm,ca)) 467 { 468 return bucket_guess(b); 469 } 470 int d=ca>pTotaldegree(lm); 471 #if 0 472 assume(sugar>=d); 473 s=1+(bucket_guess(b)1)*(sugard+1); 519 wlen_type 520 kEBucketLength (kBucket * b, poly lm, int sugar, slimgb_alg * ca) 521 { 522 wlen_type s = 0; 523 if (lm == NULL) 524 { 525 lm = kBucketGetLm (b); 526 } 527 if (lm == NULL) 528 return 0; 529 if (elength_is_normal_length (lm, ca)) 530 { 531 return bucket_guess (b); 532 } 533 int d = ca>pTotaldegree (lm); 534 #if 0 535 assume (sugar >= d); 536 s = 1 + (bucket_guess (b)  1) * (sugar  d + 1); 474 537 return s; 475 538 #else 476 539 477 540 //int d=pTotaldegree(lm,ca>r); 478 541 int i; 479 for (i=b>buckets_used;i>=0;i) 480 { 481 if(b>buckets[i]==NULL) continue; 482 483 if ((ca>pTotaldegree(b>buckets[i])<=d) &&(elength_is_normal_length(b>buckets[i],ca))) 484 { 485 s+=b>buckets_length[i]; 542 for (i = b>buckets_used; i >= 0; i) 543 { 544 if (b>buckets[i] == NULL) 545 continue; 546 547 if ((ca>pTotaldegree (b>buckets[i]) <= d) 548 && (elength_is_normal_length (b>buckets[i], ca))) 549 { 550 s += b>buckets_length[i]; 486 551 } 487 552 else 488 553 { 489 s+=do_pELength(b>buckets[i],ca,d);554 s += do_pELength (b>buckets[i], ca, d); 490 555 } 491 556 } 492 557 return s; 493 #endif 494 } 495 496 static inline int pELength(poly p, slimgb_alg* c,int l) 497 { 498 if (p==NULL) return 0; 499 if ((l>0) &&(elength_is_normal_length(p,c))) 558 #endif 559 } 560 561 static inline int 562 pELength (poly p, slimgb_alg * c, int l) 563 { 564 if (p == NULL) 565 return 0; 566 if ((l > 0) && (elength_is_normal_length (p, c))) 500 567 return l; 501 return do_pELength(p,c); 502 } 503 504 static inline wlen_type pQuality(poly p, slimgb_alg* c, int l=1) 505 { 506 if(l<0) 507 l=pLength(p); 508 if(c>isDifficultField) { 509 if(c>eliminationProblem) 568 return do_pELength (p, c); 569 } 570 571 static inline wlen_type 572 pQuality (poly p, slimgb_alg * c, int l = 1) 573 { 574 if (l < 0) 575 l = pLength (p); 576 if (c>isDifficultField) 577 { 578 if (c>eliminationProblem) 510 579 { 511 580 wlen_type cs; 512 number coef =pGetCoeff(p);513 if (rField_is_Q (currRing))514 { 515 cs=QlogSize(coef);581 number coef = pGetCoeff (p); 582 if (rField_is_Q (currRing)) 583 { 584 cs = QlogSize (coef); 516 585 } 517 586 else 518 cs=nSize(coef);519 wlen_type erg=cs;520 if(TEST_V_COEFSTRAT)521 erg*=cs;522 //erg*=cs;//for quadratic523 erg*=pELength(p,c,l);524 //FIXME: not quadratic coeff size587 cs = nSize (coef); 588 wlen_type erg = cs; 589 if (TEST_V_COEFSTRAT) 590 erg *= cs; 591 //erg*=cs;//for quadratic 592 erg *= pELength (p, c, l); 593 //FIXME: not quadratic coeff size 525 594 //return cs*pELength(p,c,l); 526 595 return erg; 527 596 } 528 597 //PrintS("I am here"); 529 wlen_type r =pSLength(p,l);530 assume (r>=0);598 wlen_type r = pSLength (p, l); 599 assume (r >= 0); 531 600 return r; 532 601 } 533 if(c>eliminationProblem) return pELength(p,c,l); 602 if (c>eliminationProblem) 603 return pELength (p, c, l); 534 604 return l; 535 605 } 536 606 537 static inline int pTotaldegree_full(poly p) 538 { 539 int r=0; 540 while(p) 541 { 542 int d=pTotaldegree(p); 543 r=si_max(r,d); 544 pIter(p); 607 static inline int 608 pTotaldegree_full (poly p) 609 { 610 int r = 0; 611 while (p) 612 { 613 int d = pTotaldegree (p); 614 r = si_max (r, d); 615 pIter (p); 545 616 } 546 617 return r; 547 618 } 548 619 549 wlen_type red_object::guess_quality(slimgb_alg* c) 550 { 551 //works at the moment only for lenvar 1, because in different 552 //case, you have to look on coefs 553 wlen_type s=0; 554 if (c>isDifficultField) 555 { 556 //s=kSBucketLength(bucket,this>p); 557 if(c>eliminationProblem) 558 { 559 wlen_type cs; 560 number coef; 561 562 coef=pGetCoeff(kBucketGetLm(bucket)); 563 //c=nSize(pGetCoeff(kBucketGetLm(b))); 564 565 //c=nSize(pGetCoeff(lm)); 566 if (rField_is_Q(currRing)) 567 { 568 cs=QlogSize(coef); 569 } 620 wlen_type 621 red_object::guess_quality (slimgb_alg * c) 622 { 623 //works at the moment only for lenvar 1, because in different 624 //case, you have to look on coefs 625 wlen_type s = 0; 626 if (c>isDifficultField) 627 { 628 //s=kSBucketLength(bucket,this>p); 629 if (c>eliminationProblem) 630 { 631 wlen_type cs; 632 number coef; 633 634 coef = pGetCoeff (kBucketGetLm (bucket)); 635 //c=nSize(pGetCoeff(kBucketGetLm(b))); 636 637 //c=nSize(pGetCoeff(lm)); 638 if (rField_is_Q (currRing)) 639 { 640 cs = QlogSize (coef); 641 } 642 else 643 cs = nSize (coef); 644 #ifdef HAVE_COEF_BUCKETS 645 if (bucket>coef[0] != NULL) 646 { 647 if (rField_is_Q (currRing)) 648 { 649 int modifier = QlogSize (pGetCoeff (bucket>coef[0])); 650 cs += modifier; 651 } 652 else 653 { 654 int modifier = nSize (pGetCoeff (bucket>coef[0])); 655 cs *= modifier; 656 } 657 } 658 #endif 659 //FIXME:not quadratic 660 wlen_type erg = kEBucketLength (this>bucket, this>p, this>sugar, c); 661 //erg*=cs;//for quadratic 662 erg *= cs; 663 if (TEST_V_COEFSTRAT) 664 erg *= cs; 665 //return cs*kEBucketLength(this>bucket,this>p,c); 666 return erg; 667 } 668 s = kSBucketLength (bucket, NULL); 669 } 670 else 671 { 672 if (c>eliminationProblem) 673 //if (false) 674 s = kEBucketLength (this>bucket, this>p, this>sugar, c); 570 675 else 571 cs=nSize(coef); 572 #ifdef HAVE_COEF_BUCKETS 573 if (bucket>coef[0]!=NULL) 574 { 575 if (rField_is_Q(currRing)) 576 { 577 int modifier=QlogSize(pGetCoeff(bucket>coef[0])); 578 cs+=modifier; 579 } 580 else 581 { 582 int modifier=nSize(pGetCoeff(bucket>coef[0])); 583 cs*=modifier;} 584 } 585 #endif 586 //FIXME:not quadratic 587 wlen_type erg=kEBucketLength(this>bucket,this>p,this>sugar,c); 588 //erg*=cs;//for quadratic 589 erg*=cs; 590 if (TEST_V_COEFSTRAT) 591 erg*=cs; 592 //return cs*kEBucketLength(this>bucket,this>p,c); 593 return erg; 594 } 595 s=kSBucketLength(bucket,NULL); 596 } 597 else 598 { 599 if(c>eliminationProblem) 600 //if (false) 601 s=kEBucketLength(this>bucket,this>p,this>sugar,c); 602 else s=bucket_guess(bucket); 603 } 604 return s; 605 } 606 607 #if 0 //currently unused 608 static void finalize_reduction_step(reduction_step* r) 676 s = bucket_guess (bucket); 677 } 678 return s; 679 } 680 681 #if 0 //currently unused 682 static void 683 finalize_reduction_step (reduction_step * r) 609 684 { 610 685 delete r; 611 686 } 612 687 #endif 613 #if 0 //currently unused 614 static int LObject_better_gen(const void* ap, const void* bp) 615 { 616 LObject* a=*(LObject**)ap; 617 LObject* b=*(LObject**)bp; 618 return(pLmCmp(a>p,b>p)); 619 } 620 #endif 621 static int red_object_better_gen(const void* ap, const void* bp) 622 { 623 return(pLmCmp(((red_object*) ap)>p,((red_object*) bp)>p)); 624 } 625 626 #if 0 //currently unused 627 static int pLmCmp_func_inverted(const void* ap1, const void* ap2) 628 { 629 poly p1,p2; 630 p1=*((poly*) ap1); 631 p2=*((poly*)ap2); 632 return pLmCmp(p1,p2); 633 } 634 #endif 635 636 int tgb_pair_better_gen2(const void* ap,const void* bp) 637 { 638 return(tgb_pair_better_gen(ap,bp)); 639 } 640 int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj) 688 #if 0 //currently unused 689 static int 690 LObject_better_gen (const void *ap, const void *bp) 691 { 692 LObject *a = *(LObject **) ap; 693 LObject *b = *(LObject **) bp; 694 return (pLmCmp (a>p, b>p)); 695 } 696 #endif 697 static int 698 red_object_better_gen (const void *ap, const void *bp) 699 { 700 return (pLmCmp (((red_object *) ap)>p, ((red_object *) bp)>p)); 701 } 702 703 #if 0 //currently unused 704 static int 705 pLmCmp_func_inverted (const void *ap1, const void *ap2) 706 { 707 poly p1, p2; 708 p1 = *((poly *) ap1); 709 p2 = *((poly *) ap2); 710 return pLmCmp (p1, p2); 711 } 712 #endif 713 714 int 715 tgb_pair_better_gen2 (const void *ap, const void *bp) 716 { 717 return (tgb_pair_better_gen (ap, bp)); 718 } 719 720 int 721 kFindDivisibleByInS_easy (kStrategy strat, const red_object & obj) 641 722 { 642 723 int i; 643 long not_sev =~obj.sev;644 poly p =obj.p;645 for (i=0;i<=strat>sl;i++)646 { 647 if (pLmShortDivisibleBy (strat>S[i],strat>sevS[i],p,not_sev))724 long not_sev = ~obj.sev; 725 poly p = obj.p; 726 for (i = 0; i <= strat>sl; i++) 727 { 728 if (pLmShortDivisibleBy (strat>S[i], strat>sevS[i], p, not_sev)) 648 729 return i; 649 730 } 650 731 return 1; 651 732 } 652 int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev) 733 734 int 735 kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev) 653 736 { 654 737 int i; 655 long not_sev =~sev;656 for (i=0;i<=strat>sl;i++)657 { 658 if (pLmShortDivisibleBy (strat>S[i],strat>sevS[i],p,not_sev))738 long not_sev = ~sev; 739 for (i = 0; i <= strat>sl; i++) 740 { 741 if (pLmShortDivisibleBy (strat>S[i], strat>sevS[i], p, not_sev)) 659 742 return i; 660 743 } 661 744 return 1; 662 745 } 663 static int posInPairs (sorted_pair_node** p, int pn, sorted_pair_node* qe,slimgb_alg* c,int an=0) 664 { 665 if(pn==0) return 0; 666 667 int length=pn1; 746 747 static int 748 posInPairs (sorted_pair_node ** p, int pn, sorted_pair_node * qe, 749 slimgb_alg * c, int an = 0) 750 { 751 if (pn == 0) 752 return 0; 753 754 int length = pn  1; 668 755 int i; 669 756 //int an = 0; 670 int en= length; 671 672 if (pair_better(qe,p[en],c)) 673 return length+1; 674 675 while(1) 676 { 677 //if (an >= en1) 678 if(en1<=an) 679 { 680 if (pair_better(p[an],qe,c)) return an; 681 return en; 682 } 683 i=(an+en) / 2; 684 if (pair_better(p[i],qe,c)) 685 en=i; 686 else an=i; 687 } 688 } 689 690 static BOOLEAN ascending(int* i,int top) 691 { 692 if(top<1) return TRUE; 693 if(i[top]<i[top1]) return FALSE; 694 return ascending(i,top1); 695 } 696 697 sorted_pair_node** spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c) 757 int en = length; 758 759 if (pair_better (qe, p[en], c)) 760 return length + 1; 761 762 while (1) 763 { 764 //if (an >= en1) 765 if (en  1 <= an) 766 { 767 if (pair_better (p[an], qe, c)) 768 return an; 769 return en; 770 } 771 i = (an + en) / 2; 772 if (pair_better (p[i], qe, c)) 773 en = i; 774 else 775 an = i; 776 } 777 } 778 779 static BOOLEAN 780 ascending (int *i, int top) 781 { 782 if (top < 1) 783 return TRUE; 784 if (i[top] < i[top  1]) 785 return FALSE; 786 return ascending (i, top  1); 787 } 788 789 sorted_pair_node ** 790 spn_merge (sorted_pair_node ** p, int pn, sorted_pair_node ** q, int qn, 791 slimgb_alg * c) 698 792 { 699 793 int i; 700 int * a= (int*) omalloc(qn*sizeof(int));794 int *a = (int *) omalloc (qn * sizeof (int)); 701 795 // int mc; 702 796 // PrintS("Debug\n"); … … 712 806 // PrintS("\n"); 713 807 // } 714 int lastpos =0;715 for (i=0;i<qn;i++)716 { 717 lastpos =posInPairs(p,pn,q[i],c, si_max(lastpos1,0));808 int lastpos = 0; 809 for (i = 0; i < qn; i++) 810 { 811 lastpos = posInPairs (p, pn, q[i], c, si_max (lastpos  1, 0)); 718 812 // cout<<lastpos<<"\n"; 719 a[i]=lastpos; 720 } 721 if((pn+qn)>c>max_pairs) 722 { 723 p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*)); 724 c>max_pairs=2*(pn+qn); 725 } 726 for(i=qn1;i>=0;i) 813 a[i] = lastpos; 814 } 815 if ((pn + qn) > c>max_pairs) 816 { 817 p = 818 (sorted_pair_node **) omrealloc (p, 819 2 * (pn + 820 qn) * 821 sizeof (sorted_pair_node *)); 822 c>max_pairs = 2 * (pn + qn); 823 } 824 for (i = qn  1; i >= 0; i) 727 825 { 728 826 size_t size; 729 if (qn1>i)730 size =(a[i+1]a[i])*sizeof(sorted_pair_node*);827 if (qn  1 > i) 828 size = (a[i + 1]  a[i]) * sizeof (sorted_pair_node *); 731 829 else 732 size =(pna[i])*sizeof(sorted_pair_node*);//as indices begin with 0733 memmove (p +a[i]+(1+i), p+a[i], size);734 p[a[i] +i]=q[i];735 } 736 omfree (a);830 size = (pn  a[i]) * sizeof (sorted_pair_node *); //as indices begin with 0 831 memmove (p + a[i] + (1 + i), p + a[i], size); 832 p[a[i] + i] = q[i]; 833 } 834 omfree (a); 737 835 return p; 738 836 } 739 837 740 static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c) 741 { 742 poly p1=c>S>m[pos1]; 743 poly p2=c>S>m[pos2]; 744 745 if (pGetComp(p1) > 0  pGetComp(p2) > 0) 838 static BOOLEAN 839 trivial_syzygie (int pos1, int pos2, poly bound, slimgb_alg * c) 840 { 841 poly p1 = c>S>m[pos1]; 842 poly p2 = c>S>m[pos2]; 843 844 if (pGetComp (p1) > 0  pGetComp (p2) > 0) 746 845 return FALSE; 747 846 int i = 1; 748 poly m=NULL; 749 poly gcd1=c>gcd_of_terms[pos1]; 750 poly gcd2=c>gcd_of_terms[pos2]; 751 752 if((gcd1!=NULL) && (gcd2!=NULL)) 753 { 754 gcd1>next=gcd2; //may ordered incorrect 755 m=gcd_of_terms(gcd1,c>r); 756 gcd1>next=NULL; 757 } 758 if (m==NULL) 759 { 760 loop 761 { 762 if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; 763 if (i == pVariables) 764 { 765 //PrintS("trivial"); 847 poly m = NULL; 848 poly gcd1 = c>gcd_of_terms[pos1]; 849 poly gcd2 = c>gcd_of_terms[pos2]; 850 851 if ((gcd1 != NULL) && (gcd2 != NULL)) 852 { 853 gcd1>next = gcd2; //may ordered incorrect 854 m = gcd_of_terms (gcd1, c>r); 855 gcd1>next = NULL; 856 } 857 if (m == NULL) 858 { 859 loop 860 { 861 if (pGetExp (p1, i) + pGetExp (p2, i) > pGetExp (bound, i)) 862 return FALSE; 863 if (i == pVariables) 864 { 865 //PrintS("trivial"); 866 return TRUE; 867 } 868 i++; 869 } 870 } 871 else 872 { 873 loop 874 { 875 if (pGetExp (p1, i)  pGetExp (m, i) + pGetExp (p2, i) > 876 pGetExp (bound, i)) 877 { 878 pDelete (&m); 879 return FALSE; 880 } 881 if (i == pVariables) 882 { 883 pDelete (&m); 884 //PrintS("trivial"); 885 return TRUE; 886 } 887 i++; 888 } 889 } 890 } 891 892 //! returns position sets w as weight 893 int 894 find_best (red_object * r, int l, int u, wlen_type & w, slimgb_alg * c) 895 { 896 int best = l; 897 int i; 898 w = r[l].guess_quality (c); 899 for (i = l + 1; i <= u; i++) 900 { 901 wlen_type w2 = r[i].guess_quality (c); 902 if (w2 < w) 903 { 904 w = w2; 905 best = i; 906 } 907 } 908 return best; 909 } 910 911 void 912 red_object::canonicalize () 913 { 914 kBucketCanonicalize (bucket); 915 } 916 917 BOOLEAN 918 good_has_t_rep (int i, int j, slimgb_alg * c) 919 { 920 assume (i >= 0); 921 assume (j >= 0); 922 if (has_t_rep (i, j, c)) 766 923 return TRUE; 767 } 768 i++; 769 } 770 } 771 else 772 { 773 loop 774 { 775 if (pGetExp(p1, i)pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i)) { 776 pDelete(&m); 777 return FALSE;} 778 if (i == pVariables) 779 { 780 pDelete(&m); 781 //PrintS("trivial"); 782 return TRUE; 783 } 784 i++; 785 } 786 } 787 } 788 789 //! returns position sets w as weight 790 int find_best(red_object* r,int l, int u, wlen_type &w, slimgb_alg* c) 791 { 792 int best=l; 924 //poly lm=pOne(); 925 assume (c>tmp_lm != NULL); 926 poly lm = c>tmp_lm; 927 928 pLcm (c>S>m[i], c>S>m[j], lm); 929 pSetm (lm); 930 assume (lm != NULL); 931 //int deciding_deg= pTotaldegree(lm); 932 int *i_con = make_connections (i, j, lm, c); 933 //p_Delete(&lm,c>r); 934 935 for (int n = 0; ((n < c>n) && (i_con[n] >= 0)); n++) 936 { 937 if (i_con[n] == j) 938 { 939 now_t_rep (i, j, c); 940 omfree (i_con); 941 return TRUE; 942 } 943 } 944 omfree (i_con); 945 946 return FALSE; 947 } 948 949 BOOLEAN 950 lenS_correct (kStrategy strat) 951 { 793 952 int i; 794 w=r[l].guess_quality(c); 795 for(i=l+1;i<=u;i++) 796 { 797 wlen_type w2=r[i].guess_quality(c); 798 if(w2<w) 799 { 800 w=w2; 801 best=i; 802 } 803 } 804 return best; 805 } 806 807 void red_object::canonicalize() 808 { 809 kBucketCanonicalize(bucket); 810 } 811 812 BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c) 813 { 814 assume(i>=0); 815 assume(j>=0); 816 if (has_t_rep(i,j,c)) return TRUE; 817 //poly lm=pOne(); 818 assume (c>tmp_lm!=NULL); 819 poly lm=c>tmp_lm; 820 821 pLcm(c>S>m[i], c>S>m[j], lm); 822 pSetm(lm); 823 assume(lm!=NULL); 824 //int deciding_deg= pTotaldegree(lm); 825 int* i_con =make_connections(i,j,lm,c); 826 //p_Delete(&lm,c>r); 827 828 for (int n=0;((n<c>n) && (i_con[n]>=0));n++) 829 { 830 if (i_con[n]==j) 831 { 832 now_t_rep(i,j,c); 833 omfree(i_con); 834 return TRUE; 835 } 836 } 837 omfree(i_con); 838 839 return FALSE; 840 } 841 BOOLEAN lenS_correct(kStrategy strat) 842 { 843 int i; 844 for(i=0;i<=strat>sl;i++) 845 { 846 if (strat>lenS[i]!=pLength(strat>S[i])) 953 for (i = 0; i <= strat>sl; i++) 954 { 955 if (strat>lenS[i] != pLength (strat>S[i])) 847 956 return FALSE; 848 957 } … … 851 960 852 961 853 static void cleanS(kStrategy strat, slimgb_alg* c) 854 { 855 int i=0; 962 static void 963 cleanS (kStrategy strat, slimgb_alg * c) 964 { 965 int i = 0; 856 966 LObject P; 857 while (i<=strat>sl)858 { 859 P.p =strat>S[i];860 P.sev =strat>sevS[i];967 while (i <= strat>sl) 968 { 969 P.p = strat>S[i]; 970 P.sev = strat>sevS[i]; 861 971 //int dummy=strat>sl; 862 972 //if(kFindDivisibleByInS(strat,&dummy,&P)!=i) 863 if (kFindDivisibleByInS_easy (strat,P.p,P.sev)!=i)864 { 865 deleteInS (i,strat);973 if (kFindDivisibleByInS_easy (strat, P.p, P.sev) != i) 974 { 975 deleteInS (i, strat); 866 976 //remember destroying poly 867 BOOLEAN found =FALSE;977 BOOLEAN found = FALSE; 868 978 int j; 869 for (j=0;j<c>n;j++)870 { 871 if(c>S>m[j]==P.p)872 873 found=TRUE;874 875 979 for (j = 0; j < c>n; j++) 980 { 981 if (c>S>m[j] == P.p) 982 { 983 found = TRUE; 984 break; 985 } 876 986 } 877 987 if (!found) 878 pDelete(&P.p);988 pDelete (&P.p); 879 989 //remember additional reductors 880 990 } 881 else i++; 882 } 883 } 884 static int bucket_guess(kBucket* bucket) 885 { 886 int sum=0; 991 else 992 i++; 993 } 994 } 995 996 static int 997 bucket_guess (kBucket * bucket) 998 { 999 int sum = 0; 887 1000 int i; 888 for (i =bucket>buckets_used;i>=0;i)889 { 890 if (bucket>buckets[i])891 sum+=bucket>buckets_length[i];1001 for (i = bucket>buckets_used; i >= 0; i) 1002 { 1003 if (bucket>buckets[i]) 1004 sum += bucket>buckets_length[i]; 892 1005 } 893 1006 return sum; 894 1007 } 895 1008 896 static int add_to_reductors(slimgb_alg* c, poly h, int len, int ecart, BOOLEAN simplified) 1009 static int 1010 add_to_reductors (slimgb_alg * c, poly h, int len, int ecart, 1011 BOOLEAN simplified) 897 1012 { 898 1013 //inDebug(h); 899 assume (lenS_correct(c>strat));900 assume (len==pLength(h));1014 assume (lenS_correct (c>strat)); 1015 assume (len == pLength (h)); 901 1016 int i; 902 1017 // if (c>isDifficultField) … … 905 1020 // i=simple_posInS(c>strat,h,len,c>isDifficultField); 906 1021 907 LObject P; memset(&P,0,sizeof(P)); 908 P.tailRing=c>r; 909 P.p=h; /*p_Copy(h,c>r);*/ 910 P.ecart=ecart; 911 P.FDeg=pFDeg(P.p,c>r); 1022 LObject P; 1023 memset (&P, 0, sizeof (P)); 1024 P.tailRing = c>r; 1025 P.p = h; /*p_Copy(h,c>r); */ 1026 P.ecart = ecart; 1027 P.FDeg = pFDeg (P.p, c>r); 912 1028 if (!(simplified)) 913 1029 { 914 if (!rField_is_Zp(c>r))915 916 p_Cleardenom(P.p,c>r);917 918 919 920 921 pNorm(P.p);922 pNormalize (P.p);923 } 924 wlen_type pq =pQuality(h,c,len);925 i =simple_posInS(c>strat,h,len,pq);926 c>strat>enterS (P,i,c>strat,1);927 928 c>strat>lenS[i] =len;929 assume (pLength(c>strat>S[i])==c>strat>lenS[i]);930 if (c>strat>lenSw!=NULL)931 c>strat>lenSw[i] =pq;1030 if (!rField_is_Zp (c>r)) 1031 { 1032 p_Cleardenom (P.p, c>r); 1033 //p_Content(P.p,c>r ); //is a duplicate call, but belongs here 1034 1035 } 1036 else 1037 pNorm (P.p); 1038 pNormalize (P.p); 1039 } 1040 wlen_type pq = pQuality (h, c, len); 1041 i = simple_posInS (c>strat, h, len, pq); 1042 c>strat>enterS (P, i, c>strat, 1); 1043 1044 c>strat>lenS[i] = len; 1045 assume (pLength (c>strat>S[i]) == c>strat>lenS[i]); 1046 if (c>strat>lenSw != NULL) 1047 c>strat>lenSw[i] = pq; 932 1048 933 1049 return i; 934 1050 } 935 1051 936 static void length_one_crit(slimgb_alg* c, int pos, int len) 1052 static void 1053 length_one_crit (slimgb_alg * c, int pos, int len) 937 1054 { 938 1055 if (c>nc) 939 1056 return; 940 if (len ==1)1057 if (len == 1) 941 1058 { 942 1059 int i; 943 for ( i=0;i<pos;i++)944 { 945 if (c>lengths[i] ==1)946 c>states[pos][i]=HASTREP;947 } 948 for ( i=pos+1;i<c>n;i++)949 { 950 if (c>lengths[i] ==1)951 c>states[i][pos]=HASTREP;1060 for (i = 0; i < pos; i++) 1061 { 1062 if (c>lengths[i] == 1) 1063 c>states[pos][i] = HASTREP; 1064 } 1065 for (i = pos + 1; i < c>n; i++) 1066 { 1067 if (c>lengths[i] == 1) 1068 c>states[i][pos] = HASTREP; 952 1069 } 953 1070 if (!c>nc) 954 shorten_tails(c,c>S>m[pos]); 955 } 956 } 957 958 static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat) 959 { 960 assume(old_pos>=new_pos); 961 poly p=strat>S[old_pos]; 962 int ecart=strat>ecartS[old_pos]; 963 long sev=strat>sevS[old_pos]; 964 int s_2_r=strat>S_2_R[old_pos]; 965 int length=strat>lenS[old_pos]; 966 assume(length==pLength(strat>S[old_pos])); 1071 shorten_tails (c, c>S>m[pos]); 1072 } 1073 } 1074 1075 static void 1076 move_forward_in_S (int old_pos, int new_pos, kStrategy strat) 1077 { 1078 assume (old_pos >= new_pos); 1079 poly p = strat>S[old_pos]; 1080 int ecart = strat>ecartS[old_pos]; 1081 long sev = strat>sevS[old_pos]; 1082 int s_2_r = strat>S_2_R[old_pos]; 1083 int length = strat>lenS[old_pos]; 1084 assume (length == pLength (strat>S[old_pos])); 967 1085 wlen_type length_w; 968 if (strat>lenSw!=NULL)969 length_w =strat>lenSw[old_pos];1086 if (strat>lenSw != NULL) 1087 length_w = strat>lenSw[old_pos]; 970 1088 int i; 971 for (i =old_pos; i>new_pos; i)972 { 973 strat>S[i] = strat>S[i 1];974 strat>ecartS[i] = strat>ecartS[i 1];975 strat>sevS[i] = strat>sevS[i 1];976 strat>S_2_R[i] = strat>S_2_R[i 1];977 } 978 if (strat>lenS !=NULL)979 for (i =old_pos; i>new_pos; i)980 strat>lenS[i] = strat>lenS[i 1];981 if (strat>lenSw !=NULL)982 for (i =old_pos; i>new_pos; i)983 strat>lenSw[i] = strat>lenSw[i 1];984 985 strat>S[new_pos] =p;986 strat>ecartS[new_pos] =ecart;987 strat>sevS[new_pos] =sev;988 strat>S_2_R[new_pos] =s_2_r;989 strat>lenS[new_pos] =length;990 if (strat>lenSw!=NULL)991 strat>lenSw[new_pos] =length_w;1089 for (i = old_pos; i > new_pos; i) 1090 { 1091 strat>S[i] = strat>S[i  1]; 1092 strat>ecartS[i] = strat>ecartS[i  1]; 1093 strat>sevS[i] = strat>sevS[i  1]; 1094 strat>S_2_R[i] = strat>S_2_R[i  1]; 1095 } 1096 if (strat>lenS != NULL) 1097 for (i = old_pos; i > new_pos; i) 1098 strat>lenS[i] = strat>lenS[i  1]; 1099 if (strat>lenSw != NULL) 1100 for (i = old_pos; i > new_pos; i) 1101 strat>lenSw[i] = strat>lenSw[i  1]; 1102 1103 strat>S[new_pos] = p; 1104 strat>ecartS[new_pos] = ecart; 1105 strat>sevS[new_pos] = sev; 1106 strat>S_2_R[new_pos] = s_2_r; 1107 strat>lenS[new_pos] = length; 1108 if (strat>lenSw != NULL) 1109 strat>lenSw[new_pos] = length_w; 992 1110 //assume(lenS_correct(strat)); 993 1111 } 994 1112 995 static void move_backward_in_S(int old_pos, int new_pos,kStrategy strat) 996 { 997 assume(old_pos<=new_pos); 998 poly p=strat>S[old_pos]; 999 int ecart=strat>ecartS[old_pos]; 1000 long sev=strat>sevS[old_pos]; 1001 int s_2_r=strat>S_2_R[old_pos]; 1002 int length=strat>lenS[old_pos]; 1003 assume(length==pLength(strat>S[old_pos])); 1113 static void 1114 move_backward_in_S (int old_pos, int new_pos, kStrategy strat) 1115 { 1116 assume (old_pos <= new_pos); 1117 poly p = strat>S[old_pos]; 1118 int ecart = strat>ecartS[old_pos]; 1119 long sev = strat>sevS[old_pos]; 1120 int s_2_r = strat>S_2_R[old_pos]; 1121 int length = strat>lenS[old_pos]; 1122 assume (length == pLength (strat>S[old_pos])); 1004 1123 wlen_type length_w; 1005 if (strat>lenSw!=NULL)1006 length_w =strat>lenSw[old_pos];1124 if (strat>lenSw != NULL) 1125 length_w = strat>lenSw[old_pos]; 1007 1126 int i; 1008 for (i =old_pos; i<new_pos; i++)1009 { 1010 strat>S[i] = strat>S[i +1];1011 strat>ecartS[i] = strat>ecartS[i +1];1012 strat>sevS[i] = strat>sevS[i +1];1013 strat>S_2_R[i] = strat>S_2_R[i +1];1014 } 1015 if (strat>lenS !=NULL)1016 for (i =old_pos; i<new_pos; i++)1017 strat>lenS[i] = strat>lenS[i +1];1018 if (strat>lenSw !=NULL)1019 for (i =old_pos; i<new_pos; i++)1020 strat>lenSw[i] = strat>lenSw[i +1];1021 1022 strat>S[new_pos] =p;1023 strat>ecartS[new_pos] =ecart;1024 strat>sevS[new_pos] =sev;1025 strat>S_2_R[new_pos] =s_2_r;1026 strat>lenS[new_pos] =length;1027 if (strat>lenSw!=NULL)1028 strat>lenSw[new_pos] =length_w;1127 for (i = old_pos; i < new_pos; i++) 1128 { 1129 strat>S[i] = strat>S[i + 1]; 1130 strat>ecartS[i] = strat>ecartS[i + 1]; 1131 strat>sevS[i] = strat>sevS[i + 1]; 1132 strat>S_2_R[i] = strat>S_2_R[i + 1]; 1133 } 1134 if (strat>lenS != NULL) 1135 for (i = old_pos; i < new_pos; i++) 1136 strat>lenS[i] = strat>lenS[i + 1]; 1137 if (strat>lenSw != NULL) 1138 for (i = old_pos; i < new_pos; i++) 1139 strat>lenSw[i] = strat>lenSw[i + 1]; 1140 1141 strat>S[new_pos] = p; 1142 strat>ecartS[new_pos] = ecart; 1143 strat>sevS[new_pos] = sev; 1144 strat>S_2_R[new_pos] = s_2_r; 1145 strat>lenS[new_pos] = length; 1146 if (strat>lenSw != NULL) 1147 strat>lenSw[new_pos] = length_w; 1029 1148 //assume(lenS_correct(strat)); 1030 1149 } 1031 1150 1032 static int* make_connections(int from, int to, poly bound, slimgb_alg* c) 1033 { 1034 ideal I=c>S; 1035 int* cans=(int*) omalloc(c>n*sizeof(int)); 1036 int* connected=(int*) omalloc(c>n*sizeof(int)); 1037 cans[0]=to; 1038 int cans_length=1; 1039 connected[0]=from; 1040 int last_cans_pos=1; 1041 int connected_length=1; 1042 long neg_bounds_short= ~p_GetShortExpVector(bound,c>r); 1043 1044 int not_yet_found=cans_length; 1045 int con_checked=0; 1151 static int * 1152 make_connections (int from, int to, poly bound, slimgb_alg * c) 1153 { 1154 ideal I = c>S; 1155 int *cans = (int *) omalloc (c>n * sizeof (int)); 1156 int *connected = (int *) omalloc (c>n * sizeof (int)); 1157 cans[0] = to; 1158 int cans_length = 1; 1159 connected[0] = from; 1160 int last_cans_pos = 1; 1161 int connected_length = 1; 1162 long neg_bounds_short = ~p_GetShortExpVector (bound, c>r); 1163 1164 int not_yet_found = cans_length; 1165 int con_checked = 0; 1046 1166 int pos; 1047 1167 1048 while(TRUE) 1049 { 1050 if ((con_checked<connected_length)&& (not_yet_found>0)) 1051 { 1052 pos=connected[con_checked]; 1053 for(int i=0;i<cans_length;i++) 1054 { 1055 if (cans[i]<0) continue; 1056 //FIXME: triv. syz. does not hold on noncommutative, check it for modules 1057 if ((has_t_rep(pos,cans[i],c)) ((!rIsPluralRing(c>r))&&(trivial_syzygie(pos,cans[i],bound,c)))) 1058 { 1059 connected[connected_length]=cans[i]; 1060 connected_length++; 1061 cans[i]=1; 1062 not_yet_found; 1063 1064 if (connected[connected_length1]==to) 1065 { 1066 if (connected_length<c>n) 1067 { 1068 connected[connected_length]=1; 1069 } 1070 omfree(cans); 1071 return connected; 1072 } 1073 } 1168 while (TRUE) 1169 { 1170 if ((con_checked < connected_length) && (not_yet_found > 0)) 1171 { 1172 pos = connected[con_checked]; 1173 for (int i = 0; i < cans_length; i++) 1174 { 1175 if (cans[i] < 0) 1176 continue; 1177 //FIXME: triv. syz. does not hold on noncommutative, check it for modules 1178 if ((has_t_rep (pos, cans[i], c)) 1179  ((!rIsPluralRing (c>r)) 1180 && (trivial_syzygie (pos, cans[i], bound, c)))) 1181 { 1182 connected[connected_length] = cans[i]; 1183 connected_length++; 1184 cans[i] = 1; 1185 not_yet_found; 1186 1187 if (connected[connected_length  1] == to) 1188 { 1189 if (connected_length < c>n) 1190 { 1191 connected[connected_length] = 1; 1192 } 1193 omfree (cans); 1194 return connected; 1195 } 1196 } 1074 1197 } 1075 1198 con_checked++; … … 1077 1200 else 1078 1201 { 1079 for(last_cans_pos++;last_cans_pos<=c>n;last_cans_pos++) 1080 { 1081 if (last_cans_pos==c>n) 1082 { 1083 if (connected_length<c>n) 1084 { 1085 connected[connected_length]=1; 1086 } 1087 omfree(cans); 1088 return connected; 1089 } 1090 if ((last_cans_pos==from)(last_cans_pos==to)) 1091 continue; 1092 if(p_LmShortDivisibleBy(I>m[last_cans_pos],c>short_Exps[last_cans_pos],bound,neg_bounds_short,c>r)) 1093 { 1094 cans[cans_length]=last_cans_pos; 1095 cans_length++; 1096 break; 1097 } 1202 for (last_cans_pos++; last_cans_pos <= c>n; last_cans_pos++) 1203 { 1204 if (last_cans_pos == c>n) 1205 { 1206 if (connected_length < c>n) 1207 { 1208 connected[connected_length] = 1; 1209 } 1210 omfree (cans); 1211 return connected; 1212 } 1213 if ((last_cans_pos == from)  (last_cans_pos == to)) 1214 continue; 1215 if (p_LmShortDivisibleBy 1216 (I>m[last_cans_pos], c>short_Exps[last_cans_pos], bound, 1217 neg_bounds_short, c>r)) 1218 { 1219 cans[cans_length] = last_cans_pos; 1220 cans_length++; 1221 break; 1222 } 1098 1223 } 1099 1224 not_yet_found++; 1100 for (int i =0;i<con_checked;i++)1101 { 1102 if (has_t_rep(connected[i],last_cans_pos,c))1103 1104 connected[connected_length]=last_cans_pos;1105 1106 cans[cans_length1]=1;1107 1108 if (connected[connected_length1]==to)1109 1110 if (connected_length<c>n)1111 1112 connected[connected_length]=1;1113 1114 omfree(cans);1115 1116 1117 1118 1119 } 1120 } 1121 } 1122 if (connected_length <c>n)1123 { 1124 connected[connected_length] =1;1125 } 1126 omfree (cans);1225 for (int i = 0; i < con_checked; i++) 1226 { 1227 if (has_t_rep (connected[i], last_cans_pos, c)) 1228 { 1229 connected[connected_length] = last_cans_pos; 1230 connected_length++; 1231 cans[cans_length  1] = 1; 1232 not_yet_found; 1233 if (connected[connected_length  1] == to) 1234 { 1235 if (connected_length < c>n) 1236 { 1237 connected[connected_length] = 1; 1238 } 1239 omfree (cans); 1240 return connected; 1241 } 1242 break; 1243 } 1244 } 1245 } 1246 } 1247 if (connected_length < c>n) 1248 { 1249 connected[connected_length] = 1; 1250 } 1251 omfree (cans); 1127 1252 return connected; 1128 1253 } 1254 1129 1255 #ifdef HEAD_BIN 1130 static inline poly p_MoveHead(poly p, omBin b) 1256 static inline poly 1257 p_MoveHead (poly p, omBin b) 1131 1258 { 1132 1259 poly np; 1133 omTypeAllocBin (poly, np, b);1134 memmove (np, p, b>sizeW*sizeof(long));1135 omFreeBinAddr (p);1260 omTypeAllocBin (poly, np, b); 1261 memmove (np, p, b>sizeW * sizeof (long)); 1262 omFreeBinAddr (p); 1136 1263 return np; 1137 1264 } 1138 1265 #endif 1139 1266 1140 static void replace_pair(int & i, int & j,slimgb_alg* c) 1141 { 1142 if (i<0) return; 1143 c>soon_free=NULL; 1267 static void 1268 replace_pair (int &i, int &j, slimgb_alg * c) 1269 { 1270 if (i < 0) 1271 return; 1272 c>soon_free = NULL; 1144 1273 int syz_deg; 1145 poly lm =pOne();1146 1147 pLcm (c>S>m[i], c>S>m[j], lm);1148 pSetm (lm);1149 1150 int * i_con =make_connections(i,j,lm,c);1151 1152 for (int n =0;((n<c>n) && (i_con[n]>=0));n++)1153 { 1154 if (i_con[n] ==j)1155 { 1156 now_t_rep (i,j,c);1157 omfree (i_con);1158 p_Delete (&lm,c>r);1274 poly lm = pOne (); 1275 1276 pLcm (c>S>m[i], c>S>m[j], lm); 1277 pSetm (lm); 1278 1279 int *i_con = make_connections (i, j, lm, c); 1280 1281 for (int n = 0; ((n < c>n) && (i_con[n] >= 0)); n++) 1282 { 1283 if (i_con[n] == j) 1284 { 1285 now_t_rep (i, j, c); 1286 omfree (i_con); 1287 p_Delete (&lm, c>r); 1159 1288 return; 1160 1289 } 1161 1290 } 1162 1291 1163 int * j_con =make_connections(j,i,lm,c);1292 int *j_con = make_connections (j, i, lm, c); 1164 1293 1165 1294 // if(c>n>1) … … 1172 1301 // j=j_con[1]; 1173 1302 // } 1174 // } 1175 1176 int sugar=syz_deg=c>pTotaldegree(lm); 1177 1178 p_Delete(&lm, c>r); 1179 if(c>T_deg_full)//Sugar 1180 { 1181 int t_i=c>T_deg_full[i]c>T_deg[i]; 1182 int t_j=c>T_deg_full[j]c>T_deg[j]; 1183 sugar+=si_max(t_i,t_j); 1184 //Print("\n max: %d\n",max(t_i,t_j)); 1185 } 1186 1187 for (int m=0;((m<c>n) && (i_con[m]>=0));m++) 1188 { 1189 if(c>T_deg_full!=NULL) 1190 { 1191 int s1=c>T_deg_full[i_con[m]]+syz_degc>T_deg[i_con[m]]; 1192 if (s1>sugar) continue; 1193 } 1194 if (c>weighted_lengths[i_con[m]]<c>weighted_lengths[i]) 1195 i=i_con[m]; 1196 } 1197 for (int m=0;((m<c>n) && (j_con[m]>=0));m++) 1198 { 1199 if (c>T_deg_full!=NULL) 1200 { 1201 int s1=c>T_deg_full[j_con[m]]+syz_degc>T_deg[j_con[m]]; 1202 if (s1>sugar) continue;} 1203 if (c>weighted_lengths[j_con[m]]<c>weighted_lengths[j]) 1204 j=j_con[m]; 1205 } 1206 1207 //can also try dependend search 1208 omfree(i_con); 1209 omfree(j_con); 1303 // } 1304 1305 int sugar = syz_deg = c>pTotaldegree (lm); 1306 1307 p_Delete (&lm, c>r); 1308 if (c>T_deg_full) //Sugar 1309 { 1310 int t_i = c>T_deg_full[i]  c>T_deg[i]; 1311 int t_j = c>T_deg_full[j]  c>T_deg[j]; 1312 sugar += si_max (t_i, t_j); 1313 //Print("\n max: %d\n",max(t_i,t_j)); 1314 } 1315 1316 for (int m = 0; ((m < c>n) && (i_con[m] >= 0)); m++) 1317 { 1318 if (c>T_deg_full != NULL) 1319 { 1320 int s1 = c>T_deg_full[i_con[m]] + syz_deg  c>T_deg[i_con[m]]; 1321 if (s1 > sugar) 1322 continue; 1323 } 1324 if (c>weighted_lengths[i_con[m]] < c>weighted_lengths[i]) 1325 i = i_con[m]; 1326 } 1327 for (int m = 0; ((m < c>n) && (j_con[m] >= 0)); m++) 1328 { 1329 if (c>T_deg_full != NULL) 1330 { 1331 int s1 = c>T_deg_full[j_con[m]] + syz_deg  c>T_deg[j_con[m]]; 1332 if (s1 > sugar) 1333 continue; 1334 } 1335 if (c>weighted_lengths[j_con[m]] < c>weighted_lengths[j]) 1336 j = j_con[m]; 1337 } 1338 1339 //can also try dependend search 1340 omfree (i_con); 1341 omfree (j_con); 1210 1342 return; 1211 1343 } 1212 1344 1213 static void add_later(poly p, const char* prot, slimgb_alg* c) 1214 { 1215 int i=0; 1216 //check, if it is already in the queue 1217 1218 while(c>add_later>m[i]!=NULL) 1219 { 1220 if (p_LmEqual(c>add_later>m[i],p,c>r)) 1221 return; 1222 i++; 1223 } 1224 if (TEST_OPT_PROT) 1225 PrintS(prot); 1226 c>add_later>m[i]=p; 1227 } 1228 static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen) 1229 { 1230 if(strat>sl==1) return 0; 1231 if (strat>lenSw) return pos_helper(strat,p,(wlen_type) wlen,(wlen_set) strat>lenSw,strat>S); 1232 return pos_helper(strat,p,len,strat>lenS,strat>S); 1345 static void 1346 add_later (poly p, const char *prot, slimgb_alg * c) 1347 { 1348 int i = 0; 1349 //check, if it is already in the queue 1350 1351 while (c>add_later>m[i] != NULL) 1352 { 1353 if (p_LmEqual (c>add_later>m[i], p, c>r)) 1354 return; 1355 i++; 1356 } 1357 if (TEST_OPT_PROT) 1358 PrintS (prot); 1359 c>add_later>m[i] = p; 1360 } 1361 1362 static int 1363 simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen) 1364 { 1365 if (strat>sl == 1) 1366 return 0; 1367 if (strat>lenSw) 1368 return pos_helper (strat, p, (wlen_type) wlen, (wlen_set) strat>lenSw, 1369 strat>S); 1370 return pos_helper (strat, p, len, strat>lenS, strat>S); 1233 1371 } 1234 1372 … … 1237 1375 *divides the leading term of some S[i] it will be canceled 1238 1376 */ 1239 static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k, 1240 kStrategy strat) 1241 { 1242 assume(p_sev == pGetShortExpVector(p)); 1243 if (!pLmShortDivisibleBy(p,p_sev, strat>S[*at], ~ strat>sevS[*at])) return; 1244 if (l>=strat>lenS[*at]) return; 1377 static inline void 1378 clearS (poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat) 1379 { 1380 assume (p_sev == pGetShortExpVector (p)); 1381 if (!pLmShortDivisibleBy (p, p_sev, strat>S[*at], ~strat>sevS[*at])) 1382 return; 1383 if (l >= strat>lenS[*at]) 1384 return; 1245 1385 if (TEST_OPT_PROT) 1246 PrintS ("!");1247 mflush ();1386 PrintS ("!"); 1387 mflush (); 1248 1388 //pDelete(&strat>S[*at]); 1249 deleteInS ((*at),strat);1389 deleteInS ((*at), strat); 1250 1390 (*at); 1251 1391 (*k); … … 1253 1393 } 1254 1394 1255 static int iq_crit(const void* ap,const void* bp) 1256 { 1257 sorted_pair_node* a=*((sorted_pair_node**)ap); 1258 sorted_pair_node* b=*((sorted_pair_node**)bp); 1259 assume(a>i>a>j); 1260 assume(b>i>b>j); 1261 1262 if (a>deg<b>deg) return 1; 1263 if (a>deg>b>deg) return 1; 1264 int comp=pLmCmp(a>lcm_of_lm, b>lcm_of_lm); 1265 if(comp!=0) 1395 static int 1396 iq_crit (const void *ap, const void *bp) 1397 { 1398 sorted_pair_node *a = *((sorted_pair_node **) ap); 1399 sorted_pair_node *b = *((sorted_pair_node **) bp); 1400 assume (a>i > a>j); 1401 assume (b>i > b>j); 1402 1403 if (a>deg < b>deg) 1404 return 1; 1405 if (a>deg > b>deg) 1406 return 1; 1407 int comp = pLmCmp (a>lcm_of_lm, b>lcm_of_lm); 1408 if (comp != 0) 1266 1409 return comp; 1267 if (a>expected_length<b>expected_length) return 1; 1268 if (a>expected_length>b>expected_length) return 1; 1269 if (a>j>b>j) return 1; 1270 if (a>j<b>j) return 1; 1410 if (a>expected_length < b>expected_length) 1411 return 1; 1412 if (a>expected_length > b>expected_length) 1413 return 1; 1414 if (a>j > b>j) 1415 return 1; 1416 if (a>j < b>j) 1417 return 1; 1271 1418 return 0; 1272 1419 } 1273 static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r) 1274 { 1275 if (rField_is_Q(r)) return s1+s2; 1276 else return s1*s2; 1277 } 1278 static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c) 1279 { 1280 if ((c>isDifficultField) && (c>eliminationProblem)) { 1281 int c1=slim_nsize(p_GetCoeff(c>S>m[i],c>r),c>r); 1282 int c2=slim_nsize(p_GetCoeff(c>S>m[j],c>r),c>r); 1283 wlen_type el1=c>weighted_lengths[i]/c1; 1284 assume(el1!=0); 1285 assume(c>weighted_lengths[i] %c1==0); 1286 wlen_type el2=c>weighted_lengths[j]/c2; 1287 assume(el2!=0); 1288 assume(c>weighted_lengths[j] %c2==0); 1289 //should be * for function fields 1290 //return (c1+c2) * (el1+el22); 1291 wlen_type res=coeff_mult_size_estimate(c1,c2,c>r); 1292 res*=el1+el22; 1293 return res; 1294 1295 } 1296 if (c>isDifficultField) { 1297 //int cs=slim_nsize(p_GetCoeff(c>S>m[i],c>r),c>r)+ 1298 // slim_nsize(p_GetCoeff(c>S>m[j],c>r),c>r); 1299 if(!(TEST_V_COEFSTRAT)) 1300 { 1301 wlen_type cs= 1302 coeff_mult_size_estimate( 1303 slim_nsize(p_GetCoeff(c>S>m[i],c>r),c>r), 1304 slim_nsize(p_GetCoeff(c>S>m[j],c>r),c>r),c>r); 1305 return (wlen_type)(c>lengths[i]+c>lengths[j]2)* 1306 (wlen_type)cs;} 1307 else 1308 { 1309 1310 wlen_type cs= 1311 coeff_mult_size_estimate( 1312 slim_nsize(p_GetCoeff(c>S>m[i],c>r),c>r), 1313 slim_nsize(p_GetCoeff(c>S>m[j],c>r),c>r),c>r); 1314 cs*=cs; 1315 return (wlen_type)(c>lengths[i]+c>lengths[j]2)* 1316 (wlen_type)cs; 1317 } 1318 } 1319 if (c>eliminationProblem) { 1320 1321 return (c>weighted_lengths[i]+c>weighted_lengths[j]2); 1322 } 1323 return c>lengths[i]+c>lengths[j]2; 1324 1325 } 1326 sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip) 1327 { 1328 p_Test(h,c>r); 1329 assume(h!=NULL); 1330 poly got=gcd_of_terms(h,c>r); 1331 if((got!=NULL) &&(TEST_V_UPTORADICAL)) { 1332 poly copy=p_Copy(got,c>r); 1420 1421 static wlen_type 1422 coeff_mult_size_estimate (int s1, int s2, ring r) 1423 { 1424 if (rField_is_Q (r)) 1425 return s1 + s2; 1426 else 1427 return s1 * s2; 1428 } 1429 1430 static wlen_type 1431 pair_weighted_length (int i, int j, slimgb_alg * c) 1432 { 1433 if ((c>isDifficultField) && (c>eliminationProblem)) 1434 { 1435 int c1 = slim_nsize (p_GetCoeff (c>S>m[i], c>r), c>r); 1436 int c2 = slim_nsize (p_GetCoeff (c>S>m[j], c>r), c>r); 1437 wlen_type el1 = c>weighted_lengths[i] / c1; 1438 assume (el1 != 0); 1439 assume (c>weighted_lengths[i] % c1 == 0); 1440 wlen_type el2 = c>weighted_lengths[j] / c2; 1441 assume (el2 != 0); 1442 assume (c>weighted_lengths[j] % c2 == 0); 1443 //should be * for function fields 1444 //return (c1+c2) * (el1+el22); 1445 wlen_type res = coeff_mult_size_estimate (c1, c2, c>r); 1446 res *= el1 + el2  2; 1447 return res; 1448 1449 } 1450 if (c>isDifficultField) 1451 { 1452 //int cs=slim_nsize(p_GetCoeff(c>S>m[i],c>r),c>r)+ 1453 // slim_nsize(p_GetCoeff(c>S>m[j],c>r),c>r); 1454 if (!(TEST_V_COEFSTRAT)) 1455 { 1456 wlen_type cs = 1457 coeff_mult_size_estimate (slim_nsize 1458 (p_GetCoeff (c>S>m[i], c>r), c>r), 1459 slim_nsize (p_GetCoeff (c>S>m[j], c>r), 1460 c>r), c>r); 1461 return (wlen_type) (c>lengths[i] + c>lengths[j]  2) * (wlen_type) cs; 1462 } 1463 else 1464 { 1465 1466 wlen_type cs = 1467 coeff_mult_size_estimate (slim_nsize 1468 (p_GetCoeff (c>S>m[i], c>r), c>r), 1469 slim_nsize (p_GetCoeff (c>S>m[j], c>r), 1470 c>r), c>r); 1471 cs *= cs; 1472 return (wlen_type) (c>lengths[i] + c>lengths[j]  2) * (wlen_type) cs; 1473 } 1474 } 1475 if (c>eliminationProblem) 1476 { 1477 1478 return (c>weighted_lengths[i] + c>weighted_lengths[j]  2); 1479 } 1480 return c>lengths[i] + c>lengths[j]  2; 1481 1482 } 1483 1484 sorted_pair_node ** 1485 add_to_basis_ideal_quotient (poly h, slimgb_alg * c, int *ip) 1486 { 1487 p_Test (h, c>r); 1488 assume (h != NULL); 1489 poly got = gcd_of_terms (h, c>r); 1490 if ((got != NULL) && (TEST_V_UPTORADICAL)) 1491 { 1492 poly copy = p_Copy (got, c>r); 1333 1493 //p_wrp(got,c>r); 1334 BOOLEAN changed =monomial_root(got,c>r);1494 BOOLEAN changed = monomial_root (got, c>r); 1335 1495 if (changed) 1336 1496 { 1337 poly div_by=pDivide(copy, got);1338 poly iter=h;1339 while(iter)1340 1341 pExpVectorSub(iter,div_by);1342 pIter(iter);1343 1344 p_Delete(&div_by, c>r);1345 PrintS("U");1346 } 1347 p_Delete (©,c>r);1497 poly div_by = pDivide (copy, got); 1498 poly iter = h; 1499 while (iter) 1500 { 1501 pExpVectorSub (iter, div_by); 1502 pIter (iter); 1503 } 1504 p_Delete (&div_by, c>r); 1505 PrintS ("U"); 1506 } 1507 p_Delete (©, c>r); 1348 1508 } 1349 1509 … … 1351 1511 // BOOLEAN corr=lenS_correct(c>strat); 1352 1512 int sugar; 1353 int ecart =0;1513 int ecart = 0; 1354 1514 ++(c>n); 1355 1515 ++(c>S>ncols); 1356 int i,j; 1357 i=c>n1; 1358 sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); 1359 int spc=0; 1360 if(c>n>c>array_lengths) 1361 { 1362 c>array_lengths=c>array_lengths*2; 1363 assume(c>array_lengths>=c>n); 1364 ENLARGE(c>T_deg, int); 1365 ENLARGE(c>tmp_pair_lm,poly); 1366 ENLARGE(c>tmp_spn,sorted_pair_node*); 1367 1368 ENLARGE(c>short_Exps,long); 1369 ENLARGE(c>lengths,int); 1370 #ifndef HAVE_BOOST 1371 #ifndef USE_STDVECBOOL 1372 1373 ENLARGE(c>states, char*); 1374 #endif 1375 #endif 1376 ENLARGE(c>gcd_of_terms,poly); 1516 int i, j; 1517 i = c>n  1; 1518 sorted_pair_node **nodes = 1519 (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i); 1520 int spc = 0; 1521 if (c>n > c>array_lengths) 1522 { 1523 c>array_lengths = c>array_lengths * 2; 1524 assume (c>array_lengths >= c>n); 1525 ENLARGE (c>T_deg, int); 1526 ENLARGE (c>tmp_pair_lm, poly); 1527 ENLARGE (c>tmp_spn, sorted_pair_node *); 1528 1529 ENLARGE (c>short_Exps, long); 1530 ENLARGE (c>lengths, int); 1531 #ifndef HAVE_BOOST 1532 #ifndef USE_STDVECBOOL 1533 1534 ENLARGE (c>states, char *); 1535 #endif 1536 #endif 1537 ENLARGE (c>gcd_of_terms, poly); 1377 1538 //if (c>weighted_lengths!=NULL) { 1378 ENLARGE (c>weighted_lengths,wlen_type);1539 ENLARGE (c>weighted_lengths, wlen_type); 1379 1540 //} 1380 1541 //ENLARGE(c>S>m,poly); 1381 1542 } 1382 pEnlargeSet (&c>S>m,c>n1,1);1543 pEnlargeSet (&c>S>m, c>n  1, 1); 1383 1544 if (c>T_deg_full) 1384 ENLARGE (c>T_deg_full,int);1385 sugar =c>T_deg[i]=c>pTotaldegree(h);1386 if (c>T_deg_full)1387 { 1388 sugar =c>T_deg_full[i]=c>pTotaldegree_full(h);1389 ecart =sugarc>T_deg[i];1390 assume (ecart>=0);1391 } 1392 c>tmp_pair_lm[i] =pOne_Special(c>r);1393 1394 c>tmp_spn[i] =(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));1395 1396 c>lengths[i] =pLength(h);1545 ENLARGE (c>T_deg_full, int); 1546 sugar = c>T_deg[i] = c>pTotaldegree (h); 1547 if (c>T_deg_full) 1548 { 1549 sugar = c>T_deg_full[i] = c>pTotaldegree_full (h); 1550 ecart = sugar  c>T_deg[i]; 1551 assume (ecart >= 0); 1552 } 1553 c>tmp_pair_lm[i] = pOne_Special (c>r); 1554 1555 c>tmp_spn[i] = (sorted_pair_node *) omalloc (sizeof (sorted_pair_node)); 1556 1557 c>lengths[i] = pLength (h); 1397 1558 1398 1559 //necessary for correct weighted length 1399 1560 1400 if (!rField_is_Zp (c>r))1401 { 1402 p_Cleardenom (h, c>r);1561 if (!rField_is_Zp (c>r)) 1562 { 1563 p_Cleardenom (h, c>r); 1403 1564 //p_Content(h,c>r); //is a duplicate call, but belongs here 1404 1565 } 1405 1566 else 1406 pNorm (h);1407 pNormalize (h);1408 1409 c>weighted_lengths[i] =pQuality(h, c, c>lengths[i]);1410 c>gcd_of_terms[i] =got;1411 1412 c>states.push_back(dynamic_bitset<>(i));1413 1414 1415 1416 1417 c>states.push_back(vector<bool>(i));1418 1419 1420 if (i >0)1421 c>states[i] =(char*) omalloc(i*sizeof(char));1567 pNorm (h); 1568 pNormalize (h); 1569 1570 c>weighted_lengths[i] = pQuality (h, c, c>lengths[i]); 1571 c>gcd_of_terms[i] = got; 1572 #ifdef HAVE_BOOST 1573 c>states.push_back (dynamic_bitset <> (i)); 1574 1575 #else 1576 #ifdef USE_STDVECBOOL 1577 1578 c>states.push_back (vector < bool > (i)); 1579 1580 #else 1581 if (i > 0) 1582 c>states[i] = (char *) omalloc (i * sizeof (char)); 1422 1583 else 1423 c>states[i] =NULL;1424 1425 1426 1427 c>S>m[i] =h;1428 c>short_Exps[i] =p_GetShortExpVector(h,c>r);1584 c>states[i] = NULL; 1585 #endif 1586 #endif 1587 1588 c>S>m[i] = h; 1589 c>short_Exps[i] = p_GetShortExpVector (h, c>r); 1429 1590 1430 1591 #undef ENLARGE 1431 if (p_GetComp(h,currRing)<=c>syz_comp) 1432 { 1433 for (j=0;j<i;j++) 1434 { 1435 1436 1437 #ifndef HAVE_BOOST 1438 c>states[i][j]=UNCALCULATED; 1439 #endif 1440 assume(p_LmDivisibleBy(c>S>m[i],c>S>m[j],c>r)== 1441 p_LmShortDivisibleBy(c>S>m[i],c>short_Exps[i],c>S>m[j],~(c>short_Exps[j]),c>r)); 1442 1443 if (_p_GetComp(c>S>m[i],c>r)!=_p_GetComp(c>S>m[j],c>r)) 1444 { 1445 //c>states[i][j]=UNCALCULATED; 1446 //WARNUNG: be careful 1447 continue; 1448 } 1449 else 1450 if ((!c>nc) && (c>lengths[i]==1) && (c>lengths[j]==1)) 1451 { 1452 c>states[i][j]=HASTREP; 1453 } 1454 else if (( (!c>nc)  (c>is_homog && rIsSCA(c>r) ) ) && (pHasNotCF(c>S>m[i],c>S>m[j]))) 1592 if (p_GetComp (h, currRing) <= c>syz_comp) 1593 { 1594 for (j = 0; j < i; j++) 1595 { 1596 1597 1598 #ifndef HAVE_BOOST 1599 c>states[i][j] = UNCALCULATED; 1600 #endif 1601 assume (p_LmDivisibleBy (c>S>m[i], c>S>m[j], c>r) == 1602 p_LmShortDivisibleBy (c>S>m[i], c>short_Exps[i], c>S>m[j], 1603 ~(c>short_Exps[j]), c>r)); 1604 1605 if (_p_GetComp (c>S>m[i], c>r) != _p_GetComp (c>S>m[j], c>r)) 1606 { 1607 //c>states[i][j]=UNCALCULATED; 1608 //WARNUNG: be careful 1609 continue; 1610 } 1611 else if ((!c>nc) && (c>lengths[i] == 1) && (c>lengths[j] == 1)) 1612 { 1613 c>states[i][j] = HASTREP; 1614 } 1615 else if (((!c>nc)  (c>is_homog && rIsSCA (c>r))) 1616 && (pHasNotCF (c>S>m[i], c>S>m[j]))) 1455 1617 // else if ((!(c>nc)) && (pHasNotCF(c>S>m[i],c>S>m[j]))) 1456 { 1457 c>easy_product_crit++; 1458 c>states[i][j]=HASTREP; 1459 continue; 1460 } 1461 else if(extended_product_criterion(c>S>m[i],c>gcd_of_terms[i],c>S>m[j],c>gcd_of_terms[j],c)) 1462 { 1463 c>states[i][j]=HASTREP; 1464 c>extended_product_crit++; 1465 //PrintS("E"); 1466 } 1618 { 1619 c>easy_product_crit++; 1620 c>states[i][j] = HASTREP; 1621 continue; 1622 } 1623 else 1624 if (extended_product_criterion 1625 (c>S>m[i], c>gcd_of_terms[i], c>S>m[j], c>gcd_of_terms[j], 1626 c)) 1627 { 1628 c>states[i][j] = HASTREP; 1629 c>extended_product_crit++; 1630 //PrintS("E"); 1631 } 1467 1632 // if (c>states[i][j]==UNCALCULATED) 1468 1633 // { 1469 1634 1470 if ((TEST_V_FINDMONOM) &&(!c>nc)) { 1471 //PrintS("COMMU"); 1472 // if (c>lengths[i]==c>lengths[j]) 1473 // { 1635 if ((TEST_V_FINDMONOM) && (!c>nc)) 1636 { 1637 //PrintS("COMMU"); 1638 // if (c>lengths[i]==c>lengths[j]) 1639 // { 1474 1640 // poly short_s=ksCreateShortSpoly(c>S>m[i],c>S>m[j],c>r); 1475 1641 // if (short_s==NULL) … … 1482 1648 // } 1483 1649 // } 1484 if (c>lengths[i]+c>lengths[j]==3) 1485 { 1486 1487 1488 poly short_s=ksCreateShortSpoly(c>S>m[i],c>S>m[j],c>r); 1489 if (short_s==NULL) 1490 { 1491 c>states[i][j]=HASTREP; 1492 } 1493 else 1494 { 1495 assume(pLength(short_s)==1); 1496 if (TEST_V_UPTORADICAL) 1497 monomial_root(short_s,c>r); 1498 int iS= 1499 kFindDivisibleByInS_easy(c>strat,short_s, p_GetShortExpVector(short_s,c>r)); 1500 if (iS<0) 1501 { 1502 //PrintS("N"); 1503 if (TRUE) 1504 { 1505 c>states[i][j]=HASTREP; 1506 add_later(short_s,"N",c); 1507 } 1508 else 1509 p_Delete(&short_s,currRing); 1510 } 1511 else 1512 { 1513 if (c>strat>lenS[iS]>1) 1514 { 1515 //PrintS("O"); 1516 if (TRUE) { 1517 c>states[i][j]=HASTREP; 1518 add_later(short_s,"O",c); 1519 } 1520 else p_Delete(&short_s,currRing); 1521 } 1522 else 1523 p_Delete(&short_s, currRing); 1524 c>states[i][j]=HASTREP; 1525 } 1526 1527 1528 } 1529 } 1530 } 1650 if (c>lengths[i] + c>lengths[j] == 3) 1651 { 1652 1653 1654 poly short_s = ksCreateShortSpoly (c>S>m[i], c>S>m[j], c>r); 1655 if (short_s == NULL) 1656 { 1657 c>states[i][j] = HASTREP; 1658 } 1659 else 1660 { 1661 assume (pLength (short_s) == 1); 1662 if (TEST_V_UPTORADICAL) 1663 monomial_root (short_s, c>r); 1664 int iS = 1665 kFindDivisibleByInS_easy (c>strat, short_s, 1666 p_GetShortExpVector (short_s, c>r)); 1667 if (iS < 0) 1668 { 1669 //PrintS("N"); 1670 if (TRUE) 1671 { 1672 c>states[i][j] = HASTREP; 1673 add_later (short_s, "N", c); 1674 } 1675 else 1676 p_Delete (&short_s, currRing); 1677 } 1678 else 1679 { 1680 if (c>strat>lenS[iS] > 1) 1681 { 1682 //PrintS("O"); 1683 if (TRUE) 1684 { 1685 c>states[i][j] = HASTREP; 1686 add_later (short_s, "O", c); 1687 } 1688 else 1689 p_Delete (&short_s, currRing); 1690 } 1691 else 1692 p_Delete (&short_s, currRing); 1693 c>states[i][j] = HASTREP; 1694 } 1695 1696 1697 } 1698 } 1699 } 1531 1700 // if (short_s) 1532 1701 // { 1533 assume(spc<=j);1534 sorted_pair_node* s=c>tmp_spn[spc];//(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));1535 s>i=si_max(i,j);1536 s>j=si_min(i,j);1537 assume(s>j==j);1538 s>expected_length=pair_weighted_length(i,j,c);//c>lengths[i]+c>lengths[j]2;1539 1540 poly lm=c>tmp_pair_lm[spc];//=pOne_Special();1541 1542 pLcm(c>S>m[i], c>S>m[j], lm);1543 pSetm(lm);1544 p_Test(lm,c>r);1545 s>deg=c>pTotaldegree(lm);1546 1547 if(c>T_deg_full)//Sugar1548 {1549 int t_i=c>T_deg_full[s>i]c>T_deg[s>i];1550 int t_j=c>T_deg_full[s>j]c>T_deg[s>j];1551 s>deg+=si_max(t_i,t_j);1552 1553 }1554 p_Test(lm,c>r);1555 s>lcm_of_lm=lm;1556 // pDelete(&short_s);1557 //assume(lm!=NULL);1558 nodes[spc]=s;1559 spc++;1560 1561 // }1562 //else1563 //{1564 1565 //}1566 }1567 } //if syz_comp end1568 1569 assume (spc<=i);1702 assume (spc <= j); 1703 sorted_pair_node *s = c>tmp_spn[spc]; //(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 1704 s>i = si_max (i, j); 1705 s>j = si_min (i, j); 1706 assume (s>j == j); 1707 s>expected_length = pair_weighted_length (i, j, c); //c>lengths[i]+c>lengths[j]2; 1708 1709 poly lm = c>tmp_pair_lm[spc]; //=pOne_Special(); 1710 1711 pLcm (c>S>m[i], c>S>m[j], lm); 1712 pSetm (lm); 1713 p_Test (lm, c>r); 1714 s>deg = c>pTotaldegree (lm); 1715 1716 if (c>T_deg_full) //Sugar 1717 { 1718 int t_i = c>T_deg_full[s>i]  c>T_deg[s>i]; 1719 int t_j = c>T_deg_full[s>j]  c>T_deg[s>j]; 1720 s>deg += si_max (t_i, t_j); 1721 //Print("\n max: %d\n",max(t_i,t_j)); 1722 } 1723 p_Test (lm, c>r); 1724 s>lcm_of_lm = lm; 1725 // pDelete(&short_s); 1726 //assume(lm!=NULL); 1727 nodes[spc] = s; 1728 spc++; 1729 1730 // } 1731 //else 1732 //{ 1733 //c>states[i][j]=HASTREP; 1734 //} 1735 } 1736 } //if syz_comp end 1737 1738 assume (spc <= i); 1570 1739 //now ideal quotient crit 1571 qsort(nodes,spc,sizeof(sorted_pair_node*),iq_crit); 1572 1573 sorted_pair_node** nodes_final=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); 1574 int spc_final=0; 1575 j=0; 1576 while(j<spc) 1577 { 1578 int lower=j; 1740 qsort (nodes, spc, sizeof (sorted_pair_node *), iq_crit); 1741 1742 sorted_pair_node **nodes_final = 1743 (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i); 1744 int spc_final = 0; 1745 j = 0; 1746 while (j < spc) 1747 { 1748 int lower = j; 1579 1749 int upper; 1580 BOOLEAN has =FALSE;1581 for (upper=lower+1;upper<spc;upper++)1582 { 1583 if (!pLmEqual(nodes[lower]>lcm_of_lm,nodes[upper]>lcm_of_lm))1584 { 1585 1586 } 1587 if (has_t_rep (nodes[upper]>i,nodes[upper]>j,c))1588 has=TRUE;1589 } 1590 upper =upper1;1750 BOOLEAN has = FALSE; 1751 for (upper = lower + 1; upper < spc; upper++) 1752 { 1753 if (!pLmEqual (nodes[lower]>lcm_of_lm, nodes[upper]>lcm_of_lm)) 1754 { 1755 break; 1756 } 1757 if (has_t_rep (nodes[upper]>i, nodes[upper]>j, c)) 1758 has = TRUE; 1759 } 1760 upper = upper  1; 1591 1761 int z; 1592 assume(spc_final<=j); 1593 for(z=0;z<spc_final;z++) 1594 { 1595 if(p_LmDivisibleBy(nodes_final[z]>lcm_of_lm,nodes[lower]>lcm_of_lm,c>r)) 1596 { 1597 has=TRUE; 1598 break; 1599 } 1600 } 1601 1602 if(has) 1603 { 1604 for(;lower<=upper;lower++) 1605 { 1606 //free_sorted_pair_node(nodes[lower],c>r); 1607 //omfree(nodes[lower]); 1608 nodes[lower]=NULL; 1609 } 1610 j=upper+1; 1762 assume (spc_final <= j); 1763 for (z = 0; z < spc_final; z++) 1764 { 1765 if (p_LmDivisibleBy 1766 (nodes_final[z]>lcm_of_lm, nodes[lower]>lcm_of_lm, c>r)) 1767 { 1768 has = TRUE; 1769 break; 1770 } 1771 } 1772 1773 if (has) 1774 { 1775 for (; lower <= upper; lower++) 1776 { 1777 //free_sorted_pair_node(nodes[lower],c>r); 1778 //omfree(nodes[lower]); 1779 nodes[lower] = NULL; 1780 } 1781 j = upper + 1; 1611 1782 continue; 1612 1783 } 1613 1784 else 1614 1785 { 1615 p_Test(nodes[lower]>lcm_of_lm,c>r); 1616 nodes[lower]>lcm_of_lm=pCopy(nodes[lower]>lcm_of_lm); 1617 assume(_p_GetComp(c>S>m[nodes[lower]>i],c>r)==_p_GetComp(c>S>m[nodes[lower]>j],c>r)); 1618 nodes_final[spc_final]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 1619 1620 *(nodes_final[spc_final++])=*(nodes[lower]); 1786 p_Test (nodes[lower]>lcm_of_lm, c>r); 1787 nodes[lower]>lcm_of_lm = pCopy (nodes[lower]>lcm_of_lm); 1788 assume (_p_GetComp (c>S>m[nodes[lower]>i], c>r) == 1789 _p_GetComp (c>S>m[nodes[lower]>j], c>r)); 1790 nodes_final[spc_final] = 1791 (sorted_pair_node *) omalloc (sizeof (sorted_pair_node)); 1792 1793 *(nodes_final[spc_final++]) = *(nodes[lower]); 1621 1794 //c>tmp_spn[nodes[lower]>j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 1622 nodes[lower] =NULL;1623 for (lower=lower+1;lower<=upper;lower++)1624 { 1625 1626 1627 nodes[lower]=NULL;1628 } 1629 j =upper+1;1795 nodes[lower] = NULL; 1796 for (lower = lower + 1; lower <= upper; lower++) 1797 { 1798 // free_sorted_pair_node(nodes[lower],c>r); 1799 //omfree(nodes[lower]); 1800 nodes[lower] = NULL; 1801 } 1802 j = upper + 1; 1630 1803 continue; 1631 1804 } … … 1634 1807 // Print("i:%d,spc_final:%d",i,spc_final); 1635 1808 1636 assume (spc_final<=spc);1637 omfree (nodes);1638 nodes =NULL;1639 1640 add_to_reductors (c, h, c>lengths[c>n1], ecart,TRUE);1809 assume (spc_final <= spc); 1810 omfree (nodes); 1811 nodes = NULL; 1812 1813 add_to_reductors (c, h, c>lengths[c>n  1], ecart, TRUE); 1641 1814 //i=posInS(c>strat,c>strat>sl,h,0 ecart); 1642 1815 if (!(c>nc)) 1643 1816 { 1644 if (c>lengths[c>n 1]==1)1645 shorten_tails (c,c>S>m[c>n1]);1817 if (c>lengths[c>n  1] == 1) 1818 shorten_tails (c, c>S>m[c>n  1]); 1646 1819 } 1647 1820 //you should really update c>lengths, c>strat>lenS, and the oder of polys in strat if you sort after lengths … … 1649 1822 //for(i=c>strat>sl; i>0;i) 1650 1823 // if(c>strat>lenS[i]<c>strat>lenS[i1]) printf("fehler bei %d\n",i); 1651 if (c>Rcounter>50) { 1652 c>Rcounter=0; 1653 cleanS(c>strat,c); 1824 if (c>Rcounter > 50) 1825 { 1826 c>Rcounter = 0; 1827 cleanS (c>strat, c); 1654 1828 } 1655 1829 … … 1657 1831 // for SCA: 1658 1832 // here write at the end of nodes_final[spc_final,...,spc_final+lmdeg1] 1659 if (rIsSCA(c>r))1660 { 1661 const poly pNext = pNext (h);1662 1663 if (pNext != NULL)1833 if (rIsSCA (c>r)) 1834 { 1835 const poly pNext = pNext (h); 1836 1837 if (pNext != NULL) 1664 1838 { 1665 1839 // for additional polynomials 1666 const unsigned int m_iFirstAltVar = scaFirstAltVar (c>r);1667 const unsigned int m_iLastAltVar = scaLastAltVar(c>r);1668 1669 int N = 1670 m_iLastAltVar  m_iFirstAltVar + 1;// should be enough1840 const unsigned int m_iFirstAltVar = scaFirstAltVar (c>r); 1841 const unsigned int m_iLastAltVar = scaLastAltVar (c>r); 1842 1843 int N = // c>r>N; 1844 m_iLastAltVar  m_iFirstAltVar + 1; // should be enough 1671 1845 // TODO: but we may also use got = gcd({m}_{m\in f}))! 1672 1846 1673 poly* array_arg=(poly*)omalloc(N*sizeof(poly));// !1674 1675 1676 1677 for ( unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++)1678 1679 if( p_GetExp(h, v, c>r) )// TODO: use 'got' here!1680 1681 assume(p_GetExp(h, v, c>r)==1);1682 1683 poly p = sca_pp_Mult_xi_pp(v, pNext, c>r);// x_v * h;1684 1685 if(p != NULL)// if (x_v * h != 0)1686 1687 }// for all x_v  Ann(lm(h))1688 1689 c>introduceDelayedPairs (array_arg, j);1690 1691 omfree (array_arg);// !!!1847 poly *array_arg = (poly *) omalloc (N * sizeof (poly)); // ! 1848 int j = 0; 1849 1850 1851 for (unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++) 1852 // for all x_v  Ann(lm(h)) 1853 if (p_GetExp (h, v, c>r)) // TODO: use 'got' here! 1854 { 1855 assume (p_GetExp (h, v, c>r) == 1); 1856 1857 poly p = sca_pp_Mult_xi_pp (v, pNext, c>r); // x_v * h; 1858 1859 if (p != NULL) // if (x_v * h != 0) 1860 array_arg[j++] = p; 1861 } // for all x_v  Ann(lm(h)) 1862 1863 c>introduceDelayedPairs (array_arg, j); 1864 1865 omfree (array_arg); // !!! 1692 1866 } 1693 1867 // PrintS("Saturation  done!!!\n"); … … 1696 1870 1697 1871 1698 if(!ip) 1699 { 1700 qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),tgb_pair_better_gen2); 1701 1702 1703 c>apairs=spn_merge(c>apairs,c>pair_top+1,nodes_final,spc_final,c); 1704 c>pair_top+=spc_final; 1705 clean_top_of_pair_list(c); 1706 omfree(nodes_final); 1872 if (!ip) 1873 { 1874 qsort (nodes_final, spc_final, sizeof (sorted_pair_node *), 1875 tgb_pair_better_gen2); 1876 1877 1878 c>apairs = 1879 spn_merge (c>apairs, c>pair_top + 1, nodes_final, spc_final, c); 1880 c>pair_top += spc_final; 1881 clean_top_of_pair_list (c); 1882 omfree (nodes_final); 1707 1883 return NULL; 1708 1884 } 1709 1885 { 1710 *ip =spc_final;1886 *ip = spc_final; 1711 1887 return nodes_final; 1712 1888 } 1713 1889 } 1714 1890 1715 static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) 1716 { 1717 m=nInit(1); 1718 if (h==NULL) return NULL; 1719 1720 assume(len==pLength(h)); 1721 kStrategy strat=c>strat; 1891 static poly 1892 redNF2 (poly h, slimgb_alg * c, int &len, number & m, int n) 1893 { 1894 m = nInit (1); 1895 if (h == NULL) 1896 return NULL; 1897 1898 assume (len == pLength (h)); 1899 kStrategy strat = c>strat; 1722 1900 if (0 > strat>sl) 1723 1901 { … … 1726 1904 int j; 1727 1905 1728 LObject P (h);1729 P.SetShortExpVector ();1730 P.bucket = kBucketCreate (currRing);1906 LObject P (h); 1907 P.SetShortExpVector (); 1908 P.bucket = kBucketCreate (currRing); 1731 1909 // BOOLEAN corr=lenS_correct(strat); 1732 kBucketInit (P.bucket,P.p,len /*pLength(P.p)*/);1910 kBucketInit (P.bucket, P.p, len /*pLength(P.p) */ ); 1733 1911 //wlen_set lenSw=(wlen_set) c>strat>lenS; 1734 1912 //FIXME: plainly wrong … … 1739 1917 loop 1740 1918 { 1741 //int dummy=strat>sl; 1742 j=kFindDivisibleByInS_easy(strat,P.p,P.sev); 1743 //j=kFindDivisibleByInS(strat,&dummy,&P); 1744 if ((j>=0) && ((!n) 1745 ((strat>lenS[j]<=n) && 1746 ((strat>lenSw==NULL) 1747 (strat>lenSw[j]<=n))))) 1748 { 1749 nNormalize(pGetCoeff(P.p)); 1919 //int dummy=strat>sl; 1920 j = kFindDivisibleByInS_easy (strat, P.p, P.sev); 1921 //j=kFindDivisibleByInS(strat,&dummy,&P); 1922 if ((j >= 0) && ((!n)  1923 ((strat>lenS[j] <= n) && 1924 ((strat>lenSw == NULL)  (strat>lenSw[j] <= n))))) 1925 { 1926 nNormalize (pGetCoeff (P.p)); 1750 1927 #ifdef KDEBUG 1751 if (TEST_OPT_DEBUG) 1752 { 1753 PrintS("red:"); 1754 wrp(h); 1755 PrintS(" with "); 1756 wrp(strat>S[j]); 1757 } 1758 #endif 1759 1760 number coef=kBucketPolyRed(P.bucket,strat>S[j], 1761 strat>lenS[j]/*pLength(strat>S[j])*/, 1762 strat>kNoether); 1763 number m2=nMult(m,coef); 1764 nDelete(&m); 1765 m=m2; 1766 nDelete(&coef); 1767 h = kBucketGetLm(P.bucket); 1768 1769 if (h==NULL) { 1770 len=0; 1771 kBucketDestroy(&P.bucket); 1772 return 1773 NULL;} 1774 P.p=h; 1775 P.t_p=NULL; 1776 P.SetShortExpVector(); 1928 if (TEST_OPT_DEBUG) 1929 { 1930 PrintS ("red:"); 1931 wrp (h); 1932 PrintS (" with "); 1933 wrp (strat>S[j]); 1934 } 1935 #endif 1936 1937 number coef = kBucketPolyRed (P.bucket, strat>S[j], 1938 strat>lenS[j] /*pLength(strat>S[j]) */ , 1939 strat>kNoether); 1940 number m2 = nMult (m, coef); 1941 nDelete (&m); 1942 m = m2; 1943 nDelete (&coef); 1944 h = kBucketGetLm (P.bucket); 1945 1946 if (h == NULL) 1947 { 1948 len = 0; 1949 kBucketDestroy (&P.bucket); 1950 return NULL; 1951 } 1952 P.p = h; 1953 P.t_p = NULL; 1954 P.SetShortExpVector (); 1777 1955 #ifdef KDEBUG 1778 if (TEST_OPT_DEBUG) 1779 { 1780 PrintS("\nto:"); 1781 wrp(h); 1782 PrintLn(); 1783 } 1784 #endif 1785 } 1786 else 1787 { 1788 kBucketClear(P.bucket,&(P.p),&len); 1789 kBucketDestroy(&P.bucket); 1790 pNormalize(P.p); 1791 assume(len==(pLength(P.p))); 1792 return P.p; 1793 } 1794 } 1795 } 1796 1797 static poly redTailShort(poly h, kStrategy strat) 1798 { 1799 if (h==NULL) return NULL;//n_Init(1,currRing); 1956 if (TEST_OPT_DEBUG) 1957 { 1958 PrintS ("\nto:"); 1959 wrp (h); 1960 PrintLn (); 1961 } 1962 #endif 1963 } 1964 else 1965 { 1966 kBucketClear (P.bucket, &(P.p), &len); 1967 kBucketDestroy (&P.bucket); 1968 pNormalize (P.p); 1969 assume (len == (pLength (P.p))); 1970 return P.p; 1971 } 1972 } 1973 } 1974 1975 static poly 1976 redTailShort (poly h, kStrategy strat) 1977 { 1978 if (h == NULL) 1979 return NULL; //n_Init(1,currRing); 1800 1980 if (TEST_V_MODPSOLVSB) 1801 1981 { 1802 bit_reduce (pNext(h), strat>tailRing);1982 bit_reduce (pNext (h), strat>tailRing); 1803 1983 } 1804 1984 int i; 1805 int len=pLength(h); 1806 for(i=0;i<=strat>sl;i++) 1807 { 1808 if((strat>lenS[i]>2)  ((strat>lenSw!=NULL) && (strat>lenSw[i]>2))) 1985 int len = pLength (h); 1986 for (i = 0; i <= strat>sl; i++) 1987 { 1988 if ((strat>lenS[i] > 2) 1989  ((strat>lenSw != NULL) && (strat>lenSw[i] > 2))) 1809 1990 break; 1810 1991 } 1811 return(redNFTail(h,i1,strat, len)); 1812 } 1813 1814 static void line_of_extended_prod(int fixpos,slimgb_alg* c) 1815 { 1816 if (c>gcd_of_terms[fixpos]==NULL) 1817 { 1818 c>gcd_of_terms[fixpos]=gcd_of_terms(c>S>m[fixpos],c>r); 1992 return (redNFTail (h, i  1, strat, len)); 1993 } 1994 1995 static void 1996 line_of_extended_prod (int fixpos, slimgb_alg * c) 1997 { 1998 if (c>gcd_of_terms[fixpos] == NULL) 1999 { 2000 c>gcd_of_terms[fixpos] = gcd_of_terms (c>S>m[fixpos], c>r); 1819 2001 if (c>gcd_of_terms[fixpos]) 1820 2002 { 1821 2003 int i; 1822 for(i=0;i<fixpos;i++) 1823 if((c>states[fixpos][i]!=HASTREP)&& (extended_product_criterion(c>S>m[fixpos],c>gcd_of_terms[fixpos], c>S>m[i],c>gcd_of_terms[i],c))) 1824 { 1825 c>states[fixpos][i]=HASTREP; 1826 c>extended_product_crit++; 1827 } 1828 for(i=fixpos+1;i<c>n;i++) 1829 if((c>states[i][fixpos]!=HASTREP)&& (extended_product_criterion(c>S>m[fixpos],c>gcd_of_terms[fixpos], c>S>m[i],c>gcd_of_terms[i],c))) 1830 { c>states[i][fixpos]=HASTREP; 1831 c>extended_product_crit++; 1832 } 1833 } 1834 } 1835 } 1836 static void c_S_element_changed_hook(int pos, slimgb_alg* c) 1837 { 1838 length_one_crit(c,pos, c>lengths[pos]); 2004 for (i = 0; i < fixpos; i++) 2005 if ((c>states[fixpos][i] != HASTREP) 2006 && 2007 (extended_product_criterion 2008 (c>S>m[fixpos], c>gcd_of_terms[fixpos], c>S>m[i], 2009 c>gcd_of_terms[i], c))) 2010 { 2011 c>states[fixpos][i] = HASTREP; 2012 c>extended_product_crit++; 2013 } 2014 for (i = fixpos + 1; i < c>n; i++) 2015 if ((c>states[i][fixpos] != HASTREP) 2016 && 2017 (extended_product_criterion 2018 (c>S>m[fixpos], c>gcd_of_terms[fixpos], c>S>m[i], 2019 c>gcd_of_terms[i], c))) 2020 { 2021 c>states[i][fixpos] = HASTREP; 2022 c>extended_product_crit++; 2023 } 2024 } 2025 } 2026 } 2027 2028 static void 2029 c_S_element_changed_hook (int pos, slimgb_alg * c) 2030 { 2031 length_one_crit (c, pos, c>lengths[pos]); 1839 2032 if (!c>nc) 1840 line_of_extended_prod(pos,c); 1841 } 1842 class poly_tree_node { 2033 line_of_extended_prod (pos, c); 2034 } 2035 2036 class poly_tree_node 2037 { 1843 2038 public: 1844 2039 poly p; 1845 poly_tree_node *l;1846 poly_tree_node *r;2040 poly_tree_node *l; 2041 poly_tree_node *r; 1847 2042 int n; 1848 poly_tree_node(int sn):l(NULL),r(NULL),n(sn) 1849 {} 2043 poly_tree_node (int sn):l (NULL), r (NULL), n (sn) 2044 { 2045 } 1850 2046 }; 1851 class exp_number_builder{ 2047 class exp_number_builder 2048 { 1852 2049 public: 1853 poly_tree_node * top_level;2050 poly_tree_node * top_level; 1854 2051 int n; 1855 int get_n(poly p); 1856 exp_number_builder():top_level(0),n(0) 1857 {} 2052 int get_n (poly p); 2053 exp_number_builder ():top_level (0), n (0) 2054 { 2055 } 1858 2056 }; 1859 int exp_number_builder::get_n(poly p) 1860 { 1861 poly_tree_node** node=&top_level; 1862 while(*node!=NULL) 1863 { 1864 int c=pLmCmp(p,(*node)>p); 1865 if (c==0) return (*node)>n; 1866 if (c==1) node=&((*node)>r); 2057 int 2058 exp_number_builder::get_n (poly p) 2059 { 2060 poly_tree_node **node = &top_level; 2061 while (*node != NULL) 2062 { 2063 int c = pLmCmp (p, (*node)>p); 2064 if (c == 0) 2065 return (*node)>n; 2066 if (c == 1) 2067 node = &((*node)>r); 1867 2068 else 1868 node =&((*node)>l);1869 } 1870 (*node) = new poly_tree_node(n);2069 node = &((*node)>l); 2070 } 2071 (*node) = new poly_tree_node (n); 1871 2072 n++; 1872 (*node)>p =pLmInit(p);2073 (*node)>p = pLmInit (p); 1873 2074 return (*node)>n; 1874 2075 } … … 1878 2079 1879 2080 //! obsolete 1880 struct int_poly_pair{ 2081 struct int_poly_pair 2082 { 1881 2083 poly p; 1882 2084 int n; … … 1885 2087 1886 2088 //! obsolete 1887 void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset) 1888 { 1889 if(!k) return; 1890 t2ippa_rec(ip,ia,k>l,offset); 1891 ip[offset]=k>p; 1892 ia[k>n]=offset; 1893 ++offset; 1894 1895 t2ippa_rec(ip,ia,k>r,offset); 1896 delete k; 1897 } 2089 void 2090 t2ippa_rec (poly * ip, int *ia, poly_tree_node * k, int &offset) 2091 { 2092 if (!k) 2093 return; 2094 t2ippa_rec (ip, ia, k>l, offset); 2095 ip[offset] = k>p; 2096 ia[k>n] = offset; 2097 ++offset; 2098 2099 t2ippa_rec (ip, ia, k>r, offset); 2100 delete k; 2101 } 1898 2102 1899 2103 //! obsolete 1900 void t2ippa(poly* ip,int* ia,exp_number_builder & e) 1901 { 1902 1903 int o=0; 1904 t2ippa_rec(ip,ia,e.top_level,o); 1905 } 1906 int anti_poly_order(const void* a, const void* b) 1907 { 1908 return pLmCmp(((int_poly_pair*) a)>p,((int_poly_pair*) b)>p ); 1909 } 1910 1911 BOOLEAN is_valid_ro(red_object & ro) 1912 { 1913 red_object r2=ro; 1914 ro.validate(); 1915 if ((r2.p!=ro.p)(r2.sev!=ro.sev)) return FALSE; 2104 void 2105 t2ippa (poly * ip, int *ia, exp_number_builder & e) 2106 { 2107 2108 int o = 0; 2109 t2ippa_rec (ip, ia, e.top_level, o); 2110 } 2111 2112 int 2113 anti_poly_order (const void *a, const void *b) 2114 { 2115 return pLmCmp (((int_poly_pair *) a)>p, ((int_poly_pair *) b)>p); 2116 } 2117 2118 BOOLEAN 2119 is_valid_ro (red_object & ro) 2120 { 2121 red_object r2 = ro; 2122 ro.validate (); 2123 if ((r2.p != ro.p)  (r2.sev != ro.sev)) 2124 return FALSE; 1916 2125 return TRUE; 1917 2126 } 1918 int terms_sort_crit(const void* a, const void* b) 1919 { 1920 return pLmCmp(*((poly*) a),*((poly*) b)); 1921 } 1922 #if 0 // currently unused 1923 static void unify_terms(poly* terms,int & sum) 1924 { 1925 if (sum==0) return; 1926 int last=0; 1927 int curr=1; 1928 while(curr<sum) 1929 { 1930 if (!(pLmEqual(terms[curr],terms[last]))) 1931 { 1932 terms[++last]=terms[curr]; 2127 2128 int 2129 terms_sort_crit (const void *a, const void *b) 2130 { 2131 return pLmCmp (*((poly *) a), *((poly *) b)); 2132 } 2133 2134 #if 0 // currently unused 2135 static void 2136 unify_terms (poly * terms, int &sum) 2137 { 2138 if (sum == 0) 2139 return; 2140 int last = 0; 2141 int curr = 1; 2142 while (curr < sum) 2143 { 2144 if (!(pLmEqual (terms[curr], terms[last]))) 2145 { 2146 terms[++last] = terms[curr]; 1933 2147 } 1934 2148 ++curr; 1935 2149 } 1936 sum=last+1; 1937 } 1938 #endif 1939 #if 0 // currently unused 1940 static void export_mat(number* number_array,int pn, int tn,const char* format_str, int mat_nr) 2150 sum = last + 1; 2151 } 2152 #endif 2153 #if 0 // currently unused 2154 static void 2155 export_mat (number * number_array, int pn, int tn, const char *format_str, 2156 int mat_nr) 1941 2157 { 1942 2158 char matname[20]; 1943 sprintf (matname,format_str,mat_nr);1944 FILE * out=fopen(matname,"w");1945 int i, j;1946 fprintf (out,"mat=[\n");1947 for (i=0;i<pn;i++)1948 { 1949 fprintf (out,"[\n");1950 for (j=0;j<tn;j++)1951 { 1952 if (j >0)1953 { 1954 fprintf(out,", ");1955 } 1956 fprintf (out,"%i",npInt(number_array[i*tn+j],currRing));1957 } 1958 if (i <pn1)1959 fprintf (out,"],\n");2159 sprintf (matname, format_str, mat_nr); 2160 FILE *out = fopen (matname, "w"); 2161 int i, j; 2162 fprintf (out, "mat=[\n"); 2163 for (i = 0; i < pn; i++) 2164 { 2165 fprintf (out, "[\n"); 2166 for (j = 0; j < tn; j++) 2167 { 2168 if (j > 0) 2169 { 2170 fprintf (out, ", "); 2171 } 2172 fprintf (out, "%i", npInt (number_array[i * tn + j], currRing)); 2173 } 2174 if (i < pn  1) 2175 fprintf (out, "],\n"); 1960 2176 else 1961 fprintf (out,"],\n");1962 } 1963 fprintf (out,"]\n");1964 fclose (out);2177 fprintf (out, "],\n"); 2178 } 2179 fprintf (out, "]\n"); 2180 fclose (out); 1965 2181 } 1966 2182 #endif … … 1970 2186 #ifdef USE_NORO 1971 2187 #ifndef NORO_CACHE 1972 static void linalg_step_modp(poly *p, poly* p_out, int& pn, poly* terms,int tn, slimgb_alg* c) 1973 { 1974 static int export_n=0; 1975 assume(terms[tn1]!=NULL); 1976 assume(rField_is_Zp(c>r)); 2188 static void 2189 linalg_step_modp (poly * p, poly * p_out, int &pn, poly * terms, int tn, 2190 slimgb_alg * c) 2191 { 2192 static int export_n = 0; 2193 assume (terms[tn  1] != NULL); 2194 assume (rField_is_Zp (c>r)); 1977 2195 //I don't do deletes, copies of number_types ... 1978 const number_type zero=0;//npInit(0); 1979 int array_size=pn*tn; 1980 number_type* number_array=(number_type*) omalloc(pn*tn*sizeof(number_type)); 2196 const number_type zero = 0; //npInit(0); 2197 int array_size = pn * tn; 2198 number_type *number_array = 2199 (number_type *) omalloc (pn * tn * sizeof (number_type)); 1981 2200 int i; 1982 for (i=0;i<array_size;i++)1983 { 1984 number_array[i] =zero;1985 } 1986 for (i=0;i<pn;i++)1987 { 1988 poly h =p[i];2201 for (i = 0; i < array_size; i++) 2202 { 2203 number_array[i] = zero; 2204 } 2205 for (i = 0; i < pn; i++) 2206 { 2207 poly h = p[i]; 1989 2208 //int base=tn*i; 1990 write_poly_to_row (number_array+tn*i,h,terms,tn,c>r);2209 write_poly_to_row (number_array + tn * i, h, terms, tn, c>r); 1991 2210 1992 2211 } 1993 2212 #if 0 1994 2213 //export matrix 1995 export_mat (number_array,pn,tn,"mat%i.py",++export_n);1996 #endif 1997 int rank =pn;1998 simplest_gauss_modp (number_array,rank,tn);1999 int act_row =0;2000 int p_pos =0;2001 for (i=0;i<pn;i++)2002 { 2003 poly h =NULL;2214 export_mat (number_array, pn, tn, "mat%i.py", ++export_n); 2215 #endif 2216 int rank = pn; 2217 simplest_gauss_modp (number_array, rank, tn); 2218 int act_row = 0; 2219 int p_pos = 0; 2220 for (i = 0; i < pn; i++) 2221 { 2222 poly h = NULL; 2004 2223 int j; 2005 int base =tn*i;2006 number * row=number_array+base;2007 h =row_to_poly(row,terms,tn,c>r);2008 2009 if (h!=NULL)2010 {2011 p_out[p_pos++]=h;2012 }2013 } 2014 pn =p_pos;2224 int base = tn * i; 2225 number *row = number_array + base; 2226 h = row_to_poly (row, terms, tn, c>r); 2227 2228 if (h != NULL) 2229 { 2230 p_out[p_pos++] = h; 2231 } 2232 } 2233 pn = p_pos; 2015 2234 //assert(p_pos==rank) 2016 while (p_pos<pn)2017 { 2018 p_out[p_pos++] =NULL;2235 while (p_pos < pn) 2236 { 2237 p_out[p_pos++] = NULL; 2019 2238 } 2020 2239 #if 0 2021 export_mat(number_array,pn,tn,"mat%i.py",++export_n); 2022 #endif 2023 } 2024 #endif 2025 #endif 2026 static void mass_add(poly* p, int pn,slimgb_alg* c) 2027 { 2028 int j; 2029 int* ibuf=(int*) omalloc(pn*sizeof(int)); 2030 sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(pn*sizeof(sorted_pair_node**)); 2031 for(j=0;j<pn;j++) 2032 { 2033 p_Test(p[j],c>r); 2034 sbuf[j]=add_to_basis_ideal_quotient(p[j],c,ibuf+j); 2035 } 2036 int sum=0; 2037 for(j=0;j<pn;j++) 2038 { 2039 sum+=ibuf[j]; 2040 } 2041 sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*)); 2042 int partsum=0; 2043 for(j=0;j<pn;j++) 2044 { 2045 memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*)); 2046 omfree(sbuf[j]); 2047 partsum+=ibuf[j]; 2048 } 2049 2050 qsort(big_sbuf,sum,sizeof(sorted_pair_node*),tgb_pair_better_gen2); 2051 c>apairs=spn_merge(c>apairs,c>pair_top+1,big_sbuf,sum,c); 2052 c>pair_top+=sum; 2053 clean_top_of_pair_list(c); 2054 omfree(big_sbuf); 2055 omfree(sbuf); 2056 omfree(ibuf); 2057 //omfree(buf); 2058 #ifdef TGB_DEBUG 2059 int z; 2060 for(z=1;z<=c>pair_top;z++) 2061 { 2062 assume(pair_better(c>apairs[z],c>apairs[z1],c)); 2063 } 2064 #endif 2240 export_mat (number_array, pn, tn, "mat%i.py", ++export_n); 2241 #endif 2242 } 2243 #endif 2244 #endif 2245 static void 2246 mass_add (poly * p, int pn, slimgb_alg * c) 2247 { 2248 int j; 2249 int *ibuf = (int *) omalloc (pn * sizeof (int)); 2250 sorted_pair_node ***sbuf = 2251 (sorted_pair_node ***) omalloc (pn * sizeof (sorted_pair_node **)); 2252 for (j = 0; j < pn; j++) 2253 { 2254 p_Test (p[j], c>r); 2255 sbuf[j] = add_to_basis_ideal_quotient (p[j], c, ibuf + j); 2256 } 2257 int sum = 0; 2258 for (j = 0; j < pn; j++) 2259 { 2260 sum += ibuf[j]; 2261 } 2262 sorted_pair_node **big_sbuf = 2263 (sorted_pair_node **) omalloc (sum * sizeof (sorted_pair_node *)); 2264 int partsum = 0; 2265 for (j = 0; j < pn; j++) 2266 { 2267 memmove (big_sbuf + partsum, sbuf[j], 2268 ibuf[j] * sizeof (sorted_pair_node *)); 2269 omfree (sbuf[j]); 2270 partsum += ibuf[j]; 2271 } 2272 2273 qsort (big_sbuf, sum, sizeof (sorted_pair_node *), tgb_pair_better_gen2); 2274 c>apairs = spn_merge (c>apairs, c>pair_top + 1, big_sbuf, sum, c); 2275 c>pair_top += sum; 2276 clean_top_of_pair_list (c); 2277 omfree (big_sbuf); 2278 omfree (sbuf); 2279 omfree (ibuf); 2280 //omfree(buf); 2281 #ifdef TGB_DEBUG 2282 int z; 2283 for (z = 1; z <= c>pair_top; z++) 2284 { 2285 assume (pair_better (c>apairs[z], c>apairs[z  1], c)); 2286 } 2287 #endif 2065 2288 2066 2289 } … … 2068 2291 #ifdef NORO_CACHE 2069 2292 #ifndef NORO_NON_POLY 2070 void NoroCache::evaluateRows() 2293 void 2294 NoroCache::evaluateRows () 2071 2295 { 2072 2296 //after that can evaluate placeholders 2073 2297 int i; 2074 buffer=(number*) omalloc(nIrreducibleMonomials*sizeof(number)); 2075 for(i=0;i<root.branches_len;i++) 2076 { 2077 evaluateRows(1,root.branches[i]); 2078 } 2079 omfree(buffer); 2080 buffer=NULL; 2081 } 2082 void NoroCache::evaluateRows(int level, NoroCacheNode* node) 2083 { 2084 assume(level>=0); 2085 if (node==NULL) return; 2086 if (level<pVariables) 2087 { 2088 int i,sum; 2089 for(i=0;i<node>branches_len;i++) 2090 { 2091 evaluateRows(level+1,node>branches[i]); 2298 buffer = (number *) omalloc (nIrreducibleMonomials * sizeof (number)); 2299 for (i = 0; i < root.branches_len; i++) 2300 { 2301 evaluateRows (1, root.branches[i]); 2302 } 2303 omfree (buffer); 2304 buffer = NULL; 2305 } 2306 2307 void 2308 NoroCache::evaluateRows (int level, NoroCacheNode * node) 2309 { 2310 assume (level >= 0); 2311 if (node == NULL) 2312 return; 2313 if (level < pVariables) 2314 { 2315 int i, sum; 2316 for (i = 0; i < node>branches_len; i++) 2317 { 2318 evaluateRows (level + 1, node>branches[i]); 2092 2319 } 2093 2320 } 2094 2321 else 2095 2322 { 2096 DataNoroCacheNode* dn=(DataNoroCacheNode*) node; 2097 if (dn>value_len!=backLinkCode) 2098 { 2099 poly p=dn>value_poly; 2100 #ifndef NORO_SPARSE_ROWS_PRE 2101 dn>row=new DenseRow(); 2102 DenseRow* row=dn>row; 2103 memset(buffer,0,sizeof(number)*nIrreducibleMonomials); 2104 2105 if (p==NULL) {row>array=NULL;row>begin=0;row>end=0; return;} 2106 int i=0; 2323 DataNoroCacheNode *dn = (DataNoroCacheNode *) node; 2324 if (dn>value_len != backLinkCode) 2325 { 2326 poly p = dn>value_poly; 2327 #ifndef NORO_SPARSE_ROWS_PRE 2328 dn>row = new DenseRow (); 2329 DenseRow *row = dn>row; 2330 memset (buffer, 0, sizeof (number) * nIrreducibleMonomials); 2331 2332 if (p == NULL) 2333 { 2334 row>array = NULL; 2335 row>begin = 0; 2336 row>end = 0; 2337 return; 2338 } 2339 int i = 0; 2107 2340 int idx; 2108 number* a=buffer; 2109 while(p) 2110 { 2111 DataNoroCacheNode* ref=getCacheReference(p); 2112 2113 idx=ref>term_index; 2114 assume(idx>=0); 2115 a[idx]=p_GetCoeff(p,currRing); 2116 if (i==0) row>begin=idx; 2117 i++; 2118 pIter(p); 2119 } 2120 row>end=idx+1; 2121 assume(row>end>row>begin); 2122 int len=row>endrow>begin; 2123 row>array=(number*) omalloc((len)*sizeof(number)); 2124 memcpy(row>array,a+row>begin,len*sizeof(number)); 2125 #else 2126 assume(dn>value_len==pLength(dn>value_poly)); 2127 dn>row=new SparseRow(dn>value_len); 2128 SparseRow* row=dn>row; 2129 int i=0; 2130 while(p) 2131 { 2132 DataNoroCacheNode* ref=getCacheReference(p); 2133 2134 int idx=ref>term_index; 2135 assume(idx>=0); 2136 row>idx_array[i]=idx; 2137 row>coef_array[i]=p_GetCoeff(p,currRing); 2138 i++; 2139 pIter(p); 2140 } 2141 if (i!=dn>value_len) 2142 { 2143 PrintS("F4 calc wrong, as poly len was wrong\n"); 2144 } 2145 assume(i==dn>value_len); 2146 #endif 2147 } 2148 } 2149 } 2150 2151 void NoroCache::evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders) 2341 number *a = buffer; 2342 while (p) 2343 { 2344 DataNoroCacheNode *ref = getCacheReference (p); 2345 2346 idx = ref>term_index; 2347 assume (idx >= 0); 2348 a[idx] = p_GetCoeff (p, currRing); 2349 if (i == 0) 2350 row>begin = idx; 2351 i++; 2352 pIter (p); 2353 } 2354 row>end = idx + 1; 2355 assume (row>end > row>begin); 2356 int len = row>end  row>begin; 2357 row>array = (number *) omalloc ((len) * sizeof (number)); 2358 memcpy (row>array, a + row>begin, len * sizeof (number)); 2359 #else 2360 assume (dn>value_len == pLength (dn>value_poly)); 2361 dn>row = new SparseRow (dn>value_len); 2362 SparseRow *row = dn>row; 2363 int i = 0; 2364 while (p) 2365 { 2366 DataNoroCacheNode *ref = getCacheReference (p); 2367 2368 int idx = ref>term_index; 2369 assume (idx >= 0); 2370 row>idx_array[i] = idx; 2371 row>coef_array[i] = p_GetCoeff (p, currRing); 2372 i++; 2373 pIter (p); 2374 } 2375 if (i != dn>value_len) 2376 { 2377 PrintS ("F4 calc wrong, as poly len was wrong\n"); 2378 } 2379 assume (i == dn>value_len); 2380 #endif 2381 } 2382 } 2383 } 2384 2385 void 2386 NoroCache::evaluatePlaceHolder (number * row, 2387 std::vector < NoroPlaceHolder > 2388 &place_holders) 2152 2389 { 2153 2390 int i; 2154 int s =place_holders.size();2155 for (i=0;i<s;i++)2156 { 2157 DataNoroCacheNode * ref=place_holders[i].ref;2158 number coef =place_holders[i].coef;2159 if (ref>value_len ==backLinkCode)2160 { 2161 row[ref>term_index] =npAddM(row[ref>term_index],coef);2391 int s = place_holders.size (); 2392 for (i = 0; i < s; i++) 2393 { 2394 DataNoroCacheNode *ref = place_holders[i].ref; 2395 number coef = place_holders[i].coef; 2396 if (ref>value_len == backLinkCode) 2397 { 2398 row[ref>term_index] = npAddM (row[ref>term_index], coef); 2162 2399 } 2163 2400 else 2164 2401 { 2165 #ifndef NORO_SPARSE_ROWS_PRE 2166 DenseRow* ref_row=ref>row; 2167 if (ref_row==NULL) continue; 2168 number* ref_begin=ref_row>array; 2169 number* ref_end=ref_row>array+(ref_row>endref_row>begin); 2170 number* my_pos=row+ref_row>begin; 2402 #ifndef NORO_SPARSE_ROWS_PRE 2403 DenseRow *ref_row = ref>row; 2404 if (ref_row == NULL) 2405 continue; 2406 number *ref_begin = ref_row>array; 2407 number *ref_end = ref_row>array + (ref_row>end  ref_row>begin); 2408 number *my_pos = row + ref_row>begin; 2171 2409 //TODO npisOne distinction 2172 if (!(npIsOne (coef)))2173 { 2174 while(ref_begin!=ref_end)2175 2176 2177 *my_pos=npAddM(*my_pos,npMult(coef,*ref_begin));2178 2179 2180 2410 if (!(npIsOne (coef))) 2411 { 2412 while (ref_begin != ref_end) 2413 { 2414 2415 *my_pos = npAddM (*my_pos, npMult (coef, *ref_begin)); 2416 ++ref_begin; 2417 ++my_pos; 2418 } 2181 2419 } 2182 2420 else 2183 2421 { 2184 while(ref_begin!=ref_end) 2185 { 2186 2187 *my_pos=npAddM(*my_pos,*ref_begin); 2188 ++ref_begin; 2189 ++my_pos; 2190 } 2191 } 2192 2193 #else 2194 SparseRow* ref_row=ref>row; 2195 if (ref_row==NULL) continue; 2196 int n=ref_row>len; 2197 int j; 2198 int* idx_array=ref_row>idx_array; 2199 number* coef_array=ref_row>coef_array; 2200 for(j=0;j<n;j++) 2201 { 2202 int idx=idx_array[j]; 2203 number ref_coef=coef_array[j]; 2204 row[idx]=npAddM(row[idx],npMult(coef,ref_coef)); 2205 } 2206 #endif 2207 } 2422 while (ref_begin != ref_end) 2423 { 2424 2425 *my_pos = npAddM (*my_pos, *ref_begin); 2426 ++ref_begin; 2427 ++my_pos; 2428 } 2429 } 2430 2431 #else 2432 SparseRow *ref_row = ref>row; 2433 if (ref_row == NULL) 2434 continue; 2435 int n = ref_row>len; 2436 int j; 2437 int *idx_array = ref_row>idx_array; 2438 number *coef_array = ref_row>coef_array; 2439 for (j = 0; j < n; j++) 2440 { 2441 int idx = idx_array[j]; 2442 number ref_coef = coef_array[j]; 2443 row[idx] = npAddM (row[idx], npMult (coef, ref_coef)); 2444 } 2445 #endif 2446 } 2208 2447 } 2209 2448 } … … 2213 2452 2214 2453 #ifndef NORO_NON_POLY 2215 MonRedRes noro_red_mon(poly t, BOOLEAN force_unique, NoroCache* cache,slimgb_alg* c) 2454 MonRedRes 2455 noro_red_mon (poly t, BOOLEAN force_unique, NoroCache * cache, slimgb_alg * c) 2216 2456 { 2217 2457 MonRedRes res_holder; 2218 2458 2219 2459 //wrp(t); 2220 res_holder.changed =TRUE;2460 res_holder.changed = TRUE; 2221 2461 if (force_unique) 2222 2462 { 2223 DataNoroCacheNode * ref=cache>getCacheReference(t);2224 if (ref !=NULL)2225 { 2226 res_holder.len =ref>value_len;2227 if (res_holder.len ==NoroCache::backLinkCode)2228 { 2229 res_holder.len=1;2230 } 2231 res_holder.coef =p_GetCoeff(t,c>r);2232 res_holder.p =ref>value_poly;2233 res_holder.ref =ref;2234 res_holder.onlyBorrowed =TRUE;2235 res_holder.changed =TRUE;2236 p_Delete (&t,c>r);2463 DataNoroCacheNode *ref = cache>getCacheReference (t); 2464 if (ref != NULL) 2465 { 2466 res_holder.len = ref>value_len; 2467 if (res_holder.len == NoroCache::backLinkCode) 2468 { 2469 res_holder.len = 1; 2470 } 2471 res_holder.coef = p_GetCoeff (t, c>r); 2472 res_holder.p = ref>value_poly; 2473 res_holder.ref = ref; 2474 res_holder.onlyBorrowed = TRUE; 2475 res_holder.changed = TRUE; 2476 p_Delete (&t, c>r); 2237 2477 return res_holder; 2238 2478 } … … 2241 2481 { 2242 2482 BOOLEAN succ; 2243 poly cache_lookup =cache>lookup(t,succ, res_holder.len);//don't own this yet2483 poly cache_lookup = cache>lookup (t, succ, res_holder.len); //don't own this yet 2244 2484 if (succ) 2245 2485 { 2246 if (cache_lookup ==t)2247 { 2248 2249 2250 2251 res_holder.changed=FALSE;2252 res_holder.p=t;2253 res_holder.coef=npInit(1);2254 2255 res_holder.onlyBorrowed=FALSE;2256 2257 } 2258 2259 res_holder.coef =p_GetCoeff(t,c>r);2260 p_Delete (&t,c>r);2261 2262 res_holder.p =cache_lookup;2263 2264 res_holder.onlyBorrowed =TRUE;2486 if (cache_lookup == t) 2487 { 2488 //know they are equal 2489 //res_holder.len=1; 2490 2491 res_holder.changed = FALSE; 2492 res_holder.p = t; 2493 res_holder.coef = npInit (1); 2494 2495 res_holder.onlyBorrowed = FALSE; 2496 return res_holder; 2497 } 2498 2499 res_holder.coef = p_GetCoeff (t, c>r); 2500 p_Delete (&t, c>r); 2501 2502 res_holder.p = cache_lookup; 2503 2504 res_holder.onlyBorrowed = TRUE; 2265 2505 return res_holder; 2266 2506 … … 2268 2508 } 2269 2509 2270 unsigned long sev =p_GetShortExpVector(t,currRing);2271 int i =kFindDivisibleByInS_easy(c>strat,t,sev);2272 if (i >=0)2273 { 2274 number coef_bak =p_GetCoeff(t,c>r);2275 2276 p_SetCoeff (t,npInit(1),c>r);2277 assume (npIsOne(p_GetCoeff(c>strat>S[i],c>r)));2278 number coefstrat =p_GetCoeff(c>strat>S[i],c>r);2279 2280 2281 poly exp_diff =cache>temp_term;2282 p_ExpVectorDiff (exp_diff,t,c>strat>S[i],c>r);2283 p_SetCoeff (exp_diff,npNeg(nInvers(coefstrat)),c>r);2284 2285 p_Setm (exp_diff,c>r);2286 assume (c>strat>S[i]!=NULL);2287 2510 unsigned long sev = p_GetShortExpVector (t, currRing); 2511 int i = kFindDivisibleByInS_easy (c>strat, t, sev); 2512 if (i >= 0) 2513 { 2514 number coef_bak = p_GetCoeff (t, c>r); 2515 2516 p_SetCoeff (t, npInit (1), c>r); 2517 assume (npIsOne (p_GetCoeff (c>strat>S[i], c>r))); 2518 number coefstrat = p_GetCoeff (c>strat>S[i], c>r); 2519 2520 //poly t_copy_mon=p_Copy(t,c>r); 2521 poly exp_diff = cache>temp_term; 2522 p_ExpVectorDiff (exp_diff, t, c>strat>S[i], c>r); 2523 p_SetCoeff (exp_diff, npNeg (nInvers (coefstrat)), c>r); 2524 // nInvers may be npInvers or nvInvers 2525 p_Setm (exp_diff, c>r); 2526 assume (c>strat>S[i] != NULL); 2527 //poly t_to_del=t; 2288 2528 poly res; 2289 res =pp_Mult_mm(pNext(c>strat>S[i]),exp_diff,c>r);2290 2291 res_holder.len =c>strat>lenS[i]1;2292 res =noro_red_non_unique(res,res_holder.len,cache,c);2293 2294 DataNoroCacheNode * ref=cache>insert(t,res,res_holder.len);2295 p_Delete (&t,c>r);2296 2297 2298 res_holder.changed =TRUE;2299 res_holder.p =res;2300 res_holder.coef =coef_bak;2301 res_holder.onlyBorrowed =TRUE;2302 res_holder.ref =ref;2529 res = pp_Mult_mm (pNext (c>strat>S[i]), exp_diff, c>r); 2530 2531 res_holder.len = c>strat>lenS[i]  1; 2532 res = noro_red_non_unique (res, res_holder.len, cache, c); 2533 2534 DataNoroCacheNode *ref = cache>insert (t, res, res_holder.len); 2535 p_Delete (&t, c>r); 2536 //p_Delete(&t_copy_mon,c>r); 2537 //res=pMult_nn(res,coef_bak); 2538 res_holder.changed = TRUE; 2539 res_holder.p = res; 2540 res_holder.coef = coef_bak; 2541 res_holder.onlyBorrowed = TRUE; 2542 res_holder.ref = ref; 2303 2543 return res_holder; 2304 2544 } 2305 2545 else 2306 2546 { 2307 number coef_bak =p_GetCoeff(t,c>r);2308 number one =npInit(1);2309 p_SetCoeff (t,one,c>r);2310 res_holder.len =1;2547 number coef_bak = p_GetCoeff (t, c>r); 2548 number one = npInit (1); 2549 p_SetCoeff (t, one, c>r); 2550 res_holder.len = 1; 2311 2551 if (!(force_unique)) 2312 2552 { 2313 res_holder.ref =cache>insert(t,t,res_holder.len);2314 p_SetCoeff (t,coef_bak,c>r);2553 res_holder.ref = cache>insert (t, t, res_holder.len); 2554 p_SetCoeff (t, coef_bak, c>r); 2315 2555 //return t; 2316 2556 2317 2557 //we need distinction 2318 res_holder.changed =FALSE;2319 res_holder.p =t;2320 2321 res_holder.coef =npInit(1);2322 res_holder.onlyBorrowed =FALSE;2558 res_holder.changed = FALSE; 2559 res_holder.p = t; 2560 2561 res_holder.coef = npInit (1); 2562 res_holder.onlyBorrowed = FALSE; 2323 2563 return res_holder; 2324 2564 } 2325 2565 else 2326 2566 { 2327 res_holder.ref =cache>insertAndTransferOwnerShip(t,c>r);2328 res_holder.coef =coef_bak;2329 res_holder.onlyBorrowed =TRUE;2330 res_holder.changed =FALSE;2331 res_holder.p =t;2567 res_holder.ref = cache>insertAndTransferOwnerShip (t, c>r); 2568 res_holder.coef = coef_bak; 2569 res_holder.onlyBorrowed = TRUE; 2570 res_holder.changed = FALSE; 2571 res_holder.p = t; 2332 2572 return res_holder; 2333 2573 } … … 2339 2579 #ifndef NORO_NON_POLY 2340 2580 //len input and out: Idea: reverse addition 2341 poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c) 2342 { 2343 assume(len==pLength(p)); 2344 poly orig_p=p; 2345 if (p==NULL) { 2346 len=0; 2581 poly 2582 noro_red_non_unique (poly p, int &len, NoroCache * cache, slimgb_alg * c) 2583 { 2584 assume (len == pLength (p)); 2585 poly orig_p = p; 2586 if (p == NULL) 2587 { 2588 len = 0; 2347 2589 return NULL; 2348 2590 } 2349 kBucket_pt bucket =kBucketCreate(currRing);2350 kBucketInit (bucket,NULL,0);2351 poly unchanged_head =NULL;2352 poly unchanged_tail =NULL;2353 int unchanged_size =0;2354 2355 while (p)2356 { 2357 poly t =p;2358 pIter (p);2359 pNext (t)=NULL;2591 kBucket_pt bucket = kBucketCreate (currRing); 2592 kBucketInit (bucket, NULL, 0); 2593 poly unchanged_head = NULL; 2594 poly unchanged_tail = NULL; 2595 int unchanged_size = 0; 2596 2597 while (p) 2598 { 2599 poly t = p; 2600 pIter (p); 2601 pNext (t) = NULL; 2360 2602 #ifndef NDEBUG 2361 number coef_debug =p_GetCoeff(t,currRing);2362 #endif 2363 MonRedRes red =noro_red_mon(t,FALSE,cache,c);2364 if ((!(red.changed)) &&(!(red.onlyBorrowed)))2603 number coef_debug = p_GetCoeff (t, currRing); 2604 #endif 2605 MonRedRes red = noro_red_mon (t, FALSE, cache, c); 2606 if ((!(red.changed)) && (!(red.onlyBorrowed))) 2365 2607 { 2366 2608 unchanged_size++; 2367 assume (npIsOne(red.coef));2368 assume (p_GetCoeff(red.p,currRing)==coef_debug);2609 assume (npIsOne (red.coef)); 2610 assume (p_GetCoeff (red.p, currRing) == coef_debug); 2369 2611 if (unchanged_head) 2370 2612 { 2371 pNext(unchanged_tail)=red.p;2372 pIter(unchanged_tail);2613 pNext (unchanged_tail) = red.p; 2614 pIter (unchanged_tail); 2373 2615 } 2374 2616 else 2375 2617 { 2376 unchanged_tail=red.p;2377 unchanged_head=red.p;2618 unchanged_tail = red.p; 2619 unchanged_head = red.p; 2378 2620 } 2379 2621 } 2380 2622 else 2381 2623 { 2382 assume (red.len==pLength(red.p));2624 assume (red.len == pLength (red.p)); 2383 2625 if (red.onlyBorrowed) 2384 2626 { 2385 if (npIsOne(red.coef))2386 2387 t=p_Copy(red.p,currRing);2388 2389 2390 t=pp_Mult_nn(red.p,red.coef,currRing);2627 if (npIsOne (red.coef)) 2628 { 2629 t = p_Copy (red.p, currRing); 2630 } 2631 else 2632 t = pp_Mult_nn (red.p, red.coef, currRing); 2391 2633 } 2392 2634 else 2393 2635 { 2394 if (npIsOne(red.coef))2395 t=red.p;2396 2397 t=p_Mult_nn(red.p,red.coef,currRing);2398 } 2399 kBucket_Add_q (bucket,t,&red.len);2400 } 2401 } 2402 poly res =NULL;2403 len =0;2404 kBucket_Add_q (bucket,unchanged_head,&unchanged_size);2405 kBucketClear (bucket,&res,&len);2406 kBucketDestroy (&bucket);2636 if (npIsOne (red.coef)) 2637 t = red.p; 2638 else 2639 t = p_Mult_nn (red.p, red.coef, currRing); 2640 } 2641 kBucket_Add_q (bucket, t, &red.len); 2642 } 2643 } 2644 poly res = NULL; 2645 len = 0; 2646 kBucket_Add_q (bucket, unchanged_head, &unchanged_size); 2647 kBucketClear (bucket, &res, &len); 2648 kBucketDestroy (&bucket); 2407 2649 return res; 2408 2650 } … … 2432 2674 //len input and out: Idea: reverse addition 2433 2675 #ifndef NORO_NON_POLY 2434 std::vector<NoroPlaceHolder> noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c) 2435 { 2436 std::vector<NoroPlaceHolder> res; 2437 while(p) 2438 { 2439 poly t=p; 2440 pIter(p); 2441 pNext(t)=NULL; 2442 2443 MonRedRes red=noro_red_mon(t,TRUE,cache,c); 2444 assume(red.onlyBorrowed); 2445 assume(red.coef); 2446 assume(red.ref); 2447 NoroPlaceHolder h; 2448 h.ref=red.ref; 2449 h.coef=red.coef; 2450 assume(!((h.ref>value_poly==NULL) &&(h.ref>value_len!=0))); 2451 if (h.ref>value_poly) 2452 res.push_back(h); 2453 } 2454 return res; 2676 std::vector < NoroPlaceHolder > noro_red (poly p, int &len, NoroCache * cache, 2677 slimgb_alg * c) 2678 { 2679 std::vector < NoroPlaceHolder > res; 2680 while (p) 2681 { 2682 poly t = p; 2683 pIter (p); 2684 pNext (t) = NULL; 2685 2686 MonRedRes red = noro_red_mon (t, TRUE, cache, c); 2687 assume (red.onlyBorrowed); 2688 assume (red.coef); 2689 assume (red.ref); 2690 NoroPlaceHolder h; 2691 h.ref = red.ref; 2692 h.coef = red.coef; 2693 assume (!((h.ref>value_poly == NULL) && (h.ref>value_len != 0))); 2694 if (h.ref>value_poly) 2695 res.push_back (h); 2696 } 2697 return res; 2455 2698 } 2456 2699 #endif … … 2459 2702 #ifdef USE_NORO 2460 2703 #ifndef NORO_CACHE 2461 void noro_step(poly*p,int &pn,slimgb_alg* c) 2462 { 2463 poly* reduced=(poly*) omalloc(pn*sizeof(poly)); 2704 void 2705 noro_step (poly * p, int &pn, slimgb_alg * c) 2706 { 2707 poly *reduced = (poly *) omalloc (pn * sizeof (poly)); 2464 2708 int j; 2465 int * reduced_len=(int*) omalloc(pn*sizeof(int));2466 int reduced_c =0;2709 int *reduced_len = (int *) omalloc (pn * sizeof (int)); 2710 int reduced_c = 0; 2467 2711 //if (TEST_OPT_PROT) 2468 2712 // PrintS("reduced system:\n"); … … 2470 2714 NoroCache cache; 2471 2715 #endif 2472 for (j=0;j<pn;j++)2473 { 2474 2475 poly h =p[j];2476 int h_len =pLength(h);2716 for (j = 0; j < pn; j++) 2717 { 2718 2719 poly h = p[j]; 2720 int h_len = pLength (h); 2477 2721 2478 2722 number coef; 2479 2723 #ifndef NORO_CACHE 2480 h =redNF2(p_Copy(h,c>r),c,h_len,coef,0);2724 h = redNF2 (p_Copy (h, c>r), c, h_len, coef, 0); 2481 2725 #else 2482 h =noro_red(p_Copy(h,c>r),h_len,&cache,c);2483 assume (pLength(h)==h_len);2484 #endif 2485 if (h !=NULL)2726 h = noro_red (p_Copy (h, c>r), h_len, &cache, c); 2727 assume (pLength (h) == h_len); 2728 #endif 2729 if (h != NULL) 2486 2730 { 2487 2731 #ifndef NORO_CACHE 2488 2732 2489 h =redNFTail(h,c>strat>sl,c>strat,h_len);2490 h_len =pLength(h);2491 #endif 2492 reduced[reduced_c] =h;2493 reduced_len[reduced_c] =h_len;2733 h = redNFTail (h, c>strat>sl, c>strat, h_len); 2734 h_len = pLength (h); 2735 #endif 2736 reduced[reduced_c] = h; 2737 reduced_len[reduced_c] = h_len; 2494 2738 reduced_c++; 2495 2739 if (TEST_OPT_PROT) 2496 Print("%d ",h_len);2497 } 2498 } 2499 int reduced_sum =0;2500 for (j=0;j<reduced_c;j++)2501 { 2502 reduced_sum +=reduced_len[j];2503 } 2504 poly * terms=(poly*) omalloc(reduced_sum*sizeof(poly));2505 int tc =0;2506 for (j=0;j<reduced_c;j++)2507 { 2508 poly h =reduced[j];2509 2510 while (h!=NULL)2511 { 2512 terms[tc++] =h;2513 pIter (h);2514 assume (tc<=reduced_sum);2515 } 2516 } 2517 assume (tc==reduced_sum);2518 qsort (terms,reduced_sum,sizeof(poly),terms_sort_crit);2519 int nterms =reduced_sum;2740 Print ("%d ", h_len); 2741 } 2742 } 2743 int reduced_sum = 0; 2744 for (j = 0; j < reduced_c; j++) 2745 { 2746 reduced_sum += reduced_len[j]; 2747 } 2748 poly *terms = (poly *) omalloc (reduced_sum * sizeof (poly)); 2749 int tc = 0; 2750 for (j = 0; j < reduced_c; j++) 2751 { 2752 poly h = reduced[j]; 2753 2754 while (h != NULL) 2755 { 2756 terms[tc++] = h; 2757 pIter (h); 2758 assume (tc <= reduced_sum); 2759 } 2760 } 2761 assume (tc == reduced_sum); 2762 qsort (terms, reduced_sum, sizeof (poly), terms_sort_crit); 2763 int nterms = reduced_sum; 2520 2764 //if (TEST_OPT_PROT) 2521 2765 //Print("orig estimation:%i\n",reduced_sum); 2522 unify_terms (terms,nterms);2766 unify_terms (terms, nterms); 2523 2767 //if (TEST_OPT_PROT) 2524 2768 // Print("actual number of columns:%i\n",nterms); 2525 int rank =reduced_c;2526 linalg_step_modp (reduced, p,rank,terms,nterms,c);2527 omfree (terms);2528 2529 pn =rank;2530 omfree (reduced);2769 int rank = reduced_c; 2770 linalg_step_modp (reduced, p, rank, terms, nterms, c); 2771 omfree (terms); 2772 2773 pn = rank; 2774 omfree (reduced); 2531 2775 2532 2776 if (TEST_OPT_PROT) 2533 PrintS ("\n");2777 PrintS ("\n"); 2534 2778 } 2535 2779 #else … … 2537 2781 #endif 2538 2782 #endif 2539 static void go_on (slimgb_alg* c) 2783 static void 2784 go_on (slimgb_alg * c) 2540 2785 { 2541 2786 //set limit of 1000 for multireductions, at the moment for 2542 2787 //programming reasons 2543 2788 #ifdef USE_NORO 2544 2789 //Print("module rank%d\n",c>S>rank); 2545 const BOOLEAN use_noro=c>use_noro; 2546 #else 2547 const BOOLEAN use_noro=FALSE; 2548 #endif 2549 int i=0; 2550 c>average_length=0; 2551 for(i=0;i<c>n;i++) 2552 { 2553 c>average_length+=c>lengths[i]; 2554 } 2555 c>average_length=c>average_length/c>n; 2556 i=0; 2557 int max_pairs=bundle_size; 2558 2559 #ifdef USE_NORO 2560 if ((use_noro)(c>use_noro_last_block)) 2561 max_pairs=bundle_size_noro; 2562 #endif 2563 poly* p=(poly*) omalloc((max_pairs+1)*sizeof(poly));//nullterminated 2564 2565 int curr_deg=1; 2566 while(i<max_pairs) 2567 { 2568 sorted_pair_node* s=top_pair(c);//here is actually chain criterium done 2569 2570 if (!s) break; 2571 2572 if(curr_deg>=0) 2573 { 2574 if (s>deg >curr_deg) break; 2575 } 2576 2577 else curr_deg=s>deg; 2578 quick_pop_pair(c); 2579 if(s>i>=0) 2790 const BOOLEAN use_noro = c>use_noro; 2791 #else 2792 const BOOLEAN use_noro = FALSE; 2793 #endif 2794 int i = 0; 2795 c>average_length = 0; 2796 for (i = 0; i < c>n; i++) 2797 { 2798 c>average_length += c>lengths[i]; 2799 } 2800 c>average_length = c>average_length / c>n; 2801 i = 0; 2802 int max_pairs = bundle_size; 2803 2804 #ifdef USE_NORO 2805 if ((use_noro)  (c>use_noro_last_block)) 2806 max_pairs = bundle_size_noro; 2807 #endif 2808 poly *p = (poly *) omalloc ((max_pairs + 1) * sizeof (poly)); //nullterminated 2809 2810 int curr_deg = 1; 2811 while (i < max_pairs) 2812 { 2813 sorted_pair_node *s = top_pair (c); //here is actually chain criterium done 2814 2815 if (!s) 2816 break; 2817 2818 if (curr_deg >= 0) 2819 { 2820 if (s>deg > curr_deg) 2821 break; 2822 } 2823 2824 else 2825 curr_deg = s>deg; 2826 quick_pop_pair (c); 2827 if (s>i >= 0) 2580 2828 { 2581 2829 //be careful replace_pair use createShortSpoly which is not noncommutative 2582 now_t_rep(s>i,s>j,c); 2583 replace_pair(s>i,s>j,c); 2584 2585 if(s>i==s>j) { 2586 free_sorted_pair_node(s,c>r); 2587 continue; 2588 } 2589 now_t_rep(s>i,s>j,c); 2830 now_t_rep (s>i, s>j, c); 2831 replace_pair (s>i, s>j, c); 2832 2833 if (s>i == s>j) 2834 { 2835 free_sorted_pair_node (s, c>r); 2836 continue; 2837 } 2838 now_t_rep (s>i, s>j, c); 2590 2839 } 2591 2840 poly h; 2592 if (s>i>=0)2841 if (s>i >= 0) 2593 2842 { 2594 2843 #ifdef HAVE_PLURAL 2595 2844 if (c>nc) 2596 2845 { 2597 h= nc_CreateSpoly(c>S>m[s>i], c>S>m[s>j]/*, NULL*/, c>r);2598 2599 if (h!=NULL)2600 p_Cleardenom(h, c>r);2846 h = nc_CreateSpoly (c>S>m[s>i], c>S>m[s>j] /*, NULL */ , c>r); 2847 2848 if (h != NULL) 2849 p_Cleardenom (h, c>r); 2601 2850 } 2602 2851 else 2603 2852 #endif 2604 h=ksOldCreateSpoly(c>S>m[s>i], c>S>m[s>j], NULL, c>r);2605 p_Test(h,c>r);2853 h = ksOldCreateSpoly (c>S>m[s>i], c>S>m[s>j], NULL, c>r); 2854 p_Test (h, c>r); 2606 2855 } 2607 2856 else 2608 2857 { 2609 h =s>lcm_of_lm;2610 p_Test (h,c>r);2611 }2858 h = s>lcm_of_lm; 2859 p_Test (h, c>r); 2860 } 2612 2861 // if(s>i>=0) 2613 2862 // now_t_rep(s>j,s>i,c); 2614 2863 number coef; 2615 int mlen=pLength(h); 2616 p_Test(h,c>r); 2617 if ((!c>nc)&(!(use_noro))) 2618 { 2619 h=redNF2(h,c,mlen,coef,2); 2620 redTailShort(h,c>strat); 2621 nDelete(&coef); 2622 } 2623 p_Test(h,c>r); 2624 free_sorted_pair_node(s,c>r); 2625 if(!h) continue; 2626 p[i]=h; 2864 int mlen = pLength (h); 2865 p_Test (h, c>r); 2866 if ((!c>nc) & (!(use_noro))) 2867 { 2868 h = redNF2 (h, c, mlen, coef, 2); 2869 redTailShort (h, c>strat); 2870 nDelete (&coef); 2871 } 2872 p_Test (h, c>r); 2873 free_sorted_pair_node (s, c>r); 2874 if (!h) 2875 continue; 2876 p[i] = h; 2627 2877 i++; 2628 2878 } 2629 p[i] =NULL;2879 p[i] = NULL; 2630 2880 // pre_comp(p,i,c); 2631 if (i==0)2632 { 2633 omfree (p);2881 if (i == 0) 2882 { 2883 omfree (p); 2634 2884 return; 2635 2885 } 2636 2637 c>replaced =new bool[c>n];2638 c>used_b =FALSE;2639 2640 2641 c>normal_forms +=i;2886 #ifdef TGB_RESORT_PAIRS 2887 c>replaced = new bool[c>n]; 2888 c>used_b = FALSE; 2889 #endif 2890 2891 c>normal_forms += i; 2642 2892 int j; 2643 2893 #ifdef USE_NORO … … 2646 2896 if (use_noro) 2647 2897 { 2648 int pn=i; 2649 if (pn==0) {omfree(p);return;} 2650 { 2651 if (npPrimeM<255) 2652 { 2653 noro_step<tgb_uint8>(p,pn,c); 2898 int pn = i; 2899 if (pn == 0) 2900 { 2901 omfree (p); 2902 return; 2903 } 2904 { 2905 if (npPrimeM < 255) 2906 { 2907 noro_step < tgb_uint8 > (p, pn, c); 2654 2908 } 2655 2909 else 2656 2910 { 2657 if (npPrimeM<65000)2658 2659 noro_step<tgb_uint16>(p,pn,c);2660 2661 2662 2663 noro_step<tgb_uint32>(p,pn,c);2664 2911 if (npPrimeM < 65000) 2912 { 2913 noro_step < tgb_uint16 > (p, pn, c); 2914 } 2915 else 2916 { 2917 noro_step < tgb_uint32 > (p, pn, c); 2918 } 2665 2919 } 2666 2920 } … … 2670 2924 // Print("reported rank:%i\n",pn); 2671 2925 //} 2672 mass_add (p,pn,c);2673 omfree (p);2926 mass_add (p, pn, c); 2927 omfree (p); 2674 2928 return; 2675 2929 /*if (TEST_OPT_PROT) 2676 for(j=0;j<pn;j++)2677 {2678 2679 }*/2680 } 2681 #endif 2682 red_object * buf=(red_object*) omalloc(i*sizeof(red_object));2683 for (j=0;j<i;j++)2684 { 2685 p_Test (p[j],c>r);2686 buf[j].p =p[j];2687 buf[j].sev =pGetShortExpVector(p[j]);2688 buf[j].bucket = kBucketCreate (currRing);2689 p_Test (p[j],c>r);2930 for(j=0;j<pn;j++) 2931 { 2932 p_wrp(p[j],c>r); 2933 } */ 2934 } 2935 #endif 2936 red_object *buf = (red_object *) omalloc (i * sizeof (red_object)); 2937 for (j = 0; j < i; j++) 2938 { 2939 p_Test (p[j], c>r); 2940 buf[j].p = p[j]; 2941 buf[j].sev = pGetShortExpVector (p[j]); 2942 buf[j].bucket = kBucketCreate (currRing); 2943 p_Test (p[j], c>r); 2690 2944 if (c>eliminationProblem) 2691 2945 { 2692 buf[j].sugar=c>pTotaldegree_full(p[j]);2693 } 2694 int len =pLength(p[j]);2695 kBucketInit (buf[j].bucket,buf[j].p,len);2696 buf[j].initial_quality =buf[j].guess_quality(c);2697 assume (buf[j].initial_quality>=0);2698 } 2699 omfree (p);2700 qsort (buf,i,sizeof(red_object),red_object_better_gen);2946 buf[j].sugar = c>pTotaldegree_full (p[j]); 2947 } 2948 int len = pLength (p[j]); 2949 kBucketInit (buf[j].bucket, buf[j].p, len); 2950 buf[j].initial_quality = buf[j].guess_quality (c); 2951 assume (buf[j].initial_quality >= 0); 2952 } 2953 omfree (p); 2954 qsort (buf, i, sizeof (red_object), red_object_better_gen); 2701 2955 // Print("\ncurr_deg:%i\n",curr_deg); 2702 2956 if (TEST_OPT_PROT) 2703 2957 { 2704 Print("%dM[%d,",curr_deg,i); 2705 } 2706 2707 multi_reduction(buf, i, c); 2708 #ifdef TGB_RESORT_PAIRS 2709 if (c>used_b) { 2958 Print ("%dM[%d,", curr_deg, i); 2959 } 2960 2961 multi_reduction (buf, i, c); 2962 #ifdef TGB_RESORT_PAIRS 2963 if (c>used_b) 2964 { 2710 2965 if (TEST_OPT_PROT) 2711 PrintS("B");2966 PrintS ("B"); 2712 2967 int e; 2713 for(e=0;e<=c>pair_top;e++) 2714 { 2715 if(c>apairs[e]>i<0) continue; 2716 assume(c>apairs[e]>j>=0); 2717 if ((c>replaced[c>apairs[e]>i])(c>replaced[c>apairs[e]>j])) { 2718 sorted_pair_node* s=c>apairs[e]; 2719 s>expected_length=pair_weighted_length(s>i,s>j,c); 2720 } 2721 } 2722 qsort(c>apairs,c>pair_top+1,sizeof(sorted_pair_node*),tgb_pair_better_gen2); 2723 } 2724 #endif 2968 for (e = 0; e <= c>pair_top; e++) 2969 { 2970 if (c>apairs[e]>i < 0) 2971 continue; 2972 assume (c>apairs[e]>j >= 0); 2973 if ((c>replaced[c>apairs[e]>i])  (c>replaced[c>apairs[e]>j])) 2974 { 2975 sorted_pair_node *s = c>apairs[e]; 2976 s>expected_length = pair_weighted_length (s>i, s>j, c); 2977 } 2978 } 2979 qsort (c>apairs, c>pair_top + 1, sizeof (sorted_pair_node *), 2980 tgb_pair_better_gen2); 2981 } 2982 #endif 2725 2983 #ifdef TGB_DEBUG 2726 { 2727 int k; 2728 for(k=0;k<i;k++) 2729 { 2730 assume(kFindDivisibleByInS_easy(c>strat,buf[k])<0); 2731 int k2; 2732 for(k2=0;k2<i;k2++) 2733 { 2734 if(k==k2) continue; 2735 assume((!(p_LmDivisibleBy(buf[k].p,buf[k2].p,c>r)))(wrp(buf[k].p),Print(" k %d k2 %d ",k,k2),wrp(buf[k2].p),FALSE)); 2736 } 2737 } 2738 } 2984 { 2985 int k; 2986 for (k = 0; k < i; k++) 2987 { 2988 assume (kFindDivisibleByInS_easy (c>strat, buf[k]) < 0); 2989 int k2; 2990 for (k2 = 0; k2 < i; k2++) 2991 { 2992 if (k == k2) 2993 continue; 2994 assume ((!(p_LmDivisibleBy (buf[k].p, buf[k2].p, c>r))) 2995  (wrp (buf[k].p), Print (" k %d k2 %d ", k, k2), 2996 wrp (buf[k2].p), FALSE)); 2997 } 2998 } 2999 } 2739 3000 #endif 2740 3001 //resort S 2741 3002 2742 3003 if (TEST_OPT_PROT) 2743 Print("%i]",i);2744 2745 poly * add_those=(poly*) omalloc(i*sizeof(poly));2746 for (j=0;j<i;j++)3004 Print ("%i]", i); 3005 3006 poly *add_those = (poly *) omalloc (i * sizeof (poly)); 3007 for (j = 0; j < i; j++) 2747 3008 { 2748 3009 int len; 2749 3010 poly p; 2750 buf[j].flatten ();2751 kBucketClear (buf[j].bucket,&p, &len);2752 kBucketDestroy (&buf[j].bucket);2753 p_Test (p,c>r);3011 buf[j].flatten (); 3012 kBucketClear (buf[j].bucket, &p, &len); 3013 kBucketDestroy (&buf[j].bucket); 3014 p_Test (p, c>r); 2754 3015 //if (!c>nc) { 2755 if ((c>tailReductions) (lies_in_last_dp_block(p,c)))2756 2757 p =redNFTail(p,c>strat>sl,c>strat, 0);2758 2759 2760 2761 p =redTailShort(p, c>strat);2762 2763 2764 p_Test(p,c>r);2765 add_those[j]=p;3016 if ((c>tailReductions)  (lies_in_last_dp_block (p, c))) 3017 { 3018 p = redNFTail (p, c>strat>sl, c>strat, 0); 3019 } 3020 else 3021 { 3022 p = redTailShort (p, c>strat); 3023 } 3024 //} 3025 p_Test (p, c>r); 3026 add_those[j] = p; 2766 3027 2767 3028 //sbuf[j]=add_to_basis(p,1,1,c,ibuf+j); 2768 3029 } 2769 mass_add (add_those,i,c);2770 omfree (add_those);2771 omfree (buf);3030 mass_add (add_those, i, c); 3031 omfree (add_those); 3032 omfree (buf); 2772 3033 2773 3034 if (TEST_OPT_PROT) 2774 Print("(%d)",c>pair_top+1);3035 Print ("(%d)", c>pair_top + 1); 2775 3036 //TODO: implement that while(!(idIs0(c>add_later))) 2776 3037 #ifdef TGB_RESORT_PAIRS 2777 3038 delete c>replaced; 2778 c>replaced =NULL;2779 c>used_b =FALSE;2780 3039 c>replaced = NULL; 3040 c>used_b = FALSE; 3041 #endif 2781 3042 return; 2782 3043 } … … 2784 3045 #ifdef REDTAIL_S 2785 3046 2786 static poly redNFTail (poly h,const int sl,kStrategy strat, int len) 2787 { 2788 BOOLEAN nc=rIsPluralRing(currRing); 2789 if (h==NULL) return NULL; 2790 pTest(h); 3047 static poly 3048 redNFTail (poly h, const int sl, kStrategy strat, int len) 3049 { 3050 BOOLEAN nc = rIsPluralRing (currRing); 3051 if (h == NULL) 3052 return NULL; 3053 pTest (h); 2791 3054 if (0 > sl) 2792 3055 return h; 2793 if (pNext(h)==NULL) return h; 3056 if (pNext (h) == NULL) 3057 return h; 2794 3058 2795 3059 int j; 2796 poly res =h;2797 poly act =res;2798 LObject P (pNext(h));2799 pNext (res)=NULL;2800 P.bucket = kBucketCreate (currRing);3060 poly res = h; 3061 poly act = res; 3062 LObject P (pNext (h)); 3063 pNext (res) = NULL; 3064 P.bucket = kBucketCreate (currRing); 2801 3065 len; 2802 h=P.p; 2803 if (len <=0) len=pLength(h); 2804 kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/); 2805 pTest(h); 3066 h = P.p; 3067 if (len <= 0) 3068 len = pLength (h); 3069 kBucketInit (P.bucket, h /*P.p */ , len /*pLength(P.p) */ ); 3070 pTest (h); 2806 3071 loop 2807 3072 { 2808 P.p=h;2809 P.t_p=NULL;2810 P.SetShortExpVector();2811 2812 2813 2814 j=kFindDivisibleByInS_easy(strat,P.p,P.sev);//kFindDivisibleByInS(strat,&dummy,&P);2815 if (j>=0)2816 3073 P.p = h; 3074 P.t_p = NULL; 3075 P.SetShortExpVector (); 3076 loop 3077 { 3078 //int dummy=strat>sl; 3079 j = kFindDivisibleByInS_easy (strat, P.p, P.sev); //kFindDivisibleByInS(strat,&dummy,&P); 3080 if (j >= 0) 3081 { 2817 3082 #ifdef REDTAIL_PROT 2818 PrintS("r");2819 #endif 2820 nNormalize(pGetCoeff(P.p));3083 PrintS ("r"); 3084 #endif 3085 nNormalize (pGetCoeff (P.p)); 2821 3086 #ifdef KDEBUG 2822 2823 2824 PrintS("red tail:");2825 wrp(h);2826 PrintS(" with ");2827 wrp(strat>S[j]);2828 2829 #endif 2830 2831 pTest(strat>S[j]);3087 if (TEST_OPT_DEBUG) 3088 { 3089 PrintS ("red tail:"); 3090 wrp (h); 3091 PrintS (" with "); 3092 wrp (strat>S[j]); 3093 } 3094 #endif 3095 number coef; 3096 pTest (strat>S[j]); 2832 3097 #ifdef HAVE_PLURAL 2833 if (nc) 2834 { 2835 nc_BucketPolyRed_Z(P.bucket, strat>S[j], &coef); 2836 } 2837 else 2838 #endif 2839 coef=kBucketPolyRed(P.bucket,strat>S[j], 2840 strat>lenS[j]/*pLength(strat>S[j])*/,strat>kNoether); 2841 pMult_nn(res,coef); 2842 nDelete(&coef); 2843 h = kBucketGetLm(P.bucket); 2844 pTest(h); 2845 if (h==NULL) 2846 { 3098 if (nc) 3099 { 3100 nc_BucketPolyRed_Z (P.bucket, strat>S[j], &coef); 3101 } 3102 else 3103 #endif 3104 coef = kBucketPolyRed (P.bucket, strat>S[j], 3105 strat>lenS[j] /*pLength(strat>S[j]) */ , 3106 strat>kNoether); 3107 pMult_nn (res, coef); 3108 nDelete (&coef); 3109 h = kBucketGetLm (P.bucket); 3110 pTest (h); 3111 if (h == NULL) 3112 { 2847 3113 #ifdef REDTAIL_PROT 2848 PrintS(" ");2849 #endif 2850 kBucketDestroy(&P.bucket);2851 2852 2853 pTest(h);2854 P.p=h;2855 P.t_p=NULL;2856 P.SetShortExpVector();3114 PrintS (" "); 3115 #endif 3116 kBucketDestroy (&P.bucket); 3117 return res; 3118 } 3119 pTest (h); 3120 P.p = h; 3121 P.t_p = NULL; 3122 P.SetShortExpVector (); 2857 3123 #ifdef KDEBUG 2858 2859 2860 PrintS("\nto tail:");2861 wrp(h);2862 PrintLn();2863 2864 #endif 2865 2866 2867 3124 if (TEST_OPT_DEBUG) 3125 { 3126 PrintS ("\nto tail:"); 3127 wrp (h); 3128 PrintLn (); 3129 } 3130 #endif 3131 } 3132 else 3133 { 2868 3134 #ifdef REDTAIL_PROT 2869 PrintS("n"); 2870 #endif 2871 break; 2872 } 2873 } /* end loop current mon */ 2874 // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/); 2875 //act>next=tmp;pIter(act); 2876 act>next=kBucketExtractLm(P.bucket);pIter(act); 2877 h = kBucketGetLm(P.bucket); 2878 if (h==NULL) 2879 { 3135 PrintS ("n"); 3136 #endif 3137 break; 3138 } 3139 } /* end loop current mon */ 3140 // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/); 3141 //act>next=tmp;pIter(act); 3142 act>next = kBucketExtractLm (P.bucket); 3143 pIter (act); 3144 h = kBucketGetLm (P.bucket); 3145 if (h == NULL) 3146 { 2880 3147 #ifdef REDTAIL_PROT 2881 PrintS(" ");2882 #endif 2883 kBucketDestroy(&P.bucket);2884 2885 2886 pTest(h);3148 PrintS (" "); 3149 #endif 3150 kBucketDestroy (&P.bucket); 3151 return res; 3152 } 3153 pTest (h); 2887 3154 } 2888 3155 } … … 2893 3160 2894 3161 //transfers ownership of m to mat 2895 void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m) 2896 { 2897 assume(mat>mp[row]==NULL); 2898 mat>mp[row]=m; 3162 void 3163 init_with_mac_poly (tgb_sparse_matrix * mat, int row, mac_poly m) 3164 { 3165 assume (mat>mp[row] == NULL); 3166 mat>mp[row] = m; 2899 3167 #ifdef TGB_DEBUG 2900 mac_poly r=m; 2901 while(r) 2902 { 2903 assume(r>exp<mat>columns); 2904 r=r>next; 2905 } 2906 #endif 2907 } 2908 poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index) 2909 { 2910 poly p=NULL; 2911 poly* set_this=&p; 2912 mac_poly r=mat>mp[row]; 2913 mat>mp[row]=NULL; 2914 while(r) 2915 { 2916 (*set_this)=pLmInit(monoms[monom_index1r>exp]); 2917 pSetCoeff((*set_this),r>coef); 2918 set_this=&((*set_this)>next); 2919 mac_poly old=r; 2920 r=r>next; 3168 mac_poly r = m; 3169 while (r) 3170 { 3171 assume (r>exp < mat>columns); 3172 r = r>next; 3173 } 3174 #endif 3175 } 3176 3177 poly 3178 free_row_to_poly (tgb_sparse_matrix * mat, int row, poly * monoms, 3179 int monom_index) 3180 { 3181 poly p = NULL; 3182 poly *set_this = &p; 3183 mac_poly r = mat>mp[row]; 3184 mat>mp[row] = NULL; 3185 while (r) 3186 { 3187 (*set_this) = pLmInit (monoms[monom_index  1  r>exp]); 3188 pSetCoeff ((*set_this), r>coef); 3189 set_this = &((*set_this)>next); 3190 mac_poly old = r; 3191 r = r>next; 2921 3192 delete old; 2922 3193 … … 2925 3196 } 2926 3197 2927 static int poly_crit(const void* ap1, const void* ap2) 2928 { 2929 poly p1,p2; 2930 p1=*((poly*) ap1); 2931 p2=*((poly*)ap2); 2932 2933 int c=pLmCmp(p1,p2); 2934 if (c !=0) return c; 2935 int l1=pLength(p1); 2936 int l2=pLength(p2); 2937 if (l1<l2) return 1; 2938 if (l1>l2) return 1; 3198 static int 3199 poly_crit (const void *ap1, const void *ap2) 3200 { 3201 poly p1, p2; 3202 p1 = *((poly *) ap1); 3203 p2 = *((poly *) ap2); 3204 3205 int c = pLmCmp (p1, p2); 3206 if (c != 0) 3207 return c; 3208 int l1 = pLength (p1); 3209 int l2 = pLength (p2); 3210 if (l1 < l2) 3211 return 1; 3212 if (l1 > l2) 3213 return 1; 2939 3214 return 0; 2940 3215 } 2941 3216 2942 void slimgb_alg::introduceDelayedPairs(poly* pa,int s) 2943 { 2944 if (s==0) return; 2945 sorted_pair_node** si_array=(sorted_pair_node**) omalloc(s* sizeof(sorted_pair_node*)); 2946 2947 for( int i = 0; i < s; i++ ) 2948 { 2949 sorted_pair_node* si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 2950 si>i=1; 2951 si>j=2; 2952 poly p=pa[i]; 2953 simplify_poly(p,r); 2954 si>expected_length=pQuality(p,this,pLength(p)); 2955 p_Test(p,r); 2956 si>deg=this>pTotaldegree_full(p); 2957 /*if (!rField_is_Zp(r)) 3217 void 3218 slimgb_alg::introduceDelayedPairs (poly * pa, int s) 3219 { 3220 if (s == 0) 3221 return; 3222 sorted_pair_node **si_array = 3223 (sorted_pair_node **) omalloc (s * sizeof (sorted_pair_node *)); 3224 3225 for (int i = 0; i < s; i++) 3226 { 3227 sorted_pair_node *si = 3228 (sorted_pair_node *) omalloc (sizeof (sorted_pair_node)); 3229 si>i = 1; 3230 si>j = 2; 3231 poly p = pa[i]; 3232 simplify_poly (p, r); 3233 si>expected_length = pQuality (p, this, pLength (p)); 3234 p_Test (p, r); 3235 si>deg = this>pTotaldegree_full (p); 3236 /*if (!rField_is_Zp(r)) 2958 3237 { 2959 2960 2961 }*/2962 2963 si>lcm_of_lm=p;2964 2965 2966 si_array[i]=si;2967 } 2968 2969 qsort (si_array,s,sizeof(sorted_pair_node*),tgb_pair_better_gen2);2970 apairs=spn_merge(apairs,pair_top+1,si_array,s,this);2971 pair_top +=s;2972 omfree (si_array);2973 } 2974 2975 slimgb_alg::slimgb_alg (ideal I, int syz_comp,BOOLEAN F4,int deg_pos)2976 { 2977 this>deg_pos =deg_pos;2978 lastCleanedDeg =1;2979 completed =FALSE;2980 this>syz_comp =syz_comp;2981 r =currRing;2982 nc =rIsPluralRing(r);2983 this>lastDpBlockStart =get_last_dp_block_start(r);3238 p_Content(p,r); 3239 p_Cleardenom(p,r); 3240 } */ 3241 3242 si>lcm_of_lm = p; 3243 3244 // c>apairs[n1i]=si; 3245 si_array[i] = si; 3246 } 3247 3248 qsort (si_array, s, sizeof (sorted_pair_node *), tgb_pair_better_gen2); 3249 apairs = spn_merge (apairs, pair_top + 1, si_array, s, this); 3250 pair_top += s; 3251 omfree (si_array); 3252 } 3253 3254 slimgb_alg::slimgb_alg (ideal I, int syz_comp, BOOLEAN F4, int deg_pos) 3255 { 3256 this>deg_pos = deg_pos; 3257 lastCleanedDeg = 1; 3258 completed = FALSE; 3259 this>syz_comp = syz_comp; 3260 r = currRing; 3261 nc = rIsPluralRing (r); 3262 this>lastDpBlockStart = get_last_dp_block_start (r); 2984 3263 //Print("last dp Block start: %i\n", this>lastDpBlockStart); 2985 is_homog =TRUE;3264 is_homog = TRUE; 2986 3265 { 2987 3266 int hzz; 2988 for(hzz=0;hzz<IDELEMS(I);hzz++) 2989 { 2990 assume(I>m[hzz]!=NULL); 2991 int d=this>pTotaldegree(I>m[hzz]); 2992 poly t=I>m[hzz]>next; 2993 while(t) 2994 { 2995 if (d!=this>pTotaldegree(t)) 2996 { 2997 is_homog=FALSE; 2998 break; 2999 } 3000 t=t>next; 3001 } 3002 if(!(is_homog)) break; 3003 } 3004 } 3005 eliminationProblem=((!(is_homog))&&((pLexOrder)(I>rank>1))); 3006 tailReductions=((is_homog)((TEST_OPT_REDTAIL)&&(!(I>rank>1)))); 3267 for (hzz = 0; hzz < IDELEMS (I); hzz++) 3268 { 3269 assume (I>m[hzz] != NULL); 3270 int d = this>pTotaldegree (I>m[hzz]); 3271 poly t = I>m[hzz]>next; 3272 while (t) 3273 { 3274 if (d != this>pTotaldegree (t)) 3275 { 3276 is_homog = FALSE; 3277 break; 3278 } 3279 t = t>next; 3280 } 3281 if (!(is_homog)) 3282 break; 3283 } 3284 } 3285 eliminationProblem = ((!(is_homog)) && ((pLexOrder)  (I>rank > 1))); 3286 tailReductions = ((is_homog)  ((TEST_OPT_REDTAIL) && (!(I>rank > 1)))); 3007 3287 // Print("is homog:%d",c>is_homog); 3008 void *h;3288 void *h; 3009 3289 int i; 3010 to_destroy =NULL;3011 easy_product_crit =0;3012 extended_product_crit =0;3013 if (rField_is_Zp (r))3014 isDifficultField =FALSE;3290 to_destroy = NULL; 3291 easy_product_crit = 0; 3292 extended_product_crit = 0; 3293 if (rField_is_Zp (r)) 3294 isDifficultField = FALSE; 3015 3295 else 3016 isDifficultField =TRUE;3296 isDifficultField = TRUE; 3017 3297 //not fully correct 3018 3298 //(rChar()==0); 3019 F4_mode=F4; 3020 3021 reduction_steps=0; 3022 last_index=1; 3023 3024 F=NULL; 3025 F_minus=NULL; 3026 3027 Rcounter=0; 3028 3029 soon_free=NULL; 3030 3031 tmp_lm=pOne(); 3032 3033 normal_forms=0; 3034 current_degree=1; 3035 3036 max_pairs=5*IDELEMS(I); 3037 3038 apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*max_pairs); 3039 pair_top=1; 3040 3041 int n=IDELEMS(I); 3042 array_lengths=n; 3043 3044 3045 i=0; 3046 this>n=0; 3047 T_deg=(int*) omalloc(n*sizeof(int)); 3048 if(eliminationProblem) 3049 T_deg_full=(int*) omalloc(n*sizeof(int)); 3299 F4_mode = F4; 3300 3301 reduction_steps = 0; 3302 last_index = 1; 3303 3304 F = NULL; 3305 F_minus = NULL; 3306 3307 Rcounter = 0; 3308 3309 soon_free = NULL; 3310 3311 tmp_lm = pOne (); 3312 3313 normal_forms = 0; 3314 current_degree = 1; 3315 3316 max_pairs = 5 * IDELEMS (I); 3317 3318 apairs = 3319 (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * max_pairs); 3320 pair_top = 1; 3321 3322 int n = IDELEMS (I); 3323 array_lengths = n; 3324 3325 3326 i = 0; 3327 this>n = 0; 3328 T_deg = (int *) omalloc (n * sizeof (int)); 3329 if (eliminationProblem) 3330 T_deg_full = (int *) omalloc (n * sizeof (int)); 3050 3331 else 3051 T_deg_full =NULL;3052 tmp_pair_lm =(poly*) omalloc(n*sizeof(poly));3053 tmp_spn =(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*));3054 lm_bin =omGetSpecBin(POLYSIZE + (r>ExpL_Size)*sizeof(long));3332 T_deg_full = NULL; 3333 tmp_pair_lm = (poly *) omalloc (n * sizeof (poly)); 3334 tmp_spn = (sorted_pair_node **) omalloc (n * sizeof (sorted_pair_node *)); 3335 lm_bin = omGetSpecBin (POLYSIZE + (r>ExpL_Size) * sizeof (long)); 3055 3336 #ifdef HEAD_BIN 3056 HeadBin =omGetSpecBin(POLYSIZE + (currRing>ExpL_Size)*sizeof(long));3337 HeadBin = omGetSpecBin (POLYSIZE + (currRing>ExpL_Size) * sizeof (long)); 3057 3338 #endif 3058 3339 /* omUnGetSpecBin(&(c>HeadBin)); */ 3059 3060 3061 3062 h =omalloc(n*sizeof(char*));3063 3064 states =(char**) h;3065 3066 3067 h =omalloc(n*sizeof(int));3068 lengths =(int*) h;3069 weighted_lengths =(wlen_type*)omalloc(n*sizeof(wlen_type));3070 gcd_of_terms =(poly*) omalloc(n*sizeof(poly));3071 3072 short_Exps =(long*) omalloc(n*sizeof(long));3340 #ifndef HAVE_BOOST 3341 #ifdef USE_STDVECBOOL 3342 #else 3343 h = omalloc (n * sizeof (char *)); 3344 3345 states = (char **) h; 3346 #endif 3347 #endif 3348 h = omalloc (n * sizeof (int)); 3349 lengths = (int *) h; 3350 weighted_lengths = (wlen_type *) omalloc (n * sizeof (wlen_type)); 3351 gcd_of_terms = (poly *) omalloc (n * sizeof (poly)); 3352 3353 short_Exps = (long *) omalloc (n * sizeof (long)); 3073 3354 if (F4_mode) 3074 S =idInit(n,I>rank);3355 S = idInit (n, I>rank); 3075 3356 else 3076 S =idInit(1,I>rank);3077 strat =new skStrategy;3357 S = idInit (1, I>rank); 3358 strat = new skStrategy; 3078 3359 if (eliminationProblem) 3079 strat>honey =TRUE;3360 strat>honey = TRUE; 3080 3361 strat>syzComp = 0; 3081 initBuchMoraCrit (strat);3082 initBuchMoraPos (strat);3362 initBuchMoraCrit (strat); 3363 initBuchMoraPos (strat); 3083 3364 strat>initEcart = initEcartBBA; 3084 strat>tailRing =r;3365 strat>tailRing = r; 3085 3366 strat>enterS = enterSBba; 3086 3367 strat>sl = 1; 3087 i =n;3088 i =1;//some strange bug else3368 i = n; 3369 i = 1; //some strange bug else 3089 3370 /* initS(c>S,NULL,c>strat); */ 3090 3371 /* intS start: */ 3091 3372 // i=((i+IDELEMS(c>S)+15)/16)*16; 3092 strat>ecartS =(intset)omAlloc(i*sizeof(int)); /*initec(i);*/3093 strat>sevS =(unsigned long*)omAlloc0(i*sizeof(unsigned long));3094 /*initsevS(i); */3095 strat>S_2_R =(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/3096 strat>fromQ =NULL;3097 strat>Shdl =idInit(1,1);3098 strat>S =strat>Shdl>m;3099 strat>lenS =(int*)omAlloc0(i*sizeof(int));3100 if ((isDifficultField)(eliminationProblem))3101 strat>lenSw =(wlen_type*)omAlloc0(i*sizeof(wlen_type));3373 strat>ecartS = (intset) omAlloc (i * sizeof (int)); /*initec(i); */ 3374 strat>sevS = (unsigned long *) omAlloc0 (i * sizeof (unsigned long)); 3375 /*initsevS(i); */ 3376 strat>S_2_R = (int *) omAlloc0 (i * sizeof (int)); /*initS_2_R(i); */ 3377 strat>fromQ = NULL; 3378 strat>Shdl = idInit (1, 1); 3379 strat>S = strat>Shdl>m; 3380 strat>lenS = (int *) omAlloc0 (i * sizeof (int)); 3381 if ((isDifficultField)  (eliminationProblem)) 3382 strat>lenSw = (wlen_type *) omAlloc0 (i * sizeof (wlen_type)); 3102 3383 else 3103 strat>lenSw =NULL;3104 assume (n>0);3105 add_to_basis_ideal_quotient (I>m[0],this,NULL);3106 3107 assume (strat>sl==IDELEMS(strat>Shdl)1);3108 if (!(F4_mode))3109 { 3110 poly* array_arg=I>m;3111 3112 introduceDelayedPairs(array_arg,n1);3113 3114 for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis3115 {3116 // add_to_basis(I>m[i],1,1,c);3117 si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));3118 si>i=1;3119 si>j=2;3120 si>expected_length=pQuality(I>m[i],this,pLength(I>m[i]));3121 si>deg=pTotaldegree(I>m[i]);3122 if (!rField_is_Zp(r))3123 {3124 3125 }3126 si>lcm_of_lm=I>m[i];3127 3128 // c>apairs[n1i]=si;3129 apairs[ni1]=si;3130 ++(pair_top);3131 }*/3384 strat>lenSw = NULL; 3385 assume (n > 0); 3386 add_to_basis_ideal_quotient (I>m[0], this, NULL); 3387 3388 assume (strat>sl == IDELEMS (strat>Shdl)  1); 3389 if (!(F4_mode)) 3390 { 3391 poly *array_arg = I>m; 3392 array_arg++; 3393 introduceDelayedPairs (array_arg, n  1); 3394 /* 3395 for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis 3396 { 3397 // add_to_basis(I>m[i],1,1,c); 3398 si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); 3399 si>i=1; 3400 si>j=2; 3401 si>expected_length=pQuality(I>m[i],this,pLength(I>m[i])); 3402 si>deg=pTotaldegree(I>m[i]); 3403 if (!rField_is_Zp(r)) 3404 { 3405 p_Cleardenom(I>m[i], r); 3406 } 3407 si>lcm_of_lm=I>m[i]; 3408 3409 // c>apairs[n1i]=si; 3410 apairs[ni1]=si; 3411 ++(pair_top); 3412 } */ 3132 3413 } 3133 3414 else 3134 3415 { 3135 for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis 3136 add_to_basis_ideal_quotient(I>m[i],this,NULL); 3137 } 3138 for(i=0;i<IDELEMS(I);i++) 3139 { 3140 I>m[i]=NULL; 3141 } 3142 idDelete(&I); 3143 add_later=idInit(ADD_LATER_SIZE,S>rank); 3144 #ifdef USE_NORO 3145 use_noro=((!(nc))&&(S>rank<=1)&&(rField_is_Zp(r)) &&(!(eliminationProblem))&&(npPrimeM<=32003)); 3146 use_noro_last_block=false; 3147 if ((!(use_noro))&&(lastDpBlockStart<=pVariables)) 3148 { 3149 use_noro_last_block=((!(nc))&&(S>rank<=1)&&(rField_is_Zp(r)) &&(npPrimeM<=32003)); 3150 } 3151 #else 3152 use_noro=false; 3153 use_noro_last_block=false; 3154 #endif 3416 for (i = 1; i < n; i++) //the 1 is wanted, because first element is added to basis 3417 add_to_basis_ideal_quotient (I>m[i], this, NULL); 3418 } 3419 for (i = 0; i < IDELEMS (I); i++) 3420 { 3421 I>m[i] = NULL; 3422 } 3423 idDelete (&I); 3424 add_later = idInit (ADD_LATER_SIZE, S>rank); 3425 #ifdef USE_NORO 3426 use_noro = ((!(nc)) && (S>rank <= 1) && (rField_is_Zp (r)) 3427 && (!(eliminationProblem)) && (npPrimeM <= 32003)); 3428 use_noro_last_block = false; 3429 if ((!(use_noro)) && (lastDpBlockStart <= pVariables)) 3430 { 3431 use_noro_last_block = ((!(nc)) && (S>rank <= 1) && (rField_is_Zp (r)) 3432 && (npPrimeM <= 32003)); 3433 } 3434 #else 3435 use_noro = false; 3436 use_noro_last_block = false; 3437 #endif 3155 3438 //Print("NORO last block %i",use_noro_last_block); 3156 memset(add_later>m,0,ADD_LATER_SIZE*sizeof(poly)); 3157 } 3158 slimgb_alg::~slimgb_alg() 3439 memset (add_later>m, 0, ADD_LATER_SIZE * sizeof (poly)); 3440 } 3441 3442 slimgb_alg::~slimgb_alg () 3159 3443 { 3160 3444 3161 3445 if (!(completed)) 3162 3446 { 3163 poly* add=(poly*) omalloc((pair_top+2)*sizeof(poly));3164 3165 int pos=0;3166 for(piter=0;piter<=pair_top;piter++)3167 3168 sorted_pair_node* s=apairs[piter];3169 if (s>i<0)3170 3171 3172 if (s>lcm_of_lm!=NULL)3173 3174 add[pos]=s>lcm_of_lm;3175 3176 3177 3178 free_sorted_pair_node(s,r);3179 apairs[piter]=NULL;3180 3181 pair_top=1;3182 add[pos]=NULL;3183 pos=0;3184 while(add[pos]!=NULL)3185 3186 add_to_basis_ideal_quotient(add[pos],this,NULL);3187 3188 3189 for(piter=0;piter<=pair_top;piter++)3190 3191 sorted_pair_node* s=apairs[piter];3192 assume(s>i>=0);3193 free_sorted_pair_node(s,r);3194 apairs[piter]=NULL;3195 3196 pair_top=1;3197 } 3198 id_Delete (&add_later,r);3199 int i, j;3200 slimgb_alg * c=this;3201 while (c>to_destroy)3202 { 3203 pDelete (&(c>to_destroy>p));3204 poly_list_node * old=c>to_destroy;3205 c>to_destroy =c>to_destroy>next;3206 omfree (old);3207 } 3208 while (c>F)3209 { 3210 for (i=0;i<c>F>size;i++)3211 { 3212 pDelete (&(c>F>mp[i].m));3213 } 3214 omfree (c>F>mp);3215 c>F>mp =NULL;3216 mp_array_list * old=c>F;3217 c>F =c>F>next;3218 omfree (old);3219 } 3220 while (c>F_minus)3221 { 3222 for (i=0;i<c>F_minus>size;i++)3223 { 3224 pDelete (&(c>F_minus>p[i]));3225 } 3226 omfree (c>F_minus>p);3227 c>F_minus>p =NULL;3228 poly_array_list * old=c>F_minus;3229 c>F_minus =c>F_minus>next;3230 omfree (old);3231 } 3232 3233 3234 for (int z=1 /* zero length at 0 */;z<c>n;z++)3235 { 3236 omfree (c>states[z]);3237 } 3238 omfree (c>states);3239 3240 3241 3242 omfree (c>lengths);3243 omfree (c>weighted_lengths);3244 for (int z=0;z<c>n;z++)3245 { 3246 pDelete (&c>tmp_pair_lm[z]);3247 omfree (c>tmp_spn[z]);3248 } 3249 omfree (c>tmp_pair_lm);3250 omfree (c>tmp_spn);3251 3252 omfree (c>T_deg);3253 if (c>T_deg_full)3254 omfree (c>T_deg_full);3255 3256 omFree (c>strat>ecartS);3257 omFree (c>strat>sevS);3447 poly *add = (poly *) omalloc ((pair_top + 2) * sizeof (poly)); 3448 int piter; 3449 int pos = 0; 3450 for (piter = 0; piter <= pair_top; piter++) 3451 { 3452 sorted_pair_node *s = apairs[piter]; 3453 if (s>i < 0) 3454 { 3455 //delayed element 3456 if (s>lcm_of_lm != NULL) 3457 { 3458 add[pos] = s>lcm_of_lm; 3459 pos++; 3460 } 3461 } 3462 free_sorted_pair_node (s, r); 3463 apairs[piter] = NULL; 3464 } 3465 pair_top = 1; 3466 add[pos] = NULL; 3467 pos = 0; 3468 while (add[pos] != NULL) 3469 { 3470 add_to_basis_ideal_quotient (add[pos], this, NULL); 3471 pos++; 3472 } 3473 for (piter = 0; piter <= pair_top; piter++) 3474 { 3475 sorted_pair_node *s = apairs[piter]; 3476 assume (s>i >= 0); 3477 free_sorted_pair_node (s, r); 3478 apairs[piter] = NULL; 3479 } 3480 pair_top = 1; 3481 } 3482 id_Delete (&add_later, r); 3483 int i, j; 3484 slimgb_alg *c = this; 3485 while (c>to_destroy) 3486 { 3487 pDelete (&(c>to_destroy>p)); 3488 poly_list_node *old = c>to_destroy; 3489 c>to_destroy = c>to_destroy>next; 3490 omfree (old); 3491 } 3492 while (c>F) 3493 { 3494 for (i = 0; i < c>F>size; i++) 3495 { 3496 pDelete (&(c>F>mp[i].m)); 3497 } 3498 omfree (c>F>mp); 3499 c>F>mp = NULL; 3500 mp_array_list *old = c>F; 3501 c>F = c>F>next; 3502 omfree (old); 3503 } 3504 while (c>F_minus) 3505 { 3506 for (i = 0; i < c>F_minus>size; i++) 3507 { 3508 pDelete (&(c>F_minus>p[i])); 3509 } 3510 omfree (c>F_minus>p); 3511 c>F_minus>p = NULL; 3512 poly_array_list *old = c>F_minus; 3513 c>F_minus = c>F_minus>next; 3514 omfree (old); 3515 } 3516 #ifndef HAVE_BOOST 3517 #ifndef USE_STDVECBOOL 3518 for (int z = 1 /* zero length at 0 */ ; z < c>n; z++) 3519 { 3520 omfree (c>states[z]); 3521 } 3522 omfree (c>states); 3523 #endif 3524 #endif 3525 3526 omfree (c>lengths); 3527 omfree (c>weighted_lengths); 3528 for (int z = 0; z < c>n; z++) 3529 { 3530 pDelete (&c>tmp_pair_lm[z]); 3531 omfree (c>tmp_spn[z]); 3532 } 3533 omfree (c>tmp_pair_lm); 3534 omfree (c>tmp_spn); 3535 3536 omfree (c>T_deg); 3537 if (c>T_deg_full) 3538 omfree (c>T_deg_full); 3539 3540 omFree (c>strat>ecartS); 3541 omFree (c>strat>sevS); 3258 3542 // initsevS(i); 3259 omFree(c>strat>S_2_R); 3260 3261 3262 omFree(c>strat>lenS); 3263 3264 if(c>strat>lenSw) omFree(c>strat>lenSw); 3265 3266 for(i=0;i<c>n;i++) 3267 { 3268 if(c>gcd_of_terms[i]) 3269 pDelete(&(c>gcd_of_terms[i])); 3270 } 3271 omfree(c>gcd_of_terms); 3272 3273 omfree(c>apairs); 3543 omFree (c>strat>S_2_R); 3544 3545 3546 omFree (c>strat>lenS); 3547 3548 if (c>strat>lenSw) 3549 omFree (c>strat>lenSw); 3550 3551 for (i = 0; i < c>n; i++) 3552 { 3553 if (c>gcd_of_terms[i]) 3554 pDelete (&(c>gcd_of_terms[i])); 3555 } 3556 omfree (c>gcd_of_terms); 3557 3558 omfree (c>apairs); 3274 3559 if (TEST_OPT_PROT) 3275 3560 { 3276 3561 //Print("calculated %d NFs\n",c>normal_forms); 3277 Print("\nNF:%i product criterion:%i, ext_product criterion:%i \n", c>normal_forms, c>easy_product_crit, c>extended_product_crit); 3278 } 3279 3280 for(i=0;i<=c>strat>sl;i++) 3281 { 3282 if (!c>strat>S[i]) continue; 3283 BOOLEAN found=FALSE; 3284 for(j=0;j<c>n;j++) 3285 { 3286 if (c>S>m[j]==c>strat>S[i]) 3287 { 3288 found=TRUE; 3289 break; 3290 } 3291 } 3292 if(!found) pDelete(&c>strat>S[i]); 3562 Print ("\nNF:%i product criterion:%i, ext_product criterion:%i \n", 3563 c>normal_forms, c>easy_product_crit, c>extended_product_crit); 3564 } 3565 3566 for (i = 0; i <= c>strat>sl; i++) 3567 { 3568 if (!c>strat>S[i]) 3569 continue; 3570 BOOLEAN found = FALSE; 3571 for (j = 0; j < c>n; j++) 3572 { 3573 if (c>S>m[j] == c>strat>S[i]) 3574 { 3575 found = TRUE; 3576 break; 3577 } 3578 } 3579 if (!found) 3580 pDelete (&c>strat>S[i]); 3293 3581 } 3294 3582 // for(i=0;i<c>n;i++) … … 3311 3599 if (completed) 3312 3600 { 3313 for(i=0;i<c>n;i++)3314 {3315 assume(c>S>m[i]!=NULL);3316 if (p_GetComp(c>S>m[i],currRing)>this>syz_comp) continue;3317 for(j=0;j<c>n;j++) 3318 {3319 if((c>S>m[j]==NULL)(i==j))3320 continue; 3321 assume(p_LmShortDivisibleBy(c>S>m[j],c>short_Exps[j], 3322 c>S>m[i],~c>short_Exps[i],3323 c>r)==p_LmDivisibleBy(c>S>m[j],3324 c>S>m[i],3325 c>r)); 3326 if (p_LmShortDivisibleBy(c>S>m[j],c>short_Exps[j], 3327 c>S>m[i],~c>short_Exps[i],3328 3329 3330 pDelete(&c>S>m[i]);3331 3332 3333 }3334 }3335 } 3336 omfree (c>short_Exps);3337 3338 ideal I =c>S;3339 IDELEMS (I)=c>n;3340 idSkipZeroes (I);3341 for (i=0;i<=c>strat>sl;i++)3342 c>strat>S[i] =NULL;3343 id_Delete (&c>strat>Shdl,c>r);3344 pDelete (&c>tmp_lm);3345 omUnGetSpecBin (&lm_bin);3601 for (i = 0; i < c>n; i++) 3602 { 3603 assume (c>S>m[i] != NULL); 3604 if (p_GetComp (c>S>m[i], currRing) > this>syz_comp) 3605 continue; 3606 for (j = 0; j < c>n; j++) 3607 { 3608 if ((c>S>m[j] == NULL)  (i == j)) 3609 continue; 3610 assume (p_LmShortDivisibleBy (c>S>m[j], c>short_Exps[j], 3611 c>S>m[i], ~c>short_Exps[i], 3612 c>r) == p_LmDivisibleBy (c>S>m[j], 3613 c>S>m[i], 3614 c>r)); 3615 if (p_LmShortDivisibleBy (c>S>m[j], c>short_Exps[j], 3616 c>S>m[i], ~c>short_Exps[i], c>r)) 3617 { 3618 pDelete (&c>S>m[i]); 3619 break; 3620 } 3621 } 3622 } 3623 } 3624 omfree (c>short_Exps); 3625 3626 ideal I = c>S; 3627 IDELEMS (I) = c>n; 3628 idSkipZeroes (I); 3629 for (i = 0; i <= c>strat>sl; i++) 3630 c>strat>S[i] = NULL; 3631 id_Delete (&c>strat>Shdl, c>r); 3632 pDelete (&c>tmp_lm); 3633 omUnGetSpecBin (&lm_bin); 3346 3634 delete c>strat; 3347 3635 } 3348 ideal t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode) 3349 { 3350 assume(r==currRing); 3351 ring orig_ring=r; 3352 int pos; 3353 ring new_ring=rAssure_TDeg(orig_ring,1,rVar(orig_ring),pos); 3354 ideal s_h; 3355 if (orig_ring != new_ring) 3356 { 3357 rChangeCurrRing(new_ring); 3358 s_h=idrCopyR_NoSort(arg_I,orig_ring); 3359 idTest(s_h); 3360 /*int i; 3361 for(i=0;i<IDELEMS(s_h);i++) 3362 { 3363 poly p=s_h>m[i]; 3364 while(p) 3365 { 3366 p_Setm(p,new_ring); 3367 pIter(p); 3368 } 3369 }*/ 3370 } 3371 else 3372 { 3373 s_h = id_Copy(arg_I,orig_ring); 3374 } 3375 3376 ideal s_result=do_t_rep_gb(new_ring,s_h,syz_comp,F4_mode,pos); 3377 ideal result; 3378 if(orig_ring != new_ring) 3379 { 3380 idTest(s_result); 3381 rChangeCurrRing(orig_ring); 3382 result = idrMoveR_NoSort(s_result, new_ring); 3383 3384 idTest(result); 3385 //rChangeCurrRing(new_ring); 3386 rKill(new_ring); 3387 //rChangeCurrRing(orig_ring); 3388 } 3389 else 3390 result=s_result; 3391 idTest(result); 3392 return result; 3393 } 3394 3395 ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos) 3636 3637 ideal 3638 t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode) 3639 { 3640 assume (r == currRing); 3641 ring orig_ring = r; 3642 int pos; 3643 ring new_ring = rAssure_TDeg (orig_ring, 1, rVar (orig_ring), pos); 3644 ideal s_h; 3645 if (orig_ring != new_ring) 3646 { 3647 rChangeCurrRing (new_ring); 3648 s_h = idrCopyR_NoSort (arg_I, orig_ring); 3649 idTest (s_h); 3650 /*int i; 3651 for(i=0;i<IDELEMS(s_h);i++) 3652 { 3653 poly p=s_h>m[i]; 3654 while(p) 3655 { 3656 p_Setm(p,new_ring); 3657 pIter(p); 3658 } 3659 } */ 3660 } 3661 else 3662 { 3663 s_h = id_Copy (arg_I, orig_ring); 3664 } 3665 3666 ideal s_result = do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos); 3667 ideal result; 3668 if (orig_ring != new_ring) 3669 { 3670 idTest (s_result); 3671 rChangeCurrRing (orig_ring); 3672 result = idrMoveR_NoSort (s_result, new_ring); 3673 3674 idTest (result); 3675 //rChangeCurrRing(new_ring); 3676 rKill (new_ring); 3677 //rChangeCurrRing(orig_ring); 3678 } 3679 else 3680 result = s_result; 3681 idTest (result); 3682 return result; 3683 } 3684 3685 ideal 3686 do_t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos) 3396 3687 { 3397 3688 // Print("QlogSize(0) %d, QlogSize(1) %d,QlogSize(2) %d, QlogSize(5) %d\n", QlogSize(nlInit(0)),QlogSize(nlInit(1)),QlogSize(nlInit(2)),QlogSize(nlInit(5))); … … 3399 3690 if (TEST_OPT_PROT) 3400 3691 if (F4_mode) 3401 PrintS ("F4 Modus \n");3692 PrintS ("F4 Modus \n"); 3402 3693 3403 3694 //debug_Ideal=arg_debug_Ideal; 3404 3695 //if (debug_Ideal) PrintS("DebugIdeal received\n"); 3405 3696 // Print("Idelems %i \n\n",IDELEMS(arg_I)); 3406 ideal I=arg_I; 3407 idCompactify(I); 3408 if (idIs0(I)) return I; 3697 ideal I = arg_I; 3698 idCompactify (I); 3699 if (idIs0 (I)) 3700 return I; 3409 3701 int i; 3410 for (i=0;i<IDELEMS(I);i++)3411 { 3412 assume (I>m[i]!=NULL);3413 simplify_poly (I>m[i],currRing);3414 } 3415 3416 qsort (I>m,IDELEMS(I),sizeof(poly),poly_crit);3702 for (i = 0; i < IDELEMS (I); i++) 3703 { 3704 assume (I>m[i] != NULL); 3705 simplify_poly (I>m[i], currRing); 3706 } 3707 3708 qsort (I>m, IDELEMS (I), sizeof (poly), poly_crit); 3417 3709 //Print("Idelems %i \n\n",IDELEMS(I)); 3418 3710 //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg)); 3419 3711 //int syz_comp=arg_I>rank; 3420 slimgb_alg* c=new slimgb_alg(I, syz_comp,F4_mode,deg_pos); 3421 3422 while ((c>pair_top>=0) && ((!(TEST_OPT_DEGBOUND))  (c>apairs[c>pair_top]>deg<=Kstd1_deg))) 3423 { 3424 #ifdef HAVE_F4 3425 if(F4_mode) 3426 go_on_F4(c); 3712 slimgb_alg *c = new slimgb_alg (I, syz_comp, F4_mode, deg_pos); 3713 3714 while ((c>pair_top >= 0) 3715 && ((!(TEST_OPT_DEGBOUND)) 3716  (c>apairs[c>pair_top]>deg <= Kstd1_deg))) 3717 { 3718 #ifdef HAVE_F4 3719 if (F4_mode) 3720 go_on_F4 (c); 3427 3721 else 3428 3429 go_on (c);3430 } 3431 if (c>pair_top <0)3432 c>completed =TRUE;3433 I =c>S;3722 #endif 3723 go_on (c); 3724 } 3725 if (c>pair_top < 0) 3726 c>completed = TRUE; 3727 I = c>S; 3434 3728 delete c; 3435 3729 if (TEST_OPT_REDSB) 3436 3730 { 3437 ideal erg =kInterRed(I,NULL);3438 assume (I!=erg);3439 id_Delete (&I, currRing);3731 ideal erg = kInterRed (I, NULL); 3732 assume (I != erg); 3733 id_Delete (&I, currRing); 3440 3734 return erg; 3441 3735 } 3442 3736 //qsort(I>m, IDELEMS(I),sizeof(poly),pLmCmp_func); 3443 assume(I>rank>=idRankFreeModule(I)); 3444 return(I); 3445 } 3446 3447 void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c) 3448 { 3449 int i,j; 3450 if (arg_i==arg_j) 3737 assume (I>rank >= idRankFreeModule (I)); 3738 return (I); 3739 } 3740 3741 void 3742 now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * c) 3743 { 3744 int i, j; 3745 if (arg_i == arg_j) 3451 3746 { 3452 3747 return; 3453 3748 } 3454 if (arg_i >arg_j)3455 { 3456 i =arg_j;3457 j =arg_i;3749 if (arg_i > arg_j) 3750 { 3751 i = arg_j; 3752 j = arg_i; 3458 3753 } 3459 3754 else 3460 3755 { 3461 i=arg_i; 3462 j=arg_j; 3463 } 3464 c>states[j][i]=HASTREP; 3465 } 3466 3467 static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state) 3468 { 3469 assume(0<=arg_i); 3470 assume(0<=arg_j); 3471 assume(arg_i<state>n); 3472 assume(arg_j<state>n); 3473 if (arg_i==arg_j) 3756 i = arg_i; 3757 j = arg_j; 3758 } 3759 c>states[j][i] = HASTREP; 3760 } 3761 3762 static BOOLEAN 3763 has_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * state) 3764 { 3765 assume (0 <= arg_i); 3766 assume (0 <= arg_j); 3767 assume (arg_i < state>n); 3768 assume (arg_j < state>n); 3769 if (arg_i == arg_j) 3474 3770 { 3475 3771 return (TRUE); 3476 3772 } 3477 if (arg_i >arg_j)3478 { 3479 return (state>states[arg_i][arg_j] ==HASTREP);3773 if (arg_i > arg_j) 3774 { 3775 return (state>states[arg_i][arg_j] == HASTREP); 3480 3776 } 3481 3777 else 3482 3778 { 3483 return (state>states[arg_j][arg_i]==HASTREP); 3484 } 3485 } 3486 3487 #if 0 // unused 3488 static int pLcmDeg(poly a, poly b) 3779 return (state>states[arg_j][arg_i] == HASTREP); 3780 } 3781 } 3782 3783 #if 0 // unused 3784 static int 3785 pLcmDeg (poly a, poly b) 3489 3786 { 3490 3787 int i; 3491 int n =0;3492 for (i =pVariables; i; i)3493 { 3494 n +=si_max( pGetExp(a,i), pGetExp(b,i));3788 int n = 0; 3789 for (i = pVariables; i; i) 3790 { 3791 n += si_max (pGetExp (a, i), pGetExp (b, i)); 3495 3792 } 3496 3793 return n; … … 3498 3795 #endif 3499 3796 3500 static void shorten_tails(slimgb_alg* c, poly monom) 3797 static void 3798 shorten_tails (slimgb_alg * c, poly monom) 3501 3799 { 3502 3800 return; 3503 3801 // BOOLEAN corr=lenS_correct(c>strat); 3504 for (int i=0;i<c>n;i++)3802 for (int i = 0; i < c>n; i++) 3505 3803 { 3506 3804 //enter tail 3507 3805 3508 if (c>S>m[i]==NULL) continue; 3509 poly tail=c>S>m[i]>next; 3510 poly prev=c>S>m[i]; 3511 BOOLEAN did_something=FALSE; 3512 while((tail!=NULL)&& (pLmCmp(tail, monom)>=0)) 3513 { 3514 if (p_LmDivisibleBy(monom,tail,c>r)) 3515 { 3516 did_something=TRUE; 3517 prev>next=tail>next; 3518 tail>next=NULL; 3519 p_Delete(& tail,c>r); 3520 tail=prev; 3521 //PrintS("Shortened"); 3522 c>lengths[i]; 3523 } 3524 prev=tail; 3525 tail=tail>next; 3806 if (c>S>m[i] == NULL) 3807 continue; 3808 poly tail = c>S>m[i]>next; 3809 poly prev = c>S>m[i]; 3810 BOOLEAN did_something = FALSE; 3811 while ((tail != NULL) && (pLmCmp (tail, monom) >= 0)) 3812 { 3813 if (p_LmDivisibleBy (monom, tail, c>r)) 3814 { 3815 did_something = TRUE; 3816 prev>next = tail>next; 3817 tail>next = NULL; 3818 p_Delete (&tail, c>r); 3819 tail = prev; 3820 //PrintS("Shortened"); 3821 c>lengths[i]; 3822 } 3823 prev = tail; 3824 tail = tail>next; 3526 3825 } 3527 3826 if (did_something) … … 3529 3828 int new_pos; 3530 3829 wlen_type q; 3531 q =pQuality(c>S>m[i],c,c>lengths[i]);3532 new_pos =simple_posInS(c>strat,c>S>m[i],c>lengths[i],q);3533 3534 int old_pos =1;3830 q = pQuality (c>S>m[i], c, c>lengths[i]); 3831 new_pos = simple_posInS (c>strat, c>S>m[i], c>lengths[i], q); 3832 3833 int old_pos = 1; 3535 3834 //assume new_pos<old_pos 3536 for (int z =0;z<=c>strat>sl;z++)3537 { 3538 if (c>strat>S[z]==c>S>m[i])3539 3540 old_pos=z;3541 3542 3543 } 3544 if (old_pos == 1)3545 for (int z=new_pos1;z>=0;z)3546 3547 if (c>strat>S[z]==c>S>m[i])3548 3549 old_pos=z;3550 3551 3552 3553 assume (old_pos>=0);3554 assume (new_pos<=old_pos);3555 assume (pLength(c>strat>S[old_pos])==c>lengths[i]);3556 c>strat>lenS[old_pos] =c>lengths[i];3835 for (int z = 0; z <= c>strat>sl; z++) 3836 { 3837 if (c>strat>S[z] == c>S>m[i]) 3838 { 3839 old_pos = z; 3840 break; 3841 } 3842 } 3843 if (old_pos == 1) 3844 for (int z = new_pos  1; z >= 0; z) 3845 { 3846 if (c>strat>S[z] == c>S>m[i]) 3847 { 3848 old_pos = z; 3849 break; 3850 } 3851 } 3852 assume (old_pos >= 0); 3853 assume (new_pos <= old_pos); 3854 assume (pLength (c>strat>S[old_pos]) == c>lengths[i]); 3855 c>strat>lenS[old_pos] = c>lengths[i]; 3557 3856 if (c>strat>lenSw) 3558 c>strat>lenSw[old_pos]=q; 3559 if (new_pos<old_pos) 3560 move_forward_in_S(old_pos,new_pos,c>strat); 3561 length_one_crit(c,i,c>lengths[i]); 3562 } 3563 } 3564 } 3565 3566 #if 0 // currently unused 3567 static sorted_pair_node* pop_pair(slimgb_alg* c) 3568 { 3569 clean_top_of_pair_list(c); 3570 3571 if(c>pair_top<0) return NULL; 3572 else return (c>apairs[c>pair_top]); 3573 } 3574 #endif 3575 3576 void slimgb_alg::cleanDegs(int lower, int upper) 3577 { 3578 assume(is_homog); 3857 c>strat>lenSw[old_pos] = q; 3858 if (new_pos < old_pos) 3859 move_forward_in_S (old_pos, new_pos, c>strat); 3860 length_one_crit (c, i, c>lengths[i]); 3861 } 3862 } 3863 } 3864 3865 #if 0 // currently unused 3866 static sorted_pair_node * 3867 pop_pair (slimgb_alg * c) 3868 { 3869 clean_top_of_pair_list (c); 3870 3871 if (c>pair_top < 0) 3872