[b553e5] | 1 | //! \file tgb.cc |
---|
[4f858ce] | 2 | // #define OM_CHECK 3 |
---|
| 3 | // #define OM_TRACK 5 |
---|
| 4 | // #define OM_KEEP 1 |
---|
| 5 | // TODO: |
---|
| 6 | // deg -> poly_crit |
---|
| 7 | // multiple rings |
---|
| 8 | // shorten_tails und dessen Aufrufe pruefen wlength!!! |
---|
| 9 | // calculating with formal sums |
---|
| 10 | // try to create spolys as formal sums |
---|
| 11 | |
---|
| 12 | #include "tgb.h" |
---|
[0f7b79] | 13 | #include "tgb_internal.h" |
---|
[b055de9] | 14 | #include "tgbgauss.h" |
---|
[4f858ce] | 15 | static const int bundle_size=100; |
---|
| 16 | #if 1 |
---|
| 17 | static omBin lm_bin=NULL; |
---|
| 18 | static inline poly p_Init_Special(const ring r) |
---|
| 19 | { |
---|
| 20 | return p_Init(r,lm_bin); |
---|
| 21 | } |
---|
| 22 | static inline poly pOne_Special(const ring r=currRing) |
---|
| 23 | { |
---|
| 24 | poly rc = p_Init_Special(r); |
---|
| 25 | pSetCoeff0(rc,r->cf->nInit(1)); |
---|
| 26 | return rc; |
---|
| 27 | } |
---|
| 28 | // zum Initialiseren: in t_rep_gb plazieren: |
---|
| 29 | |
---|
| 30 | #endif |
---|
| 31 | #define LEN_VAR3 |
---|
| 32 | #define degbound(p) assume(pTotaldegree(p)<10) |
---|
| 33 | //#define inDebug(p) assume((debug_Ideal==NULL)||(kNF(debug_Ideal,NULL,p,0,0)==0)) |
---|
| 34 | |
---|
| 35 | //die meisten Varianten stossen sich an coef_buckets |
---|
| 36 | #ifdef LEN_VAR1 |
---|
| 37 | // erste Variante: Laenge: Anzahl der Monome |
---|
| 38 | inline int pSLength(poly p, int l) { |
---|
| 39 | return l; } |
---|
| 40 | inline int kSBucketLength(kBucket* bucket, poly lm) {return bucket_guess(bucket);} |
---|
| 41 | #endif |
---|
| 42 | |
---|
| 43 | #ifdef LEN_VAR2 |
---|
| 44 | // 2. Variante: Laenge: Platz fuer die Koeff. |
---|
| 45 | int pSLength(poly p,int l) |
---|
| 46 | { |
---|
| 47 | int s=0; |
---|
| 48 | while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } |
---|
| 49 | return s; |
---|
| 50 | } |
---|
| 51 | int kSBucketLength(kBucket* b, poly lm) |
---|
| 52 | { |
---|
| 53 | int s=0; |
---|
| 54 | int i; |
---|
| 55 | for (i=MAX_BUCKET;i>=0;i--) |
---|
| 56 | { |
---|
| 57 | s+=pSLength(b->buckets[i],0); |
---|
| 58 | } |
---|
| 59 | return s; |
---|
| 60 | } |
---|
| 61 | #endif |
---|
| 62 | |
---|
| 63 | #ifdef LEN_VAR3 |
---|
| 64 | // 3.Variante: Laenge: Platz fuer Leitk * Monomanzahl |
---|
| 65 | inline int pSLength(poly p,int l) |
---|
| 66 | { |
---|
| 67 | int c=nSize(pGetCoeff(p)); |
---|
| 68 | return c*l /*pLength(p)*/; |
---|
| 69 | } |
---|
| 70 | int kSBucketLength(kBucket* b, poly lm=NULL) |
---|
| 71 | { |
---|
| 72 | int s=0; |
---|
| 73 | int c; |
---|
| 74 | if(lm==NULL) |
---|
| 75 | c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 76 | else |
---|
| 77 | c=nSize(pGetCoeff(lm)); |
---|
| 78 | int i; |
---|
| 79 | for (i=b->buckets_used;i>=0;i--) |
---|
| 80 | { |
---|
| 81 | assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL)); |
---|
| 82 | s+=b->buckets_length[i] /*pLength(b->buckets[i])*/; |
---|
| 83 | } |
---|
| 84 | return s*c; |
---|
| 85 | } |
---|
| 86 | #endif |
---|
| 87 | |
---|
| 88 | #ifdef LEN_VAR4 |
---|
| 89 | // 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.) |
---|
| 90 | int pSLength(poly p, int l) |
---|
| 91 | { |
---|
| 92 | int s=1; |
---|
| 93 | int c=nSize(pGetCoeff(p)); |
---|
| 94 | pIter(p); |
---|
| 95 | while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } |
---|
| 96 | return s*c; |
---|
| 97 | } |
---|
| 98 | int kSBucketLength(kBucket* b) |
---|
| 99 | { |
---|
| 100 | int s=1; |
---|
| 101 | int c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 102 | int i; |
---|
| 103 | for (i=MAX_BUCKET;i>0;i--) |
---|
| 104 | { |
---|
| 105 | if(b->buckets[i]==NULL) continue; |
---|
| 106 | s+=pSLength(b->buckets[i],0); |
---|
| 107 | } |
---|
| 108 | return s*c; |
---|
| 109 | } |
---|
| 110 | #endif |
---|
| 111 | static int do_pELength(poly p, calc_dat* c, int dlm=-1){ |
---|
| 112 | if(p==NULL) return 0; |
---|
| 113 | int s=0; |
---|
| 114 | poly pi=p; |
---|
| 115 | if(dlm<0){ |
---|
| 116 | dlm=pTotaldegree(p,c->r); |
---|
| 117 | s=1; |
---|
| 118 | pi=p->next; |
---|
| 119 | } |
---|
| 120 | |
---|
| 121 | while(pi){ |
---|
| 122 | int d=pTotaldegree(pi,c->r); |
---|
| 123 | if(d>dlm) |
---|
| 124 | s+=1+d-dlm; |
---|
| 125 | else |
---|
| 126 | ++s; |
---|
| 127 | pi=pi->next; |
---|
| 128 | } |
---|
| 129 | return s; |
---|
| 130 | } |
---|
| 131 | int kEBucketLength(kBucket* b, poly lm,calc_dat* ca) |
---|
| 132 | { |
---|
| 133 | int s=0; |
---|
| 134 | if(lm==NULL){ |
---|
| 135 | lm=kBucketGetLm(b); |
---|
| 136 | } |
---|
| 137 | if(lm==NULL) return 0; |
---|
| 138 | int d=pTotaldegree(lm,ca->r); |
---|
| 139 | int i; |
---|
| 140 | for (i=b->buckets_used;i>=0;i--) |
---|
| 141 | { |
---|
| 142 | if(b->buckets[i]==NULL) continue; |
---|
| 143 | s+=do_pELength(b->buckets[i],ca,d); |
---|
| 144 | } |
---|
| 145 | return s; |
---|
| 146 | } |
---|
| 147 | |
---|
| 148 | static inline int pELength(poly p, calc_dat* c,int l){ |
---|
| 149 | if (p==NULL) return 0; |
---|
| 150 | return do_pELength(p,c); |
---|
| 151 | } |
---|
| 152 | // static int quality(poly p, int len, calc_dat* c){ |
---|
| 153 | // if (c->is_char0) return pSLength(p,len); |
---|
| 154 | // return pLength(p); |
---|
| 155 | // } |
---|
| 156 | static inline int pQuality(poly p, calc_dat* c, int l=-1){ |
---|
| 157 | |
---|
| 158 | if(l<0) |
---|
| 159 | l=pLength(p); |
---|
| 160 | if(c->is_char0) return pSLength(p,l); |
---|
| 161 | if((pLexOrder) &&(!c->is_homog)) return pELength(p,c,l); |
---|
| 162 | return l; |
---|
| 163 | } |
---|
| 164 | static inline int pTotaldegree_full(poly p){ |
---|
| 165 | int r=0; |
---|
| 166 | while(p){ |
---|
| 167 | int d=pTotaldegree(p); |
---|
| 168 | r=si_max(r,d); |
---|
| 169 | pIter(p); |
---|
| 170 | } |
---|
| 171 | return r; |
---|
| 172 | } |
---|
| 173 | |
---|
| 174 | int red_object::guess_quality(calc_dat* c){ |
---|
| 175 | //works at the moment only for lenvar 1, because in different |
---|
| 176 | //case, you have to look on coefs |
---|
| 177 | int s=0; |
---|
| 178 | if (c->is_char0) |
---|
| 179 | s=kSBucketLength(bucket,this->p); |
---|
| 180 | else |
---|
| 181 | { |
---|
| 182 | if((pLexOrder) &&(!c->is_homog)) |
---|
| 183 | //if (false) |
---|
| 184 | s=kEBucketLength(this->bucket,this->p,c); |
---|
| 185 | else s=bucket_guess(bucket); |
---|
| 186 | } |
---|
| 187 | if (sum!=NULL){ |
---|
| 188 | if (c->is_char0) |
---|
| 189 | s+=kSBucketLength(sum->ac->bucket); |
---|
| 190 | else |
---|
| 191 | { |
---|
| 192 | if((pLexOrder) &&(!c->is_homog)) |
---|
| 193 | //if (false) |
---|
| 194 | s+=kEBucketLength(sum->ac->bucket,this->p,c); |
---|
| 195 | else |
---|
| 196 | s+=bucket_guess(sum->ac->bucket); |
---|
| 197 | } |
---|
| 198 | } |
---|
| 199 | return s; |
---|
| 200 | } |
---|
| 201 | // static int guess_quality(const red_object & p, calc_dat* c){ |
---|
| 202 | // //looks only on bucket |
---|
| 203 | // if (c->is_char0) return kSBucketLength(p.bucket,p.p); |
---|
| 204 | // if((pLexOrder) &&(!c->is_homog)) return kEBucketLength(p.bucket,p.p,c); |
---|
| 205 | // return (bucket_guess(p.bucket)); |
---|
| 206 | // } |
---|
| 207 | |
---|
| 208 | static void finalize_reduction_step(reduction_step* r){ |
---|
| 209 | delete r; |
---|
| 210 | } |
---|
| 211 | static int LObject_better_gen(const void* ap, const void* bp) |
---|
| 212 | { |
---|
| 213 | LObject* a=*(LObject**)ap; |
---|
| 214 | LObject* b=*(LObject**)bp; |
---|
| 215 | return(pLmCmp(a->p,b->p)); |
---|
| 216 | } |
---|
| 217 | static int red_object_better_gen(const void* ap, const void* bp) |
---|
| 218 | { |
---|
| 219 | |
---|
| 220 | |
---|
| 221 | return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p)); |
---|
| 222 | } |
---|
| 223 | static int monom_poly_crit(const void* ap1, const void* ap2){ |
---|
| 224 | monom_poly* p1; |
---|
| 225 | monom_poly* p2; |
---|
| 226 | p1=((monom_poly*) ap1); |
---|
| 227 | p2=((monom_poly*)ap2); |
---|
| 228 | if(((unsigned long) p1->f)>((unsigned long) p2->f)) return 1; |
---|
| 229 | if(((unsigned long) p1->f)<((unsigned long)p2->f)) return -1; |
---|
| 230 | |
---|
| 231 | return pLmCmp(p1->m,p2->m); |
---|
| 232 | |
---|
| 233 | } |
---|
| 234 | static int pLmCmp_func(const void* ap1, const void* ap2){ |
---|
| 235 | poly p1,p2; |
---|
| 236 | p1=*((poly*) ap1); |
---|
| 237 | p2=*((poly*)ap2); |
---|
| 238 | |
---|
| 239 | return pLmCmp(p1,p2); |
---|
| 240 | } |
---|
| 241 | static int pLmCmp_func_inverted(const void* ap1, const void* ap2){ |
---|
| 242 | poly p1,p2; |
---|
| 243 | p1=*((poly*) ap1); |
---|
| 244 | p2=*((poly*)ap2); |
---|
| 245 | |
---|
| 246 | return -pLmCmp(p1,p2); |
---|
| 247 | } |
---|
| 248 | |
---|
| 249 | static int pair_better_gen2(const void* ap,const void* bp){ |
---|
| 250 | return(-pair_better_gen(ap,bp)); |
---|
| 251 | } |
---|
| 252 | static int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj){ |
---|
| 253 | int i; |
---|
| 254 | long not_sev=~obj.sev; |
---|
| 255 | poly p=obj.p; |
---|
| 256 | for(i=0;i<=strat->sl;i++){ |
---|
| 257 | if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) |
---|
| 258 | return i; |
---|
| 259 | } |
---|
| 260 | return -1; |
---|
| 261 | } |
---|
| 262 | static int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev){ |
---|
| 263 | int i; |
---|
| 264 | long not_sev=~sev; |
---|
| 265 | for(i=0;i<=strat->sl;i++){ |
---|
| 266 | if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) |
---|
| 267 | return i; |
---|
| 268 | } |
---|
| 269 | return -1; |
---|
| 270 | } |
---|
| 271 | static int posInPairs (sorted_pair_node** p, int pn, sorted_pair_node* qe,calc_dat* c,int an=0) |
---|
| 272 | { |
---|
| 273 | if(pn==0) return 0; |
---|
| 274 | |
---|
| 275 | int length=pn-1; |
---|
| 276 | int i; |
---|
| 277 | //int an = 0; |
---|
| 278 | int en= length; |
---|
| 279 | |
---|
| 280 | if (pair_better(qe,p[en],c)) |
---|
| 281 | return length+1; |
---|
| 282 | |
---|
| 283 | while(1) |
---|
| 284 | { |
---|
| 285 | //if (an >= en-1) |
---|
| 286 | if(en-1<=an) |
---|
| 287 | { |
---|
| 288 | if (pair_better(p[an],qe,c)) return an; |
---|
| 289 | return en; |
---|
| 290 | } |
---|
| 291 | i=(an+en) / 2; |
---|
| 292 | if (pair_better(p[i],qe,c)) |
---|
| 293 | en=i; |
---|
| 294 | else an=i; |
---|
| 295 | } |
---|
| 296 | } |
---|
| 297 | static int posInPolys (poly* p, int pn, poly qe,calc_dat* c) |
---|
| 298 | { |
---|
| 299 | if(pn==0) return 0; |
---|
| 300 | |
---|
| 301 | int length=pn-1; |
---|
| 302 | int i; |
---|
| 303 | int an = 0; |
---|
| 304 | int en= length; |
---|
| 305 | |
---|
| 306 | if (pLmCmp(qe,p[en])==1) |
---|
| 307 | return length+1; |
---|
| 308 | |
---|
| 309 | while(1) |
---|
| 310 | { |
---|
| 311 | //if (an >= en-1) |
---|
| 312 | if(en-1<=an) |
---|
| 313 | { |
---|
| 314 | if (pLmCmp(p[an],qe)==1) return an; |
---|
| 315 | return en; |
---|
| 316 | } |
---|
| 317 | i=(an+en) / 2; |
---|
| 318 | if (pLmCmp(p[i],qe)==1) |
---|
| 319 | en=i; |
---|
| 320 | else an=i; |
---|
| 321 | } |
---|
| 322 | } |
---|
| 323 | static int posInMonomPolys (monom_poly* p, int pn, monom_poly & qe,calc_dat* c) |
---|
| 324 | { |
---|
| 325 | if(pn==0) return 0; |
---|
| 326 | |
---|
| 327 | int length=pn-1; |
---|
| 328 | int i; |
---|
| 329 | int an = 0; |
---|
| 330 | int en= length; |
---|
| 331 | |
---|
| 332 | if (monom_poly_crit(&qe,&p[en])==1) |
---|
| 333 | return length+1; |
---|
| 334 | |
---|
| 335 | while(1) |
---|
| 336 | { |
---|
| 337 | //if (an >= en-1) |
---|
| 338 | if(en-1<=an) |
---|
| 339 | { |
---|
| 340 | if (monom_poly_crit(&p[an],&qe)==1) return an; |
---|
| 341 | return en; |
---|
| 342 | } |
---|
| 343 | i=(an+en) / 2; |
---|
| 344 | if (monom_poly_crit(&p[i],&qe)==1) |
---|
| 345 | en=i; |
---|
| 346 | else an=i; |
---|
| 347 | } |
---|
| 348 | } |
---|
| 349 | static BOOLEAN ascending(int* i,int top){ |
---|
| 350 | if(top<1) return TRUE; |
---|
| 351 | if(i[top]<i[top-1]) return FALSE; |
---|
| 352 | return ascending(i,top-1); |
---|
| 353 | } |
---|
| 354 | |
---|
| 355 | sorted_pair_node** merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,calc_dat* c){ |
---|
| 356 | int i; |
---|
[ec8a6b6] | 357 | int* a= (int*) omalloc(qn*sizeof(int)); |
---|
[4f858ce] | 358 | // int mc; |
---|
| 359 | // PrintS("Debug\n"); |
---|
| 360 | // for(mc=0;mc<qn;mc++) |
---|
| 361 | // { |
---|
| 362 | |
---|
| 363 | // wrp(q[mc]->lcm_of_lm); |
---|
| 364 | // PrintS("\n"); |
---|
| 365 | // } |
---|
| 366 | // PrintS("Debug they are in\n"); |
---|
| 367 | // for(mc=0;mc<pn;mc++) |
---|
| 368 | // { |
---|
| 369 | |
---|
| 370 | // wrp(p[mc]->lcm_of_lm); |
---|
| 371 | // PrintS("\n"); |
---|
| 372 | // } |
---|
| 373 | int lastpos=0; |
---|
| 374 | for(i=0;i<qn;i++){ |
---|
| 375 | lastpos=posInPairs(p,pn,q[i],c, si_max(lastpos-1,0)); |
---|
| 376 | // cout<<lastpos<<"\n"; |
---|
| 377 | a[i]=lastpos; |
---|
| 378 | |
---|
| 379 | } |
---|
| 380 | if((pn+qn)>c->max_pairs){ |
---|
[ec8a6b6] | 381 | p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 382 | c->max_pairs=2*(pn+qn); |
---|
| 383 | } |
---|
| 384 | for(i=qn-1;i>=0;i--){ |
---|
| 385 | size_t size; |
---|
| 386 | if(qn-1>i) |
---|
| 387 | size=(a[i+1]-a[i])*sizeof(sorted_pair_node*); |
---|
| 388 | else |
---|
| 389 | size=(pn-a[i])*sizeof(sorted_pair_node*); //as indices begin with 0 |
---|
| 390 | memmove (p+a[i]+(1+i), p+a[i], size); |
---|
| 391 | p[a[i]+i]=q[i]; |
---|
| 392 | } |
---|
| 393 | omfree(a); |
---|
| 394 | return p; |
---|
| 395 | } |
---|
| 396 | |
---|
| 397 | |
---|
| 398 | static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,calc_dat* c){ |
---|
| 399 | |
---|
| 400 | |
---|
| 401 | poly p1=c->S->m[pos1]; |
---|
| 402 | poly p2=c->S->m[pos2]; |
---|
| 403 | ring r=c->r; |
---|
| 404 | |
---|
| 405 | |
---|
| 406 | if (pGetComp(p1) > 0 || pGetComp(p2) > 0) |
---|
| 407 | return FALSE; |
---|
| 408 | int i = 1; |
---|
| 409 | poly m=NULL; |
---|
| 410 | poly gcd1=c->gcd_of_terms[pos1]; |
---|
| 411 | poly gcd2=c->gcd_of_terms[pos2]; |
---|
| 412 | |
---|
| 413 | if((gcd1!=NULL) && (gcd2!=NULL)) |
---|
| 414 | { |
---|
| 415 | gcd1->next=gcd2; //may ordered incorrect |
---|
| 416 | poly m=gcd_of_terms(gcd1,c->r); |
---|
| 417 | gcd1->next=NULL; |
---|
| 418 | |
---|
| 419 | } |
---|
| 420 | |
---|
| 421 | if (m==NULL) |
---|
| 422 | { |
---|
| 423 | loop |
---|
| 424 | { |
---|
| 425 | if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; |
---|
| 426 | if (i == pVariables){ |
---|
| 427 | //PrintS("trivial"); |
---|
| 428 | return TRUE; |
---|
| 429 | } |
---|
| 430 | i++; |
---|
| 431 | } |
---|
| 432 | } |
---|
| 433 | else |
---|
| 434 | { |
---|
| 435 | loop |
---|
| 436 | { |
---|
| 437 | if (pGetExp(p1, i)-pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; |
---|
| 438 | if (i == pVariables){ |
---|
| 439 | pDelete(&m); |
---|
| 440 | //PrintS("trivial"); |
---|
| 441 | return TRUE; |
---|
| 442 | } |
---|
| 443 | i++; |
---|
| 444 | } |
---|
| 445 | } |
---|
| 446 | |
---|
| 447 | |
---|
| 448 | |
---|
| 449 | |
---|
| 450 | } |
---|
| 451 | |
---|
[b553e5] | 452 | //! returns position sets w as weight |
---|
[4f858ce] | 453 | int find_best(red_object* r,int l, int u, int &w, calc_dat* c){ |
---|
| 454 | int best=l; |
---|
| 455 | int i; |
---|
| 456 | w=r[l].guess_quality(c); |
---|
| 457 | for(i=l+1;i<=u;i++){ |
---|
| 458 | int w2=r[i].guess_quality(c); |
---|
| 459 | if(w2<w){ |
---|
| 460 | w=w2; |
---|
| 461 | best=i; |
---|
| 462 | } |
---|
| 463 | |
---|
| 464 | } |
---|
| 465 | return best; |
---|
| 466 | } |
---|
| 467 | |
---|
| 468 | #if 0 |
---|
| 469 | int find_best(red_object* r,int l, int u, int &w, calc_dat* c){ |
---|
| 470 | |
---|
| 471 | int sz=u-l+1; |
---|
| 472 | int n=sz/10+1; |
---|
| 473 | int filled=0; |
---|
[ec8a6b6] | 474 | int* indizes=(int*) omalloc(n*sizeof(int)); |
---|
| 475 | int* weight=(int*) omalloc(n*sizeof(int)); |
---|
[4f858ce] | 476 | int worst=-1; |
---|
| 477 | int i; |
---|
| 478 | for(i=l;i<=u;i++){ |
---|
| 479 | int q=r[i].guess_quality(c); |
---|
| 480 | if ((filled<n)||(q<worst)){ |
---|
| 481 | if(filled<n){ |
---|
| 482 | worst=si_max(q,worst); |
---|
| 483 | indizes[filled]=i; |
---|
| 484 | weight[filled]=q; |
---|
| 485 | filled++; |
---|
| 486 | } |
---|
| 487 | } |
---|
| 488 | else{ |
---|
| 489 | int j; |
---|
| 490 | for(j=0;j<filled;j++){ |
---|
| 491 | if (worst==weight[j]){ |
---|
| 492 | weight[j]=q; |
---|
| 493 | indizes[j]=i; |
---|
| 494 | } |
---|
| 495 | } |
---|
| 496 | worst=-1; |
---|
| 497 | for(j=0;j<filled;j++){ |
---|
| 498 | if (worst<weight[j]){ |
---|
| 499 | worst=weight[j]; |
---|
| 500 | } |
---|
| 501 | } |
---|
| 502 | } |
---|
| 503 | } |
---|
| 504 | assume(filled==n); |
---|
| 505 | int pos=0; |
---|
| 506 | |
---|
| 507 | for(i=0;i<filled;i++){ |
---|
| 508 | r[indizes[i]].canonicalize(); |
---|
| 509 | weight[i]=r[indizes[i]].guess_quality(c); |
---|
| 510 | if(weight[i]<weight[pos]) pos=i; |
---|
| 511 | } |
---|
| 512 | w=weight[pos]; |
---|
| 513 | pos=indizes[pos]; |
---|
| 514 | |
---|
| 515 | omfree(indizes); |
---|
| 516 | omfree(weight); |
---|
| 517 | |
---|
| 518 | assume(w==r[pos].guess_quality(c)); |
---|
| 519 | assume(l<=pos); |
---|
| 520 | assume(u>=pos); |
---|
| 521 | return pos; |
---|
| 522 | |
---|
| 523 | } |
---|
| 524 | |
---|
| 525 | #endif |
---|
| 526 | void red_object::canonicalize(){ |
---|
| 527 | kBucketCanonicalize(bucket); |
---|
| 528 | if(sum) |
---|
| 529 | kBucketCanonicalize(sum->ac->bucket); |
---|
| 530 | |
---|
| 531 | } |
---|
| 532 | BOOLEAN good_has_t_rep(int i, int j,calc_dat* c){ |
---|
| 533 | assume(i>=0); |
---|
| 534 | assume(j>=0); |
---|
| 535 | if (has_t_rep(i,j,c)) return TRUE; |
---|
| 536 | //poly lm=pOne(); |
---|
| 537 | assume (c->tmp_lm!=NULL); |
---|
| 538 | poly lm=c->tmp_lm; |
---|
| 539 | |
---|
| 540 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 541 | pSetm(lm); |
---|
| 542 | assume(lm!=NULL); |
---|
| 543 | //int deciding_deg= pTotaldegree(lm); |
---|
| 544 | int* i_con =make_connections(i,j,lm,c); |
---|
| 545 | //p_Delete(&lm,c->r); |
---|
| 546 | |
---|
| 547 | |
---|
| 548 | for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ |
---|
| 549 | if (i_con[n]==j){ |
---|
| 550 | now_t_rep(i,j,c); |
---|
| 551 | omfree(i_con); |
---|
| 552 | |
---|
| 553 | return TRUE; |
---|
| 554 | } |
---|
| 555 | } |
---|
| 556 | omfree(i_con); |
---|
| 557 | |
---|
| 558 | return FALSE; |
---|
| 559 | } |
---|
| 560 | BOOLEAN lenS_correct(kStrategy strat){ |
---|
| 561 | int i; |
---|
| 562 | for(i=0;i<=strat->sl;i++){ |
---|
| 563 | if (strat->lenS[i]!=pLength(strat->S[i])) |
---|
| 564 | return FALSE; |
---|
| 565 | } |
---|
| 566 | return TRUE; |
---|
| 567 | } |
---|
| 568 | |
---|
| 569 | static void notice_miss(int i, int j, calc_dat* c){ |
---|
| 570 | if (TEST_OPT_PROT) |
---|
| 571 | PrintS("-"); |
---|
| 572 | |
---|
| 573 | } |
---|
| 574 | |
---|
| 575 | static void cleanS(kStrategy strat, calc_dat* c){ |
---|
| 576 | int i=0; |
---|
| 577 | LObject P; |
---|
| 578 | while(i<=strat->sl){ |
---|
| 579 | P.p=strat->S[i]; |
---|
| 580 | P.sev=strat->sevS[i]; |
---|
| 581 | if(kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P)!=i) |
---|
| 582 | { |
---|
| 583 | deleteInS(i,strat); |
---|
| 584 | //remember destroying poly |
---|
| 585 | BOOLEAN found=FALSE; |
---|
| 586 | int j; |
---|
| 587 | for(j=0;j<c->n;j++) |
---|
| 588 | if(c->S->m[j]==P.p) |
---|
| 589 | { |
---|
| 590 | found=TRUE; |
---|
| 591 | break; |
---|
| 592 | } |
---|
| 593 | if (!found) |
---|
| 594 | pDelete(&P.p); |
---|
| 595 | //remember additional reductors |
---|
| 596 | } |
---|
| 597 | else i++; |
---|
| 598 | } |
---|
| 599 | } |
---|
| 600 | static int bucket_guess(kBucket* bucket){ |
---|
| 601 | int sum=0; |
---|
| 602 | int i; |
---|
| 603 | for (i=bucket->buckets_used;i>=0;i--){ |
---|
| 604 | if(bucket->buckets[i]) |
---|
| 605 | sum+=bucket->buckets_length[i]; |
---|
| 606 | } |
---|
| 607 | return sum; |
---|
| 608 | } |
---|
| 609 | |
---|
| 610 | |
---|
| 611 | |
---|
| 612 | |
---|
| 613 | |
---|
| 614 | |
---|
| 615 | static int add_to_reductors(calc_dat* c, poly h, int len){ |
---|
| 616 | //inDebug(h); |
---|
| 617 | assume(lenS_correct(c->strat)); |
---|
| 618 | assume(len==pLength(h)); |
---|
| 619 | int i; |
---|
| 620 | // if (c->is_char0) |
---|
| 621 | // i=simple_posInS(c->strat,h,pSLength(h,len),c->is_char0); |
---|
| 622 | // else |
---|
| 623 | // i=simple_posInS(c->strat,h,len,c->is_char0); |
---|
| 624 | |
---|
| 625 | LObject P; memset(&P,0,sizeof(P)); |
---|
| 626 | P.tailRing=c->r; |
---|
| 627 | P.p=h; /*p_Copy(h,c->r);*/ |
---|
| 628 | P.FDeg=pFDeg(P.p,c->r); |
---|
| 629 | |
---|
| 630 | if (!rField_is_Zp(c->r)){ |
---|
| 631 | pCleardenom(P.p); |
---|
| 632 | pContent(P.p); //is a duplicate call, but belongs here |
---|
| 633 | |
---|
| 634 | } |
---|
| 635 | else |
---|
| 636 | pNorm(P.p); |
---|
| 637 | pNormalize(P.p); |
---|
| 638 | int pq=pQuality(h,c,len); |
---|
| 639 | i=simple_posInS(c->strat,h,pq); |
---|
| 640 | c->strat->enterS(P,i,c->strat,-1); |
---|
| 641 | |
---|
| 642 | |
---|
| 643 | |
---|
| 644 | c->strat->lenS[i]=len; |
---|
| 645 | assume(pLength(c->strat->S[i])==c->strat->lenS[i]); |
---|
| 646 | if(c->strat->lenSw) |
---|
| 647 | c->strat->lenSw[i]=pq; |
---|
| 648 | |
---|
| 649 | return i; |
---|
| 650 | |
---|
| 651 | } |
---|
| 652 | static void length_one_crit(calc_dat* c, int pos, int len) |
---|
| 653 | { |
---|
| 654 | if (len==1) |
---|
| 655 | { |
---|
| 656 | int i; |
---|
| 657 | for ( i=0;i<pos;i++) |
---|
| 658 | { |
---|
| 659 | if (c->lengths[i]==1) |
---|
| 660 | c->states[pos][i]=HASTREP; |
---|
| 661 | } |
---|
| 662 | for ( i=pos+1;i<c->n;i++){ |
---|
| 663 | if (c->lengths[i]==1) |
---|
| 664 | c->states[i][pos]=HASTREP; |
---|
| 665 | } |
---|
| 666 | shorten_tails(c,c->S->m[pos]); |
---|
| 667 | } |
---|
| 668 | } |
---|
| 669 | static sorted_pair_node* find_next_pair2(calc_dat* c, BOOLEAN go_higher){ |
---|
| 670 | clean_top_of_pair_list(c); |
---|
| 671 | sorted_pair_node* s=pop_pair(c); |
---|
| 672 | |
---|
| 673 | |
---|
| 674 | return s; |
---|
| 675 | } |
---|
| 676 | |
---|
| 677 | static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat) |
---|
| 678 | { |
---|
| 679 | assume(old_pos>=new_pos); |
---|
| 680 | poly p=strat->S[old_pos]; |
---|
| 681 | int ecart=strat->ecartS[old_pos]; |
---|
| 682 | long sev=strat->sevS[old_pos]; |
---|
| 683 | int s_2_r=strat->S_2_R[old_pos]; |
---|
| 684 | int length=strat->lenS[old_pos]; |
---|
| 685 | assume(length==pLength(strat->S[old_pos])); |
---|
| 686 | int length_w; |
---|
| 687 | if(strat->lenSw) |
---|
| 688 | length_w=strat->lenSw[old_pos]; |
---|
| 689 | int i; |
---|
| 690 | for (i=old_pos; i>new_pos; i--) |
---|
| 691 | { |
---|
| 692 | strat->S[i] = strat->S[i-1]; |
---|
| 693 | strat->ecartS[i] = strat->ecartS[i-1]; |
---|
| 694 | strat->sevS[i] = strat->sevS[i-1]; |
---|
| 695 | strat->S_2_R[i] = strat->S_2_R[i-1]; |
---|
| 696 | } |
---|
| 697 | if (strat->lenS!=NULL) |
---|
| 698 | for (i=old_pos; i>new_pos; i--) |
---|
| 699 | strat->lenS[i] = strat->lenS[i-1]; |
---|
| 700 | if (strat->lenSw!=NULL) |
---|
| 701 | for (i=old_pos; i>new_pos; i--) |
---|
| 702 | strat->lenSw[i] = strat->lenSw[i-1]; |
---|
| 703 | |
---|
| 704 | strat->S[new_pos]=p; |
---|
| 705 | strat->ecartS[new_pos]=ecart; |
---|
| 706 | strat->sevS[new_pos]=sev; |
---|
| 707 | strat->S_2_R[new_pos]=s_2_r; |
---|
| 708 | strat->lenS[new_pos]=length; |
---|
| 709 | if(strat->lenSw) |
---|
| 710 | strat->lenSw[new_pos]=length_w; |
---|
| 711 | //assume(lenS_correct(strat)); |
---|
| 712 | } |
---|
| 713 | static void replace_pair(int & i, int & j, calc_dat* c) |
---|
| 714 | { |
---|
| 715 | c->soon_free=NULL; |
---|
| 716 | int curr_deg; |
---|
| 717 | poly lm=pOne(); |
---|
| 718 | |
---|
| 719 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 720 | pSetm(lm); |
---|
| 721 | int deciding_deg= pTotaldegree(lm); |
---|
| 722 | int* i_con =make_connections(i,j,lm,c); |
---|
| 723 | int z=0; |
---|
| 724 | |
---|
| 725 | for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ |
---|
| 726 | if (i_con[n]==j){ |
---|
| 727 | now_t_rep(i,j,c); |
---|
| 728 | omfree(i_con); |
---|
| 729 | p_Delete(&lm,c->r); |
---|
| 730 | return; |
---|
| 731 | } |
---|
| 732 | } |
---|
| 733 | |
---|
| 734 | int* j_con =make_connections(j,lm,c); |
---|
| 735 | i= i_con[0]; |
---|
| 736 | j=j_con[0]; |
---|
| 737 | if(c->n>1){ |
---|
| 738 | if (i_con[1]>=0) |
---|
| 739 | i=i_con[1]; |
---|
| 740 | else { |
---|
| 741 | if (j_con[1]>=0) |
---|
| 742 | j=j_con[1]; |
---|
| 743 | } |
---|
| 744 | } |
---|
| 745 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 746 | pSetm(lm); |
---|
| 747 | poly short_s; |
---|
| 748 | curr_deg=pTotaldegree(lm); |
---|
| 749 | int_pair_node* last=NULL; |
---|
| 750 | |
---|
| 751 | for (int n=0;((n<c->n) && (j_con[n]>=0));n++){ |
---|
| 752 | for (int m=0;((m<c->n) && (i_con[m]>=0));m++){ |
---|
| 753 | pLcm(c->S->m[i_con[m]], c->S->m[j_con[n]], lm); |
---|
| 754 | pSetm(lm); |
---|
| 755 | if (pTotaldegree(lm)>=deciding_deg) |
---|
| 756 | { |
---|
| 757 | soon_t_rep(i_con[m],j_con[n],c); |
---|
[ec8a6b6] | 758 | int_pair_node* h= (int_pair_node*)omalloc(sizeof(int_pair_node)); |
---|
[4f858ce] | 759 | if (last!=NULL) |
---|
| 760 | last->next=h; |
---|
| 761 | else |
---|
| 762 | c->soon_free=h; |
---|
| 763 | h->next=NULL; |
---|
| 764 | h->a=i_con[m]; |
---|
| 765 | h->b=j_con[n]; |
---|
| 766 | last=h; |
---|
| 767 | } |
---|
| 768 | // if ((comp_deg<curr_deg) |
---|
| 769 | // || |
---|
| 770 | // ((comp_deg==curr_deg) && |
---|
| 771 | short_s=ksCreateShortSpoly(c->S->m[i_con[m]],c->S->m[j_con[n]],c->r); |
---|
| 772 | if (short_s==NULL) { |
---|
| 773 | i=i_con[m]; |
---|
| 774 | j=j_con[n]; |
---|
| 775 | now_t_rep(i_con[m],j_con[n],c); |
---|
| 776 | p_Delete(&lm,c->r); |
---|
| 777 | omfree(i_con); |
---|
| 778 | omfree(j_con); |
---|
| 779 | |
---|
| 780 | return; |
---|
| 781 | } |
---|
| 782 | #ifdef QUICK_SPOLY_TEST |
---|
| 783 | for (int dz=0;dz<=c->n;dz++){ |
---|
| 784 | if (dz==c->n) { |
---|
| 785 | //have found not head reducing pair |
---|
| 786 | i=i_con[m]; |
---|
| 787 | j=j_con[n]; |
---|
| 788 | p_Delete(&short_s,c->r); |
---|
| 789 | p_Delete(&lm,c->r); |
---|
| 790 | omfree(i_con); |
---|
| 791 | omfree(j_con); |
---|
| 792 | |
---|
| 793 | return; |
---|
| 794 | } |
---|
| 795 | if (p_LmDivisibleBy(c->S->m[dz],short_s,c->r)) break; |
---|
| 796 | } |
---|
| 797 | #endif |
---|
| 798 | int comp_deg(pTotaldegree(short_s)); |
---|
| 799 | p_Delete(&short_s,c->r); |
---|
| 800 | if ((comp_deg<curr_deg)) |
---|
| 801 | |
---|
| 802 | { |
---|
| 803 | curr_deg=comp_deg; |
---|
| 804 | i=i_con[m]; |
---|
| 805 | j=j_con[n]; |
---|
| 806 | } |
---|
| 807 | } |
---|
| 808 | } |
---|
| 809 | p_Delete(&lm,c->r); |
---|
| 810 | omfree(i_con); |
---|
| 811 | omfree(j_con); |
---|
| 812 | return; |
---|
| 813 | } |
---|
| 814 | |
---|
| 815 | |
---|
| 816 | static int* make_connections(int from, poly bound, calc_dat* c) |
---|
| 817 | { |
---|
| 818 | ideal I=c->S; |
---|
| 819 | int s=pTotaldegree(bound); |
---|
[ec8a6b6] | 820 | int* cans=(int*) omalloc(c->n*sizeof(int)); |
---|
| 821 | int* connected=(int*) omalloc(c->n*sizeof(int)); |
---|
[4f858ce] | 822 | int cans_length=0; |
---|
| 823 | connected[0]=from; |
---|
| 824 | int connected_length=1; |
---|
| 825 | long neg_bounds_short= ~p_GetShortExpVector(bound,c->r); |
---|
| 826 | for (int i=0;i<c->n;i++){ |
---|
| 827 | if (c->T_deg[i]>s) continue; |
---|
| 828 | if (i!=from){ |
---|
| 829 | if(p_LmShortDivisibleBy(I->m[i],c->short_Exps[i],bound,neg_bounds_short,c->r)){ |
---|
| 830 | cans[cans_length]=i; |
---|
| 831 | cans_length++; |
---|
| 832 | } |
---|
| 833 | } |
---|
| 834 | } |
---|
| 835 | int not_yet_found=cans_length; |
---|
| 836 | int con_checked=0; |
---|
| 837 | int pos; |
---|
| 838 | while((not_yet_found>0) && (con_checked<connected_length)){ |
---|
| 839 | pos=connected[con_checked]; |
---|
| 840 | for(int i=0;i<cans_length;i++){ |
---|
| 841 | if (cans[i]<0) continue; |
---|
| 842 | if (has_t_rep(pos,cans[i],c)) |
---|
| 843 | { |
---|
| 844 | connected[connected_length]=cans[i]; |
---|
| 845 | connected_length++; |
---|
| 846 | cans[i]=-1; |
---|
| 847 | --not_yet_found; |
---|
| 848 | } |
---|
| 849 | } |
---|
| 850 | con_checked++; |
---|
| 851 | } |
---|
| 852 | if (connected_length<c->n){ |
---|
| 853 | connected[connected_length]=-1; |
---|
| 854 | } |
---|
| 855 | omfree(cans); |
---|
| 856 | return connected; |
---|
| 857 | } |
---|
| 858 | static int* make_connections(int from, int to, poly bound, calc_dat* c) |
---|
| 859 | { |
---|
| 860 | ideal I=c->S; |
---|
| 861 | int s=pTotaldegree(bound); |
---|
[ec8a6b6] | 862 | int* cans=(int*) omalloc(c->n*sizeof(int)); |
---|
| 863 | int* connected=(int*) omalloc(c->n*sizeof(int)); |
---|
[4f858ce] | 864 | cans[0]=to; |
---|
| 865 | int cans_length=1; |
---|
| 866 | connected[0]=from; |
---|
| 867 | int last_cans_pos=-1; |
---|
| 868 | int connected_length=1; |
---|
| 869 | long neg_bounds_short= ~p_GetShortExpVector(bound,c->r); |
---|
| 870 | |
---|
| 871 | int not_yet_found=cans_length; |
---|
| 872 | int con_checked=0; |
---|
| 873 | int pos; |
---|
| 874 | BOOLEAN can_find_more=TRUE; |
---|
| 875 | while(TRUE){ |
---|
| 876 | if ((con_checked<connected_length)&& (not_yet_found>0)){ |
---|
| 877 | pos=connected[con_checked]; |
---|
| 878 | for(int i=0;i<cans_length;i++){ |
---|
| 879 | if (cans[i]<0) continue; |
---|
| 880 | if (has_t_rep(pos,cans[i],c))//||(trivial_syzygie(pos,cans[i],bound,c)) |
---|
| 881 | { |
---|
| 882 | |
---|
| 883 | connected[connected_length]=cans[i]; |
---|
| 884 | connected_length++; |
---|
| 885 | cans[i]=-1; |
---|
| 886 | --not_yet_found; |
---|
| 887 | |
---|
| 888 | if (connected[connected_length-1]==to){ |
---|
| 889 | if (connected_length<c->n){ |
---|
| 890 | connected[connected_length]=-1; |
---|
| 891 | } |
---|
| 892 | omfree(cans); |
---|
| 893 | return connected; |
---|
| 894 | } |
---|
| 895 | } |
---|
| 896 | } |
---|
| 897 | con_checked++; |
---|
| 898 | } |
---|
| 899 | else |
---|
| 900 | { |
---|
| 901 | for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++){ |
---|
| 902 | if (last_cans_pos==c->n){ |
---|
| 903 | if (connected_length<c->n){ |
---|
| 904 | connected[connected_length]=-1; |
---|
| 905 | } |
---|
| 906 | omfree(cans); |
---|
| 907 | return connected; |
---|
| 908 | } |
---|
| 909 | if ((last_cans_pos==from)||(last_cans_pos==to)) |
---|
| 910 | continue; |
---|
| 911 | if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)){ |
---|
| 912 | cans[cans_length]=last_cans_pos; |
---|
| 913 | cans_length++; |
---|
| 914 | break; |
---|
| 915 | } |
---|
| 916 | } |
---|
| 917 | not_yet_found++; |
---|
| 918 | for (int i=0;i<con_checked;i++){ |
---|
| 919 | if (has_t_rep(connected[i],last_cans_pos,c)){ |
---|
| 920 | |
---|
| 921 | connected[connected_length]=last_cans_pos; |
---|
| 922 | connected_length++; |
---|
| 923 | cans[cans_length-1]=-1; |
---|
| 924 | |
---|
| 925 | --not_yet_found; |
---|
| 926 | if (connected[connected_length-1]==to){ |
---|
| 927 | if (connected_length<c->n){ |
---|
| 928 | connected[connected_length]=-1; |
---|
| 929 | } |
---|
| 930 | |
---|
| 931 | omfree(cans); |
---|
| 932 | return connected; |
---|
| 933 | } |
---|
| 934 | break; |
---|
| 935 | } |
---|
| 936 | } |
---|
| 937 | } |
---|
| 938 | } |
---|
| 939 | if (connected_length<c->n){ |
---|
| 940 | connected[connected_length]=-1; |
---|
| 941 | } |
---|
| 942 | |
---|
| 943 | omfree(cans); |
---|
| 944 | return connected; |
---|
| 945 | } |
---|
| 946 | #ifdef HEAD_BIN |
---|
| 947 | static inline poly p_MoveHead(poly p, omBin b) |
---|
| 948 | { |
---|
| 949 | poly np; |
---|
| 950 | omTypeAllocBin(poly, np, b); |
---|
| 951 | memmove(np, p, b->sizeW*sizeof(long)); |
---|
| 952 | omFreeBinAddr(p); |
---|
| 953 | return np; |
---|
| 954 | } |
---|
| 955 | #endif |
---|
| 956 | |
---|
| 957 | |
---|
| 958 | |
---|
| 959 | //len should be weighted length in char 0 |
---|
| 960 | static int simple_posInS (kStrategy strat, poly p,int len) |
---|
| 961 | { |
---|
| 962 | |
---|
| 963 | |
---|
| 964 | if(strat->sl==-1) return 0; |
---|
| 965 | polyset set=strat->S; |
---|
| 966 | intset setL=strat->lenS; |
---|
| 967 | if (strat->lenSw) setL=strat->lenSw; |
---|
| 968 | int length=strat->sl; |
---|
| 969 | int i; |
---|
| 970 | int an = 0; |
---|
| 971 | int en= length; |
---|
| 972 | |
---|
| 973 | if ((len>setL[length]) |
---|
| 974 | || ((len==setL[length]) && (pLmCmp(set[length],p)== -1))) |
---|
| 975 | return length+1; |
---|
| 976 | |
---|
| 977 | loop |
---|
| 978 | { |
---|
| 979 | if (an >= en-1) |
---|
| 980 | { |
---|
| 981 | if ((len<setL[an]) |
---|
| 982 | || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an; |
---|
| 983 | return en; |
---|
| 984 | } |
---|
| 985 | i=(an+en) / 2; |
---|
| 986 | if ((len<setL[i]) |
---|
| 987 | || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i; |
---|
| 988 | //else if ((len>setL[i]) |
---|
| 989 | //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i; |
---|
| 990 | else an=i; |
---|
| 991 | } |
---|
| 992 | } |
---|
| 993 | /*2 |
---|
| 994 | *if the leading term of p |
---|
| 995 | *divides the leading term of some S[i] it will be canceled |
---|
| 996 | */ |
---|
| 997 | static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k, |
---|
| 998 | kStrategy strat) |
---|
| 999 | { |
---|
| 1000 | assume(p_sev == pGetShortExpVector(p)); |
---|
| 1001 | if (!pLmShortDivisibleBy(p,p_sev, strat->S[*at], ~ strat->sevS[*at])) return; |
---|
| 1002 | if (l>=strat->lenS[*at]) return; |
---|
| 1003 | if (TEST_OPT_PROT) |
---|
| 1004 | PrintS("!"); |
---|
| 1005 | mflush(); |
---|
| 1006 | //pDelete(&strat->S[*at]); |
---|
| 1007 | deleteInS((*at),strat); |
---|
| 1008 | (*at)--; |
---|
| 1009 | (*k)--; |
---|
| 1010 | // assume(lenS_correct(strat)); |
---|
| 1011 | } |
---|
| 1012 | static sorted_pair_node** add_to_basis(poly h, int i_pos, int j_pos,calc_dat* c, int* ip) |
---|
| 1013 | { |
---|
| 1014 | |
---|
| 1015 | assume(h!=NULL); |
---|
| 1016 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 1017 | BOOLEAN R_found=FALSE; |
---|
| 1018 | void* hp; |
---|
| 1019 | |
---|
| 1020 | ++(c->n); |
---|
| 1021 | ++(c->S->ncols); |
---|
| 1022 | int i,j; |
---|
| 1023 | i=c->n-1; |
---|
[ec8a6b6] | 1024 | sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 1025 | int spc=0; |
---|
[ec8a6b6] | 1026 | c->T_deg=(int*) omrealloc(c->T_deg,c->n*sizeof(int)); |
---|
[4f858ce] | 1027 | c->T_deg[i]=pTotaldegree(h); |
---|
| 1028 | if(c->T_deg_full){ |
---|
[ec8a6b6] | 1029 | c->T_deg_full=(int*) omrealloc(c->T_deg_full,c->n*sizeof(int)); |
---|
[4f858ce] | 1030 | c->T_deg_full[i]=pTotaldegree_full(h); |
---|
| 1031 | } |
---|
| 1032 | |
---|
[ec8a6b6] | 1033 | c->tmp_pair_lm=(poly*) omrealloc(c->tmp_pair_lm,c->n*sizeof(poly)); |
---|
[4f858ce] | 1034 | c->tmp_pair_lm[i]=pOne_Special(c->r); |
---|
[ec8a6b6] | 1035 | c->tmp_spn=(sorted_pair_node**) omrealloc(c->tmp_spn,c->n*sizeof(sorted_pair_node*)); |
---|
| 1036 | c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
| 1037 | hp=omrealloc(c->rep, c->n *sizeof(int)); |
---|
[4f858ce] | 1038 | if (hp!=NULL){ |
---|
| 1039 | c->rep=(int*) hp; |
---|
| 1040 | } else { |
---|
| 1041 | exit(1); |
---|
| 1042 | } |
---|
[ec8a6b6] | 1043 | c->short_Exps=(long *) omrealloc(c->short_Exps ,c->n*sizeof(long)); |
---|
[4f858ce] | 1044 | |
---|
[ec8a6b6] | 1045 | hp=omrealloc(c->lengths, c->n *sizeof(int)); |
---|
[4f858ce] | 1046 | if (hp!=NULL){ |
---|
| 1047 | c->lengths=(int*) hp; |
---|
| 1048 | } else { |
---|
| 1049 | exit(1); |
---|
| 1050 | } |
---|
| 1051 | c->lengths[i]=pLength(h); |
---|
[ec8a6b6] | 1052 | hp=omrealloc(c->states, c->n * sizeof(char*)); |
---|
[4f858ce] | 1053 | |
---|
| 1054 | c->states=(char**) hp; |
---|
[ec8a6b6] | 1055 | c->gcd_of_terms=(poly*) omrealloc(c->gcd_of_terms, c->n *sizeof(poly)); |
---|
[4f858ce] | 1056 | c->gcd_of_terms[i]=gcd_of_terms(h,c->r); |
---|
| 1057 | c->rep[i]=i; |
---|
[76b225] | 1058 | if (i>0) |
---|
| 1059 | hp=omalloc(i*sizeof(char)); |
---|
| 1060 | else |
---|
| 1061 | hp=NULL; |
---|
[4f858ce] | 1062 | if (hp!=NULL){ |
---|
| 1063 | c->states[i]=(char*) hp; |
---|
| 1064 | } else { |
---|
[76b225] | 1065 | //exit(1); |
---|
[4f858ce] | 1066 | } |
---|
[ec8a6b6] | 1067 | hp=omrealloc(c->S->m,c->n*sizeof(poly)); |
---|
[4f858ce] | 1068 | if (hp!=NULL){ |
---|
| 1069 | c->S->m=(poly*) hp; |
---|
| 1070 | } else { |
---|
| 1071 | exit(1); |
---|
| 1072 | } |
---|
| 1073 | c->S->m[i]=h; |
---|
| 1074 | c->short_Exps[i]=p_GetShortExpVector(h,c->r); |
---|
| 1075 | for (j=0;j<i;j++){ |
---|
| 1076 | if (c->rep[j]==j){ |
---|
| 1077 | //check product criterion |
---|
| 1078 | |
---|
| 1079 | c->states[i][j]=UNCALCULATED; |
---|
| 1080 | assume(p_LmDivisibleBy(c->S->m[i],c->S->m[j],c->r)== |
---|
| 1081 | p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)); |
---|
| 1082 | if(!c->F4_mode) |
---|
| 1083 | { |
---|
| 1084 | assume(!(p_LmDivisibleBy(c->S->m[j],c->S->m[i],c->r))); |
---|
| 1085 | } |
---|
| 1086 | //lies I[i] under I[j] ? |
---|
| 1087 | if(p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)){ |
---|
| 1088 | c->rep[j]=i; |
---|
| 1089 | if (TEST_OPT_PROT) |
---|
| 1090 | PrintS("R"); |
---|
| 1091 | R_found=TRUE; |
---|
| 1092 | |
---|
| 1093 | c->Rcounter++; |
---|
| 1094 | if((i_pos>=0) && (j_pos>=0)){ |
---|
| 1095 | |
---|
| 1096 | } |
---|
| 1097 | for(int z=0;z<j;z++){ |
---|
| 1098 | if(c->rep[z]!=z) continue; |
---|
| 1099 | if (c->states[j][z]==UNCALCULATED){ |
---|
| 1100 | c->states[j][z]=UNIMPORTANT; |
---|
| 1101 | } |
---|
| 1102 | } |
---|
| 1103 | for(int z=j+1;z<i;z++){ |
---|
| 1104 | if(c->rep[z]!=z) continue; |
---|
| 1105 | if (c->states[z][j]==UNCALCULATED){ |
---|
| 1106 | c->states[z][j]=UNIMPORTANT; |
---|
| 1107 | } |
---|
| 1108 | } |
---|
| 1109 | } |
---|
| 1110 | } |
---|
| 1111 | else { |
---|
| 1112 | c->states[i][j]=UNIMPORTANT; |
---|
| 1113 | } |
---|
| 1114 | if ((c->lengths[i]==1) && (c->lengths[j]==1)) |
---|
| 1115 | c->states[i][j]=HASTREP; |
---|
| 1116 | else if (pHasNotCF(c->S->m[i],c->S->m[j])){ |
---|
| 1117 | c->easy_product_crit++; |
---|
| 1118 | c->states[i][j]=HASTREP; |
---|
| 1119 | } |
---|
| 1120 | else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c)){ |
---|
| 1121 | c->states[i][j]=HASTREP; |
---|
| 1122 | c->extended_product_crit++; |
---|
| 1123 | //PrintS("E"); |
---|
| 1124 | } |
---|
| 1125 | if (c->states[i][j]==UNCALCULATED){ |
---|
| 1126 | |
---|
| 1127 | |
---|
| 1128 | // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r); |
---|
| 1129 | // if (short_s) |
---|
| 1130 | // { |
---|
[ec8a6b6] | 1131 | sorted_pair_node* s=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1132 | s->i=si_max(i,j); |
---|
| 1133 | s->j=si_min(i,j); |
---|
| 1134 | s->expected_length=c->lengths[i]+c->lengths[j]-2; |
---|
| 1135 | |
---|
| 1136 | poly lm=pOne(); |
---|
| 1137 | |
---|
| 1138 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 1139 | pSetm(lm); |
---|
| 1140 | s->deg=pTotaldegree(lm); |
---|
| 1141 | if(c->T_deg_full) |
---|
| 1142 | { |
---|
| 1143 | int t_i=c->T_deg_full[s->i]-c->T_deg[s->i]; |
---|
| 1144 | int t_j=c->T_deg_full[s->j]-c->T_deg[s->j]; |
---|
| 1145 | s->deg+=si_max(t_i,t_j); |
---|
| 1146 | } |
---|
| 1147 | s->lcm_of_lm=lm; |
---|
| 1148 | // pDelete(&short_s); |
---|
| 1149 | //assume(lm!=NULL); |
---|
| 1150 | nodes[spc]=s; |
---|
| 1151 | spc++; |
---|
| 1152 | // } |
---|
| 1153 | //else |
---|
| 1154 | //{ |
---|
| 1155 | //c->states[i][j]=HASTREP; |
---|
| 1156 | //} |
---|
| 1157 | } |
---|
| 1158 | } |
---|
| 1159 | |
---|
| 1160 | add_to_reductors(c, h, c->lengths[c->n-1]); |
---|
| 1161 | //i=posInS(c->strat,c->strat->sl,h,0 ecart); |
---|
| 1162 | |
---|
| 1163 | if (c->lengths[c->n-1]==1) |
---|
| 1164 | shorten_tails(c,c->S->m[c->n-1]); |
---|
| 1165 | //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths |
---|
| 1166 | |
---|
| 1167 | //for(i=c->strat->sl; i>0;i--) |
---|
| 1168 | // if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i); |
---|
| 1169 | if (c->Rcounter>50) { |
---|
| 1170 | c->Rcounter=0; |
---|
| 1171 | cleanS(c->strat,c); |
---|
| 1172 | } |
---|
| 1173 | if(!ip){ |
---|
| 1174 | qsort(nodes,spc,sizeof(sorted_pair_node*),pair_better_gen2); |
---|
| 1175 | |
---|
| 1176 | |
---|
| 1177 | c->apairs=merge(c->apairs,c->pair_top+1,nodes,spc,c); |
---|
| 1178 | c->pair_top+=spc; |
---|
| 1179 | clean_top_of_pair_list(c); |
---|
| 1180 | omfree(nodes); |
---|
| 1181 | return NULL; |
---|
| 1182 | } |
---|
| 1183 | { |
---|
| 1184 | *ip=spc; |
---|
| 1185 | return nodes; |
---|
| 1186 | } |
---|
| 1187 | |
---|
| 1188 | |
---|
| 1189 | |
---|
| 1190 | } |
---|
| 1191 | |
---|
| 1192 | |
---|
| 1193 | static int iq_crit(const void* ap,const void* bp){ |
---|
| 1194 | |
---|
| 1195 | sorted_pair_node* a=*((sorted_pair_node**)ap); |
---|
| 1196 | sorted_pair_node* b=*((sorted_pair_node**)bp); |
---|
| 1197 | assume(a->i>a->j); |
---|
| 1198 | assume(b->i>b->j); |
---|
| 1199 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 1200 | if(comp!=0) |
---|
| 1201 | return comp; |
---|
| 1202 | if (a->deg<b->deg) return -1; |
---|
| 1203 | if (a->deg>b->deg) return 1; |
---|
| 1204 | |
---|
| 1205 | |
---|
| 1206 | if (a->expected_length<b->expected_length) return -1; |
---|
| 1207 | if (a->expected_length>b->expected_length) return 1; |
---|
| 1208 | if (a->j>b->j) return 1; |
---|
| 1209 | if (a->j<b->j) return -1; |
---|
| 1210 | return 0; |
---|
| 1211 | } |
---|
| 1212 | |
---|
| 1213 | static sorted_pair_node** add_to_basis_ideal_quotient(poly h, int i_pos, int j_pos,calc_dat* c, int* ip) |
---|
| 1214 | { |
---|
| 1215 | |
---|
| 1216 | assume(h!=NULL); |
---|
| 1217 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 1218 | BOOLEAN R_found=FALSE; |
---|
| 1219 | void* hp; |
---|
| 1220 | |
---|
| 1221 | ++(c->n); |
---|
| 1222 | ++(c->S->ncols); |
---|
| 1223 | int i,j; |
---|
| 1224 | i=c->n-1; |
---|
[ec8a6b6] | 1225 | sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 1226 | int spc=0; |
---|
[ec8a6b6] | 1227 | c->T_deg=(int*) omrealloc(c->T_deg,c->n*sizeof(int)); |
---|
[4f858ce] | 1228 | c->T_deg[i]=pTotaldegree(h); |
---|
| 1229 | if(c->T_deg_full){ |
---|
[ec8a6b6] | 1230 | c->T_deg_full=(int*) omrealloc(c->T_deg_full,c->n*sizeof(int)); |
---|
[4f858ce] | 1231 | c->T_deg_full[i]=pTotaldegree_full(h); |
---|
| 1232 | } |
---|
[ec8a6b6] | 1233 | c->tmp_pair_lm=(poly*) omrealloc(c->tmp_pair_lm,c->n*sizeof(poly)); |
---|
[4f858ce] | 1234 | c->tmp_pair_lm[i]=pOne_Special(c->r); |
---|
[ec8a6b6] | 1235 | c->tmp_spn=(sorted_pair_node**) omrealloc(c->tmp_spn,c->n*sizeof(sorted_pair_node*)); |
---|
| 1236 | c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1237 | |
---|
[ec8a6b6] | 1238 | hp=omrealloc(c->rep, c->n *sizeof(int)); |
---|
[4f858ce] | 1239 | if (hp!=NULL){ |
---|
| 1240 | c->rep=(int*) hp; |
---|
| 1241 | } else { |
---|
| 1242 | exit(1); |
---|
| 1243 | } |
---|
[ec8a6b6] | 1244 | c->short_Exps=(long *) omrealloc(c->short_Exps ,c->n*sizeof(long)); |
---|
[4f858ce] | 1245 | |
---|
[ec8a6b6] | 1246 | hp=omrealloc(c->lengths, c->n *sizeof(int)); |
---|
[4f858ce] | 1247 | if (hp!=NULL){ |
---|
| 1248 | c->lengths=(int*) hp; |
---|
| 1249 | } else { |
---|
| 1250 | exit(1); |
---|
| 1251 | } |
---|
| 1252 | c->lengths[i]=pLength(h); |
---|
[ec8a6b6] | 1253 | hp=omrealloc(c->states, c->n * sizeof(char*)); |
---|
[4f858ce] | 1254 | |
---|
| 1255 | c->states=(char**) hp; |
---|
[ec8a6b6] | 1256 | c->gcd_of_terms=(poly*) omrealloc(c->gcd_of_terms, c->n *sizeof(poly)); |
---|
[4f858ce] | 1257 | c->gcd_of_terms[i]=gcd_of_terms(h,c->r); |
---|
| 1258 | c->rep[i]=i; |
---|
[ec8a6b6] | 1259 | hp=omalloc(i*sizeof(char)); |
---|
[4f858ce] | 1260 | if (hp!=NULL){ |
---|
| 1261 | c->states[i]=(char*) hp; |
---|
| 1262 | } else { |
---|
| 1263 | exit(1); |
---|
| 1264 | } |
---|
[ec8a6b6] | 1265 | hp=omrealloc(c->S->m,c->n*sizeof(poly)); |
---|
[4f858ce] | 1266 | if (hp!=NULL){ |
---|
| 1267 | c->S->m=(poly*) hp; |
---|
| 1268 | } else { |
---|
| 1269 | exit(1); |
---|
| 1270 | } |
---|
| 1271 | c->S->m[i]=h; |
---|
| 1272 | c->short_Exps[i]=p_GetShortExpVector(h,c->r); |
---|
| 1273 | for (j=0;j<i;j++){ |
---|
| 1274 | |
---|
| 1275 | //check product criterion |
---|
| 1276 | |
---|
| 1277 | c->states[i][j]=UNCALCULATED; |
---|
| 1278 | assume(p_LmDivisibleBy(c->S->m[i],c->S->m[j],c->r)== |
---|
| 1279 | p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)); |
---|
| 1280 | if(!c->F4_mode) |
---|
| 1281 | { |
---|
| 1282 | assume(!(p_LmDivisibleBy(c->S->m[j],c->S->m[i],c->r))); |
---|
| 1283 | } |
---|
| 1284 | //lies I[i] under I[j] ? |
---|
| 1285 | |
---|
| 1286 | if ((c->lengths[i]==1) && (c->lengths[j]==1)) |
---|
| 1287 | c->states[i][j]=HASTREP; |
---|
| 1288 | else if (pHasNotCF(c->S->m[i],c->S->m[j])) |
---|
| 1289 | { |
---|
| 1290 | c->easy_product_crit++; |
---|
| 1291 | c->states[i][j]=HASTREP; |
---|
| 1292 | } |
---|
| 1293 | else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c)) |
---|
| 1294 | { |
---|
| 1295 | c->states[i][j]=HASTREP; |
---|
| 1296 | c->extended_product_crit++; |
---|
| 1297 | //PrintS("E"); |
---|
| 1298 | } |
---|
| 1299 | // if (c->states[i][j]==UNCALCULATED){ |
---|
| 1300 | |
---|
| 1301 | |
---|
| 1302 | // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r); |
---|
| 1303 | // if (short_s) |
---|
| 1304 | // { |
---|
[ec8a6b6] | 1305 | sorted_pair_node* s=c->tmp_spn[j];//(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1306 | s->i=si_max(i,j); |
---|
| 1307 | s->j=si_min(i,j); |
---|
| 1308 | assume(s->j==j); |
---|
| 1309 | s->expected_length=c->lengths[i]+c->lengths[j]-2; |
---|
| 1310 | |
---|
| 1311 | poly lm=c->tmp_pair_lm[j];//=pOne_Special(); |
---|
| 1312 | |
---|
| 1313 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 1314 | pSetm(lm); |
---|
| 1315 | s->deg=pTotaldegree(lm); |
---|
| 1316 | if(c->T_deg_full) |
---|
| 1317 | { |
---|
| 1318 | int t_i=c->T_deg_full[s->i]-c->T_deg[s->i]; |
---|
| 1319 | int t_j=c->T_deg_full[s->j]-c->T_deg[s->j]; |
---|
| 1320 | s->deg+=si_max(t_i,t_j); |
---|
| 1321 | //Print("\n max: %d\n",max(t_i,t_j)); |
---|
| 1322 | } |
---|
| 1323 | s->lcm_of_lm=lm; |
---|
| 1324 | // pDelete(&short_s); |
---|
| 1325 | //assume(lm!=NULL); |
---|
| 1326 | nodes[spc]=s; |
---|
| 1327 | spc++; |
---|
| 1328 | // } |
---|
| 1329 | //else |
---|
| 1330 | //{ |
---|
| 1331 | //c->states[i][j]=HASTREP; |
---|
| 1332 | //} |
---|
| 1333 | } |
---|
| 1334 | |
---|
| 1335 | assume(spc==i); |
---|
| 1336 | //now ideal quotient crit |
---|
| 1337 | qsort(nodes,spc,sizeof(sorted_pair_node*),iq_crit); |
---|
| 1338 | |
---|
[ec8a6b6] | 1339 | sorted_pair_node** nodes_final=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 1340 | int spc_final=0; |
---|
| 1341 | j=0; |
---|
| 1342 | while(j<spc) |
---|
| 1343 | { |
---|
| 1344 | int lower=j; |
---|
| 1345 | int upper; |
---|
| 1346 | BOOLEAN has=FALSE; |
---|
| 1347 | for(upper=lower+1;upper<spc;upper++) |
---|
| 1348 | { |
---|
| 1349 | |
---|
| 1350 | if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm)) |
---|
| 1351 | { |
---|
| 1352 | break; |
---|
| 1353 | } |
---|
| 1354 | if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c)) |
---|
| 1355 | has=TRUE; |
---|
| 1356 | |
---|
| 1357 | } |
---|
| 1358 | upper=upper-1; |
---|
| 1359 | int z; |
---|
| 1360 | assume(spc_final<=j); |
---|
| 1361 | for(z=0;z<spc_final;z++) |
---|
| 1362 | { |
---|
| 1363 | if(p_LmDivisibleBy(nodes_final[z]->lcm_of_lm,nodes[lower]->lcm_of_lm,c->r)) |
---|
| 1364 | { |
---|
| 1365 | has=TRUE; |
---|
| 1366 | break; |
---|
| 1367 | } |
---|
| 1368 | } |
---|
| 1369 | |
---|
| 1370 | if(has) |
---|
| 1371 | { |
---|
| 1372 | for(;lower<=upper;lower++) |
---|
| 1373 | { |
---|
| 1374 | //free_sorted_pair_node(nodes[lower],c->r); |
---|
| 1375 | //omfree(nodes[lower]); |
---|
| 1376 | nodes[lower]=NULL; |
---|
| 1377 | } |
---|
| 1378 | j=upper+1; |
---|
| 1379 | continue; |
---|
| 1380 | } |
---|
| 1381 | else |
---|
| 1382 | { |
---|
| 1383 | nodes[lower]->lcm_of_lm=pCopy(nodes[lower]->lcm_of_lm); |
---|
| 1384 | nodes_final[spc_final++]=nodes[lower]; |
---|
[ec8a6b6] | 1385 | c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1386 | nodes[lower]=NULL; |
---|
| 1387 | for(lower=lower+1;lower<=upper;lower++) |
---|
| 1388 | { |
---|
| 1389 | // free_sorted_pair_node(nodes[lower],c->r); |
---|
| 1390 | //omfree(nodes[lower]); |
---|
| 1391 | nodes[lower]=NULL; |
---|
| 1392 | } |
---|
| 1393 | j=upper+1; |
---|
| 1394 | continue; |
---|
| 1395 | } |
---|
| 1396 | } |
---|
| 1397 | |
---|
| 1398 | // Print("i:%d,spc_final:%d",i,spc_final); |
---|
| 1399 | |
---|
| 1400 | |
---|
| 1401 | |
---|
| 1402 | |
---|
| 1403 | assume(spc_final<=spc); |
---|
| 1404 | omfree(nodes); |
---|
| 1405 | nodes=NULL; |
---|
| 1406 | |
---|
| 1407 | add_to_reductors(c, h, c->lengths[c->n-1]); |
---|
| 1408 | //i=posInS(c->strat,c->strat->sl,h,0 ecart); |
---|
| 1409 | |
---|
| 1410 | if (c->lengths[c->n-1]==1) |
---|
| 1411 | shorten_tails(c,c->S->m[c->n-1]); |
---|
| 1412 | //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths |
---|
| 1413 | |
---|
| 1414 | //for(i=c->strat->sl; i>0;i--) |
---|
| 1415 | // if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i); |
---|
| 1416 | if (c->Rcounter>50) { |
---|
| 1417 | c->Rcounter=0; |
---|
| 1418 | cleanS(c->strat,c); |
---|
| 1419 | } |
---|
| 1420 | if(!ip){ |
---|
| 1421 | qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),pair_better_gen2); |
---|
| 1422 | |
---|
| 1423 | |
---|
| 1424 | c->apairs=merge(c->apairs,c->pair_top+1,nodes_final,spc_final,c); |
---|
| 1425 | c->pair_top+=spc_final; |
---|
| 1426 | clean_top_of_pair_list(c); |
---|
| 1427 | omfree(nodes_final); |
---|
| 1428 | return NULL; |
---|
| 1429 | } |
---|
| 1430 | { |
---|
| 1431 | *ip=spc_final; |
---|
| 1432 | return nodes_final; |
---|
| 1433 | } |
---|
| 1434 | |
---|
| 1435 | |
---|
| 1436 | |
---|
| 1437 | } |
---|
| 1438 | |
---|
| 1439 | |
---|
| 1440 | |
---|
| 1441 | |
---|
| 1442 | |
---|
| 1443 | |
---|
| 1444 | #if 0 |
---|
| 1445 | static poly redNF (poly h,kStrategy strat) |
---|
| 1446 | { |
---|
| 1447 | int j = 0; |
---|
| 1448 | int z = 3; |
---|
| 1449 | unsigned long not_sev; |
---|
| 1450 | |
---|
| 1451 | if (0 > strat->sl) |
---|
| 1452 | { |
---|
| 1453 | return h; |
---|
| 1454 | } |
---|
| 1455 | not_sev = ~ pGetShortExpVector(h); |
---|
| 1456 | loop |
---|
| 1457 | { |
---|
| 1458 | if (pLmShortDivisibleBy(strat->S[j], strat->sevS[j], h, not_sev)) |
---|
| 1459 | { |
---|
| 1460 | //if (strat->interpt) test_int_std(strat->kIdeal); |
---|
| 1461 | /*- compute the s-polynomial -*/ |
---|
| 1462 | #ifdef KDEBUG |
---|
| 1463 | if (TEST_OPT_DEBUG) |
---|
| 1464 | { |
---|
| 1465 | |
---|
| 1466 | PrintS("red:"); |
---|
| 1467 | wrp(h); |
---|
| 1468 | PrintS(" with "); |
---|
| 1469 | wrp(strat->S[j]); |
---|
| 1470 | } |
---|
| 1471 | #endif |
---|
| 1472 | h = ksOldSpolyRed(strat->S[j],h,strat->kNoether); |
---|
| 1473 | #ifdef KDEBUG |
---|
| 1474 | if (TEST_OPT_DEBUG) |
---|
| 1475 | { |
---|
| 1476 | PrintS("\nto:"); |
---|
| 1477 | wrp(h); |
---|
| 1478 | PrintLn(); |
---|
| 1479 | } |
---|
| 1480 | #endif |
---|
| 1481 | if (h == NULL) return NULL; |
---|
| 1482 | z++; |
---|
| 1483 | if (z>=10) |
---|
| 1484 | { |
---|
| 1485 | z=0; |
---|
| 1486 | pNormalize(h); |
---|
| 1487 | } |
---|
| 1488 | /*- try to reduce the s-polynomial -*/ |
---|
| 1489 | j = 0; |
---|
| 1490 | not_sev = ~ pGetShortExpVector(h); |
---|
| 1491 | } |
---|
| 1492 | else |
---|
| 1493 | { |
---|
| 1494 | if (j >= strat->sl) return h; |
---|
| 1495 | j++; |
---|
| 1496 | } |
---|
| 1497 | } |
---|
| 1498 | } |
---|
| 1499 | #else |
---|
| 1500 | |
---|
| 1501 | static poly redNF2 (poly h,calc_dat* c , int &len, number& m,int n) |
---|
| 1502 | { |
---|
| 1503 | m=nInit(1); |
---|
| 1504 | if (h==NULL) return NULL; |
---|
| 1505 | |
---|
| 1506 | assume(len==pLength(h)); |
---|
| 1507 | kStrategy strat=c->strat; |
---|
| 1508 | if (0 > strat->sl) |
---|
| 1509 | { |
---|
| 1510 | return h; |
---|
| 1511 | } |
---|
| 1512 | int j; |
---|
| 1513 | |
---|
| 1514 | LObject P(h); |
---|
| 1515 | P.SetShortExpVector(); |
---|
| 1516 | P.bucket = kBucketCreate(currRing); |
---|
| 1517 | // BOOLEAN corr=lenS_correct(strat); |
---|
| 1518 | kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/); |
---|
| 1519 | //int max_pos=simple_posInS(strat,P.p); |
---|
| 1520 | loop |
---|
| 1521 | { |
---|
| 1522 | |
---|
| 1523 | j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P); |
---|
| 1524 | if ((j>=0) && ((!n)||(strat->lenS[j]<=n))) |
---|
| 1525 | { |
---|
| 1526 | |
---|
| 1527 | |
---|
| 1528 | nNormalize(pGetCoeff(P.p)); |
---|
| 1529 | #ifdef KDEBUG |
---|
| 1530 | if (TEST_OPT_DEBUG) |
---|
| 1531 | { |
---|
| 1532 | PrintS("red:"); |
---|
| 1533 | wrp(h); |
---|
| 1534 | PrintS(" with "); |
---|
| 1535 | wrp(strat->S[j]); |
---|
| 1536 | } |
---|
| 1537 | #endif |
---|
| 1538 | |
---|
| 1539 | number coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 1540 | strat->lenS[j]/*pLength(strat->S[j])*/, |
---|
| 1541 | strat->kNoether); |
---|
| 1542 | number m2=nMult(m,coef); |
---|
| 1543 | nDelete(&m); |
---|
| 1544 | m=m2; |
---|
| 1545 | nDelete(&coef); |
---|
| 1546 | h = kBucketGetLm(P.bucket); |
---|
| 1547 | |
---|
| 1548 | if (h==NULL) { |
---|
| 1549 | len=0; |
---|
| 1550 | kBucketDestroy(&P.bucket); |
---|
| 1551 | return |
---|
| 1552 | NULL;} |
---|
| 1553 | P.p=h; |
---|
| 1554 | P.t_p=NULL; |
---|
| 1555 | P.SetShortExpVector(); |
---|
| 1556 | #ifdef KDEBUG |
---|
| 1557 | if (TEST_OPT_DEBUG) |
---|
| 1558 | { |
---|
| 1559 | PrintS("\nto:"); |
---|
| 1560 | wrp(h); |
---|
| 1561 | PrintLn(); |
---|
| 1562 | } |
---|
| 1563 | #endif |
---|
| 1564 | } |
---|
| 1565 | else |
---|
| 1566 | { |
---|
| 1567 | kBucketClear(P.bucket,&(P.p),&len); |
---|
| 1568 | kBucketDestroy(&P.bucket); |
---|
| 1569 | pNormalize(P.p); |
---|
| 1570 | assume(len==(pLength(P.p))); |
---|
| 1571 | return P.p; |
---|
| 1572 | } |
---|
| 1573 | } |
---|
| 1574 | } |
---|
| 1575 | |
---|
| 1576 | |
---|
| 1577 | static poly redTailShort(poly h, kStrategy strat){ |
---|
| 1578 | |
---|
| 1579 | int sl=strat->sl; |
---|
| 1580 | int i; |
---|
| 1581 | int len=pLength(h); |
---|
| 1582 | for(i=0;i<=strat->sl;i++){ |
---|
| 1583 | if(strat->lenS[i]>2) |
---|
| 1584 | break; |
---|
| 1585 | } |
---|
| 1586 | return(redNFTail(h,i-1,strat, len)); |
---|
| 1587 | } |
---|
| 1588 | |
---|
| 1589 | static void line_of_extended_prod(int fixpos,calc_dat* c){ |
---|
| 1590 | if (c->gcd_of_terms[fixpos]==NULL) |
---|
| 1591 | { |
---|
| 1592 | c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r); |
---|
| 1593 | if (c->gcd_of_terms[fixpos]) |
---|
| 1594 | { |
---|
| 1595 | int i; |
---|
| 1596 | for(i=0;i<fixpos;i++) |
---|
| 1597 | 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))) |
---|
| 1598 | { |
---|
| 1599 | c->states[fixpos][i]=HASTREP; |
---|
| 1600 | c->extended_product_crit++; |
---|
| 1601 | } |
---|
| 1602 | for(i=fixpos+1;i<c->n;i++) |
---|
| 1603 | 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))) |
---|
| 1604 | { c->states[i][fixpos]=HASTREP; |
---|
| 1605 | c->extended_product_crit++; |
---|
| 1606 | } |
---|
| 1607 | } |
---|
| 1608 | } |
---|
| 1609 | } |
---|
| 1610 | static void c_S_element_changed_hook(int pos, calc_dat* c){ |
---|
| 1611 | length_one_crit(c,pos, c->lengths[pos]); |
---|
| 1612 | line_of_extended_prod(pos,c); |
---|
| 1613 | } |
---|
| 1614 | class poly_tree_node { |
---|
| 1615 | public: |
---|
| 1616 | poly p; |
---|
| 1617 | poly_tree_node* l; |
---|
| 1618 | poly_tree_node* r; |
---|
| 1619 | int n; |
---|
| 1620 | poly_tree_node(int sn):l(NULL),r(NULL),n(sn){} |
---|
| 1621 | }; |
---|
| 1622 | class exp_number_builder{ |
---|
| 1623 | public: |
---|
| 1624 | poly_tree_node* top_level; |
---|
| 1625 | int n; |
---|
| 1626 | int get_n(poly p); |
---|
| 1627 | exp_number_builder():top_level(0),n(0){} |
---|
| 1628 | }; |
---|
| 1629 | int exp_number_builder::get_n(poly p){ |
---|
| 1630 | poly_tree_node** node=&top_level; |
---|
| 1631 | while(*node!=NULL){ |
---|
| 1632 | int c=pLmCmp(p,(*node)->p); |
---|
| 1633 | if (c==0) return (*node)->n; |
---|
| 1634 | if (c==-1) node=&((*node)->r); |
---|
| 1635 | else |
---|
| 1636 | node=&((*node)->l); |
---|
| 1637 | } |
---|
| 1638 | (*node)= new poly_tree_node(n); |
---|
| 1639 | n++; |
---|
| 1640 | (*node)->p=pLmInit(p); |
---|
| 1641 | return (*node)->n; |
---|
| 1642 | } |
---|
| 1643 | |
---|
| 1644 | //mac_polys exp are smaller iff they are greater by monomial ordering |
---|
| 1645 | //corresponding to solving linear equations notation |
---|
[196cdf] | 1646 | |
---|
[b553e5] | 1647 | //! obsolete |
---|
[4f858ce] | 1648 | struct int_poly_pair{ |
---|
| 1649 | poly p; |
---|
| 1650 | int n; |
---|
| 1651 | }; |
---|
| 1652 | |
---|
[196cdf] | 1653 | |
---|
[b553e5] | 1654 | //! obsolete |
---|
[4f858ce] | 1655 | void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset){ |
---|
| 1656 | if(!k) return; |
---|
| 1657 | t2ippa_rec(ip,ia,k->l,offset); |
---|
| 1658 | ip[offset]=k->p; |
---|
| 1659 | ia[k->n]=offset; |
---|
| 1660 | ++offset; |
---|
| 1661 | |
---|
| 1662 | t2ippa_rec(ip,ia,k->r,offset); |
---|
| 1663 | delete k; |
---|
| 1664 | } |
---|
[196cdf] | 1665 | |
---|
[b553e5] | 1666 | //! obsolete |
---|
[4f858ce] | 1667 | void t2ippa(poly* ip,int* ia,exp_number_builder & e){ |
---|
| 1668 | |
---|
| 1669 | int o=0; |
---|
| 1670 | t2ippa_rec(ip,ia,e.top_level,o); |
---|
| 1671 | } |
---|
| 1672 | int anti_poly_order(const void* a, const void* b){ |
---|
| 1673 | return -pLmCmp(((int_poly_pair*) a)->p,((int_poly_pair*) b)->p ); |
---|
| 1674 | } |
---|
[81306a] | 1675 | |
---|
[4f858ce] | 1676 | BOOLEAN is_valid_ro(red_object & ro){ |
---|
| 1677 | red_object r2=ro; |
---|
| 1678 | ro.validate(); |
---|
| 1679 | if ((r2.p!=ro.p)||(r2.sev!=ro.sev)||(r2.sum!=ro.sum)) return FALSE; |
---|
| 1680 | return TRUE; |
---|
| 1681 | } |
---|
[196cdf] | 1682 | |
---|
| 1683 | //*obsolete |
---|
[4f858ce] | 1684 | void pre_comp(poly* p,int & pn,calc_dat* c){ |
---|
| 1685 | if(!(pn)) |
---|
| 1686 | return; |
---|
[ec8a6b6] | 1687 | mac_poly* q=(mac_poly*) omalloc(pn*sizeof(mac_poly)); |
---|
[4f858ce] | 1688 | int i; |
---|
| 1689 | exp_number_builder e; |
---|
| 1690 | for(i=0;i<pn;i++){ |
---|
| 1691 | assume(p[i]!=NULL); |
---|
| 1692 | q[i]=new mac_poly_r(); |
---|
| 1693 | q[i]->exp=e.get_n(p[i]); |
---|
| 1694 | q[i]->coef=nCopy(p[i]->coef); |
---|
| 1695 | |
---|
| 1696 | mac_poly qa=q[i]; |
---|
| 1697 | poly pa=p[i]; |
---|
| 1698 | while(pa->next!=NULL){ |
---|
| 1699 | qa->next = new mac_poly_r(); |
---|
| 1700 | qa=qa->next; |
---|
| 1701 | pa=pa->next, |
---|
| 1702 | qa->exp=e.get_n(pa); |
---|
| 1703 | qa->coef=nCopy(pa->coef); |
---|
| 1704 | |
---|
| 1705 | |
---|
| 1706 | } |
---|
| 1707 | qa->next=NULL; |
---|
| 1708 | pDelete(&p[i]); |
---|
| 1709 | } |
---|
[ec8a6b6] | 1710 | poly* ip= (poly*)omalloc (e.n*sizeof(poly)); |
---|
| 1711 | int* ia=(int*) omalloc (e.n*sizeof(int)); |
---|
[4f858ce] | 1712 | t2ippa(ip,ia,e); |
---|
| 1713 | for(i=0;i<pn;i++){ |
---|
| 1714 | mac_poly mp=q[i]; |
---|
| 1715 | while(mp!=NULL){ |
---|
| 1716 | mp->exp=ia[mp->exp]; |
---|
| 1717 | mp=mp->next; |
---|
| 1718 | } |
---|
| 1719 | |
---|
| 1720 | } |
---|
| 1721 | //gaus reduction start |
---|
| 1722 | int col, row; |
---|
| 1723 | col=0; |
---|
| 1724 | row=0; |
---|
| 1725 | assume(pn>0); |
---|
| 1726 | while(row<pn-1){ |
---|
| 1727 | //row is the row where pivot should be |
---|
| 1728 | // row== pn-1 means we have only to act on one row so no red nec. |
---|
| 1729 | //we assume further all rows till the pn-1 row are non-zero |
---|
| 1730 | |
---|
| 1731 | //select column |
---|
| 1732 | int i; |
---|
| 1733 | col=q[row]->exp; |
---|
| 1734 | int found_in_row=row; |
---|
| 1735 | for(i=row;i<pn;i++){ |
---|
| 1736 | if(q[i]->exp<col){ |
---|
| 1737 | col=q[i]->exp; |
---|
| 1738 | found_in_row=i; |
---|
| 1739 | } |
---|
| 1740 | |
---|
| 1741 | } |
---|
| 1742 | //select pivot |
---|
| 1743 | int act_l=mac_length(q[found_in_row]); |
---|
| 1744 | for(i=row+1;i<pn;i++){ |
---|
| 1745 | if((q[i]->exp==col)&&(mac_length(q[i])<act_l)){ |
---|
| 1746 | found_in_row=i; |
---|
| 1747 | act_l=mac_length(q[i]);//should be optimized here |
---|
| 1748 | } |
---|
| 1749 | } |
---|
| 1750 | mac_poly h=q[row]; |
---|
| 1751 | q[row]=q[found_in_row]; |
---|
| 1752 | q[found_in_row]=h; |
---|
| 1753 | |
---|
| 1754 | //reduction |
---|
| 1755 | for(i=row+1;i<pn;i++){ |
---|
| 1756 | if(q[i]->exp==q[row]->exp){ |
---|
| 1757 | |
---|
| 1758 | number c1=nNeg(nCopy(q[i]->coef)); |
---|
| 1759 | number c2=q[row]->coef; |
---|
| 1760 | //use checkcoeff later |
---|
| 1761 | mac_mult_cons(q[i],c2); |
---|
| 1762 | q[i]=mac_p_add_ff_qq(q[i],c1,q[row]); |
---|
| 1763 | } |
---|
| 1764 | |
---|
| 1765 | |
---|
| 1766 | |
---|
| 1767 | } |
---|
| 1768 | for(i=row+1;i<pn;i++){ |
---|
| 1769 | if(q[i]==NULL){ |
---|
| 1770 | q[i]=q[pn-1]; |
---|
| 1771 | pn--; |
---|
| 1772 | if(i!=pn){i--;} |
---|
| 1773 | } |
---|
| 1774 | } |
---|
| 1775 | |
---|
| 1776 | row++; |
---|
| 1777 | } |
---|
| 1778 | |
---|
| 1779 | |
---|
| 1780 | //gaus reduction end |
---|
| 1781 | |
---|
| 1782 | for(i=0;i<pn;i++){ |
---|
| 1783 | poly pa; |
---|
| 1784 | mac_poly qa; |
---|
| 1785 | p[i]=pLmInit(ip[q[i]->exp]); |
---|
| 1786 | pSetCoeff(p[i],q[i]->coef); |
---|
| 1787 | pa=p[i]; |
---|
| 1788 | qa=q[i]; |
---|
| 1789 | while(qa->next!=NULL){ |
---|
| 1790 | qa=qa->next; |
---|
| 1791 | pa->next=pLmInit(ip[qa->exp]); |
---|
| 1792 | pa=pa->next; |
---|
| 1793 | pa->coef=qa->coef; |
---|
| 1794 | } |
---|
| 1795 | pa->next=NULL; |
---|
| 1796 | } |
---|
| 1797 | for(i=0;i<e.n;i++){ |
---|
| 1798 | pDelete(&ip[i]); |
---|
| 1799 | } |
---|
| 1800 | omfree(ip); |
---|
| 1801 | omfree(ia); |
---|
| 1802 | } |
---|
| 1803 | |
---|
| 1804 | static void go_on (calc_dat* c){ |
---|
| 1805 | //set limit of 1000 for multireductions, at the moment for |
---|
| 1806 | //programming reasons |
---|
| 1807 | int i=0; |
---|
| 1808 | c->average_length=0; |
---|
| 1809 | for(i=0;i<c->n;i++){ |
---|
| 1810 | c->average_length+=c->lengths[i]; |
---|
| 1811 | } |
---|
| 1812 | c->average_length=c->average_length/c->n; |
---|
| 1813 | i=0; |
---|
[ec8a6b6] | 1814 | poly* p=(poly*) omalloc((PAR_N+1)*sizeof(poly));//nullterminated |
---|
[4f858ce] | 1815 | |
---|
| 1816 | int curr_deg=-1; |
---|
| 1817 | while(i<PAR_N){ |
---|
| 1818 | sorted_pair_node* s=top_pair(c);//here is actually chain criterium done |
---|
| 1819 | if (!s) break; |
---|
| 1820 | if(curr_deg>=0){ |
---|
| 1821 | if (s->deg >curr_deg) break; |
---|
| 1822 | } |
---|
| 1823 | |
---|
| 1824 | else curr_deg=s->deg; |
---|
| 1825 | quick_pop_pair(c); |
---|
| 1826 | if(s->i>=0){ |
---|
| 1827 | //replace_pair(s->i,s->j,c); |
---|
| 1828 | if(s->i==s->j) { |
---|
| 1829 | free_sorted_pair_node(s,c->r); |
---|
| 1830 | continue; |
---|
| 1831 | } |
---|
| 1832 | } |
---|
| 1833 | poly h; |
---|
| 1834 | if(s->i>=0) |
---|
| 1835 | h=ksOldCreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r); |
---|
| 1836 | else |
---|
| 1837 | h=s->lcm_of_lm; |
---|
| 1838 | if(s->i>=0) |
---|
| 1839 | now_t_rep(s->j,s->i,c); |
---|
| 1840 | number coef; |
---|
| 1841 | int mlen=pLength(h); |
---|
| 1842 | h=redNF2(h,c,mlen,coef,2); |
---|
| 1843 | redTailShort(h,c->strat); |
---|
| 1844 | nDelete(&coef); |
---|
| 1845 | |
---|
| 1846 | free_sorted_pair_node(s,c->r); |
---|
| 1847 | if(!h) continue; |
---|
| 1848 | int len=pLength(h); |
---|
| 1849 | p[i]=h; |
---|
| 1850 | |
---|
| 1851 | i++; |
---|
| 1852 | } |
---|
| 1853 | p[i]=NULL; |
---|
| 1854 | // pre_comp(p,i,c); |
---|
| 1855 | if(i==0){ |
---|
| 1856 | omfree(p); |
---|
| 1857 | return; |
---|
| 1858 | } |
---|
[ec8a6b6] | 1859 | red_object* buf=(red_object*) omalloc(i*sizeof(red_object)); |
---|
[4f858ce] | 1860 | c->normal_forms+=i; |
---|
| 1861 | int j; |
---|
| 1862 | for(j=0;j<i;j++){ |
---|
| 1863 | buf[j].p=p[j]; |
---|
| 1864 | buf[j].sev=pGetShortExpVector(p[j]); |
---|
| 1865 | buf[j].sum=NULL; |
---|
| 1866 | buf[j].bucket = kBucketCreate(currRing); |
---|
| 1867 | int len=pLength(p[j]); |
---|
| 1868 | kBucketInit(buf[j].bucket,buf[j].p,len); |
---|
| 1869 | } |
---|
| 1870 | omfree(p); |
---|
| 1871 | qsort(buf,i,sizeof(red_object),red_object_better_gen); |
---|
| 1872 | // Print("\ncurr_deg:%i\n",curr_deg); |
---|
| 1873 | if (TEST_OPT_PROT) |
---|
| 1874 | Print("M[%i, ",i); |
---|
| 1875 | #ifdef FIND_DETERMINISTIC |
---|
[ec8a6b6] | 1876 | c->modifiedS=(BOOLEAN*) omalloc((c->strat->sl+1)*sizeof(BOOLEAN)); |
---|
| 1877 | c->expandS=(poly*) omalloc((1)*sizeof(poly)); |
---|
[4f858ce] | 1878 | c->expandS[0]=NULL; |
---|
| 1879 | int z2; |
---|
| 1880 | for(z2=0;z2<=c->strat->sl;z2++) |
---|
| 1881 | c->modifiedS[z2]=FALSE; |
---|
| 1882 | #endif |
---|
| 1883 | multi_reduction(buf, i, c); |
---|
| 1884 | #ifdef TGB_DEBUG |
---|
| 1885 | { |
---|
| 1886 | int k; |
---|
| 1887 | for(k=0;k<i;k++) |
---|
| 1888 | { |
---|
| 1889 | assume(kFindDivisibleByInS_easy(c->strat,buf[k])<0); |
---|
| 1890 | int k2; |
---|
| 1891 | for(k2=0;k2<i;k2++) |
---|
| 1892 | { |
---|
| 1893 | if(k==k2) continue; |
---|
| 1894 | 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)); |
---|
| 1895 | } |
---|
| 1896 | } |
---|
| 1897 | } |
---|
| 1898 | #endif |
---|
| 1899 | //resort S |
---|
| 1900 | #ifdef FIND_DETERMINISTIC |
---|
| 1901 | for(z2=0;z2<=c->strat->sl;z2++) |
---|
| 1902 | { |
---|
| 1903 | if (c->modifiedS[z2]) |
---|
| 1904 | { |
---|
| 1905 | int qal; |
---|
| 1906 | if (c->strat->lenSw) |
---|
| 1907 | qal=c->strat->lenSw[z2]; |
---|
| 1908 | else |
---|
| 1909 | qal=c->strat->lenS[z2]; |
---|
| 1910 | int new_pos=simple_posInS(c->strat,c->strat->S[z2],qal); |
---|
| 1911 | if (new_pos<z2) |
---|
| 1912 | { |
---|
| 1913 | move_forward_in_S(z2,new_pos,c->strat); |
---|
| 1914 | } |
---|
| 1915 | } |
---|
| 1916 | } |
---|
| 1917 | for(z2=0;c->expandS[z2]!=NULL;z2++) |
---|
| 1918 | { |
---|
| 1919 | add_to_reductors(c,c->expandS[z2],pLength(c->expandS[z2])); |
---|
| 1920 | // PrintS("E"); |
---|
| 1921 | } |
---|
| 1922 | omfree(c->modifiedS); |
---|
| 1923 | c->modifiedS=NULL; |
---|
| 1924 | omfree(c->expandS); |
---|
| 1925 | c->expandS=NULL; |
---|
| 1926 | #endif |
---|
| 1927 | if (TEST_OPT_PROT) |
---|
| 1928 | Print("%i]",i); |
---|
| 1929 | // for(j=0;j<i;j++){ |
---|
| 1930 | // if(buf[j].p==NULL) PrintS("\n ZERO ALERT \n"); |
---|
| 1931 | // int z; |
---|
| 1932 | // for(z=0;z<j;z++){ |
---|
| 1933 | // if (pLmEqual(buf[z].p, buf[j].p)) |
---|
| 1934 | // PrintS("\n Critical Warning!!!! \n"); |
---|
| 1935 | |
---|
| 1936 | // } |
---|
| 1937 | // } |
---|
[ec8a6b6] | 1938 | int* ibuf=(int*) omalloc(i*sizeof(int)); |
---|
| 1939 | sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(i*sizeof(sorted_pair_node**)); |
---|
[4f858ce] | 1940 | for(j=0;j<i;j++) |
---|
| 1941 | { |
---|
| 1942 | int len; |
---|
| 1943 | poly p; |
---|
| 1944 | buf[j].flatten(); |
---|
| 1945 | kBucketClear(buf[j].bucket,&p, &len); |
---|
| 1946 | kBucketDestroy(&buf[j].bucket); |
---|
| 1947 | // delete buf[j]; |
---|
| 1948 | //remember to free res here |
---|
| 1949 | p=redTailShort(p, c->strat); |
---|
| 1950 | sbuf[j]=add_to_basis_ideal_quotient(p,-1,-1,c,ibuf+j); |
---|
| 1951 | //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j); |
---|
| 1952 | } |
---|
| 1953 | int sum=0; |
---|
| 1954 | for(j=0;j<i;j++){ |
---|
| 1955 | sum+=ibuf[j]; |
---|
| 1956 | } |
---|
[ec8a6b6] | 1957 | sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 1958 | int partsum=0; |
---|
| 1959 | for(j=0;j<i;j++) |
---|
| 1960 | { |
---|
| 1961 | memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*)); |
---|
| 1962 | omfree(sbuf[j]); |
---|
| 1963 | partsum+=ibuf[j]; |
---|
| 1964 | } |
---|
| 1965 | |
---|
| 1966 | qsort(big_sbuf,sum,sizeof(sorted_pair_node*),pair_better_gen2); |
---|
| 1967 | c->apairs=merge(c->apairs,c->pair_top+1,big_sbuf,sum,c); |
---|
| 1968 | c->pair_top+=sum; |
---|
| 1969 | clean_top_of_pair_list(c); |
---|
| 1970 | omfree(big_sbuf); |
---|
| 1971 | omfree(sbuf); |
---|
| 1972 | omfree(ibuf); |
---|
| 1973 | omfree(buf); |
---|
| 1974 | #ifdef TGB_DEBUG |
---|
| 1975 | int z; |
---|
| 1976 | for(z=1;z<=c->pair_top;z++) |
---|
| 1977 | { |
---|
| 1978 | assume(pair_better(c->apairs[z],c->apairs[z-1],c)); |
---|
| 1979 | } |
---|
| 1980 | #endif |
---|
| 1981 | return; |
---|
| 1982 | } |
---|
| 1983 | |
---|
| 1984 | static poly redNF (poly h,kStrategy strat, int &len) |
---|
| 1985 | { |
---|
| 1986 | len=0; |
---|
| 1987 | if (h==NULL) return NULL; |
---|
| 1988 | int j; |
---|
| 1989 | |
---|
| 1990 | len=pLength(h); |
---|
| 1991 | if (0 > strat->sl) |
---|
| 1992 | { |
---|
| 1993 | return h; |
---|
| 1994 | } |
---|
| 1995 | LObject P(h); |
---|
| 1996 | P.SetShortExpVector(); |
---|
| 1997 | P.bucket = kBucketCreate(currRing); |
---|
| 1998 | kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/); |
---|
| 1999 | //int max_pos=simple_posInS(strat,P.p); |
---|
| 2000 | loop |
---|
| 2001 | { |
---|
| 2002 | j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P); |
---|
| 2003 | if (j>=0) |
---|
| 2004 | { |
---|
| 2005 | nNormalize(pGetCoeff(P.p)); |
---|
| 2006 | #ifdef KDEBUG |
---|
| 2007 | if (TEST_OPT_DEBUG) |
---|
| 2008 | { |
---|
| 2009 | PrintS("red:"); |
---|
| 2010 | wrp(h); |
---|
| 2011 | PrintS(" with "); |
---|
| 2012 | wrp(strat->S[j]); |
---|
| 2013 | } |
---|
| 2014 | #endif |
---|
| 2015 | number coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 2016 | strat->lenS[j]/*pLength(strat->S[j])*/, |
---|
| 2017 | strat->kNoether); |
---|
| 2018 | nDelete(&coef); |
---|
| 2019 | h = kBucketGetLm(P.bucket); |
---|
| 2020 | if (h==NULL) return NULL; |
---|
| 2021 | P.p=h; |
---|
| 2022 | P.t_p=NULL; |
---|
| 2023 | P.SetShortExpVector(); |
---|
| 2024 | #ifdef KDEBUG |
---|
| 2025 | if (TEST_OPT_DEBUG) |
---|
| 2026 | { |
---|
| 2027 | PrintS("\nto:"); |
---|
| 2028 | wrp(h); |
---|
| 2029 | PrintLn(); |
---|
| 2030 | } |
---|
| 2031 | #endif |
---|
| 2032 | } |
---|
| 2033 | else |
---|
| 2034 | { |
---|
| 2035 | kBucketClear(P.bucket,&(P.p),&len); |
---|
| 2036 | kBucketDestroy(&P.bucket); |
---|
| 2037 | pNormalize(P.p); |
---|
| 2038 | return P.p; |
---|
| 2039 | } |
---|
| 2040 | } |
---|
| 2041 | } |
---|
| 2042 | #endif |
---|
| 2043 | #ifdef REDTAIL_S |
---|
| 2044 | |
---|
| 2045 | static poly redNFTail (poly h,const int sl,kStrategy strat, int len) |
---|
| 2046 | { |
---|
| 2047 | if (h==NULL) return NULL; |
---|
| 2048 | pTest(h); |
---|
| 2049 | if (0 > sl) |
---|
| 2050 | return h; |
---|
| 2051 | if (pNext(h)==NULL) return h; |
---|
| 2052 | |
---|
| 2053 | int j; |
---|
| 2054 | poly res=h; |
---|
| 2055 | poly act=res; |
---|
| 2056 | LObject P(pNext(h)); |
---|
| 2057 | pNext(res)=NULL; |
---|
| 2058 | P.bucket = kBucketCreate(currRing); |
---|
| 2059 | len--; |
---|
| 2060 | h=P.p; |
---|
| 2061 | if (len <=0) len=pLength(h); |
---|
| 2062 | kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/); |
---|
| 2063 | pTest(h); |
---|
| 2064 | loop |
---|
| 2065 | { |
---|
| 2066 | P.p=h; |
---|
| 2067 | P.t_p=NULL; |
---|
| 2068 | P.SetShortExpVector(); |
---|
| 2069 | loop |
---|
| 2070 | { |
---|
| 2071 | j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P); |
---|
| 2072 | if (j>=0) |
---|
| 2073 | { |
---|
| 2074 | #ifdef REDTAIL_PROT |
---|
| 2075 | PrintS("r"); |
---|
| 2076 | #endif |
---|
| 2077 | nNormalize(pGetCoeff(P.p)); |
---|
| 2078 | #ifdef KDEBUG |
---|
| 2079 | if (TEST_OPT_DEBUG) |
---|
| 2080 | { |
---|
| 2081 | PrintS("red tail:"); |
---|
| 2082 | wrp(h); |
---|
| 2083 | PrintS(" with "); |
---|
| 2084 | wrp(strat->S[j]); |
---|
| 2085 | } |
---|
| 2086 | #endif |
---|
| 2087 | number coef; |
---|
| 2088 | pTest(strat->S[j]); |
---|
| 2089 | coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 2090 | strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether); |
---|
| 2091 | pMult_nn(res,coef); |
---|
| 2092 | nDelete(&coef); |
---|
| 2093 | h = kBucketGetLm(P.bucket); |
---|
| 2094 | pTest(h); |
---|
| 2095 | if (h==NULL) |
---|
| 2096 | { |
---|
| 2097 | #ifdef REDTAIL_PROT |
---|
| 2098 | PrintS(" "); |
---|
| 2099 | #endif |
---|
| 2100 | kBucketDestroy(&P.bucket); |
---|
| 2101 | return res; |
---|
| 2102 | } |
---|
| 2103 | pTest(h); |
---|
| 2104 | P.p=h; |
---|
| 2105 | P.t_p=NULL; |
---|
| 2106 | P.SetShortExpVector(); |
---|
| 2107 | #ifdef KDEBUG |
---|
| 2108 | if (TEST_OPT_DEBUG) |
---|
| 2109 | { |
---|
| 2110 | PrintS("\nto tail:"); |
---|
| 2111 | wrp(h); |
---|
| 2112 | PrintLn(); |
---|
| 2113 | } |
---|
| 2114 | #endif |
---|
| 2115 | } |
---|
| 2116 | else |
---|
| 2117 | { |
---|
| 2118 | #ifdef REDTAIL_PROT |
---|
| 2119 | PrintS("n"); |
---|
| 2120 | #endif |
---|
| 2121 | break; |
---|
| 2122 | } |
---|
| 2123 | } /* end loop current mon */ |
---|
| 2124 | // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/); |
---|
| 2125 | //act->next=tmp;pIter(act); |
---|
| 2126 | act->next=kBucketExtractLm(P.bucket);pIter(act); |
---|
| 2127 | h = kBucketGetLm(P.bucket); |
---|
| 2128 | if (h==NULL) |
---|
| 2129 | { |
---|
| 2130 | #ifdef REDTAIL_PROT |
---|
| 2131 | PrintS(" "); |
---|
| 2132 | #endif |
---|
| 2133 | kBucketDestroy(&P.bucket); |
---|
| 2134 | return res; |
---|
| 2135 | } |
---|
| 2136 | pTest(h); |
---|
| 2137 | } |
---|
| 2138 | } |
---|
| 2139 | #endif |
---|
| 2140 | |
---|
| 2141 | static void do_this_spoly_stuff(int i,int j,calc_dat* c){ |
---|
| 2142 | poly f=c->S->m[i]; |
---|
| 2143 | poly g=c->S->m[j]; |
---|
| 2144 | poly h=ksOldCreateSpoly(f, g, NULL, c->r); |
---|
| 2145 | poly hr=NULL; |
---|
| 2146 | #ifdef FULLREDUCTIONS |
---|
| 2147 | if (h!=NULL) |
---|
| 2148 | { |
---|
| 2149 | int len; |
---|
| 2150 | |
---|
| 2151 | // hr=redNF2(h,c,len); |
---|
| 2152 | // hr=redNF(h,c->strat,len); |
---|
| 2153 | |
---|
| 2154 | if (hr!=NULL) |
---|
| 2155 | #ifdef REDTAIL_S |
---|
| 2156 | hr = redNFTail(hr,c->strat->sl,c->strat,len); |
---|
| 2157 | #else |
---|
| 2158 | hr = redtailBba(hr,c->strat->sl,c->strat); |
---|
| 2159 | #endif |
---|
| 2160 | |
---|
| 2161 | } |
---|
| 2162 | #else |
---|
| 2163 | if (h!=NULL) |
---|
| 2164 | { |
---|
| 2165 | int len; |
---|
| 2166 | // hr=redNF2(h,c,len); |
---|
| 2167 | } |
---|
| 2168 | #endif |
---|
| 2169 | c->normal_forms++; |
---|
| 2170 | if (hr==NULL) |
---|
| 2171 | { |
---|
| 2172 | notice_miss(i, j, c); |
---|
| 2173 | |
---|
| 2174 | } |
---|
| 2175 | else |
---|
| 2176 | { |
---|
| 2177 | |
---|
| 2178 | #ifdef HEAD_BIN |
---|
| 2179 | hr=p_MoveHead(hr,c->HeadBin); |
---|
| 2180 | #endif |
---|
| 2181 | add_to_basis(hr, i,j,c); |
---|
| 2182 | } |
---|
| 2183 | } |
---|
| 2184 | //try to fill, return FALSE iff queue is empty |
---|
| 2185 | static void simplify(monom_poly& h, calc_dat* c){ |
---|
| 2186 | mp_array_list* F=c->F; |
---|
| 2187 | poly_array_list* F_minus=c->F_minus; |
---|
| 2188 | while(F) |
---|
| 2189 | { |
---|
| 2190 | assume(F_minus!=NULL); |
---|
| 2191 | int i; |
---|
| 2192 | int posm=posInMonomPolys (F->mp, F->size, h,c); |
---|
| 2193 | #ifdef TGB_DEBUG |
---|
| 2194 | #endif |
---|
| 2195 | //for(i=0;i<F->size;i++) |
---|
| 2196 | for(i=si_min(posm,F->size-1);i>=0;i--) |
---|
| 2197 | { |
---|
| 2198 | // if((i>=posm)&&(F->mp[i].f!=h.f)) break; |
---|
| 2199 | if((i<posm)&&(F->mp[i].f!=h.f)) break; |
---|
| 2200 | if ((h.f==F->mp[i].f) &&(p_LmDivisibleBy(F->mp[i].m,h.m,c->r))) |
---|
| 2201 | { |
---|
| 2202 | |
---|
| 2203 | // Print("found"); |
---|
| 2204 | |
---|
| 2205 | //according to the algorithm you should test (!(pIsConstant(F[i].m))) |
---|
| 2206 | //but I think this is only because of bad formulation |
---|
| 2207 | int j; |
---|
| 2208 | |
---|
| 2209 | poly lm=pLmInit(h.f); |
---|
| 2210 | pSetCoeff(lm,nInit(1)); |
---|
| 2211 | |
---|
| 2212 | lm=pMult_mm(lm,F->mp[i].m); |
---|
| 2213 | |
---|
| 2214 | int pos; |
---|
| 2215 | j=-1; |
---|
| 2216 | pos=posInPolys (F_minus->p, F_minus->size, lm,c); |
---|
| 2217 | if((F_minus->size>pos)&&(pLmEqual(lm,F_minus->p[pos]))) |
---|
| 2218 | j=pos; |
---|
| 2219 | if((pos>0) &&(pLmEqual(lm,F_minus->p[pos-1]))) |
---|
| 2220 | j=pos-1; |
---|
| 2221 | assume(j!=-1); |
---|
| 2222 | // if(j==-1) Print("\n jAltert \n"); |
---|
| 2223 | // for(j=0;j<F_minus->size;j++) |
---|
| 2224 | // { |
---|
| 2225 | // if (pLmEqual(F_minus->p[j],lm)) |
---|
| 2226 | // break; |
---|
| 2227 | // } |
---|
| 2228 | // assume(j<F_minus->size); |
---|
| 2229 | pDelete(&lm); |
---|
| 2230 | if(j>=0) |
---|
| 2231 | { |
---|
| 2232 | pExpVectorSub(h.m,F->mp[i].m); |
---|
| 2233 | h.f=F_minus->p[j]; |
---|
| 2234 | } |
---|
| 2235 | break; |
---|
| 2236 | } |
---|
| 2237 | } |
---|
| 2238 | F=F->next; |
---|
| 2239 | F_minus=F_minus->next; |
---|
| 2240 | } |
---|
| 2241 | assume(F_minus==NULL); |
---|
| 2242 | } |
---|
| 2243 | |
---|
| 2244 | //transfers ownership of m to mat |
---|
| 2245 | void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m){ |
---|
| 2246 | assume(mat->mp[row]==NULL); |
---|
| 2247 | mat->mp[row]=m; |
---|
| 2248 | #ifdef TGB_DEBUG |
---|
| 2249 | mac_poly r=m; |
---|
| 2250 | while(r){ |
---|
| 2251 | assume(r->exp<mat->columns); |
---|
| 2252 | r=r->next; |
---|
| 2253 | } |
---|
| 2254 | #endif |
---|
| 2255 | } |
---|
| 2256 | poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index){ |
---|
| 2257 | poly p=NULL; |
---|
| 2258 | poly* set_this=&p; |
---|
| 2259 | mac_poly r=mat->mp[row]; |
---|
| 2260 | mat->mp[row]=NULL; |
---|
| 2261 | while(r) |
---|
| 2262 | { |
---|
| 2263 | (*set_this)=pLmInit(monoms[monom_index-1-r->exp]); |
---|
| 2264 | pSetCoeff((*set_this),r->coef); |
---|
| 2265 | set_this=&((*set_this)->next); |
---|
| 2266 | mac_poly old=r; |
---|
| 2267 | r=r->next; |
---|
| 2268 | delete old; |
---|
| 2269 | |
---|
| 2270 | } |
---|
| 2271 | return p; |
---|
| 2272 | |
---|
| 2273 | } |
---|
| 2274 | |
---|
| 2275 | |
---|
| 2276 | |
---|
| 2277 | static tgb_matrix* build_matrix(poly* p,int p_index,poly* done, int done_index, calc_dat* c){ |
---|
| 2278 | tgb_matrix* t=new tgb_matrix(p_index,done_index); |
---|
| 2279 | int i, pos; |
---|
| 2280 | // Print("\n 0:%s\n",pString(done[done_index-1])); |
---|
| 2281 | //Print("\n 1:%s\n",pString(done[done_index-2])); |
---|
| 2282 | assume((!(pLmEqual(done[done_index-1],done[done_index-2])))); |
---|
| 2283 | #ifdef TGB_DEGUG |
---|
| 2284 | for(i=0;i<done_index;i++) |
---|
| 2285 | { |
---|
| 2286 | int j; |
---|
| 2287 | for(j=0;j<i;j++) |
---|
| 2288 | { |
---|
| 2289 | assume((!(pLmEqual(done[i],done[j])))); |
---|
| 2290 | } |
---|
| 2291 | } |
---|
| 2292 | #endif |
---|
| 2293 | for(i=0;i<p_index;i++) |
---|
| 2294 | { |
---|
| 2295 | // Print("%i ter Eintrag:%s\n",i,pString(p[i])); |
---|
| 2296 | poly p_i=p[i]; |
---|
| 2297 | while(p_i) |
---|
| 2298 | { |
---|
| 2299 | |
---|
| 2300 | int v=-1; |
---|
| 2301 | pos=posInPolys (done, done_index, p_i,c); |
---|
| 2302 | if((done_index>pos)&&(pLmEqual(p_i,done[pos]))) |
---|
| 2303 | v=pos; |
---|
| 2304 | if((pos>0) &&(pLmEqual(p_i,done[pos-1]))) |
---|
| 2305 | v=pos-1; |
---|
| 2306 | assume(v!=-1); |
---|
| 2307 | //v is ascending ordered, we need descending order |
---|
| 2308 | v=done_index-1-v; |
---|
| 2309 | number nt=t->get(i,v); |
---|
| 2310 | nDelete(&nt); |
---|
| 2311 | t->set(i,v,nCopy(p_i->coef)); |
---|
| 2312 | p_i=p_i->next; |
---|
| 2313 | } |
---|
| 2314 | } |
---|
| 2315 | return t; |
---|
| 2316 | } |
---|
| 2317 | static tgb_sparse_matrix* build_sparse_matrix(poly* p,int p_index,poly* done, int done_index, calc_dat* c){ |
---|
| 2318 | tgb_sparse_matrix* t=new tgb_sparse_matrix(p_index,done_index,c->r); |
---|
| 2319 | int i, pos; |
---|
| 2320 | // Print("\n 0:%s\n",pString(done[done_index-1])); |
---|
| 2321 | //Print("\n 1:%s\n",pString(done[done_index-2])); |
---|
| 2322 | // assume((!(pLmEqual(done[done_index-1],done[done_index-2])))); |
---|
| 2323 | #ifdef TGB_DEGUG |
---|
| 2324 | for(i=0;i<done_index;i++) |
---|
| 2325 | { |
---|
| 2326 | int j; |
---|
| 2327 | for(j=0;j<i;j++) |
---|
| 2328 | { |
---|
| 2329 | assume((!(pLmEqual(done[i],done[j])))); |
---|
| 2330 | } |
---|
| 2331 | } |
---|
| 2332 | #endif |
---|
| 2333 | for(i=0;i<p_index;i++) |
---|
| 2334 | { |
---|
| 2335 | // Print("%i ter Eintrag:%s\n",i,pString(p[i])); |
---|
| 2336 | mac_poly m=NULL; |
---|
| 2337 | mac_poly* set_this=&m; |
---|
| 2338 | poly p_i=p[i]; |
---|
| 2339 | while(p_i) |
---|
| 2340 | { |
---|
| 2341 | |
---|
| 2342 | int v=-1; |
---|
| 2343 | pos=posInPolys (done, done_index, p_i,c); |
---|
| 2344 | if((done_index>pos)&&(pLmEqual(p_i,done[pos]))) |
---|
| 2345 | v=pos; |
---|
| 2346 | if((pos>0) &&(pLmEqual(p_i,done[pos-1]))) |
---|
| 2347 | v=pos-1; |
---|
| 2348 | assume(v!=-1); |
---|
| 2349 | //v is ascending ordered, we need descending order |
---|
| 2350 | v=done_index-1-v; |
---|
| 2351 | (*set_this)=new mac_poly_r(); |
---|
| 2352 | (*set_this)->exp=v; |
---|
| 2353 | |
---|
| 2354 | (*set_this)->coef=nCopy(p_i->coef); |
---|
| 2355 | set_this=&(*set_this)->next; |
---|
| 2356 | p_i=p_i->next; |
---|
| 2357 | |
---|
| 2358 | } |
---|
| 2359 | init_with_mac_poly(t,i,m); |
---|
| 2360 | } |
---|
| 2361 | return t; |
---|
| 2362 | } |
---|
| 2363 | |
---|
| 2364 | |
---|
| 2365 | static int retranslate(poly* m,tgb_sparse_matrix* mat,poly* done, calc_dat* c){ |
---|
| 2366 | int i; |
---|
| 2367 | int m_index=0; |
---|
| 2368 | for(i=0;i<mat->get_rows();i++) |
---|
| 2369 | { |
---|
| 2370 | if(mat->zero_row(i)) |
---|
| 2371 | { |
---|
| 2372 | mat->free_row(i); |
---|
| 2373 | continue; |
---|
| 2374 | } |
---|
| 2375 | m[m_index++]= free_row_to_poly(mat, i, done, mat->get_columns()); |
---|
| 2376 | |
---|
| 2377 | } |
---|
| 2378 | |
---|
| 2379 | delete mat; |
---|
| 2380 | return m_index; |
---|
| 2381 | |
---|
| 2382 | } |
---|
| 2383 | |
---|
| 2384 | //returns m_index and destroys mat |
---|
| 2385 | static int retranslate(poly* m,tgb_matrix* mat,poly* done, calc_dat* c){ |
---|
| 2386 | int i; |
---|
| 2387 | int m_index=0; |
---|
| 2388 | for(i=0;i<mat->get_rows();i++) |
---|
| 2389 | { |
---|
| 2390 | if(mat->zero_row(i)) |
---|
| 2391 | { |
---|
| 2392 | mat->free_row(i); |
---|
| 2393 | continue; |
---|
| 2394 | } |
---|
| 2395 | |
---|
| 2396 | m[m_index]=pInit(); |
---|
| 2397 | int v=mat->min_col_not_zero_in_row(i); |
---|
| 2398 | //v=done_index-1-pos; => pos=done_index-1-v=mat->get_columns()-1-v |
---|
| 2399 | int pos=mat->get_columns()-1-v; |
---|
[ec8a6b6] | 2400 | int* ev=(int*) omalloc((c->r->N+1)*sizeof(int)); |
---|
[4f858ce] | 2401 | pGetExpV(done[pos],ev); |
---|
| 2402 | pSetExpV(m[m_index],ev); |
---|
| 2403 | omfree(ev); |
---|
| 2404 | |
---|
| 2405 | poly p=m[m_index]; |
---|
| 2406 | pSetCoeff(p,mat->get(i,v)); |
---|
| 2407 | while((v=mat->next_col_not_zero(i,v))!=mat->get_columns()) |
---|
| 2408 | { |
---|
| 2409 | poly pn=pInit(); |
---|
| 2410 | |
---|
| 2411 | //v=done_index-1-pos; => pos=done_index-1-v=mat->get_columns()-1-v |
---|
| 2412 | pos=mat->get_columns()-1-v; |
---|
[ec8a6b6] | 2413 | ev=(int*) omalloc((c->r->N+1)*sizeof(int)); |
---|
[4f858ce] | 2414 | pGetExpV(done[pos],ev); |
---|
| 2415 | pSetExpV(pn,ev); |
---|
| 2416 | omfree(ev); |
---|
| 2417 | pSetCoeff(pn,mat->get(i,v)); |
---|
| 2418 | p->next=pn; |
---|
| 2419 | p=pn; |
---|
| 2420 | } |
---|
| 2421 | p->next=NULL; |
---|
| 2422 | mat->free_row(i, FALSE); |
---|
| 2423 | m_index++; |
---|
| 2424 | } |
---|
| 2425 | |
---|
| 2426 | delete mat; |
---|
| 2427 | return m_index; |
---|
| 2428 | |
---|
| 2429 | } |
---|
| 2430 | static void go_on_F4 (calc_dat* c){ |
---|
| 2431 | //set limit of 1000 for multireductions, at the moment for |
---|
| 2432 | //programming reasons |
---|
| 2433 | int max_par; |
---|
| 2434 | if (c->is_homog) |
---|
| 2435 | max_par=PAR_N_F4; |
---|
| 2436 | else |
---|
| 2437 | max_par=200; |
---|
| 2438 | int done_size=max_par*2; |
---|
[ec8a6b6] | 2439 | poly* done=(poly*) omalloc(done_size*sizeof(poly)); |
---|
[4f858ce] | 2440 | int done_index=0; //done_index must always be smaller than done_size |
---|
| 2441 | int chosen_size=max_par*2; |
---|
[ec8a6b6] | 2442 | monom_poly* chosen=(monom_poly*) omalloc(chosen_size*sizeof(monom_poly)); |
---|
[4f858ce] | 2443 | int chosen_index=0; |
---|
[ec8a6b6] | 2444 | // monom_poly* vgl=(monom_poly*) omalloc(chosen_size*sizeof(monom_poly)); |
---|
[4f858ce] | 2445 | int i=0; |
---|
| 2446 | c->average_length=0; |
---|
| 2447 | for(i=0;i<c->n;i++){ |
---|
| 2448 | c->average_length+=c->lengths[i]; |
---|
| 2449 | } |
---|
| 2450 | c->average_length=c->average_length/c->n; |
---|
| 2451 | i=0; |
---|
| 2452 | poly* p; |
---|
| 2453 | int nfs=0; |
---|
| 2454 | int curr_deg=-1; |
---|
| 2455 | |
---|
| 2456 | //choose pairs and preprocess symbolically |
---|
| 2457 | while(chosen_index<max_par) |
---|
| 2458 | { |
---|
| 2459 | |
---|
| 2460 | // sorted_pair_node* s=c->apairs[c->pair_top]; |
---|
| 2461 | sorted_pair_node* s; |
---|
| 2462 | if(c->pair_top>=0) |
---|
| 2463 | s=top_pair(c);//here is actually chain criterium done |
---|
| 2464 | else |
---|
| 2465 | s=NULL; |
---|
| 2466 | if (!s) break; |
---|
| 2467 | nfs++; |
---|
| 2468 | if(curr_deg>=0) |
---|
| 2469 | { |
---|
| 2470 | if (s->deg >curr_deg) break; |
---|
| 2471 | } |
---|
| 2472 | |
---|
| 2473 | else curr_deg=s->deg; |
---|
| 2474 | quick_pop_pair(c); |
---|
| 2475 | if(s->i>=0) |
---|
| 2476 | { |
---|
| 2477 | //replace_pair(s->i,s->j,c); |
---|
| 2478 | if(s->i==s->j) |
---|
| 2479 | { |
---|
| 2480 | free_sorted_pair_node(s,c->r); |
---|
| 2481 | continue; |
---|
| 2482 | } |
---|
| 2483 | } |
---|
| 2484 | assume(s->i>=0); |
---|
| 2485 | monom_poly h; |
---|
| 2486 | BOOLEAN only_free=FALSE; |
---|
| 2487 | if(s->i>=0) |
---|
| 2488 | { |
---|
| 2489 | |
---|
| 2490 | poly lcm=pOne(); |
---|
| 2491 | |
---|
| 2492 | pLcm(c->S->m[s->i], c->S->m[s->j], lcm); |
---|
| 2493 | pSetm(lcm); |
---|
| 2494 | assume(lcm!=NULL); |
---|
| 2495 | poly factor1=pCopy(lcm); |
---|
| 2496 | pExpVectorSub(factor1,c->S->m[s->i]); |
---|
| 2497 | poly factor2=pCopy(lcm); |
---|
| 2498 | pExpVectorSub(factor2,c->S->m[s->j]); |
---|
| 2499 | |
---|
| 2500 | if(done_index>=done_size) |
---|
| 2501 | { |
---|
| 2502 | done_size+=max_par; |
---|
[ec8a6b6] | 2503 | done=(poly*) omrealloc(done,done_size*sizeof(poly)); |
---|
[4f858ce] | 2504 | } |
---|
| 2505 | done[done_index++]=lcm; |
---|
| 2506 | if(chosen_index+1>=chosen_size) |
---|
| 2507 | { |
---|
| 2508 | //max_par must be greater equal 2 |
---|
| 2509 | chosen_size+=si_max(max_par,2); |
---|
[ec8a6b6] | 2510 | chosen=(monom_poly*) omrealloc(chosen,chosen_size*sizeof(monom_poly)); |
---|
[4f858ce] | 2511 | } |
---|
| 2512 | h.f=c->S->m[s->i]; |
---|
| 2513 | h.m=factor1; |
---|
| 2514 | chosen[chosen_index++]=h; |
---|
| 2515 | h.f=c->S->m[s->j]; |
---|
| 2516 | h.m=factor2; |
---|
| 2517 | chosen[chosen_index++]=h; |
---|
| 2518 | } |
---|
| 2519 | else |
---|
| 2520 | { |
---|
| 2521 | if(chosen_index>=chosen_size) |
---|
| 2522 | { |
---|
| 2523 | chosen_size+=max_par; |
---|
[ec8a6b6] | 2524 | chosen=(monom_poly*) omrealloc(chosen,chosen_size*sizeof(monom_poly)); |
---|
[4f858ce] | 2525 | } |
---|
| 2526 | h.f=s->lcm_of_lm; |
---|
| 2527 | h.m=pOne(); |
---|
| 2528 | //pSetm(h.m); done by pOne |
---|
| 2529 | chosen[chosen_index++]=h; |
---|
| 2530 | //must carefull remember to destroy such a h; |
---|
| 2531 | poly_list_node* next=c->to_destroy; |
---|
| 2532 | |
---|
[ec8a6b6] | 2533 | c->to_destroy=(poly_list_node*) omalloc(sizeof(poly_list_node)); |
---|
[4f858ce] | 2534 | c->to_destroy->p=h.f; |
---|
| 2535 | c->to_destroy->next=next; |
---|
| 2536 | only_free=TRUE; |
---|
| 2537 | } |
---|
| 2538 | |
---|
| 2539 | if(s->i>=0) |
---|
| 2540 | now_t_rep(s->j,s->i,c); |
---|
| 2541 | |
---|
| 2542 | if(!(only_free)) |
---|
| 2543 | free_sorted_pair_node(s,c->r); |
---|
| 2544 | else |
---|
| 2545 | omfree(s); |
---|
| 2546 | |
---|
| 2547 | |
---|
| 2548 | |
---|
| 2549 | } |
---|
| 2550 | c->normal_forms+=nfs; |
---|
| 2551 | if (TEST_OPT_PROT) |
---|
| 2552 | Print("M[%i, ",nfs); |
---|
| 2553 | //next Step, simplify all pairs |
---|
| 2554 | for(i=0;i<chosen_index;i++) |
---|
| 2555 | { |
---|
| 2556 | // PrintS("simplifying "); |
---|
| 2557 | //Print("from %s",pString(chosen[i].m)); |
---|
| 2558 | //Print(", %s", pString(chosen[i].f)); |
---|
| 2559 | simplify(chosen[i],c); |
---|
| 2560 | //Print(" to %s",pString(chosen[i].m)); |
---|
| 2561 | //Print(", %s \n", pString(chosen[i].f)); |
---|
| 2562 | } |
---|
| 2563 | |
---|
| 2564 | //next Step remove duplicate entries |
---|
| 2565 | qsort(chosen,chosen_index,sizeof(monom_poly),monom_poly_crit); |
---|
| 2566 | int pos=0; |
---|
| 2567 | for(i=1;i<chosen_index;i++) |
---|
| 2568 | { |
---|
| 2569 | if(((chosen[i].f!=chosen[pos].f))||(!(pLmEqual(chosen[i].m,chosen[pos].m)))) |
---|
| 2570 | chosen[++pos]=chosen[i]; |
---|
| 2571 | else pDelete(&(chosen[i].m)); |
---|
| 2572 | } |
---|
| 2573 | if(chosen_index>0) |
---|
| 2574 | chosen_index=pos+1; |
---|
| 2575 | //next step process polys |
---|
| 2576 | int p_size=2*chosen_index; |
---|
| 2577 | int p_index=0; |
---|
[ec8a6b6] | 2578 | p=(poly*) omalloc(p_size*sizeof(poly)); |
---|
[4f858ce] | 2579 | for(p_index=0;p_index<chosen_index;p_index++) |
---|
| 2580 | { |
---|
| 2581 | p[p_index]=ppMult_mm(chosen[p_index].f,chosen[p_index].m); |
---|
| 2582 | } |
---|
| 2583 | |
---|
| 2584 | qsort(done, done_index,sizeof(poly),pLmCmp_func); |
---|
| 2585 | pos=0; |
---|
| 2586 | //Print("Done_index:%i",done_index); |
---|
| 2587 | if(done_index>0) |
---|
| 2588 | { |
---|
| 2589 | pTest(done[0]); |
---|
| 2590 | } |
---|
| 2591 | for(i=1;i<done_index;i++) |
---|
| 2592 | { |
---|
| 2593 | pTest(done[i]); |
---|
| 2594 | if((!(pLmEqual(done[i],done[pos])))) |
---|
| 2595 | done[++pos]=done[i]; |
---|
| 2596 | else pDelete(&(done[i])); |
---|
| 2597 | } |
---|
| 2598 | if(done_index>0) |
---|
| 2599 | done_index=pos+1; |
---|
| 2600 | #ifdef TGB_DEBUG |
---|
| 2601 | for(i=0;i<done_index;i++) |
---|
| 2602 | { |
---|
| 2603 | int j; |
---|
| 2604 | for(j=0;j<i;j++) |
---|
| 2605 | { |
---|
| 2606 | assume((!pLmEqual(done[j],done[i]))); |
---|
| 2607 | } |
---|
| 2608 | } |
---|
| 2609 | #endif |
---|
| 2610 | #ifdef TGB_DEBUG |
---|
| 2611 | for(i=0;i<done_index;i++) |
---|
| 2612 | { |
---|
| 2613 | pTest(done[i]); |
---|
| 2614 | } |
---|
| 2615 | #endif |
---|
| 2616 | poly* m; |
---|
| 2617 | int m_index=0; |
---|
| 2618 | int m_size=0; |
---|
| 2619 | for(i=0;i<p_index;i++) |
---|
| 2620 | { |
---|
| 2621 | m_size+=pLength(p[i]); |
---|
| 2622 | } |
---|
[ec8a6b6] | 2623 | m=(poly*) omalloc(m_size*sizeof(poly)); |
---|
| 2624 | //q=(poly*) omalloc(m_size*sizeof(poly)); |
---|
[4f858ce] | 2625 | |
---|
| 2626 | |
---|
| 2627 | |
---|
| 2628 | for(i=0;i<p_index;i++) |
---|
| 2629 | { |
---|
| 2630 | |
---|
| 2631 | poly p_i=p[i]; |
---|
| 2632 | |
---|
| 2633 | pTest(p[i]); |
---|
| 2634 | |
---|
| 2635 | while(p_i) |
---|
| 2636 | { |
---|
| 2637 | |
---|
| 2638 | m[m_index]=pLmInit(p_i); |
---|
| 2639 | |
---|
| 2640 | pSetCoeff(m[m_index],nInit(1)); |
---|
| 2641 | |
---|
| 2642 | p_i=p_i->next; |
---|
| 2643 | |
---|
| 2644 | m_index++; |
---|
| 2645 | |
---|
| 2646 | } |
---|
| 2647 | } |
---|
| 2648 | |
---|
| 2649 | int q_size=m_index; |
---|
[ec8a6b6] | 2650 | poly* q=(poly*) omalloc(q_size*sizeof(poly)); |
---|
[4f858ce] | 2651 | int q_index=0; |
---|
| 2652 | //next Step additional reductors |
---|
| 2653 | |
---|
| 2654 | while(m_index>0) |
---|
| 2655 | { |
---|
| 2656 | #ifdef TGB_DEBUG |
---|
| 2657 | |
---|
| 2658 | for(i=0;i<done_index;i++) |
---|
| 2659 | { |
---|
| 2660 | pTest(done[i]); |
---|
| 2661 | } |
---|
| 2662 | #endif |
---|
| 2663 | |
---|
| 2664 | qsort(m, m_index,sizeof(poly),pLmCmp_func); |
---|
| 2665 | |
---|
| 2666 | |
---|
| 2667 | pos=0; |
---|
| 2668 | #ifdef TGB_DEBUG |
---|
| 2669 | |
---|
| 2670 | for(i=0;i<done_index;i++) |
---|
| 2671 | { |
---|
| 2672 | |
---|
| 2673 | pTest(done[i]); |
---|
| 2674 | } |
---|
| 2675 | #endif |
---|
| 2676 | for(i=1;i<m_index;i++) |
---|
| 2677 | { |
---|
| 2678 | pTest(m[i]); |
---|
| 2679 | pTest(m[pos]); |
---|
| 2680 | if((!(pLmEqual(m[i],m[pos])))) |
---|
| 2681 | m[++pos]=m[i]; |
---|
| 2682 | else pDelete(&(m[i])); |
---|
| 2683 | } |
---|
| 2684 | if(m_index>1) |
---|
| 2685 | m_index=pos+1; |
---|
| 2686 | if(done_size<done_index+m_index) |
---|
| 2687 | { |
---|
| 2688 | done_size=done_index+2*m_index; |
---|
[ec8a6b6] | 2689 | done=(poly*) omrealloc(done,done_size*sizeof(poly)); |
---|
[4f858ce] | 2690 | } |
---|
| 2691 | if(chosen_size<chosen_index+m_index) |
---|
| 2692 | { |
---|
| 2693 | chosen_size=chosen_index+2*m_index; |
---|
[ec8a6b6] | 2694 | chosen=(monom_poly*) omrealloc(chosen,chosen_size*sizeof(monom_poly)); |
---|
[4f858ce] | 2695 | } |
---|
| 2696 | q_index=0; |
---|
| 2697 | if(q_size<m_index) |
---|
| 2698 | { |
---|
| 2699 | q_size=2*m_index; |
---|
| 2700 | omfree(q); |
---|
[ec8a6b6] | 2701 | q=(poly*) omalloc(q_size*sizeof(poly)); |
---|
[4f858ce] | 2702 | } |
---|
| 2703 | |
---|
| 2704 | for(i=0;i<m_index;i++) |
---|
| 2705 | { |
---|
| 2706 | |
---|
| 2707 | #ifdef TGB_DEBUG |
---|
| 2708 | { |
---|
| 2709 | int my_i; |
---|
| 2710 | for(my_i=0;my_i<done_index;my_i++) |
---|
| 2711 | { |
---|
| 2712 | int my_j; |
---|
| 2713 | for(my_j=0;my_j<my_i;my_j++) |
---|
| 2714 | { |
---|
| 2715 | assume((!pLmEqual(done[my_j],done[my_i]))); |
---|
| 2716 | } |
---|
| 2717 | } |
---|
| 2718 | } |
---|
| 2719 | #endif |
---|
| 2720 | BOOLEAN in_done=FALSE; |
---|
| 2721 | pTest(m[i]); |
---|
| 2722 | |
---|
| 2723 | pos=posInPolys (done, done_index, m[i],c); |
---|
| 2724 | #ifdef TGB_DEBUG |
---|
| 2725 | { |
---|
| 2726 | int my_i; |
---|
| 2727 | for (my_i=0;my_i<done_index;my_i++) |
---|
| 2728 | pTest(done[my_i]); |
---|
| 2729 | } |
---|
| 2730 | #endif |
---|
| 2731 | if(((done_index>pos)&&(pLmEqual(m[i],done[pos]))) ||(pos>0) &&(pLmEqual(m[i],done[pos-1]))) |
---|
| 2732 | in_done=TRUE; |
---|
| 2733 | if (!(in_done)) |
---|
| 2734 | { |
---|
| 2735 | |
---|
| 2736 | int S_pos=kFindDivisibleByInS_easy(c->strat,m[i], pGetShortExpVector(m[i])); |
---|
| 2737 | if(S_pos>=0) |
---|
| 2738 | { |
---|
| 2739 | monom_poly h; |
---|
| 2740 | h.f=c->strat->S[S_pos]; |
---|
| 2741 | h.m=pOne(); |
---|
[ec8a6b6] | 2742 | int* ev=(int*) omalloc((c->r->N+1)*sizeof(int)); |
---|
[4f858ce] | 2743 | pGetExpV(m[i],ev); |
---|
| 2744 | pSetExpV(h.m,ev); |
---|
| 2745 | omfree(ev); |
---|
| 2746 | pExpVectorSub(h.m,c->strat->S[S_pos]); |
---|
| 2747 | simplify(h,c); |
---|
| 2748 | q[q_index]=ppMult_mm(h.f,h.m); |
---|
| 2749 | chosen[chosen_index++]=h; |
---|
| 2750 | q_index++; |
---|
| 2751 | } |
---|
| 2752 | pTest(m[i]); |
---|
| 2753 | #ifdef TGB_DEBUG |
---|
| 2754 | { |
---|
| 2755 | int my_i; |
---|
| 2756 | for (my_i=0;my_i<done_index;my_i++) |
---|
| 2757 | pTest(done[my_i]); |
---|
| 2758 | } |
---|
| 2759 | #endif |
---|
| 2760 | memmove(&(done[pos+1]),&(done[pos]), (done_index-pos)*sizeof(poly)); |
---|
| 2761 | done[pos]=m[i]; |
---|
| 2762 | done_index++; |
---|
| 2763 | #ifdef TGB_DEBUG |
---|
| 2764 | { |
---|
| 2765 | int my_i; |
---|
| 2766 | for (my_i=0;my_i<done_index;my_i++) |
---|
| 2767 | { |
---|
| 2768 | // Print("Position %i pos %i size %i\n",my_i,pos,done_index); |
---|
| 2769 | pTest(done[my_i]); |
---|
| 2770 | } |
---|
| 2771 | } |
---|
| 2772 | #endif |
---|
| 2773 | } |
---|
| 2774 | else |
---|
| 2775 | pDelete(&m[i]); |
---|
| 2776 | #ifdef TGB_DEBUG |
---|
| 2777 | { |
---|
| 2778 | int my_i; |
---|
| 2779 | for(my_i=0;my_i<done_index;my_i++) |
---|
| 2780 | { |
---|
| 2781 | pTest(done[my_i]); |
---|
| 2782 | int my_j; |
---|
| 2783 | for(my_j=0;my_j<my_i;my_j++) |
---|
| 2784 | { |
---|
| 2785 | assume((!pLmEqual(done[my_j],done[my_i]))); |
---|
| 2786 | } |
---|
| 2787 | } |
---|
| 2788 | } |
---|
| 2789 | #endif |
---|
| 2790 | } |
---|
| 2791 | if(p_size<p_index+q_index) |
---|
| 2792 | { |
---|
| 2793 | p_size=p_index+2*q_index; |
---|
[ec8a6b6] | 2794 | p=(poly*) omrealloc(p,p_size*sizeof(poly)); |
---|
[4f858ce] | 2795 | } |
---|
| 2796 | for (i=0;i<q_index;i++) |
---|
| 2797 | p[p_index++]=q[i]; |
---|
| 2798 | m_index=0; |
---|
| 2799 | int sum=0; |
---|
| 2800 | for(i=0;i<p_index;i++) |
---|
| 2801 | { |
---|
| 2802 | sum+=pLength(p[i])-1; |
---|
| 2803 | } |
---|
| 2804 | if (m_size<sum) |
---|
| 2805 | { |
---|
| 2806 | omfree(m); |
---|
[ec8a6b6] | 2807 | m=(poly*) omalloc(sum*sizeof(poly)); |
---|
[4f858ce] | 2808 | } |
---|
| 2809 | m_size=sum; |
---|
| 2810 | for(i=0;i<q_index;i++) |
---|
| 2811 | { |
---|
| 2812 | poly p_i=q[i]->next; |
---|
| 2813 | while(p_i) |
---|
| 2814 | { |
---|
| 2815 | m[m_index]=pLmInit(p_i); |
---|
| 2816 | pSetCoeff(m[m_index],nInit(1)); |
---|
| 2817 | p_i=p_i->next; |
---|
| 2818 | m_index++; |
---|
| 2819 | } |
---|
| 2820 | } |
---|
| 2821 | //qsort(done, done_index,sizeof(poly),pLmCmp_func); |
---|
| 2822 | #ifdef TGB_DEBUG |
---|
| 2823 | for(i=0;i<done_index;i++) |
---|
| 2824 | { |
---|
| 2825 | pTest(done[i]); |
---|
| 2826 | } |
---|
| 2827 | #endif |
---|
| 2828 | } |
---|
| 2829 | #ifdef TGB_DEBUG |
---|
| 2830 | for(i=0;i<done_index;i++) |
---|
| 2831 | { |
---|
| 2832 | int j; |
---|
| 2833 | for(j=0;j<i;j++) |
---|
| 2834 | { |
---|
| 2835 | assume((!pLmEqual(done[j],done[i]))); |
---|
| 2836 | } |
---|
| 2837 | } |
---|
| 2838 | #endif |
---|
| 2839 | omfree(m); |
---|
| 2840 | omfree(q); |
---|
| 2841 | if (TEST_OPT_PROT) |
---|
| 2842 | Print("Mat[%i x %i], ",chosen_index, done_index); |
---|
| 2843 | //next Step build matrix |
---|
| 2844 | #ifdef TGB_DEBUG |
---|
| 2845 | for(i=0;i<done_index;i++) |
---|
| 2846 | { |
---|
| 2847 | int j; |
---|
| 2848 | for(j=0;j<i;j++) |
---|
| 2849 | { |
---|
| 2850 | assume((!pLmEqual(done[j],done[i]))); |
---|
| 2851 | } |
---|
| 2852 | } |
---|
| 2853 | #endif |
---|
| 2854 | assume(p_index==chosen_index); |
---|
| 2855 | |
---|
| 2856 | // tgb_matrix* mat=build_matrix(p,p_index,done, done_index,c); |
---|
| 2857 | |
---|
| 2858 | // simple_gauss2(mat); |
---|
| 2859 | tgb_sparse_matrix* mat=build_sparse_matrix(p,p_index,done, done_index,c); |
---|
| 2860 | simple_gauss(mat,c); |
---|
| 2861 | m_size=mat->get_rows(); |
---|
[ec8a6b6] | 2862 | m=(poly*) omalloc(m_size*sizeof(poly)); |
---|
[4f858ce] | 2863 | m_index=retranslate(m,mat,done,c); |
---|
| 2864 | |
---|
| 2865 | mat=NULL; |
---|
| 2866 | for(i=0;i<done_index;i++) |
---|
| 2867 | pDelete(&done[i]); |
---|
| 2868 | omfree(done); |
---|
| 2869 | done=NULL; |
---|
| 2870 | //next Step addElements to basis |
---|
| 2871 | int F_plus_size=m_index; |
---|
[ec8a6b6] | 2872 | poly* F_plus=(poly*)omalloc(F_plus_size*sizeof(poly)); |
---|
[4f858ce] | 2873 | int F_plus_index=0; |
---|
| 2874 | int F_minus_size=m_index; |
---|
[ec8a6b6] | 2875 | poly* F_minus=(poly*) omalloc(F_minus_size*sizeof(poly)); |
---|
[4f858ce] | 2876 | int F_minus_index=0; |
---|
| 2877 | |
---|
| 2878 | //better algorithm replace p by its monoms, qsort,delete duplicates and binary search for testing if monom is contained in array |
---|
| 2879 | qsort(p, p_index,sizeof(poly),pLmCmp_func); |
---|
| 2880 | for(i=0;i<p_index;i++) |
---|
| 2881 | pDelete(&p[i]->next); |
---|
| 2882 | for(i=m_index-1;i>=0;--i) |
---|
| 2883 | { |
---|
| 2884 | int j; |
---|
| 2885 | int pos=posInPolys (p,p_index, m[i],c); |
---|
| 2886 | BOOLEAN minus=FALSE; |
---|
| 2887 | if(((p_index>pos)&&(pLmEqual(m[i],p[pos]))) ||(pos>0) &&(pLmEqual(m[i],p[pos-1]))) |
---|
| 2888 | minus=TRUE; |
---|
| 2889 | |
---|
| 2890 | if(minus) |
---|
| 2891 | { |
---|
| 2892 | F_minus[F_minus_index++]=m[i]; |
---|
| 2893 | m[i]=NULL; |
---|
| 2894 | } |
---|
| 2895 | else |
---|
| 2896 | { |
---|
| 2897 | F_plus[F_plus_index++]=m[i]; |
---|
| 2898 | m[i]=NULL; |
---|
| 2899 | } |
---|
| 2900 | } |
---|
| 2901 | |
---|
| 2902 | // for(i=m_index-1;i>=0;--i) |
---|
| 2903 | // { |
---|
| 2904 | // int j; |
---|
| 2905 | // BOOLEAN minus=FALSE; |
---|
| 2906 | // for(j=0;j<p_index;j++) |
---|
| 2907 | // if (pLmEqual(p[j],m[i])) |
---|
| 2908 | // { |
---|
| 2909 | // minus=TRUE; |
---|
| 2910 | // break; |
---|
| 2911 | // } |
---|
| 2912 | // if(minus) |
---|
| 2913 | // { |
---|
| 2914 | // F_minus[F_minus_index++]=m[i]; |
---|
| 2915 | // m[i]=NULL; |
---|
| 2916 | // } |
---|
| 2917 | // else |
---|
| 2918 | // { |
---|
| 2919 | // F_plus[F_plus_index++]=m[i]; |
---|
| 2920 | // m[i]=NULL; |
---|
| 2921 | // } |
---|
| 2922 | // } |
---|
| 2923 | //in this order F_minus will be automatically ascending sorted |
---|
| 2924 | //to make this sure for foreign gauss |
---|
| 2925 | //uncomment the following line |
---|
| 2926 | // qsort(F_minus, F_minus_index,sizeof(poly),pLmCmp_func); |
---|
| 2927 | assume((F_plus_index+F_minus_index)==m_index); |
---|
| 2928 | if (TEST_OPT_PROT) |
---|
| 2929 | Print("%i]", F_plus_index); |
---|
| 2930 | for(i=0;i<p_index;i++) |
---|
| 2931 | pDelete(&p[i]); |
---|
| 2932 | omfree(p); |
---|
| 2933 | p=NULL; |
---|
| 2934 | omfree(m); |
---|
| 2935 | m=NULL; |
---|
| 2936 | |
---|
| 2937 | //the F_minus list must be cleared separately at the end |
---|
| 2938 | mp_array_list** F_i; |
---|
| 2939 | poly_array_list** F_m_i; |
---|
| 2940 | F_i=&(c->F); |
---|
| 2941 | F_m_i=&(c->F_minus); |
---|
| 2942 | |
---|
| 2943 | while((*F_i)!=NULL) |
---|
| 2944 | { |
---|
| 2945 | assume((*F_m_i)!=NULL); |
---|
| 2946 | F_i=(&((*F_i)->next)); |
---|
| 2947 | F_m_i=(&((*F_m_i)->next)); |
---|
| 2948 | } |
---|
| 2949 | assume((*F_m_i)==NULL); |
---|
| 2950 | //should resize the array to save memory |
---|
| 2951 | //F and F_minus |
---|
| 2952 | qsort(chosen,chosen_index,sizeof(monom_poly),monom_poly_crit);//important for simplify |
---|
[ec8a6b6] | 2953 | (*F_m_i)=(poly_array_list*) omalloc(sizeof(poly_array_list)); |
---|
[4f858ce] | 2954 | (*F_m_i)->size=F_minus_index; |
---|
| 2955 | (*F_m_i)->p=F_minus; |
---|
| 2956 | (*F_m_i)->next=NULL; |
---|
[ec8a6b6] | 2957 | (*F_i)=(mp_array_list*) omalloc(sizeof(poly_array_list)); |
---|
[4f858ce] | 2958 | (*F_i)->size=chosen_index; |
---|
| 2959 | (*F_i)->mp=chosen; |
---|
| 2960 | (*F_i)->next=NULL; |
---|
| 2961 | |
---|
| 2962 | if(F_plus_index>0) |
---|
| 2963 | { |
---|
| 2964 | int j; |
---|
[ec8a6b6] | 2965 | int* ibuf=(int*) omalloc(F_plus_index*sizeof(int)); |
---|
| 2966 | sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(F_plus_index*sizeof(sorted_pair_node**)); |
---|
[4f858ce] | 2967 | |
---|
| 2968 | for(j=0;j<F_plus_index;j++) |
---|
| 2969 | { |
---|
| 2970 | int len; |
---|
| 2971 | poly p=F_plus[j]; |
---|
| 2972 | |
---|
| 2973 | // delete buf[j]; |
---|
| 2974 | //remember to free res here |
---|
| 2975 | // p=redTailShort(p, c->strat); |
---|
| 2976 | sbuf[j]=add_to_basis_ideal_quotient(p,-1,-1,c,ibuf+j); |
---|
| 2977 | |
---|
| 2978 | } |
---|
| 2979 | int sum=0; |
---|
| 2980 | for(j=0;j<F_plus_index;j++) |
---|
| 2981 | { |
---|
| 2982 | sum+=ibuf[j]; |
---|
| 2983 | } |
---|
[ec8a6b6] | 2984 | sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 2985 | int partsum=0; |
---|
| 2986 | for(j=0;j<F_plus_index;j++) |
---|
| 2987 | { |
---|
| 2988 | memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*)); |
---|
| 2989 | omfree(sbuf[j]); |
---|
| 2990 | partsum+=ibuf[j]; |
---|
| 2991 | } |
---|
| 2992 | |
---|
| 2993 | qsort(big_sbuf,sum,sizeof(sorted_pair_node*),pair_better_gen2); |
---|
| 2994 | c->apairs=merge(c->apairs,c->pair_top+1,big_sbuf,sum,c); |
---|
| 2995 | c->pair_top+=sum; |
---|
| 2996 | clean_top_of_pair_list(c); |
---|
| 2997 | omfree(big_sbuf); |
---|
| 2998 | omfree(sbuf); |
---|
| 2999 | omfree(ibuf); |
---|
| 3000 | } |
---|
| 3001 | omfree(F_plus); |
---|
| 3002 | #ifdef TGB_DEBUG |
---|
| 3003 | int z; |
---|
| 3004 | for(z=1;z<=c->pair_top;z++) |
---|
| 3005 | { |
---|
| 3006 | assume(pair_better(c->apairs[z],c->apairs[z-1],c)); |
---|
| 3007 | } |
---|
| 3008 | #endif |
---|
| 3009 | |
---|
| 3010 | return; |
---|
| 3011 | } |
---|
| 3012 | |
---|
| 3013 | |
---|
| 3014 | static int poly_crit(const void* ap1, const void* ap2){ |
---|
| 3015 | poly p1,p2; |
---|
| 3016 | p1=*((poly*) ap1); |
---|
| 3017 | p2=*((poly*)ap2); |
---|
| 3018 | |
---|
| 3019 | int c=pLmCmp(p1,p2); |
---|
| 3020 | if (c !=0) return c; |
---|
| 3021 | int l1=pLength(p1); |
---|
| 3022 | int l2=pLength(p2); |
---|
| 3023 | if (l1<l2) return -1; |
---|
| 3024 | if (l1>l2) return 1; |
---|
| 3025 | return 0; |
---|
| 3026 | } |
---|
| 3027 | |
---|
| 3028 | ideal t_rep_gb(ring r,ideal arg_I, BOOLEAN F4_mode){ |
---|
| 3029 | if (TEST_OPT_PROT) |
---|
| 3030 | if (F4_mode) |
---|
| 3031 | PrintS("F4 Modus \n"); |
---|
| 3032 | |
---|
| 3033 | |
---|
| 3034 | //debug_Ideal=arg_debug_Ideal; |
---|
| 3035 | //if (debug_Ideal) PrintS("DebugIdeal received\n"); |
---|
| 3036 | // Print("Idelems %i \n----------\n",IDELEMS(arg_I)); |
---|
| 3037 | ideal I=idCompactify(arg_I); |
---|
| 3038 | if (idIs0(I)) return I; |
---|
| 3039 | |
---|
| 3040 | qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit); |
---|
| 3041 | //Print("Idelems %i \n----------\n",IDELEMS(I)); |
---|
[ec8a6b6] | 3042 | calc_dat* c=(calc_dat*) omalloc(sizeof(calc_dat)); |
---|
[4f858ce] | 3043 | |
---|
| 3044 | c->r=currRing; |
---|
| 3045 | c->is_homog=TRUE; |
---|
| 3046 | { |
---|
| 3047 | int hz; |
---|
| 3048 | for(hz=0;hz<IDELEMS(I);hz++){ |
---|
| 3049 | assume(I->m[hz]!=NULL); |
---|
| 3050 | int d=pTotaldegree(I->m[hz]); |
---|
| 3051 | poly t=I->m[hz]->next; |
---|
| 3052 | while(t) |
---|
| 3053 | { |
---|
| 3054 | if (d!=pTotaldegree(t,c->r)) |
---|
| 3055 | { |
---|
| 3056 | c->is_homog=FALSE; |
---|
| 3057 | break; |
---|
| 3058 | } |
---|
| 3059 | t=t->next; |
---|
| 3060 | } |
---|
| 3061 | if(!(c->is_homog)) break; |
---|
| 3062 | } |
---|
| 3063 | } |
---|
| 3064 | // Print("is homog:%d",c->is_homog); |
---|
| 3065 | void* h; |
---|
| 3066 | poly hp; |
---|
| 3067 | int i,j; |
---|
| 3068 | c->to_destroy=NULL; |
---|
| 3069 | c->easy_product_crit=0; |
---|
| 3070 | c->extended_product_crit=0; |
---|
| 3071 | if (rField_is_Zp(c->r)) |
---|
| 3072 | c->is_char0=FALSE; |
---|
| 3073 | else |
---|
| 3074 | c->is_char0=TRUE; |
---|
| 3075 | //not fully correct |
---|
| 3076 | |
---|
| 3077 | //(rChar()==0); |
---|
| 3078 | c->F4_mode=F4_mode; |
---|
| 3079 | c->reduction_steps=0; |
---|
| 3080 | c->last_index=-1; |
---|
| 3081 | |
---|
| 3082 | c->F=NULL; |
---|
| 3083 | c->F_minus=NULL; |
---|
| 3084 | |
---|
| 3085 | c->Rcounter=0; |
---|
| 3086 | |
---|
| 3087 | c->soon_free=NULL; |
---|
| 3088 | |
---|
| 3089 | c->tmp_lm=pOne(); |
---|
| 3090 | |
---|
| 3091 | c->normal_forms=0; |
---|
| 3092 | c->current_degree=1; |
---|
| 3093 | |
---|
| 3094 | c->max_pairs=5*I->idelems(); |
---|
| 3095 | |
---|
[ec8a6b6] | 3096 | c->apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*c->max_pairs); |
---|
[4f858ce] | 3097 | c->pair_top=-1; |
---|
| 3098 | |
---|
| 3099 | int n=I->idelems(); |
---|
| 3100 | if (TEST_OPT_PROT) |
---|
| 3101 | for (i=0;i<n;i++){ |
---|
| 3102 | wrp(I->m[i]); |
---|
| 3103 | PrintS("\n"); |
---|
| 3104 | } |
---|
| 3105 | i=0; |
---|
| 3106 | c->n=0; |
---|
[ec8a6b6] | 3107 | c->T_deg=(int*) omalloc(n*sizeof(int)); |
---|
[4f858ce] | 3108 | if((!(c->is_homog)) &&(pLexOrder)) |
---|
[ec8a6b6] | 3109 | c->T_deg_full=(int*) omalloc(n*sizeof(int)); |
---|
[4f858ce] | 3110 | else |
---|
| 3111 | c->T_deg_full=NULL; |
---|
[ec8a6b6] | 3112 | c->tmp_pair_lm=(poly*) omalloc(n*sizeof(poly)); |
---|
| 3113 | c->tmp_spn=(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 3114 | lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long)); |
---|
| 3115 | #ifdef HEAD_BIN |
---|
| 3116 | c->HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long)); |
---|
| 3117 | #endif |
---|
| 3118 | /* omUnGetSpecBin(&(c->HeadBin)); */ |
---|
[ec8a6b6] | 3119 | h=omalloc(n*sizeof(char*)); |
---|
[4f858ce] | 3120 | c->states=(char**) h; |
---|
[ec8a6b6] | 3121 | h=omalloc(n*sizeof(int)); |
---|
[4f858ce] | 3122 | c->lengths=(int*) h; |
---|
[ec8a6b6] | 3123 | h=omalloc(n*sizeof(int)); |
---|
| 3124 | c->gcd_of_terms=(poly*) omalloc(n*sizeof(poly)); |
---|
[4f858ce] | 3125 | c->rep=(int*) h; |
---|
[ec8a6b6] | 3126 | c->short_Exps=(long*) omalloc(n*sizeof(long)); |
---|
[4f858ce] | 3127 | c->S=idInit(n,1); |
---|
| 3128 | c->strat=new skStrategy; |
---|
| 3129 | c->strat->syzComp = 0; |
---|
| 3130 | initBuchMoraCrit(c->strat); |
---|
| 3131 | initBuchMoraPos(c->strat); |
---|
| 3132 | c->strat->initEcart = initEcartBBA; |
---|
| 3133 | c->strat->enterS = enterSBba; |
---|
| 3134 | c->strat->sl = -1; |
---|
| 3135 | i=n; |
---|
| 3136 | i=1; |
---|
| 3137 | /* initS(c->S,NULL,c->strat); */ |
---|
| 3138 | /* intS start: */ |
---|
| 3139 | // i=((i+IDELEMS(c->S)+15)/16)*16; |
---|
| 3140 | c->strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/ |
---|
| 3141 | c->strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long)); |
---|
| 3142 | /*initsevS(i);*/ |
---|
| 3143 | c->strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/ |
---|
| 3144 | c->strat->fromQ=NULL; |
---|
| 3145 | c->strat->Shdl=idInit(1,1); |
---|
| 3146 | c->strat->S=c->strat->Shdl->m; |
---|
| 3147 | c->strat->lenS=(int*)omAlloc0(i*sizeof(int)); |
---|
| 3148 | if((c->is_char0)||((pLexOrder) &&(!c->is_homog))) |
---|
| 3149 | c->strat->lenSw=(int*)omAlloc0(i*sizeof(int)); |
---|
| 3150 | else |
---|
| 3151 | c->strat->lenSw=NULL; |
---|
| 3152 | sorted_pair_node* si; |
---|
| 3153 | assume(n>0); |
---|
| 3154 | add_to_basis(I->m[0],-1,-1,c); |
---|
| 3155 | |
---|
| 3156 | assume(c->strat->sl==c->strat->Shdl->idelems()-1); |
---|
| 3157 | if(!(F4_mode)) |
---|
| 3158 | { |
---|
| 3159 | for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis |
---|
| 3160 | { |
---|
| 3161 | // add_to_basis(I->m[i],-1,-1,c); |
---|
[ec8a6b6] | 3162 | si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 3163 | si->i=-1; |
---|
| 3164 | si->j=-1; |
---|
| 3165 | si->expected_length=pLength(I->m[i]); |
---|
| 3166 | si->deg=pTotaldegree(I->m[i]); |
---|
| 3167 | if (!rField_is_Zp(c->r)){ |
---|
| 3168 | pCleardenom(I->m[i]); |
---|
| 3169 | } |
---|
| 3170 | si->lcm_of_lm=I->m[i]; |
---|
| 3171 | |
---|
| 3172 | // c->apairs[n-1-i]=si; |
---|
| 3173 | c->apairs[n-i-1]=si; |
---|
| 3174 | ++(c->pair_top); |
---|
| 3175 | } |
---|
| 3176 | } |
---|
| 3177 | else |
---|
| 3178 | { |
---|
| 3179 | for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis |
---|
| 3180 | add_to_basis(I->m[i],-1,-1,c); |
---|
| 3181 | } |
---|
| 3182 | |
---|
| 3183 | |
---|
| 3184 | while(c->pair_top>=0) |
---|
| 3185 | { |
---|
| 3186 | if(F4_mode) |
---|
| 3187 | go_on_F4(c); |
---|
| 3188 | else |
---|
| 3189 | go_on(c); |
---|
| 3190 | } |
---|
| 3191 | while(c->to_destroy) |
---|
| 3192 | { |
---|
| 3193 | pDelete(&(c->to_destroy->p)); |
---|
| 3194 | poly_list_node* old=c->to_destroy; |
---|
| 3195 | c->to_destroy=c->to_destroy->next; |
---|
| 3196 | omfree(old); |
---|
| 3197 | } |
---|
| 3198 | while(c->F) |
---|
| 3199 | { |
---|
| 3200 | for(i=0;i<c->F->size;i++){ |
---|
| 3201 | pDelete(&(c->F->mp[i].m)); |
---|
| 3202 | } |
---|
| 3203 | omfree(c->F->mp); |
---|
| 3204 | c->F->mp=NULL; |
---|
| 3205 | mp_array_list* old=c->F; |
---|
| 3206 | c->F=c->F->next; |
---|
| 3207 | omfree(old); |
---|
| 3208 | } |
---|
| 3209 | while(c->F_minus) |
---|
| 3210 | { |
---|
| 3211 | for(i=0;i<c->F_minus->size;i++){ |
---|
| 3212 | pDelete(&(c->F_minus->p[i])); |
---|
| 3213 | } |
---|
| 3214 | omfree(c->F_minus->p); |
---|
| 3215 | c->F_minus->p=NULL; |
---|
| 3216 | poly_array_list* old=c->F_minus; |
---|
| 3217 | c->F_minus=c->F_minus->next; |
---|
| 3218 | omfree(old); |
---|
| 3219 | } |
---|
[76b225] | 3220 | for(int z=1 /* zero length at 0 */;z<c->n;z++){ |
---|
[4f858ce] | 3221 | omfree(c->states[z]); |
---|
| 3222 | } |
---|
| 3223 | omfree(c->states); |
---|
| 3224 | omfree(c->lengths); |
---|
| 3225 | for(int z=0;z<c->n;z++) |
---|
| 3226 | { |
---|
| 3227 | pDelete(&c->tmp_pair_lm[z]); |
---|
| 3228 | omfree(c->tmp_spn[z]); |
---|
| 3229 | } |
---|
| 3230 | omfree(c->tmp_pair_lm); |
---|
| 3231 | omfree(c->tmp_spn); |
---|
| 3232 | |
---|
| 3233 | omfree(c->T_deg); |
---|
| 3234 | if(c->T_deg_full) |
---|
| 3235 | omfree(c->T_deg_full); |
---|
| 3236 | |
---|
| 3237 | omFree(c->strat->ecartS); |
---|
| 3238 | omFree(c->strat->sevS); |
---|
| 3239 | // initsevS(i); |
---|
| 3240 | omFree(c->strat->S_2_R); |
---|
| 3241 | |
---|
| 3242 | |
---|
| 3243 | omFree(c->strat->lenS); |
---|
| 3244 | |
---|
| 3245 | if(c->strat->lenSw) omFree(c->strat->lenSw); |
---|
| 3246 | |
---|
| 3247 | |
---|
| 3248 | |
---|
| 3249 | |
---|
| 3250 | for(i=0;i<c->n;i++){ |
---|
| 3251 | if(c->gcd_of_terms[i]) |
---|
| 3252 | pDelete(&(c->gcd_of_terms[i])); |
---|
| 3253 | } |
---|
| 3254 | omfree(c->gcd_of_terms); |
---|
| 3255 | |
---|
| 3256 | omfree(c->apairs); |
---|
| 3257 | if (TEST_OPT_PROT) |
---|
| 3258 | { |
---|
| 3259 | Print("calculated %d NFs\n",c->normal_forms); |
---|
| 3260 | Print("applied %i product crit, %i extended_product crit \n", c->easy_product_crit, c->extended_product_crit); |
---|
| 3261 | } |
---|
| 3262 | int deleted_form_c_s=0; |
---|
| 3263 | |
---|
| 3264 | for(i=0;i<=c->strat->sl;i++){ |
---|
| 3265 | if (!c->strat->S[i]) continue; |
---|
| 3266 | BOOLEAN found=FALSE; |
---|
| 3267 | for(j=0;j<c->n;j++){ |
---|
| 3268 | if (c->S->m[j]==c->strat->S[i]){ |
---|
| 3269 | found=TRUE; |
---|
| 3270 | break; |
---|
| 3271 | } |
---|
| 3272 | } |
---|
| 3273 | if(!found) pDelete(&c->strat->S[i]); |
---|
| 3274 | } |
---|
| 3275 | // for(i=0;i<c->n;i++){ |
---|
| 3276 | // if (c->rep[i]!=i){ |
---|
| 3277 | // // for(j=0;j<=c->strat->sl;j++){ |
---|
| 3278 | // // if(c->strat->S[j]==c->S->m[i]){ |
---|
| 3279 | // // c->strat->S[j]=NULL; |
---|
| 3280 | // // break; |
---|
| 3281 | // // } |
---|
| 3282 | // // } |
---|
| 3283 | // // PrintS("R_delete"); |
---|
| 3284 | // pDelete(&c->S->m[i]); |
---|
| 3285 | // } |
---|
| 3286 | // } |
---|
| 3287 | |
---|
| 3288 | // qsort(c->S->m, c->n,sizeof(poly),pLmCmp_func); |
---|
| 3289 | for(i=0;i<c->n;i++) |
---|
| 3290 | { |
---|
| 3291 | assume(c->S->m[i]!=NULL); |
---|
| 3292 | for(j=0;j<c->n;j++) |
---|
| 3293 | { |
---|
| 3294 | if((c->S->m[j]==NULL)||(i==j)) |
---|
| 3295 | continue; |
---|
| 3296 | assume(p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], |
---|
| 3297 | c->S->m[i],~c->short_Exps[i], |
---|
| 3298 | c->r)==p_LmDivisibleBy(c->S->m[j], |
---|
| 3299 | c->S->m[i], |
---|
| 3300 | c->r)); |
---|
| 3301 | if (p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], |
---|
| 3302 | c->S->m[i],~c->short_Exps[i], |
---|
| 3303 | c->r)) |
---|
| 3304 | { |
---|
| 3305 | pDelete(&c->S->m[i]); |
---|
| 3306 | break; |
---|
| 3307 | } |
---|
| 3308 | } |
---|
| 3309 | } |
---|
| 3310 | omfree(c->short_Exps); |
---|
| 3311 | omfree(c->rep); |
---|
| 3312 | for(i=0;i<I->idelems();i++) |
---|
| 3313 | { |
---|
| 3314 | I->m[i]=NULL; |
---|
| 3315 | } |
---|
| 3316 | idDelete(&I); |
---|
| 3317 | I=c->S; |
---|
| 3318 | |
---|
| 3319 | IDELEMS(I)=c->n; |
---|
| 3320 | |
---|
| 3321 | idSkipZeroes(I); |
---|
| 3322 | for(i=0;i<=c->strat->sl;i++) |
---|
| 3323 | c->strat->S[i]=NULL; |
---|
| 3324 | id_Delete(&c->strat->Shdl,c->r); |
---|
| 3325 | pDelete(&c->tmp_lm); |
---|
| 3326 | omUnGetSpecBin(&lm_bin); |
---|
| 3327 | delete c->strat; |
---|
| 3328 | omfree(c); |
---|
| 3329 | |
---|
| 3330 | return(I); |
---|
| 3331 | } |
---|
| 3332 | static void now_t_rep(const int & arg_i, const int & arg_j, calc_dat* c){ |
---|
| 3333 | int i,j; |
---|
| 3334 | if (arg_i==arg_j){ |
---|
| 3335 | return; |
---|
| 3336 | } |
---|
| 3337 | if (arg_i>arg_j){ |
---|
| 3338 | i=arg_j; |
---|
| 3339 | j=arg_i; |
---|
| 3340 | } else { |
---|
| 3341 | i=arg_i; |
---|
| 3342 | j=arg_j; |
---|
| 3343 | } |
---|
| 3344 | c->states[j][i]=HASTREP; |
---|
| 3345 | } |
---|
| 3346 | static void soon_t_rep(const int& arg_i, const int& arg_j, calc_dat* c) |
---|
| 3347 | { |
---|
| 3348 | assume(0<=arg_i); |
---|
| 3349 | assume(0<=arg_j); |
---|
| 3350 | assume(arg_i<c->n); |
---|
| 3351 | assume(arg_j<c->n); |
---|
| 3352 | int i,j; |
---|
| 3353 | if (arg_i==arg_j){ |
---|
| 3354 | return; |
---|
| 3355 | } |
---|
| 3356 | if (arg_i>arg_j){ |
---|
| 3357 | i=arg_j; |
---|
| 3358 | j=arg_i; |
---|
| 3359 | } else { |
---|
| 3360 | i=arg_i; |
---|
| 3361 | j=arg_j; |
---|
| 3362 | } |
---|
| 3363 | if (! |
---|
| 3364 | (c->states[j][i]==HASTREP)) |
---|
| 3365 | c->states[j][i]=SOONTREP; |
---|
| 3366 | } |
---|
| 3367 | static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, calc_dat* state){ |
---|
| 3368 | assume(0<=arg_i); |
---|
| 3369 | assume(0<=arg_j); |
---|
| 3370 | assume(arg_i<state->n); |
---|
| 3371 | assume(arg_j<state->n); |
---|
| 3372 | if (arg_i==arg_j) |
---|
| 3373 | { |
---|
| 3374 | return (TRUE); |
---|
| 3375 | } |
---|
| 3376 | if (arg_i>arg_j) |
---|
| 3377 | { |
---|
| 3378 | return (state->states[arg_i][arg_j]==HASTREP); |
---|
| 3379 | } else |
---|
| 3380 | { |
---|
| 3381 | return (state->states[arg_j][arg_i]==HASTREP); |
---|
| 3382 | } |
---|
| 3383 | } |
---|
| 3384 | static int pLcmDeg(poly a, poly b) |
---|
| 3385 | { |
---|
| 3386 | int i; |
---|
| 3387 | int n=0; |
---|
| 3388 | for (i=pVariables; i; i--) |
---|
| 3389 | { |
---|
| 3390 | n+=si_max( pGetExp(a,i), pGetExp(b,i)); |
---|
| 3391 | } |
---|
| 3392 | return n; |
---|
| 3393 | |
---|
| 3394 | } |
---|
| 3395 | |
---|
| 3396 | |
---|
| 3397 | |
---|
| 3398 | static void shorten_tails(calc_dat* c, poly monom) |
---|
| 3399 | { |
---|
| 3400 | return; |
---|
| 3401 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 3402 | for(int i=0;i<c->n;i++) |
---|
| 3403 | { |
---|
| 3404 | //enter tail |
---|
| 3405 | if (c->rep[i]!=i) continue; |
---|
| 3406 | if (c->S->m[i]==NULL) continue; |
---|
| 3407 | poly tail=c->S->m[i]->next; |
---|
| 3408 | poly prev=c->S->m[i]; |
---|
| 3409 | BOOLEAN did_something=FALSE; |
---|
| 3410 | while((tail!=NULL)&& (pLmCmp(tail, monom)>=0)) |
---|
| 3411 | { |
---|
| 3412 | if (p_LmDivisibleBy(monom,tail,c->r)) |
---|
| 3413 | { |
---|
| 3414 | did_something=TRUE; |
---|
| 3415 | prev->next=tail->next; |
---|
| 3416 | tail->next=NULL; |
---|
| 3417 | p_Delete(& tail,c->r); |
---|
| 3418 | tail=prev; |
---|
| 3419 | //PrintS("Shortened"); |
---|
| 3420 | c->lengths[i]--; |
---|
| 3421 | } |
---|
| 3422 | prev=tail; |
---|
| 3423 | tail=tail->next; |
---|
| 3424 | } |
---|
| 3425 | if (did_something) |
---|
| 3426 | { |
---|
| 3427 | int new_pos; |
---|
| 3428 | int q; |
---|
| 3429 | q=pQuality(c->S->m[i],c,c->lengths[i]); |
---|
| 3430 | new_pos=simple_posInS(c->strat,c->S->m[i],q); |
---|
| 3431 | |
---|
| 3432 | int old_pos=-1; |
---|
| 3433 | //assume new_pos<old_pos |
---|
| 3434 | for (int z=0;z<=c->strat->sl;z++) |
---|
| 3435 | { |
---|
| 3436 | if (c->strat->S[z]==c->S->m[i]) |
---|
| 3437 | { |
---|
| 3438 | old_pos=z; |
---|
| 3439 | break; |
---|
| 3440 | } |
---|
| 3441 | } |
---|
| 3442 | if (old_pos== -1) |
---|
| 3443 | for (int z=new_pos-1;z>=0;z--) |
---|
| 3444 | { |
---|
| 3445 | if (c->strat->S[z]==c->S->m[i]) |
---|
| 3446 | { |
---|
| 3447 | old_pos=z; |
---|
| 3448 | break; |
---|
| 3449 | } |
---|
| 3450 | } |
---|
| 3451 | assume(old_pos>=0); |
---|
| 3452 | assume(new_pos<=old_pos); |
---|
| 3453 | assume(pLength(c->strat->S[old_pos])==c->lengths[i]); |
---|
| 3454 | c->strat->lenS[old_pos]=c->lengths[i]; |
---|
| 3455 | if (c->strat->lenSw) |
---|
| 3456 | c->strat->lenSw[old_pos]=q; |
---|
| 3457 | |
---|
| 3458 | if (new_pos<old_pos) |
---|
| 3459 | move_forward_in_S(old_pos,new_pos,c->strat); |
---|
| 3460 | |
---|
| 3461 | length_one_crit(c,i,c->lengths[i]); |
---|
| 3462 | } |
---|
| 3463 | } |
---|
| 3464 | } |
---|
| 3465 | static sorted_pair_node* pop_pair(calc_dat* c){ |
---|
| 3466 | clean_top_of_pair_list(c); |
---|
| 3467 | |
---|
| 3468 | if(c->pair_top<0) return NULL; |
---|
| 3469 | else return (c->apairs[c->pair_top--]); |
---|
| 3470 | } |
---|
| 3471 | static sorted_pair_node* top_pair(calc_dat* c){ |
---|
| 3472 | super_clean_top_of_pair_list(c);//yeah, I know, it's odd that I use a different proc here |
---|
| 3473 | |
---|
| 3474 | if(c->pair_top<0) return NULL; |
---|
| 3475 | else return (c->apairs[c->pair_top]); |
---|
| 3476 | } |
---|
| 3477 | static sorted_pair_node* quick_pop_pair(calc_dat* c){ |
---|
| 3478 | if(c->pair_top<0) return NULL; |
---|
| 3479 | else return (c->apairs[c->pair_top--]); |
---|
| 3480 | } |
---|
| 3481 | static BOOLEAN no_pairs(calc_dat* c){ |
---|
| 3482 | clean_top_of_pair_list(c); |
---|
| 3483 | return (c->pair_top==-1); |
---|
| 3484 | } |
---|
| 3485 | |
---|
| 3486 | |
---|
| 3487 | static void super_clean_top_of_pair_list(calc_dat* c){ |
---|
| 3488 | while((c->pair_top>=0) |
---|
| 3489 | && (c->apairs[c->pair_top]->i>=0) |
---|
| 3490 | && (good_has_t_rep(c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))) |
---|
| 3491 | { |
---|
| 3492 | |
---|
| 3493 | free_sorted_pair_node(c->apairs[c->pair_top],c->r); |
---|
| 3494 | c->pair_top--; |
---|
| 3495 | |
---|
| 3496 | } |
---|
| 3497 | } |
---|
| 3498 | static void clean_top_of_pair_list(calc_dat* c){ |
---|
| 3499 | while((c->pair_top>=0) && (c->apairs[c->pair_top]->i>=0) && (!state_is(UNCALCULATED,c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))){ |
---|
| 3500 | |
---|
| 3501 | free_sorted_pair_node(c->apairs[c->pair_top],c->r); |
---|
| 3502 | c->pair_top--; |
---|
| 3503 | |
---|
| 3504 | } |
---|
| 3505 | } |
---|
| 3506 | static BOOLEAN state_is(calc_state state, const int & arg_i, const int & arg_j, calc_dat* c){ |
---|
| 3507 | assume(0<=arg_i); |
---|
| 3508 | assume(0<=arg_j); |
---|
| 3509 | assume(arg_i<c->n); |
---|
| 3510 | assume(arg_j<c->n); |
---|
| 3511 | if (arg_i==arg_j) |
---|
| 3512 | { |
---|
| 3513 | return (TRUE); |
---|
| 3514 | } |
---|
| 3515 | if (arg_i>arg_j) |
---|
| 3516 | { |
---|
| 3517 | return (c->states[arg_i][arg_j]==state); |
---|
| 3518 | } |
---|
| 3519 | else return(c->states[arg_j][arg_i]==state); |
---|
| 3520 | } |
---|
| 3521 | static void free_sorted_pair_node(sorted_pair_node* s, ring r){ |
---|
| 3522 | if (s->i>=0) |
---|
| 3523 | p_Delete(&s->lcm_of_lm,r); |
---|
| 3524 | omfree(s); |
---|
| 3525 | } |
---|
| 3526 | static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, calc_dat* c){ |
---|
| 3527 | if (a->deg<b->deg) return TRUE; |
---|
| 3528 | if (a->deg>b->deg) return FALSE; |
---|
| 3529 | |
---|
| 3530 | // if (a->expected_length<b->expected_length) return TRUE; |
---|
| 3531 | // if (a->expected_length>b->expected_length) return FALSE; |
---|
| 3532 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 3533 | if (comp==1) return FALSE; |
---|
| 3534 | if (-1==comp) return TRUE; |
---|
| 3535 | if (a->i+a->j<b->i+b->j) return TRUE; |
---|
| 3536 | if (a->i+a->j>b->i+b->j) return FALSE; |
---|
| 3537 | if (a->i<b->i) return TRUE; |
---|
| 3538 | if (a->i>b->i) return FALSE; |
---|
| 3539 | return TRUE; |
---|
| 3540 | } |
---|
| 3541 | |
---|
| 3542 | static int pair_better_gen(const void* ap,const void* bp){ |
---|
| 3543 | |
---|
| 3544 | sorted_pair_node* a=*((sorted_pair_node**)ap); |
---|
| 3545 | sorted_pair_node* b=*((sorted_pair_node**)bp); |
---|
| 3546 | assume(a->i>a->j); |
---|
| 3547 | assume(b->i>b->j); |
---|
| 3548 | if (a->deg<b->deg) return -1; |
---|
| 3549 | if (a->deg>b->deg) return 1; |
---|
| 3550 | |
---|
| 3551 | |
---|
| 3552 | // if (a->expected_length<b->expected_length) return -1; |
---|
| 3553 | // if (a->expected_length>b->expected_length) return 1; |
---|
| 3554 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 3555 | |
---|
| 3556 | if (comp==1) return 1; |
---|
| 3557 | if (-1==comp) return -1; |
---|
| 3558 | if (a->i+a->j<b->i+b->j) return -1; |
---|
| 3559 | if (a->i+a->j>b->i+b->j) return 1; |
---|
| 3560 | if (a->i<b->i) return -1; |
---|
| 3561 | if (a->i>b->i) return 1; |
---|
| 3562 | return 0; |
---|
| 3563 | } |
---|
| 3564 | |
---|
| 3565 | |
---|
| 3566 | static poly gcd_of_terms(poly p, ring r){ |
---|
| 3567 | int max_g_0=0; |
---|
| 3568 | assume(p!=NULL); |
---|
| 3569 | int i; |
---|
| 3570 | poly m=pOne(); |
---|
| 3571 | poly t; |
---|
| 3572 | for (i=pVariables; i; i--) |
---|
| 3573 | { |
---|
| 3574 | pSetExp(m,i, pGetExp(p,i)); |
---|
| 3575 | if (max_g_0==0) |
---|
| 3576 | if (pGetExp(m,i)>0) |
---|
| 3577 | max_g_0=i; |
---|
| 3578 | } |
---|
| 3579 | |
---|
| 3580 | t=p->next; |
---|
| 3581 | while (t!=NULL){ |
---|
| 3582 | |
---|
| 3583 | if (max_g_0==0) break; |
---|
| 3584 | for (i=max_g_0; i; i--) |
---|
| 3585 | { |
---|
| 3586 | pSetExp(m,i, si_min(pGetExp(t,i),pGetExp(m,i))); |
---|
| 3587 | if (max_g_0==i) |
---|
| 3588 | if (pGetExp(m,i)==0) |
---|
| 3589 | max_g_0=0; |
---|
| 3590 | if ((max_g_0==0) && (pGetExp(m,i)>0)){ |
---|
| 3591 | max_g_0=i; |
---|
| 3592 | } |
---|
| 3593 | } |
---|
| 3594 | t=t->next; |
---|
| 3595 | } |
---|
| 3596 | // for (i=pVariables;i;i--) |
---|
| 3597 | // { |
---|
| 3598 | // if(pGetExp(m,i)>0) |
---|
| 3599 | // return m; |
---|
| 3600 | // } |
---|
| 3601 | if (max_g_0>0) |
---|
| 3602 | return m; |
---|
| 3603 | pDelete(&m); |
---|
| 3604 | return NULL; |
---|
| 3605 | } |
---|
| 3606 | static inline BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m) |
---|
| 3607 | { |
---|
| 3608 | |
---|
| 3609 | if (pGetComp(p1) > 0 || pGetComp(p2) > 0) |
---|
| 3610 | return FALSE; |
---|
| 3611 | int i = 1; |
---|
| 3612 | loop |
---|
| 3613 | { |
---|
| 3614 | if ((pGetExp(p1, i)-pGetExp(m,i) >0) && (pGetExp(p2, i) -pGetExp(m,i)> 0)) return FALSE; |
---|
| 3615 | if (i == pVariables) return TRUE; |
---|
| 3616 | i++; |
---|
| 3617 | } |
---|
| 3618 | } |
---|
| 3619 | |
---|
| 3620 | |
---|
| 3621 | //for impl reasons may return false if the the normal product criterion matches |
---|
| 3622 | static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, calc_dat* c){ |
---|
| 3623 | if(gcd1==NULL) return FALSE; |
---|
| 3624 | if(gcd2==NULL) return FALSE; |
---|
| 3625 | gcd1->next=gcd2; //may ordered incorrect |
---|
| 3626 | poly m=gcd_of_terms(gcd1,c->r); |
---|
| 3627 | gcd1->next=NULL; |
---|
| 3628 | if (m==NULL) return FALSE; |
---|
| 3629 | |
---|
| 3630 | BOOLEAN erg=pHasNotCFExtended(p1,p2,m); |
---|
| 3631 | pDelete(&m); |
---|
| 3632 | return erg; |
---|
| 3633 | } |
---|
| 3634 | static poly kBucketGcd(kBucket* b, ring r) |
---|
| 3635 | { |
---|
| 3636 | int s=0; |
---|
| 3637 | int i; |
---|
| 3638 | poly m, n; |
---|
| 3639 | BOOLEAN initialized=FALSE; |
---|
| 3640 | for (i=MAX_BUCKET-1;i>=0;i--) |
---|
| 3641 | { |
---|
| 3642 | if (b->buckets[i]!=NULL){ |
---|
| 3643 | if (!initialized){ |
---|
| 3644 | m=gcd_of_terms(b->buckets[i],r); |
---|
| 3645 | initialized=TRUE; |
---|
| 3646 | if (m==NULL) return NULL; |
---|
| 3647 | } |
---|
| 3648 | else |
---|
| 3649 | { |
---|
| 3650 | n=gcd_of_terms(b->buckets[i],r); |
---|
| 3651 | if (n==NULL) { |
---|
| 3652 | pDelete(&m); |
---|
| 3653 | return NULL; |
---|
| 3654 | } |
---|
| 3655 | n->next=m; |
---|
| 3656 | poly t=gcd_of_terms(n,r); |
---|
| 3657 | n->next=NULL; |
---|
| 3658 | pDelete(&m); |
---|
| 3659 | pDelete(&n); |
---|
| 3660 | m=t; |
---|
| 3661 | if (m==NULL) return NULL; |
---|
| 3662 | |
---|
| 3663 | } |
---|
| 3664 | } |
---|
| 3665 | } |
---|
| 3666 | return m; |
---|
| 3667 | } |
---|
| 3668 | |
---|
| 3669 | |
---|
| 3670 | |
---|
| 3671 | |
---|
| 3672 | static inline int quality_of_pos_in_strat_S(int pos, calc_dat* c){ |
---|
| 3673 | if (c->strat->lenSw!=NULL) return c->strat->lenSw[pos]; |
---|
| 3674 | return c->strat->lenS[pos]; |
---|
| 3675 | } |
---|
| 3676 | |
---|
| 3677 | static void multi_reduction_lls_trick(red_object* los, int losl,calc_dat* c,find_erg & erg){ |
---|
| 3678 | erg.expand=NULL; |
---|
| 3679 | BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS |
---|
| 3680 | if(erg.fromS){ |
---|
| 3681 | if(pLmEqual(c->strat->S[erg.reduce_by],los[erg.to_reduce_u].p)) |
---|
| 3682 | { |
---|
| 3683 | int i; |
---|
| 3684 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 3685 | int best=erg.to_reduce_u+1; |
---|
| 3686 | /* |
---|
| 3687 | for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){ |
---|
| 3688 | int qc=los[i].guess_quality(c); |
---|
| 3689 | if (qc<quality_a){ |
---|
| 3690 | best=i; |
---|
| 3691 | quality_a=qc; |
---|
| 3692 | } |
---|
| 3693 | } |
---|
| 3694 | if(best!=erg.to_reduce_u+1){*/ |
---|
| 3695 | int qc; |
---|
| 3696 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 3697 | if(qc<quality_a){ |
---|
| 3698 | los[best].flatten(); |
---|
| 3699 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 3700 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 3701 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 3702 | if(qc<quality_a){ |
---|
| 3703 | red_object h=los[erg.to_reduce_u]; |
---|
| 3704 | los[erg.to_reduce_u]=los[best]; |
---|
| 3705 | los[best]=h; |
---|
| 3706 | swap_roles=TRUE; |
---|
| 3707 | } |
---|
| 3708 | else |
---|
| 3709 | swap_roles=FALSE; |
---|
| 3710 | } |
---|
| 3711 | else{ |
---|
| 3712 | |
---|
| 3713 | swap_roles=FALSE; |
---|
| 3714 | } |
---|
| 3715 | |
---|
| 3716 | } |
---|
| 3717 | else |
---|
| 3718 | { |
---|
| 3719 | if (erg.to_reduce_u>erg.to_reduce_l){ |
---|
| 3720 | |
---|
| 3721 | int i; |
---|
| 3722 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 3723 | int best=erg.to_reduce_u+1; |
---|
| 3724 | int qc; |
---|
| 3725 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 3726 | assume(qc==los[best].guess_quality(c)); |
---|
| 3727 | if(qc<quality_a){ |
---|
| 3728 | los[best].flatten(); |
---|
| 3729 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 3730 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 3731 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 3732 | //(best!=erg.to_reduce_u+1) |
---|
| 3733 | if(qc<quality_a){ |
---|
| 3734 | red_object h=los[erg.to_reduce_l]; |
---|
| 3735 | los[erg.to_reduce_l]=los[best]; |
---|
| 3736 | los[best]=h; |
---|
| 3737 | erg.reduce_by=erg.to_reduce_l; |
---|
| 3738 | erg.fromS=FALSE; |
---|
| 3739 | erg.to_reduce_l++; |
---|
| 3740 | } |
---|
| 3741 | } |
---|
| 3742 | } |
---|
| 3743 | else |
---|
| 3744 | { |
---|
| 3745 | assume(erg.to_reduce_u==erg.to_reduce_l); |
---|
| 3746 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 3747 | int qc=los[erg.to_reduce_u].guess_quality(c); |
---|
| 3748 | if(qc<quality_a){ |
---|
| 3749 | int best=erg.to_reduce_u; |
---|
| 3750 | los[best].flatten(); |
---|
| 3751 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 3752 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 3753 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 3754 | if(qc<quality_a){ |
---|
| 3755 | BOOLEAN exp=FALSE; |
---|
| 3756 | if(qc<=2) |
---|
| 3757 | exp=TRUE; |
---|
| 3758 | else { |
---|
| 3759 | if (qc<quality_a/2) |
---|
| 3760 | exp=TRUE; |
---|
| 3761 | else |
---|
| 3762 | if(erg.reduce_by<c->n/4) |
---|
| 3763 | exp=TRUE; |
---|
| 3764 | } |
---|
| 3765 | if (exp){ |
---|
| 3766 | poly clear_into; |
---|
| 3767 | los[erg.to_reduce_u].flatten(); |
---|
| 3768 | kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); |
---|
| 3769 | erg.expand=pCopy(clear_into); |
---|
| 3770 | kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); |
---|
| 3771 | if (TEST_OPT_PROT) |
---|
| 3772 | PrintS("e"); |
---|
| 3773 | |
---|
| 3774 | } |
---|
| 3775 | } |
---|
| 3776 | } |
---|
| 3777 | |
---|
| 3778 | |
---|
| 3779 | } |
---|
| 3780 | |
---|
| 3781 | swap_roles=FALSE; |
---|
| 3782 | return; |
---|
| 3783 | } |
---|
| 3784 | |
---|
| 3785 | } |
---|
| 3786 | else{ |
---|
| 3787 | if(erg.reduce_by>erg.to_reduce_u){ |
---|
| 3788 | //then lm(rb)>= lm(tru) so = |
---|
| 3789 | assume(erg.reduce_by==erg.to_reduce_u+1); |
---|
| 3790 | int best=erg.reduce_by; |
---|
| 3791 | int quality_a=los[erg.reduce_by].guess_quality(c); |
---|
| 3792 | int qc; |
---|
| 3793 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 3794 | |
---|
| 3795 | int i; |
---|
| 3796 | if(qc<quality_a){ |
---|
| 3797 | red_object h=los[erg.reduce_by]; |
---|
| 3798 | los[erg.reduce_by]=los[best]; |
---|
| 3799 | los[best]=h; |
---|
| 3800 | } |
---|
| 3801 | swap_roles=FALSE; |
---|
| 3802 | return; |
---|
| 3803 | |
---|
| 3804 | |
---|
| 3805 | } |
---|
| 3806 | else |
---|
| 3807 | { |
---|
| 3808 | assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); |
---|
| 3809 | assume(erg.to_reduce_u==erg.to_reduce_l); |
---|
| 3810 | //further assume, that reduce_by is the above all other polys |
---|
| 3811 | //with same leading term |
---|
| 3812 | int il=erg.reduce_by; |
---|
| 3813 | int quality_a =los[erg.reduce_by].guess_quality(c); |
---|
| 3814 | int qc; |
---|
| 3815 | while((il>0) && pLmEqual(los[il-1].p,los[il].p)){ |
---|
| 3816 | il--; |
---|
| 3817 | qc=los[il].guess_quality(c); |
---|
| 3818 | if (qc<quality_a){ |
---|
| 3819 | quality_a=qc; |
---|
| 3820 | erg.reduce_by=il; |
---|
| 3821 | } |
---|
| 3822 | } |
---|
| 3823 | swap_roles=FALSE; |
---|
| 3824 | } |
---|
| 3825 | |
---|
| 3826 | } |
---|
| 3827 | if(swap_roles) |
---|
| 3828 | { |
---|
| 3829 | if (TEST_OPT_PROT) |
---|
| 3830 | PrintS("b"); |
---|
| 3831 | poly clear_into; |
---|
| 3832 | int dummy_len; |
---|
| 3833 | int new_length; |
---|
| 3834 | int bp=erg.to_reduce_u;//bucket_positon |
---|
| 3835 | //kBucketClear(los[bp].bucket,&clear_into,&new_length); |
---|
| 3836 | new_length=los[bp].clear_to_poly(); |
---|
| 3837 | clear_into=los[bp].p; |
---|
| 3838 | poly p=c->strat->S[erg.reduce_by]; |
---|
| 3839 | int j=erg.reduce_by; |
---|
| 3840 | int old_length=c->strat->lenS[j];// in view of S |
---|
| 3841 | los[bp].p=p; |
---|
| 3842 | kBucketInit(los[bp].bucket,p,old_length); |
---|
| 3843 | int qal=pQuality(clear_into,c,new_length); |
---|
| 3844 | int pos_in_c=-1; |
---|
| 3845 | int z; |
---|
| 3846 | int new_pos; |
---|
| 3847 | new_pos=simple_posInS(c->strat,clear_into,qal); |
---|
| 3848 | assume(new_pos<=j); |
---|
| 3849 | for (z=c->n;z;z--) |
---|
| 3850 | { |
---|
| 3851 | if(p==c->S->m[z-1]) |
---|
| 3852 | { |
---|
| 3853 | pos_in_c=z-1; |
---|
| 3854 | break; |
---|
| 3855 | } |
---|
| 3856 | } |
---|
| 3857 | if(pos_in_c>=0) |
---|
| 3858 | { |
---|
| 3859 | c->S->m[pos_in_c]=clear_into; |
---|
| 3860 | c->lengths[pos_in_c]=new_length; |
---|
| 3861 | if (c->T_deg_full) |
---|
| 3862 | c->T_deg_full[pos_in_c]=pTotaldegree_full(clear_into); |
---|
| 3863 | c_S_element_changed_hook(pos_in_c,c); |
---|
| 3864 | } |
---|
| 3865 | c->strat->S[j]=clear_into; |
---|
| 3866 | c->strat->lenS[j]=new_length; |
---|
| 3867 | assume(pLength(clear_into)==new_length); |
---|
| 3868 | if(c->strat->lenSw) |
---|
| 3869 | c->strat->lenSw[j]=qal; |
---|
| 3870 | if (!rField_is_Zp(c->r)) |
---|
| 3871 | { |
---|
| 3872 | pContent(clear_into); |
---|
| 3873 | pCleardenom(clear_into);//should be unnecessary |
---|
| 3874 | } |
---|
| 3875 | else |
---|
| 3876 | pNorm(clear_into); |
---|
| 3877 | #ifdef FIND_DETERMINISTIC |
---|
| 3878 | erg.reduce_by=j; |
---|
| 3879 | //resort later see diploma thesis, find_in_S must be deterministic |
---|
| 3880 | //during multireduction if spolys are only in the span of the |
---|
| 3881 | //input polys |
---|
| 3882 | #else |
---|
| 3883 | |
---|
| 3884 | if (new_pos<j) |
---|
| 3885 | { |
---|
| 3886 | move_forward_in_S(j,new_pos,c->strat); |
---|
| 3887 | erg.reduce_by=new_pos; |
---|
| 3888 | } |
---|
| 3889 | #endif |
---|
| 3890 | } |
---|
| 3891 | } |
---|
| 3892 | static int fwbw(red_object* los, int i){ |
---|
| 3893 | int i2=i; |
---|
| 3894 | int step=1; |
---|
| 3895 | |
---|
| 3896 | BOOLEAN bw=FALSE; |
---|
| 3897 | BOOLEAN incr=TRUE; |
---|
| 3898 | |
---|
| 3899 | while(1) |
---|
| 3900 | { |
---|
| 3901 | if(!bw) |
---|
| 3902 | { |
---|
| 3903 | step=si_min(i2,step); |
---|
| 3904 | if (step==0) break; |
---|
| 3905 | i2-=step; |
---|
| 3906 | |
---|
| 3907 | if(!pLmEqual(los[i].p,los[i2].p)) |
---|
| 3908 | { |
---|
| 3909 | bw=TRUE; |
---|
| 3910 | incr=FALSE; |
---|
| 3911 | } |
---|
| 3912 | else |
---|
| 3913 | { |
---|
| 3914 | if ((!incr) &&(step==1)) break; |
---|
| 3915 | } |
---|
| 3916 | |
---|
| 3917 | |
---|
| 3918 | } |
---|
| 3919 | else |
---|
| 3920 | { |
---|
| 3921 | |
---|
| 3922 | step=si_min(i-i2,step); |
---|
| 3923 | if (step==0) break; |
---|
| 3924 | i2+=step; |
---|
| 3925 | if(pLmEqual(los[i].p,los[i2].p)){ |
---|
| 3926 | if(step==1) break; |
---|
| 3927 | else |
---|
| 3928 | { |
---|
| 3929 | bw=FALSE; |
---|
| 3930 | } |
---|
| 3931 | } |
---|
| 3932 | |
---|
| 3933 | } |
---|
| 3934 | if (incr) |
---|
| 3935 | step*=2; |
---|
| 3936 | else |
---|
| 3937 | { |
---|
| 3938 | if (step%2==1) |
---|
| 3939 | step=(step+1)/2; |
---|
| 3940 | else |
---|
| 3941 | step/=2; |
---|
| 3942 | |
---|
| 3943 | } |
---|
| 3944 | } |
---|
| 3945 | return i2; |
---|
| 3946 | } |
---|
| 3947 | static void multi_reduction_find(red_object* los, int losl,calc_dat* c,int startf,find_erg & erg){ |
---|
| 3948 | kStrategy strat=c->strat; |
---|
| 3949 | |
---|
| 3950 | assume(startf<=losl); |
---|
| 3951 | assume((startf==losl-1)||(pLmCmp(los[startf].p,los[startf+1].p)==-1)); |
---|
| 3952 | int i=startf; |
---|
| 3953 | |
---|
| 3954 | int j; |
---|
| 3955 | while(i>=0){ |
---|
| 3956 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)<=0)); |
---|
| 3957 | assume(is_valid_ro(los[i])); |
---|
| 3958 | j=kFindDivisibleByInS_easy(strat,los[i]); |
---|
| 3959 | if(j>=0){ |
---|
| 3960 | |
---|
| 3961 | erg.to_reduce_u=i; |
---|
| 3962 | erg.reduce_by=j; |
---|
| 3963 | erg.fromS=TRUE; |
---|
| 3964 | int i2=fwbw(los,i); |
---|
| 3965 | assume(pLmEqual(los[i].p,los[i2].p)); |
---|
| 3966 | assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); |
---|
| 3967 | assume(i>=i2); |
---|
| 3968 | |
---|
| 3969 | // int i2; |
---|
| 3970 | // for(i2=i-1;i2>=0;i2--){ |
---|
| 3971 | // if(!pLmEqual(los[i].p,los[i2].p)) |
---|
| 3972 | // break; |
---|
| 3973 | // } |
---|
| 3974 | |
---|
| 3975 | // erg.to_reduce_l=i2+1; |
---|
| 3976 | erg.to_reduce_l=i2; |
---|
| 3977 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 3978 | return; |
---|
| 3979 | } |
---|
| 3980 | if (j<0){ |
---|
| 3981 | |
---|
| 3982 | //not reduceable, try to use this for reducing higher terms |
---|
| 3983 | int i2=fwbw(los,i); |
---|
| 3984 | assume(pLmEqual(los[i].p,los[i2].p)); |
---|
| 3985 | assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); |
---|
| 3986 | assume(i>=i2); |
---|
| 3987 | if(i2!=i){ |
---|
| 3988 | |
---|
| 3989 | erg.to_reduce_u=i-1; |
---|
| 3990 | erg.to_reduce_l=i2; |
---|
| 3991 | erg.reduce_by=i; |
---|
| 3992 | erg.fromS=FALSE; |
---|
| 3993 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 3994 | return; |
---|
| 3995 | } |
---|
| 3996 | if(!(c->is_homog)) |
---|
| 3997 | { |
---|
| 3998 | |
---|
| 3999 | for (i2=i+1;i2<losl;i2++){ |
---|
| 4000 | if (p_LmShortDivisibleBy(los[i].p,los[i].sev,los[i2].p,~los[i2].sev, |
---|
| 4001 | c->r)){ |
---|
| 4002 | int i3=i2; |
---|
| 4003 | while((i3+1<losl) && (pLmEqual(los[i2].p, los[i3+1].p))) |
---|
| 4004 | i3++; |
---|
| 4005 | erg.to_reduce_u=i3; |
---|
| 4006 | erg.to_reduce_l=i2; |
---|
| 4007 | erg.reduce_by=i; |
---|
| 4008 | erg.fromS=FALSE; |
---|
| 4009 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 4010 | return; |
---|
| 4011 | } |
---|
| 4012 | // else {assume(!p_LmDivisibleBy(los[i].p, los[i2].p,c->r));} |
---|
| 4013 | } |
---|
| 4014 | } |
---|
| 4015 | i--; |
---|
| 4016 | } |
---|
| 4017 | } |
---|
| 4018 | erg.reduce_by=-1;//error code |
---|
| 4019 | return; |
---|
| 4020 | } |
---|
| 4021 | |
---|
| 4022 | // nicht reduzierbare eintraege in ergebnisliste schreiben |
---|
| 4023 | // nullen loeschen |
---|
| 4024 | // while(finde_groessten leitterm reduzierbar(c,erg)){ |
---|
| 4025 | |
---|
| 4026 | static int multi_reduction_clear_zeroes(red_object* los, int losl, int l, int u) |
---|
| 4027 | { |
---|
| 4028 | |
---|
| 4029 | |
---|
| 4030 | int deleted=0; |
---|
| 4031 | int i=l; |
---|
| 4032 | int last=-1; |
---|
| 4033 | while(i<=u) |
---|
| 4034 | { |
---|
| 4035 | |
---|
| 4036 | if(los[i].p==NULL){ |
---|
| 4037 | kBucketDestroy(&los[i].bucket); |
---|
| 4038 | // delete los[i];//here we assume los are constructed with new |
---|
| 4039 | //destroy resources, must be added here |
---|
| 4040 | if (last>=0) |
---|
| 4041 | { |
---|
| 4042 | memmove(los+(int)(last+1-deleted),los+(last+1),sizeof(red_object)*(i-1-last)); |
---|
| 4043 | } |
---|
| 4044 | last=i; |
---|
| 4045 | deleted++; |
---|
| 4046 | } |
---|
| 4047 | i++; |
---|
| 4048 | } |
---|
| 4049 | if((last>=0)&&(last!=losl-1)) |
---|
| 4050 | memmove(los+(int)(last+1-deleted),los+last+1,sizeof(red_object)*(losl-1-last)); |
---|
| 4051 | return deleted; |
---|
| 4052 | |
---|
| 4053 | } |
---|
| 4054 | |
---|
| 4055 | static void sort_region_down(red_object* los, int l, int u, calc_dat* c) |
---|
| 4056 | { |
---|
| 4057 | qsort(los+l,u-l+1,sizeof(red_object),red_object_better_gen); |
---|
| 4058 | int i; |
---|
| 4059 | |
---|
| 4060 | for(i=l;i<=u;i++) |
---|
| 4061 | { |
---|
| 4062 | BOOLEAN moved=FALSE; |
---|
| 4063 | int j; |
---|
| 4064 | for(j=i;j;j--) |
---|
| 4065 | { |
---|
| 4066 | if(pLmCmp(los[j].p,los[j-1].p)==-1){ |
---|
| 4067 | red_object h=los[j]; |
---|
| 4068 | los[j]=los[j-1]; |
---|
| 4069 | los[j-1]=h; |
---|
| 4070 | moved=TRUE; |
---|
| 4071 | } |
---|
| 4072 | else break; |
---|
| 4073 | } |
---|
| 4074 | if(!moved) return; |
---|
| 4075 | } |
---|
| 4076 | } |
---|
| 4077 | |
---|
| 4078 | //assume that los is ordered ascending by leading term, all non zero |
---|
| 4079 | static void multi_reduction(red_object* los, int & losl, calc_dat* c) |
---|
| 4080 | { |
---|
| 4081 | |
---|
| 4082 | //initialize; |
---|
| 4083 | assume(c->strat->sl>=0); |
---|
| 4084 | assume(losl>0); |
---|
| 4085 | int i; |
---|
| 4086 | for(i=0;i<losl;i++){ |
---|
| 4087 | los[i].sev=pGetShortExpVector(los[i].p); |
---|
| 4088 | //SetShortExpVector(); |
---|
| 4089 | los[i].p=kBucketGetLm(los[i].bucket); |
---|
| 4090 | } |
---|
| 4091 | |
---|
| 4092 | kStrategy strat=c->strat; |
---|
| 4093 | int curr_pos=losl-1; |
---|
| 4094 | |
---|
| 4095 | |
---|
| 4096 | // nicht reduzierbare einträge in ergebnisliste schreiben |
---|
| 4097 | // nullen loeschen |
---|
| 4098 | while(curr_pos>=0){ |
---|
| 4099 | |
---|
| 4100 | find_erg erg; |
---|
| 4101 | multi_reduction_find(los, losl,c,curr_pos,erg);//last argument should be curr_pos |
---|
| 4102 | // PrintS("\n erg:\n"); |
---|
| 4103 | // Print("upper:%i\n",erg.to_reduce_u); |
---|
| 4104 | // Print("lower:%i\n",erg.to_reduce_l); |
---|
| 4105 | // Print("reduce_by:%i\n",erg.reduce_by); |
---|
| 4106 | // Print("fromS:%i\n",erg.fromS); |
---|
| 4107 | if(erg.reduce_by<0) break; |
---|
| 4108 | |
---|
| 4109 | |
---|
| 4110 | |
---|
| 4111 | erg.expand=NULL; |
---|
| 4112 | int d=erg.to_reduce_u-erg.to_reduce_l+1; |
---|
| 4113 | //if ((!erg.fromS)&&(d>100)){ |
---|
[196cdf] | 4114 | |
---|
[4f858ce] | 4115 | multi_reduction_lls_trick(los,losl,c,erg); |
---|
| 4116 | int sum=0; |
---|
| 4117 | |
---|
| 4118 | |
---|
| 4119 | int i; |
---|
| 4120 | int len; |
---|
| 4121 | // wrp(los[erg.to_reduce_u].p); |
---|
| 4122 | //Print("\n"); |
---|
| 4123 | multi_reduce_step(erg,los,c); |
---|
[196cdf] | 4124 | |
---|
[4f858ce] | 4125 | // reduction_step *rs=create_reduction_step(erg, los, c); |
---|
| 4126 | // rs->reduce(los,erg.to_reduce_l,erg.to_reduce_u); |
---|
| 4127 | // finalize_reduction_step(rs); |
---|
| 4128 | |
---|
| 4129 | int deleted=multi_reduction_clear_zeroes(los, losl, erg.to_reduce_l, erg.to_reduce_u); |
---|
| 4130 | if(erg.fromS==FALSE) |
---|
| 4131 | curr_pos=si_max(erg.to_reduce_u,erg.reduce_by); |
---|
| 4132 | else |
---|
| 4133 | curr_pos=erg.to_reduce_u; |
---|
| 4134 | losl -= deleted; |
---|
| 4135 | curr_pos -= deleted; |
---|
| 4136 | |
---|
| 4137 | //Print("deleted %i \n",deleted); |
---|
| 4138 | sort_region_down(los, erg.to_reduce_l, erg.to_reduce_u-deleted, c); |
---|
| 4139 | // sort_region_down(los, 0, losl-1, c); |
---|
| 4140 | // qsort(los,losl,sizeof(red_object),red_object_better_gen); |
---|
| 4141 | if(erg.expand) |
---|
| 4142 | { |
---|
| 4143 | #ifdef FIND_DETERMINISTIC |
---|
| 4144 | int i; |
---|
| 4145 | for(i=0;c->expandS[i];i++); |
---|
[ec8a6b6] | 4146 | c->expandS=(poly*) omrealloc(c->expandS,(i+2)*sizeof(poly)); |
---|
[4f858ce] | 4147 | c->expandS[i]=erg.expand; |
---|
| 4148 | c->expandS[i+1]=NULL; |
---|
| 4149 | #else |
---|
| 4150 | add_to_reductors(c,erg.expand,erg.expand_length); |
---|
| 4151 | #endif |
---|
| 4152 | } |
---|
| 4153 | |
---|
| 4154 | } |
---|
| 4155 | return; |
---|
| 4156 | } |
---|
| 4157 | void red_object::flatten(){ |
---|
| 4158 | if (sum!=NULL) |
---|
| 4159 | { |
---|
| 4160 | |
---|
| 4161 | |
---|
| 4162 | if(kBucketGetLm(sum->ac->bucket)!=NULL){ |
---|
| 4163 | number mult_my=n_Mult(sum->c_my,sum->ac->multiplied,currRing); |
---|
| 4164 | number mult_my_h=mult_my; |
---|
| 4165 | number ac_h=sum->c_ac; |
---|
| 4166 | ksCheckCoeff(&mult_my_h, &ac_h); |
---|
| 4167 | nDelete(&sum->c_ac); |
---|
| 4168 | nDelete(&mult_my); |
---|
| 4169 | mult_my=mult_my_h; |
---|
| 4170 | sum->c_ac=ac_h; |
---|
| 4171 | poly add_this; |
---|
| 4172 | if(!nIsOne(mult_my)) |
---|
| 4173 | kBucket_Mult_n(bucket,mult_my); |
---|
| 4174 | int len; |
---|
| 4175 | poly clear_into; |
---|
| 4176 | kBucketClear(sum->ac->bucket,&clear_into,&len); |
---|
| 4177 | if(sum->ac->counter>1){ |
---|
| 4178 | add_this=pCopy(clear_into); |
---|
| 4179 | kBucketInit(sum->ac->bucket,clear_into,len); |
---|
| 4180 | } |
---|
| 4181 | else |
---|
| 4182 | add_this=clear_into; |
---|
| 4183 | if(!nIsOne(sum->c_ac)) |
---|
| 4184 | pMult_nn(add_this, sum->c_ac); |
---|
| 4185 | |
---|
| 4186 | kBucket_Add_q(bucket,add_this, &len); |
---|
| 4187 | nDelete(&mult_my); |
---|
| 4188 | |
---|
| 4189 | } |
---|
| 4190 | nDelete(&sum->c_ac); |
---|
| 4191 | nDelete(&sum->c_my); |
---|
| 4192 | |
---|
| 4193 | sum->ac->decrease_counter(); |
---|
| 4194 | delete sum; |
---|
| 4195 | p=kBucketGetLm(bucket); |
---|
| 4196 | sum=NULL; |
---|
| 4197 | } |
---|
| 4198 | assume(p==kBucketGetLm(bucket)); |
---|
| 4199 | assume(sum==NULL); |
---|
| 4200 | } |
---|
| 4201 | void red_object::validate(){ |
---|
| 4202 | BOOLEAN flattened=FALSE; |
---|
| 4203 | if(sum!=NULL) |
---|
| 4204 | { |
---|
| 4205 | poly lm=kBucketGetLm(bucket); |
---|
| 4206 | poly lm_ac=kBucketGetLm(sum->ac->bucket); |
---|
| 4207 | if ((lm_ac==NULL)||((lm!=NULL) && (pLmCmp(lm,lm_ac)!=-1))){ |
---|
| 4208 | flatten(); |
---|
| 4209 | assume(sum==NULL); |
---|
| 4210 | flattened=TRUE; |
---|
| 4211 | p=kBucketGetLm(bucket); |
---|
| 4212 | if (p!=NULL) |
---|
| 4213 | sev=pGetShortExpVector(p); |
---|
| 4214 | } |
---|
| 4215 | else |
---|
| 4216 | { |
---|
| 4217 | |
---|
| 4218 | p=lm_ac; |
---|
| 4219 | assume(sum->ac->sev==pGetShortExpVector(p)); |
---|
| 4220 | sev=sum->ac->sev; |
---|
| 4221 | } |
---|
| 4222 | |
---|
| 4223 | } |
---|
| 4224 | else{ |
---|
| 4225 | p=kBucketGetLm(bucket); |
---|
| 4226 | if(p) |
---|
| 4227 | sev=pGetShortExpVector(p); |
---|
| 4228 | } |
---|
| 4229 | assume((sum==NULL)||(kBucketGetLm(sum->ac->bucket)!=NULL)); |
---|
| 4230 | } |
---|
| 4231 | int red_object::clear_to_poly(){ |
---|
| 4232 | flatten(); |
---|
| 4233 | int l; |
---|
| 4234 | kBucketClear(bucket,&p,&l); |
---|
| 4235 | return l; |
---|
| 4236 | } |
---|
| 4237 | |
---|
| 4238 | |
---|
| 4239 | |
---|
| 4240 | void red_object::adjust_coefs(number c_r, number c_ac_r){ |
---|
| 4241 | assume(this->sum!=NULL); |
---|
| 4242 | number n1=nMult(sum->c_my, c_ac_r); |
---|
| 4243 | number n2=nMult(sum->c_ac,c_r); |
---|
| 4244 | nDelete(&sum->c_my); |
---|
| 4245 | nDelete(&sum->c_ac); |
---|
| 4246 | |
---|
| 4247 | int ct = ksCheckCoeff(&n1, &n2); |
---|
| 4248 | sum->c_my=n1; |
---|
| 4249 | sum->c_ac=nNeg(n2); |
---|
| 4250 | // nDelete(&n2); |
---|
| 4251 | |
---|
| 4252 | |
---|
| 4253 | } |
---|
| 4254 | |
---|
| 4255 | void reduction_step::reduce(red_object* r, int l, int u){} |
---|
| 4256 | void simple_reducer::target_is_no_sum_reduce(red_object & ro){ |
---|
| 4257 | kBucketPolyRed(ro.bucket,p, |
---|
| 4258 | p_len, |
---|
| 4259 | c->strat->kNoether); |
---|
| 4260 | } |
---|
| 4261 | |
---|
| 4262 | void simple_reducer::target_is_a_sum_reduce(red_object & ro){ |
---|
| 4263 | pTest(p); |
---|
| 4264 | kbTest(ro.bucket); |
---|
| 4265 | kbTest(ro.sum->ac->bucket); |
---|
| 4266 | assume(ro.sum!=NULL); |
---|
| 4267 | assume(ro.sum->ac!=NULL); |
---|
| 4268 | if(ro.sum->ac->last_reduction_id!=reduction_id){ |
---|
| 4269 | number n1=kBucketPolyRed(ro.sum->ac->bucket,p, p_len, c->strat->kNoether); |
---|
| 4270 | number n2=nMult(n1,ro.sum->ac->multiplied); |
---|
| 4271 | nDelete(&ro.sum->ac->multiplied); |
---|
| 4272 | nDelete(&n1); |
---|
| 4273 | ro.sum->ac->multiplied=n2; |
---|
| 4274 | poly lm=kBucketGetLm(ro.sum->ac->bucket); |
---|
| 4275 | if (lm) |
---|
| 4276 | ro.sum->ac->sev=pGetShortExpVector(lm); |
---|
| 4277 | ro.sum->ac->last_reduction_id=reduction_id; |
---|
| 4278 | } |
---|
| 4279 | ro.sev=ro.sum->ac->sev; |
---|
| 4280 | ro.p=kBucketGetLm(ro.sum->ac->bucket); |
---|
| 4281 | } |
---|
| 4282 | void simple_reducer::reduce(red_object* r, int l, int u){ |
---|
| 4283 | this->pre_reduce(r,l,u); |
---|
| 4284 | int i; |
---|
| 4285 | //debug start |
---|
| 4286 | int im; |
---|
| 4287 | // for(im=l;im<=u;im++) |
---|
| 4288 | // assume(is_valid_ro(r[im])); |
---|
| 4289 | |
---|
| 4290 | |
---|
| 4291 | //debug end |
---|
| 4292 | |
---|
| 4293 | for(i=l;i<=u;i++){ |
---|
| 4294 | |
---|
| 4295 | |
---|
| 4296 | if(r[i].sum==NULL) |
---|
| 4297 | this->target_is_no_sum_reduce(r[i]); |
---|
| 4298 | |
---|
| 4299 | else |
---|
| 4300 | { |
---|
| 4301 | this->target_is_a_sum_reduce(r[i]); |
---|
| 4302 | //reduce and adjust multiplied |
---|
| 4303 | r[i].sum->ac->last_reduction_id=reduction_id; |
---|
| 4304 | |
---|
| 4305 | } |
---|
| 4306 | //most elegant would be multimethods at this point and subclassing |
---|
| 4307 | //red_object for sum |
---|
| 4308 | |
---|
| 4309 | } |
---|
| 4310 | for(i=l;i<=u;i++){ |
---|
| 4311 | r[i].validate(); |
---|
| 4312 | #ifdef TGB_DEBUG |
---|
| 4313 | if (r[i].sum) r[i].sev=r[i].sum->ac->sev; |
---|
| 4314 | |
---|
| 4315 | #endif |
---|
| 4316 | } |
---|
| 4317 | } |
---|
| 4318 | reduction_step::~reduction_step(){} |
---|
| 4319 | simple_reducer::~simple_reducer(){ |
---|
| 4320 | if(fill_back!=NULL) |
---|
| 4321 | { |
---|
| 4322 | kBucketInit(fill_back,p,p_len); |
---|
| 4323 | } |
---|
| 4324 | fill_back=NULL; |
---|
| 4325 | |
---|
| 4326 | } |
---|
| 4327 | join_simple_reducer::~join_simple_reducer(){ |
---|
| 4328 | if(fill_back!=NULL) |
---|
| 4329 | { |
---|
| 4330 | kBucketInit(fill_back,p,p_len); |
---|
| 4331 | } |
---|
| 4332 | fill_back=NULL; |
---|
| 4333 | |
---|
| 4334 | } |
---|
| 4335 | void multi_reduce_step(find_erg & erg, red_object* r, calc_dat* c){ |
---|
| 4336 | static int id=0; |
---|
| 4337 | id++; |
---|
| 4338 | |
---|
| 4339 | int rn=erg.reduce_by; |
---|
| 4340 | poly red; |
---|
| 4341 | int red_len; |
---|
| 4342 | simple_reducer* pointer; |
---|
| 4343 | BOOLEAN woc=FALSE; |
---|
| 4344 | if(erg.fromS){ |
---|
| 4345 | red=c->strat->S[rn]; |
---|
| 4346 | red_len=c->strat->lenS[rn]; |
---|
| 4347 | assume(red_len==pLength(red)); |
---|
| 4348 | } |
---|
| 4349 | else |
---|
| 4350 | { |
---|
| 4351 | r[rn].flatten(); |
---|
| 4352 | kBucketClear(r[rn].bucket,&red,&red_len); |
---|
| 4353 | if (!rField_is_Zp(c->r)) |
---|
| 4354 | { |
---|
| 4355 | pContent(red); |
---|
| 4356 | pCleardenom(red);//should be unnecessary |
---|
| 4357 | |
---|
| 4358 | } |
---|
| 4359 | pNormalize(red); |
---|
| 4360 | red_len=pLength(red); |
---|
| 4361 | } |
---|
| 4362 | if (erg.to_reduce_u-erg.to_reduce_l>5){ |
---|
| 4363 | woc=TRUE; |
---|
| 4364 | // poly m=pOne(); |
---|
| 4365 | poly m=c->tmp_lm; |
---|
| 4366 | pSetCoeff(m,nInit(1)); |
---|
| 4367 | for(int i=1;i<=pVariables;i++) |
---|
| 4368 | pSetExp(m,i,(pGetExp(r[erg.to_reduce_l].p, i)-pGetExp(red,i))); |
---|
| 4369 | pSetm(m); |
---|
| 4370 | poly red_cp=ppMult_mm(red,m); |
---|
| 4371 | |
---|
| 4372 | if(!erg.fromS){ |
---|
| 4373 | kBucketInit(r[rn].bucket,red,red_len); |
---|
| 4374 | } |
---|
| 4375 | //now reduce the copy |
---|
| 4376 | //static poly redNF2 (poly h,calc_dat* c , int &len, number& m,int n) |
---|
| 4377 | redTailShort(red_cp,c->strat); |
---|
| 4378 | //number mul; |
---|
| 4379 | // red_len--; |
---|
| 4380 | // red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length); |
---|
| 4381 | // pSetCoeff(red_cp,nMult(red_cp->coef,mul)); |
---|
| 4382 | // nDelete(&mul); |
---|
| 4383 | // red_len++; |
---|
| 4384 | red=red_cp; |
---|
| 4385 | red_len=pLength(red); |
---|
| 4386 | // pDelete(&m); |
---|
| 4387 | |
---|
| 4388 | } |
---|
| 4389 | int i; |
---|
| 4390 | |
---|
| 4391 | |
---|
| 4392 | int red_c=0; |
---|
| 4393 | if(red_len>2*c->average_length){ |
---|
| 4394 | for(i=erg.to_reduce_l;i<=erg.to_reduce_u;i++){ |
---|
| 4395 | if((r[i].sum==NULL) ||(r[i].sum->ac->counter<=AC_FLATTEN)) red_c++; |
---|
| 4396 | } |
---|
| 4397 | } |
---|
| 4398 | assume(red_len==pLength(red)); |
---|
| 4399 | if (red_c>=AC_NEW_MIN) |
---|
| 4400 | pointer=new join_simple_reducer(red,red_len,r[erg.to_reduce_l].p); |
---|
| 4401 | else |
---|
| 4402 | pointer=new simple_reducer(red,red_len,c); |
---|
| 4403 | |
---|
| 4404 | if ((!woc) && (!erg.fromS)) |
---|
| 4405 | pointer->fill_back=r[rn].bucket; |
---|
| 4406 | else |
---|
| 4407 | pointer->fill_back=NULL; |
---|
| 4408 | pointer->reduction_id=id; |
---|
| 4409 | pointer->c=c; |
---|
| 4410 | |
---|
| 4411 | pointer->reduce(r,erg.to_reduce_l, erg.to_reduce_u); |
---|
| 4412 | if(woc) pDelete(&pointer->p); |
---|
| 4413 | delete pointer; |
---|
| 4414 | |
---|
| 4415 | }; |
---|
| 4416 | |
---|
| 4417 | void join_simple_reducer::target_is_no_sum_reduce(red_object & ro){ |
---|
| 4418 | kbTest(ro.bucket); |
---|
| 4419 | ro.sum=new formal_sum_descriptor(); |
---|
| 4420 | ro.sum->ac=ac; |
---|
| 4421 | ac->counter++; |
---|
| 4422 | kBucket_pt bucket=ro.bucket; |
---|
| 4423 | poly a1 = pNext(p), lm = kBucketExtractLm(bucket); |
---|
| 4424 | BOOLEAN reset_vec=FALSE; |
---|
| 4425 | number rn; |
---|
| 4426 | assume(a1!=NULL); |
---|
| 4427 | number an = pGetCoeff(p), bn = pGetCoeff(lm); |
---|
| 4428 | lm->next=NULL; |
---|
| 4429 | int ct = ksCheckCoeff(&an, &bn); |
---|
| 4430 | ro.sum->c_ac=nNeg(bn); |
---|
| 4431 | ro.sum->c_my=an; |
---|
| 4432 | assume(nIsZero(nAdd(nMult(ro.sum->c_my,lm->coef),nMult(p->coef,ro.sum->c_ac) ))); |
---|
| 4433 | if (p_GetComp(p, bucket->bucket_ring) != p_GetComp(lm, bucket->bucket_ring)) |
---|
| 4434 | { |
---|
| 4435 | p_SetCompP(a1, p_GetComp(lm, bucket->bucket_ring), bucket->bucket_ring); |
---|
| 4436 | reset_vec = TRUE; |
---|
| 4437 | p_SetComp(lm, p_GetComp(p, bucket->bucket_ring), bucket->bucket_ring); |
---|
| 4438 | p_Setm(lm, bucket->bucket_ring); |
---|
| 4439 | } |
---|
| 4440 | |
---|
| 4441 | |
---|
| 4442 | |
---|
| 4443 | |
---|
| 4444 | p_DeleteLm(&lm, bucket->bucket_ring); |
---|
| 4445 | if (reset_vec) p_SetCompP(a1, 0, bucket->bucket_ring); |
---|
| 4446 | kbTest(bucket); |
---|
| 4447 | |
---|
| 4448 | } |
---|
| 4449 | |
---|
| 4450 | reduction_accumulator::reduction_accumulator(poly p, int p_len, poly high_to){ |
---|
| 4451 | //sev needs to be removed from interfaces,makes no sense |
---|
| 4452 | |
---|
| 4453 | |
---|
| 4454 | poly my=pOne(); |
---|
| 4455 | counter=0; |
---|
| 4456 | |
---|
| 4457 | for(int i=1;i<=pVariables;i++) |
---|
| 4458 | pSetExp(my,i,(pGetExp(high_to, i)-pGetExp(p,i))); |
---|
| 4459 | pSetm(my); |
---|
| 4460 | |
---|
| 4461 | last_reduction_id=-1; |
---|
| 4462 | multiplied=nInit(1); |
---|
| 4463 | bucket=kBucketCreate(currRing); |
---|
| 4464 | poly a=pMult_mm(pCopy(p->next),my); |
---|
| 4465 | |
---|
| 4466 | this->sev=pGetShortExpVector(a); |
---|
| 4467 | kBucketInit(bucket, a,p_len-1); |
---|
| 4468 | pDelete(&my); |
---|
| 4469 | } |
---|
| 4470 | void simple_reducer:: pre_reduce(red_object* r, int l, int u){} |
---|
| 4471 | void join_simple_reducer:: pre_reduce(red_object* r, int l, int u){ |
---|
| 4472 | for(int i=l;i<=u;i++) |
---|
| 4473 | { |
---|
| 4474 | if (r[i].sum){ |
---|
| 4475 | if(r[i].sum->ac->counter<=AC_FLATTEN) r[i].flatten(); |
---|
| 4476 | |
---|
| 4477 | } |
---|
| 4478 | } |
---|
| 4479 | } |
---|