[b553e5] | 1 | //! \file tgb.cc |
---|
[4f858ce] | 2 | // multiple rings |
---|
| 3 | // shorten_tails und dessen Aufrufe pruefen wlength!!! |
---|
[6b9532] | 4 | /**************************************** |
---|
| 5 | * Computer Algebra System SINGULAR * |
---|
| 6 | ****************************************/ |
---|
[9cbb7a3] | 7 | /* $Id: tgb.cc,v 1.25 2005-05-17 15:26:27 bricken Exp $ */ |
---|
[6b9532] | 8 | /* |
---|
| 9 | * ABSTRACT: slimgb and F4 implementation |
---|
| 10 | */ |
---|
[4f858ce] | 11 | |
---|
| 12 | #include "tgb.h" |
---|
[0f7b79] | 13 | #include "tgb_internal.h" |
---|
[b055de9] | 14 | #include "tgbgauss.h" |
---|
[b75d13] | 15 | #include "F4.h" |
---|
[4f858ce] | 16 | static const int bundle_size=100; |
---|
| 17 | #if 1 |
---|
| 18 | static omBin lm_bin=NULL; |
---|
| 19 | static inline poly p_Init_Special(const ring r) |
---|
| 20 | { |
---|
| 21 | return p_Init(r,lm_bin); |
---|
| 22 | } |
---|
| 23 | static inline poly pOne_Special(const ring r=currRing) |
---|
| 24 | { |
---|
| 25 | poly rc = p_Init_Special(r); |
---|
| 26 | pSetCoeff0(rc,r->cf->nInit(1)); |
---|
| 27 | return rc; |
---|
| 28 | } |
---|
| 29 | // zum Initialiseren: in t_rep_gb plazieren: |
---|
| 30 | |
---|
| 31 | #endif |
---|
| 32 | #define LEN_VAR3 |
---|
| 33 | #define degbound(p) assume(pTotaldegree(p)<10) |
---|
| 34 | //#define inDebug(p) assume((debug_Ideal==NULL)||(kNF(debug_Ideal,NULL,p,0,0)==0)) |
---|
| 35 | |
---|
| 36 | //die meisten Varianten stossen sich an coef_buckets |
---|
| 37 | #ifdef LEN_VAR1 |
---|
| 38 | // erste Variante: Laenge: Anzahl der Monome |
---|
| 39 | inline int pSLength(poly p, int l) { |
---|
| 40 | return l; } |
---|
| 41 | inline int kSBucketLength(kBucket* bucket, poly lm) {return bucket_guess(bucket);} |
---|
| 42 | #endif |
---|
| 43 | |
---|
| 44 | #ifdef LEN_VAR2 |
---|
| 45 | // 2. Variante: Laenge: Platz fuer die Koeff. |
---|
| 46 | int pSLength(poly p,int l) |
---|
| 47 | { |
---|
| 48 | int s=0; |
---|
| 49 | while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } |
---|
| 50 | return s; |
---|
| 51 | } |
---|
| 52 | int kSBucketLength(kBucket* b, poly lm) |
---|
| 53 | { |
---|
| 54 | int s=0; |
---|
| 55 | int i; |
---|
| 56 | for (i=MAX_BUCKET;i>=0;i--) |
---|
| 57 | { |
---|
| 58 | s+=pSLength(b->buckets[i],0); |
---|
| 59 | } |
---|
| 60 | return s; |
---|
| 61 | } |
---|
| 62 | #endif |
---|
| 63 | |
---|
| 64 | #ifdef LEN_VAR3 |
---|
| 65 | // 3.Variante: Laenge: Platz fuer Leitk * Monomanzahl |
---|
| 66 | inline int pSLength(poly p,int l) |
---|
| 67 | { |
---|
| 68 | int c=nSize(pGetCoeff(p)); |
---|
| 69 | return c*l /*pLength(p)*/; |
---|
| 70 | } |
---|
| 71 | int kSBucketLength(kBucket* b, poly lm=NULL) |
---|
| 72 | { |
---|
| 73 | int s=0; |
---|
| 74 | int c; |
---|
| 75 | if(lm==NULL) |
---|
| 76 | c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 77 | else |
---|
| 78 | c=nSize(pGetCoeff(lm)); |
---|
| 79 | int i; |
---|
| 80 | for (i=b->buckets_used;i>=0;i--) |
---|
| 81 | { |
---|
| 82 | assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL)); |
---|
| 83 | s+=b->buckets_length[i] /*pLength(b->buckets[i])*/; |
---|
| 84 | } |
---|
| 85 | return s*c; |
---|
| 86 | } |
---|
| 87 | #endif |
---|
| 88 | |
---|
| 89 | #ifdef LEN_VAR4 |
---|
| 90 | // 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.) |
---|
| 91 | int pSLength(poly p, int l) |
---|
| 92 | { |
---|
| 93 | int s=1; |
---|
| 94 | int c=nSize(pGetCoeff(p)); |
---|
| 95 | pIter(p); |
---|
| 96 | while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); } |
---|
| 97 | return s*c; |
---|
| 98 | } |
---|
| 99 | int kSBucketLength(kBucket* b) |
---|
| 100 | { |
---|
| 101 | int s=1; |
---|
| 102 | int c=nSize(pGetCoeff(kBucketGetLm(b))); |
---|
| 103 | int i; |
---|
| 104 | for (i=MAX_BUCKET;i>0;i--) |
---|
| 105 | { |
---|
| 106 | if(b->buckets[i]==NULL) continue; |
---|
| 107 | s+=pSLength(b->buckets[i],0); |
---|
| 108 | } |
---|
| 109 | return s*c; |
---|
| 110 | } |
---|
| 111 | #endif |
---|
[9cbb7a3] | 112 | static int do_pELength(poly p, slimgb_alg* c, int dlm=-1){ |
---|
[4f858ce] | 113 | if(p==NULL) return 0; |
---|
| 114 | int s=0; |
---|
| 115 | poly pi=p; |
---|
| 116 | if(dlm<0){ |
---|
| 117 | dlm=pTotaldegree(p,c->r); |
---|
| 118 | s=1; |
---|
| 119 | pi=p->next; |
---|
| 120 | } |
---|
| 121 | |
---|
| 122 | while(pi){ |
---|
| 123 | int d=pTotaldegree(pi,c->r); |
---|
| 124 | if(d>dlm) |
---|
| 125 | s+=1+d-dlm; |
---|
| 126 | else |
---|
| 127 | ++s; |
---|
| 128 | pi=pi->next; |
---|
| 129 | } |
---|
| 130 | return s; |
---|
| 131 | } |
---|
[9cbb7a3] | 132 | int kEBucketLength(kBucket* b, poly lm,slimgb_alg* ca) |
---|
[4f858ce] | 133 | { |
---|
| 134 | int s=0; |
---|
| 135 | if(lm==NULL){ |
---|
| 136 | lm=kBucketGetLm(b); |
---|
| 137 | } |
---|
| 138 | if(lm==NULL) return 0; |
---|
| 139 | int d=pTotaldegree(lm,ca->r); |
---|
| 140 | int i; |
---|
| 141 | for (i=b->buckets_used;i>=0;i--) |
---|
| 142 | { |
---|
| 143 | if(b->buckets[i]==NULL) continue; |
---|
| 144 | s+=do_pELength(b->buckets[i],ca,d); |
---|
| 145 | } |
---|
| 146 | return s; |
---|
| 147 | } |
---|
| 148 | |
---|
[9cbb7a3] | 149 | static inline int pELength(poly p, slimgb_alg* c,int l){ |
---|
[4f858ce] | 150 | if (p==NULL) return 0; |
---|
| 151 | return do_pELength(p,c); |
---|
| 152 | } |
---|
[9cbb7a3] | 153 | // static int quality(poly p, int len, slimgb_alg* c){ |
---|
[4f858ce] | 154 | // if (c->is_char0) return pSLength(p,len); |
---|
| 155 | // return pLength(p); |
---|
| 156 | // } |
---|
[9cbb7a3] | 157 | static inline int pQuality(poly p, slimgb_alg* c, int l=-1){ |
---|
[4f858ce] | 158 | |
---|
| 159 | if(l<0) |
---|
| 160 | l=pLength(p); |
---|
| 161 | if(c->is_char0) return pSLength(p,l); |
---|
| 162 | if((pLexOrder) &&(!c->is_homog)) return pELength(p,c,l); |
---|
| 163 | return l; |
---|
| 164 | } |
---|
| 165 | static inline int pTotaldegree_full(poly p){ |
---|
| 166 | int r=0; |
---|
| 167 | while(p){ |
---|
| 168 | int d=pTotaldegree(p); |
---|
| 169 | r=si_max(r,d); |
---|
| 170 | pIter(p); |
---|
| 171 | } |
---|
| 172 | return r; |
---|
| 173 | } |
---|
| 174 | |
---|
[9cbb7a3] | 175 | int red_object::guess_quality(slimgb_alg* c){ |
---|
[4f858ce] | 176 | //works at the moment only for lenvar 1, because in different |
---|
| 177 | //case, you have to look on coefs |
---|
| 178 | int s=0; |
---|
| 179 | if (c->is_char0) |
---|
| 180 | s=kSBucketLength(bucket,this->p); |
---|
| 181 | else |
---|
| 182 | { |
---|
| 183 | if((pLexOrder) &&(!c->is_homog)) |
---|
| 184 | //if (false) |
---|
| 185 | s=kEBucketLength(this->bucket,this->p,c); |
---|
| 186 | else s=bucket_guess(bucket); |
---|
| 187 | } |
---|
[bddc9d] | 188 | |
---|
[4f858ce] | 189 | return s; |
---|
| 190 | } |
---|
[9cbb7a3] | 191 | // static int guess_quality(const red_object & p, slimgb_alg* c){ |
---|
[4f858ce] | 192 | // //looks only on bucket |
---|
| 193 | // if (c->is_char0) return kSBucketLength(p.bucket,p.p); |
---|
| 194 | // if((pLexOrder) &&(!c->is_homog)) return kEBucketLength(p.bucket,p.p,c); |
---|
| 195 | // return (bucket_guess(p.bucket)); |
---|
| 196 | // } |
---|
| 197 | |
---|
| 198 | static void finalize_reduction_step(reduction_step* r){ |
---|
| 199 | delete r; |
---|
| 200 | } |
---|
| 201 | static int LObject_better_gen(const void* ap, const void* bp) |
---|
| 202 | { |
---|
| 203 | LObject* a=*(LObject**)ap; |
---|
| 204 | LObject* b=*(LObject**)bp; |
---|
| 205 | return(pLmCmp(a->p,b->p)); |
---|
| 206 | } |
---|
| 207 | static int red_object_better_gen(const void* ap, const void* bp) |
---|
| 208 | { |
---|
| 209 | |
---|
| 210 | |
---|
| 211 | return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p)); |
---|
| 212 | } |
---|
| 213 | |
---|
| 214 | |
---|
| 215 | static int pLmCmp_func_inverted(const void* ap1, const void* ap2){ |
---|
| 216 | poly p1,p2; |
---|
| 217 | p1=*((poly*) ap1); |
---|
| 218 | p2=*((poly*)ap2); |
---|
| 219 | |
---|
| 220 | return -pLmCmp(p1,p2); |
---|
| 221 | } |
---|
| 222 | |
---|
[b75d13] | 223 | int tgb_pair_better_gen2(const void* ap,const void* bp){ |
---|
| 224 | return(-tgb_pair_better_gen(ap,bp)); |
---|
[4f858ce] | 225 | } |
---|
[b75d13] | 226 | int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj){ |
---|
[4f858ce] | 227 | int i; |
---|
| 228 | long not_sev=~obj.sev; |
---|
| 229 | poly p=obj.p; |
---|
| 230 | for(i=0;i<=strat->sl;i++){ |
---|
| 231 | if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) |
---|
| 232 | return i; |
---|
| 233 | } |
---|
| 234 | return -1; |
---|
| 235 | } |
---|
[b75d13] | 236 | int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev){ |
---|
[4f858ce] | 237 | int i; |
---|
| 238 | long not_sev=~sev; |
---|
| 239 | for(i=0;i<=strat->sl;i++){ |
---|
| 240 | if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev)) |
---|
| 241 | return i; |
---|
| 242 | } |
---|
| 243 | return -1; |
---|
| 244 | } |
---|
[9cbb7a3] | 245 | static int posInPairs (sorted_pair_node** p, int pn, sorted_pair_node* qe,slimgb_alg* c,int an=0) |
---|
[4f858ce] | 246 | { |
---|
| 247 | if(pn==0) return 0; |
---|
| 248 | |
---|
| 249 | int length=pn-1; |
---|
| 250 | int i; |
---|
| 251 | //int an = 0; |
---|
| 252 | int en= length; |
---|
| 253 | |
---|
| 254 | if (pair_better(qe,p[en],c)) |
---|
| 255 | return length+1; |
---|
| 256 | |
---|
| 257 | while(1) |
---|
| 258 | { |
---|
| 259 | //if (an >= en-1) |
---|
| 260 | if(en-1<=an) |
---|
| 261 | { |
---|
| 262 | if (pair_better(p[an],qe,c)) return an; |
---|
| 263 | return en; |
---|
| 264 | } |
---|
| 265 | i=(an+en) / 2; |
---|
| 266 | if (pair_better(p[i],qe,c)) |
---|
| 267 | en=i; |
---|
| 268 | else an=i; |
---|
| 269 | } |
---|
| 270 | } |
---|
| 271 | |
---|
| 272 | static BOOLEAN ascending(int* i,int top){ |
---|
| 273 | if(top<1) return TRUE; |
---|
| 274 | if(i[top]<i[top-1]) return FALSE; |
---|
| 275 | return ascending(i,top-1); |
---|
| 276 | } |
---|
| 277 | |
---|
[9cbb7a3] | 278 | sorted_pair_node** spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c){ |
---|
[4f858ce] | 279 | int i; |
---|
[ec8a6b6] | 280 | int* a= (int*) omalloc(qn*sizeof(int)); |
---|
[4f858ce] | 281 | // int mc; |
---|
| 282 | // PrintS("Debug\n"); |
---|
| 283 | // for(mc=0;mc<qn;mc++) |
---|
| 284 | // { |
---|
| 285 | |
---|
| 286 | // wrp(q[mc]->lcm_of_lm); |
---|
| 287 | // PrintS("\n"); |
---|
| 288 | // } |
---|
| 289 | // PrintS("Debug they are in\n"); |
---|
| 290 | // for(mc=0;mc<pn;mc++) |
---|
| 291 | // { |
---|
| 292 | |
---|
| 293 | // wrp(p[mc]->lcm_of_lm); |
---|
| 294 | // PrintS("\n"); |
---|
| 295 | // } |
---|
| 296 | int lastpos=0; |
---|
| 297 | for(i=0;i<qn;i++){ |
---|
| 298 | lastpos=posInPairs(p,pn,q[i],c, si_max(lastpos-1,0)); |
---|
| 299 | // cout<<lastpos<<"\n"; |
---|
| 300 | a[i]=lastpos; |
---|
| 301 | |
---|
| 302 | } |
---|
| 303 | if((pn+qn)>c->max_pairs){ |
---|
[ec8a6b6] | 304 | p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 305 | c->max_pairs=2*(pn+qn); |
---|
| 306 | } |
---|
| 307 | for(i=qn-1;i>=0;i--){ |
---|
| 308 | size_t size; |
---|
| 309 | if(qn-1>i) |
---|
| 310 | size=(a[i+1]-a[i])*sizeof(sorted_pair_node*); |
---|
| 311 | else |
---|
| 312 | size=(pn-a[i])*sizeof(sorted_pair_node*); //as indices begin with 0 |
---|
| 313 | memmove (p+a[i]+(1+i), p+a[i], size); |
---|
| 314 | p[a[i]+i]=q[i]; |
---|
| 315 | } |
---|
| 316 | omfree(a); |
---|
| 317 | return p; |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | |
---|
[9cbb7a3] | 321 | static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c){ |
---|
[4f858ce] | 322 | |
---|
| 323 | |
---|
| 324 | poly p1=c->S->m[pos1]; |
---|
| 325 | poly p2=c->S->m[pos2]; |
---|
| 326 | ring r=c->r; |
---|
| 327 | |
---|
| 328 | |
---|
| 329 | if (pGetComp(p1) > 0 || pGetComp(p2) > 0) |
---|
| 330 | return FALSE; |
---|
| 331 | int i = 1; |
---|
| 332 | poly m=NULL; |
---|
| 333 | poly gcd1=c->gcd_of_terms[pos1]; |
---|
| 334 | poly gcd2=c->gcd_of_terms[pos2]; |
---|
| 335 | |
---|
| 336 | if((gcd1!=NULL) && (gcd2!=NULL)) |
---|
| 337 | { |
---|
| 338 | gcd1->next=gcd2; //may ordered incorrect |
---|
| 339 | poly m=gcd_of_terms(gcd1,c->r); |
---|
| 340 | gcd1->next=NULL; |
---|
| 341 | |
---|
| 342 | } |
---|
| 343 | |
---|
| 344 | if (m==NULL) |
---|
| 345 | { |
---|
| 346 | loop |
---|
| 347 | { |
---|
| 348 | if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; |
---|
| 349 | if (i == pVariables){ |
---|
| 350 | //PrintS("trivial"); |
---|
| 351 | return TRUE; |
---|
| 352 | } |
---|
| 353 | i++; |
---|
| 354 | } |
---|
| 355 | } |
---|
| 356 | else |
---|
| 357 | { |
---|
| 358 | loop |
---|
| 359 | { |
---|
| 360 | if (pGetExp(p1, i)-pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i)) return FALSE; |
---|
| 361 | if (i == pVariables){ |
---|
| 362 | pDelete(&m); |
---|
| 363 | //PrintS("trivial"); |
---|
| 364 | return TRUE; |
---|
| 365 | } |
---|
| 366 | i++; |
---|
| 367 | } |
---|
| 368 | } |
---|
| 369 | |
---|
| 370 | |
---|
| 371 | |
---|
| 372 | |
---|
| 373 | } |
---|
| 374 | |
---|
[b553e5] | 375 | //! returns position sets w as weight |
---|
[9cbb7a3] | 376 | int find_best(red_object* r,int l, int u, int &w, slimgb_alg* c){ |
---|
[4f858ce] | 377 | int best=l; |
---|
| 378 | int i; |
---|
| 379 | w=r[l].guess_quality(c); |
---|
| 380 | for(i=l+1;i<=u;i++){ |
---|
| 381 | int w2=r[i].guess_quality(c); |
---|
| 382 | if(w2<w){ |
---|
| 383 | w=w2; |
---|
| 384 | best=i; |
---|
| 385 | } |
---|
| 386 | |
---|
| 387 | } |
---|
| 388 | return best; |
---|
| 389 | } |
---|
| 390 | |
---|
| 391 | |
---|
| 392 | void red_object::canonicalize(){ |
---|
| 393 | kBucketCanonicalize(bucket); |
---|
[bddc9d] | 394 | |
---|
[4f858ce] | 395 | |
---|
| 396 | } |
---|
[9cbb7a3] | 397 | BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c){ |
---|
[4f858ce] | 398 | assume(i>=0); |
---|
| 399 | assume(j>=0); |
---|
| 400 | if (has_t_rep(i,j,c)) return TRUE; |
---|
| 401 | //poly lm=pOne(); |
---|
| 402 | assume (c->tmp_lm!=NULL); |
---|
| 403 | poly lm=c->tmp_lm; |
---|
| 404 | |
---|
| 405 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 406 | pSetm(lm); |
---|
| 407 | assume(lm!=NULL); |
---|
| 408 | //int deciding_deg= pTotaldegree(lm); |
---|
| 409 | int* i_con =make_connections(i,j,lm,c); |
---|
| 410 | //p_Delete(&lm,c->r); |
---|
| 411 | |
---|
| 412 | |
---|
| 413 | for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ |
---|
| 414 | if (i_con[n]==j){ |
---|
| 415 | now_t_rep(i,j,c); |
---|
| 416 | omfree(i_con); |
---|
| 417 | |
---|
| 418 | return TRUE; |
---|
| 419 | } |
---|
| 420 | } |
---|
| 421 | omfree(i_con); |
---|
| 422 | |
---|
| 423 | return FALSE; |
---|
| 424 | } |
---|
| 425 | BOOLEAN lenS_correct(kStrategy strat){ |
---|
| 426 | int i; |
---|
| 427 | for(i=0;i<=strat->sl;i++){ |
---|
| 428 | if (strat->lenS[i]!=pLength(strat->S[i])) |
---|
| 429 | return FALSE; |
---|
| 430 | } |
---|
| 431 | return TRUE; |
---|
| 432 | } |
---|
| 433 | |
---|
[9cbb7a3] | 434 | static void notice_miss(int i, int j, slimgb_alg* c){ |
---|
[4f858ce] | 435 | if (TEST_OPT_PROT) |
---|
| 436 | PrintS("-"); |
---|
| 437 | |
---|
| 438 | } |
---|
| 439 | |
---|
[9cbb7a3] | 440 | static void cleanS(kStrategy strat, slimgb_alg* c){ |
---|
[4f858ce] | 441 | int i=0; |
---|
| 442 | LObject P; |
---|
| 443 | while(i<=strat->sl){ |
---|
| 444 | P.p=strat->S[i]; |
---|
| 445 | P.sev=strat->sevS[i]; |
---|
| 446 | if(kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P)!=i) |
---|
| 447 | { |
---|
| 448 | deleteInS(i,strat); |
---|
| 449 | //remember destroying poly |
---|
| 450 | BOOLEAN found=FALSE; |
---|
| 451 | int j; |
---|
| 452 | for(j=0;j<c->n;j++) |
---|
| 453 | if(c->S->m[j]==P.p) |
---|
| 454 | { |
---|
| 455 | found=TRUE; |
---|
| 456 | break; |
---|
| 457 | } |
---|
| 458 | if (!found) |
---|
| 459 | pDelete(&P.p); |
---|
| 460 | //remember additional reductors |
---|
| 461 | } |
---|
| 462 | else i++; |
---|
| 463 | } |
---|
| 464 | } |
---|
| 465 | static int bucket_guess(kBucket* bucket){ |
---|
| 466 | int sum=0; |
---|
| 467 | int i; |
---|
| 468 | for (i=bucket->buckets_used;i>=0;i--){ |
---|
| 469 | if(bucket->buckets[i]) |
---|
| 470 | sum+=bucket->buckets_length[i]; |
---|
| 471 | } |
---|
| 472 | return sum; |
---|
| 473 | } |
---|
| 474 | |
---|
| 475 | |
---|
| 476 | |
---|
| 477 | |
---|
| 478 | |
---|
| 479 | |
---|
[9cbb7a3] | 480 | static int add_to_reductors(slimgb_alg* c, poly h, int len){ |
---|
[4f858ce] | 481 | //inDebug(h); |
---|
| 482 | assume(lenS_correct(c->strat)); |
---|
| 483 | assume(len==pLength(h)); |
---|
| 484 | int i; |
---|
| 485 | // if (c->is_char0) |
---|
| 486 | // i=simple_posInS(c->strat,h,pSLength(h,len),c->is_char0); |
---|
| 487 | // else |
---|
| 488 | // i=simple_posInS(c->strat,h,len,c->is_char0); |
---|
| 489 | |
---|
| 490 | LObject P; memset(&P,0,sizeof(P)); |
---|
| 491 | P.tailRing=c->r; |
---|
| 492 | P.p=h; /*p_Copy(h,c->r);*/ |
---|
| 493 | P.FDeg=pFDeg(P.p,c->r); |
---|
| 494 | |
---|
| 495 | if (!rField_is_Zp(c->r)){ |
---|
| 496 | pCleardenom(P.p); |
---|
| 497 | pContent(P.p); //is a duplicate call, but belongs here |
---|
| 498 | |
---|
| 499 | } |
---|
| 500 | else |
---|
| 501 | pNorm(P.p); |
---|
| 502 | pNormalize(P.p); |
---|
| 503 | int pq=pQuality(h,c,len); |
---|
| 504 | i=simple_posInS(c->strat,h,pq); |
---|
| 505 | c->strat->enterS(P,i,c->strat,-1); |
---|
| 506 | |
---|
| 507 | |
---|
| 508 | |
---|
| 509 | c->strat->lenS[i]=len; |
---|
| 510 | assume(pLength(c->strat->S[i])==c->strat->lenS[i]); |
---|
| 511 | if(c->strat->lenSw) |
---|
| 512 | c->strat->lenSw[i]=pq; |
---|
| 513 | |
---|
| 514 | return i; |
---|
| 515 | |
---|
| 516 | } |
---|
[9cbb7a3] | 517 | static void length_one_crit(slimgb_alg* c, int pos, int len) |
---|
[4f858ce] | 518 | { |
---|
| 519 | if (len==1) |
---|
| 520 | { |
---|
| 521 | int i; |
---|
| 522 | for ( i=0;i<pos;i++) |
---|
| 523 | { |
---|
| 524 | if (c->lengths[i]==1) |
---|
| 525 | c->states[pos][i]=HASTREP; |
---|
| 526 | } |
---|
| 527 | for ( i=pos+1;i<c->n;i++){ |
---|
| 528 | if (c->lengths[i]==1) |
---|
| 529 | c->states[i][pos]=HASTREP; |
---|
| 530 | } |
---|
| 531 | shorten_tails(c,c->S->m[pos]); |
---|
| 532 | } |
---|
| 533 | } |
---|
[9cbb7a3] | 534 | static sorted_pair_node* find_next_pair2(slimgb_alg* c, BOOLEAN go_higher){ |
---|
[4f858ce] | 535 | clean_top_of_pair_list(c); |
---|
| 536 | sorted_pair_node* s=pop_pair(c); |
---|
| 537 | |
---|
| 538 | |
---|
| 539 | return s; |
---|
| 540 | } |
---|
| 541 | |
---|
| 542 | static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat) |
---|
| 543 | { |
---|
| 544 | assume(old_pos>=new_pos); |
---|
| 545 | poly p=strat->S[old_pos]; |
---|
| 546 | int ecart=strat->ecartS[old_pos]; |
---|
| 547 | long sev=strat->sevS[old_pos]; |
---|
| 548 | int s_2_r=strat->S_2_R[old_pos]; |
---|
| 549 | int length=strat->lenS[old_pos]; |
---|
| 550 | assume(length==pLength(strat->S[old_pos])); |
---|
| 551 | int length_w; |
---|
| 552 | if(strat->lenSw) |
---|
| 553 | length_w=strat->lenSw[old_pos]; |
---|
| 554 | int i; |
---|
| 555 | for (i=old_pos; i>new_pos; i--) |
---|
| 556 | { |
---|
| 557 | strat->S[i] = strat->S[i-1]; |
---|
| 558 | strat->ecartS[i] = strat->ecartS[i-1]; |
---|
| 559 | strat->sevS[i] = strat->sevS[i-1]; |
---|
| 560 | strat->S_2_R[i] = strat->S_2_R[i-1]; |
---|
| 561 | } |
---|
| 562 | if (strat->lenS!=NULL) |
---|
| 563 | for (i=old_pos; i>new_pos; i--) |
---|
| 564 | strat->lenS[i] = strat->lenS[i-1]; |
---|
| 565 | if (strat->lenSw!=NULL) |
---|
| 566 | for (i=old_pos; i>new_pos; i--) |
---|
| 567 | strat->lenSw[i] = strat->lenSw[i-1]; |
---|
| 568 | |
---|
| 569 | strat->S[new_pos]=p; |
---|
| 570 | strat->ecartS[new_pos]=ecart; |
---|
| 571 | strat->sevS[new_pos]=sev; |
---|
| 572 | strat->S_2_R[new_pos]=s_2_r; |
---|
| 573 | strat->lenS[new_pos]=length; |
---|
| 574 | if(strat->lenSw) |
---|
| 575 | strat->lenSw[new_pos]=length_w; |
---|
| 576 | //assume(lenS_correct(strat)); |
---|
| 577 | } |
---|
[9cbb7a3] | 578 | static void replace_pair(int & i, int & j, slimgb_alg* c) |
---|
[4f858ce] | 579 | { |
---|
| 580 | c->soon_free=NULL; |
---|
| 581 | int curr_deg; |
---|
| 582 | poly lm=pOne(); |
---|
| 583 | |
---|
| 584 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 585 | pSetm(lm); |
---|
| 586 | int deciding_deg= pTotaldegree(lm); |
---|
| 587 | int* i_con =make_connections(i,j,lm,c); |
---|
| 588 | int z=0; |
---|
| 589 | |
---|
| 590 | for (int n=0;((n<c->n) && (i_con[n]>=0));n++){ |
---|
| 591 | if (i_con[n]==j){ |
---|
| 592 | now_t_rep(i,j,c); |
---|
| 593 | omfree(i_con); |
---|
| 594 | p_Delete(&lm,c->r); |
---|
| 595 | return; |
---|
| 596 | } |
---|
| 597 | } |
---|
| 598 | |
---|
| 599 | int* j_con =make_connections(j,lm,c); |
---|
| 600 | i= i_con[0]; |
---|
| 601 | j=j_con[0]; |
---|
| 602 | if(c->n>1){ |
---|
| 603 | if (i_con[1]>=0) |
---|
| 604 | i=i_con[1]; |
---|
| 605 | else { |
---|
| 606 | if (j_con[1]>=0) |
---|
| 607 | j=j_con[1]; |
---|
| 608 | } |
---|
| 609 | } |
---|
| 610 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 611 | pSetm(lm); |
---|
| 612 | poly short_s; |
---|
| 613 | curr_deg=pTotaldegree(lm); |
---|
| 614 | int_pair_node* last=NULL; |
---|
| 615 | |
---|
| 616 | for (int n=0;((n<c->n) && (j_con[n]>=0));n++){ |
---|
| 617 | for (int m=0;((m<c->n) && (i_con[m]>=0));m++){ |
---|
| 618 | pLcm(c->S->m[i_con[m]], c->S->m[j_con[n]], lm); |
---|
| 619 | pSetm(lm); |
---|
| 620 | if (pTotaldegree(lm)>=deciding_deg) |
---|
| 621 | { |
---|
| 622 | soon_t_rep(i_con[m],j_con[n],c); |
---|
[ec8a6b6] | 623 | int_pair_node* h= (int_pair_node*)omalloc(sizeof(int_pair_node)); |
---|
[4f858ce] | 624 | if (last!=NULL) |
---|
| 625 | last->next=h; |
---|
| 626 | else |
---|
| 627 | c->soon_free=h; |
---|
| 628 | h->next=NULL; |
---|
| 629 | h->a=i_con[m]; |
---|
| 630 | h->b=j_con[n]; |
---|
| 631 | last=h; |
---|
| 632 | } |
---|
| 633 | // if ((comp_deg<curr_deg) |
---|
| 634 | // || |
---|
| 635 | // ((comp_deg==curr_deg) && |
---|
| 636 | short_s=ksCreateShortSpoly(c->S->m[i_con[m]],c->S->m[j_con[n]],c->r); |
---|
| 637 | if (short_s==NULL) { |
---|
| 638 | i=i_con[m]; |
---|
| 639 | j=j_con[n]; |
---|
| 640 | now_t_rep(i_con[m],j_con[n],c); |
---|
| 641 | p_Delete(&lm,c->r); |
---|
| 642 | omfree(i_con); |
---|
| 643 | omfree(j_con); |
---|
| 644 | |
---|
| 645 | return; |
---|
| 646 | } |
---|
| 647 | #ifdef QUICK_SPOLY_TEST |
---|
| 648 | for (int dz=0;dz<=c->n;dz++){ |
---|
| 649 | if (dz==c->n) { |
---|
| 650 | //have found not head reducing pair |
---|
| 651 | i=i_con[m]; |
---|
| 652 | j=j_con[n]; |
---|
| 653 | p_Delete(&short_s,c->r); |
---|
| 654 | p_Delete(&lm,c->r); |
---|
| 655 | omfree(i_con); |
---|
| 656 | omfree(j_con); |
---|
| 657 | |
---|
| 658 | return; |
---|
| 659 | } |
---|
| 660 | if (p_LmDivisibleBy(c->S->m[dz],short_s,c->r)) break; |
---|
| 661 | } |
---|
| 662 | #endif |
---|
| 663 | int comp_deg(pTotaldegree(short_s)); |
---|
| 664 | p_Delete(&short_s,c->r); |
---|
| 665 | if ((comp_deg<curr_deg)) |
---|
| 666 | |
---|
| 667 | { |
---|
| 668 | curr_deg=comp_deg; |
---|
| 669 | i=i_con[m]; |
---|
| 670 | j=j_con[n]; |
---|
| 671 | } |
---|
| 672 | } |
---|
| 673 | } |
---|
| 674 | p_Delete(&lm,c->r); |
---|
| 675 | omfree(i_con); |
---|
| 676 | omfree(j_con); |
---|
| 677 | return; |
---|
| 678 | } |
---|
| 679 | |
---|
| 680 | |
---|
[9cbb7a3] | 681 | static int* make_connections(int from, poly bound, slimgb_alg* c) |
---|
[4f858ce] | 682 | { |
---|
| 683 | ideal I=c->S; |
---|
| 684 | int s=pTotaldegree(bound); |
---|
[ec8a6b6] | 685 | int* cans=(int*) omalloc(c->n*sizeof(int)); |
---|
| 686 | int* connected=(int*) omalloc(c->n*sizeof(int)); |
---|
[4f858ce] | 687 | int cans_length=0; |
---|
| 688 | connected[0]=from; |
---|
| 689 | int connected_length=1; |
---|
| 690 | long neg_bounds_short= ~p_GetShortExpVector(bound,c->r); |
---|
| 691 | for (int i=0;i<c->n;i++){ |
---|
| 692 | if (c->T_deg[i]>s) continue; |
---|
| 693 | if (i!=from){ |
---|
| 694 | if(p_LmShortDivisibleBy(I->m[i],c->short_Exps[i],bound,neg_bounds_short,c->r)){ |
---|
| 695 | cans[cans_length]=i; |
---|
| 696 | cans_length++; |
---|
| 697 | } |
---|
| 698 | } |
---|
| 699 | } |
---|
| 700 | int not_yet_found=cans_length; |
---|
| 701 | int con_checked=0; |
---|
| 702 | int pos; |
---|
| 703 | while((not_yet_found>0) && (con_checked<connected_length)){ |
---|
| 704 | pos=connected[con_checked]; |
---|
| 705 | for(int i=0;i<cans_length;i++){ |
---|
| 706 | if (cans[i]<0) continue; |
---|
| 707 | if (has_t_rep(pos,cans[i],c)) |
---|
| 708 | { |
---|
| 709 | connected[connected_length]=cans[i]; |
---|
| 710 | connected_length++; |
---|
| 711 | cans[i]=-1; |
---|
| 712 | --not_yet_found; |
---|
| 713 | } |
---|
| 714 | } |
---|
| 715 | con_checked++; |
---|
| 716 | } |
---|
| 717 | if (connected_length<c->n){ |
---|
| 718 | connected[connected_length]=-1; |
---|
| 719 | } |
---|
| 720 | omfree(cans); |
---|
| 721 | return connected; |
---|
| 722 | } |
---|
[9cbb7a3] | 723 | static int* make_connections(int from, int to, poly bound, slimgb_alg* c) |
---|
[4f858ce] | 724 | { |
---|
| 725 | ideal I=c->S; |
---|
| 726 | int s=pTotaldegree(bound); |
---|
[ec8a6b6] | 727 | int* cans=(int*) omalloc(c->n*sizeof(int)); |
---|
| 728 | int* connected=(int*) omalloc(c->n*sizeof(int)); |
---|
[4f858ce] | 729 | cans[0]=to; |
---|
| 730 | int cans_length=1; |
---|
| 731 | connected[0]=from; |
---|
| 732 | int last_cans_pos=-1; |
---|
| 733 | int connected_length=1; |
---|
| 734 | long neg_bounds_short= ~p_GetShortExpVector(bound,c->r); |
---|
| 735 | |
---|
| 736 | int not_yet_found=cans_length; |
---|
| 737 | int con_checked=0; |
---|
| 738 | int pos; |
---|
| 739 | BOOLEAN can_find_more=TRUE; |
---|
| 740 | while(TRUE){ |
---|
| 741 | if ((con_checked<connected_length)&& (not_yet_found>0)){ |
---|
| 742 | pos=connected[con_checked]; |
---|
| 743 | for(int i=0;i<cans_length;i++){ |
---|
| 744 | if (cans[i]<0) continue; |
---|
| 745 | if (has_t_rep(pos,cans[i],c))//||(trivial_syzygie(pos,cans[i],bound,c)) |
---|
| 746 | { |
---|
| 747 | |
---|
| 748 | connected[connected_length]=cans[i]; |
---|
| 749 | connected_length++; |
---|
| 750 | cans[i]=-1; |
---|
| 751 | --not_yet_found; |
---|
| 752 | |
---|
| 753 | if (connected[connected_length-1]==to){ |
---|
| 754 | if (connected_length<c->n){ |
---|
| 755 | connected[connected_length]=-1; |
---|
| 756 | } |
---|
| 757 | omfree(cans); |
---|
| 758 | return connected; |
---|
| 759 | } |
---|
| 760 | } |
---|
| 761 | } |
---|
| 762 | con_checked++; |
---|
| 763 | } |
---|
| 764 | else |
---|
| 765 | { |
---|
| 766 | for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++){ |
---|
| 767 | if (last_cans_pos==c->n){ |
---|
| 768 | if (connected_length<c->n){ |
---|
| 769 | connected[connected_length]=-1; |
---|
| 770 | } |
---|
| 771 | omfree(cans); |
---|
| 772 | return connected; |
---|
| 773 | } |
---|
| 774 | if ((last_cans_pos==from)||(last_cans_pos==to)) |
---|
| 775 | continue; |
---|
| 776 | if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)){ |
---|
| 777 | cans[cans_length]=last_cans_pos; |
---|
| 778 | cans_length++; |
---|
| 779 | break; |
---|
| 780 | } |
---|
| 781 | } |
---|
| 782 | not_yet_found++; |
---|
| 783 | for (int i=0;i<con_checked;i++){ |
---|
| 784 | if (has_t_rep(connected[i],last_cans_pos,c)){ |
---|
| 785 | |
---|
| 786 | connected[connected_length]=last_cans_pos; |
---|
| 787 | connected_length++; |
---|
| 788 | cans[cans_length-1]=-1; |
---|
| 789 | |
---|
| 790 | --not_yet_found; |
---|
| 791 | if (connected[connected_length-1]==to){ |
---|
| 792 | if (connected_length<c->n){ |
---|
| 793 | connected[connected_length]=-1; |
---|
| 794 | } |
---|
| 795 | |
---|
| 796 | omfree(cans); |
---|
| 797 | return connected; |
---|
| 798 | } |
---|
| 799 | break; |
---|
| 800 | } |
---|
| 801 | } |
---|
| 802 | } |
---|
| 803 | } |
---|
| 804 | if (connected_length<c->n){ |
---|
| 805 | connected[connected_length]=-1; |
---|
| 806 | } |
---|
| 807 | |
---|
| 808 | omfree(cans); |
---|
| 809 | return connected; |
---|
| 810 | } |
---|
| 811 | #ifdef HEAD_BIN |
---|
| 812 | static inline poly p_MoveHead(poly p, omBin b) |
---|
| 813 | { |
---|
| 814 | poly np; |
---|
| 815 | omTypeAllocBin(poly, np, b); |
---|
| 816 | memmove(np, p, b->sizeW*sizeof(long)); |
---|
| 817 | omFreeBinAddr(p); |
---|
| 818 | return np; |
---|
| 819 | } |
---|
| 820 | #endif |
---|
| 821 | |
---|
| 822 | |
---|
| 823 | |
---|
| 824 | //len should be weighted length in char 0 |
---|
| 825 | static int simple_posInS (kStrategy strat, poly p,int len) |
---|
| 826 | { |
---|
| 827 | |
---|
| 828 | |
---|
| 829 | if(strat->sl==-1) return 0; |
---|
| 830 | polyset set=strat->S; |
---|
| 831 | intset setL=strat->lenS; |
---|
| 832 | if (strat->lenSw) setL=strat->lenSw; |
---|
| 833 | int length=strat->sl; |
---|
| 834 | int i; |
---|
| 835 | int an = 0; |
---|
| 836 | int en= length; |
---|
| 837 | |
---|
| 838 | if ((len>setL[length]) |
---|
| 839 | || ((len==setL[length]) && (pLmCmp(set[length],p)== -1))) |
---|
| 840 | return length+1; |
---|
| 841 | |
---|
| 842 | loop |
---|
| 843 | { |
---|
| 844 | if (an >= en-1) |
---|
| 845 | { |
---|
| 846 | if ((len<setL[an]) |
---|
| 847 | || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an; |
---|
| 848 | return en; |
---|
| 849 | } |
---|
| 850 | i=(an+en) / 2; |
---|
| 851 | if ((len<setL[i]) |
---|
| 852 | || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i; |
---|
| 853 | //else if ((len>setL[i]) |
---|
| 854 | //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i; |
---|
| 855 | else an=i; |
---|
| 856 | } |
---|
| 857 | } |
---|
| 858 | /*2 |
---|
| 859 | *if the leading term of p |
---|
| 860 | *divides the leading term of some S[i] it will be canceled |
---|
| 861 | */ |
---|
| 862 | static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k, |
---|
| 863 | kStrategy strat) |
---|
| 864 | { |
---|
| 865 | assume(p_sev == pGetShortExpVector(p)); |
---|
| 866 | if (!pLmShortDivisibleBy(p,p_sev, strat->S[*at], ~ strat->sevS[*at])) return; |
---|
| 867 | if (l>=strat->lenS[*at]) return; |
---|
| 868 | if (TEST_OPT_PROT) |
---|
| 869 | PrintS("!"); |
---|
| 870 | mflush(); |
---|
| 871 | //pDelete(&strat->S[*at]); |
---|
| 872 | deleteInS((*at),strat); |
---|
| 873 | (*at)--; |
---|
| 874 | (*k)--; |
---|
| 875 | // assume(lenS_correct(strat)); |
---|
| 876 | } |
---|
| 877 | |
---|
| 878 | |
---|
| 879 | |
---|
| 880 | static int iq_crit(const void* ap,const void* bp){ |
---|
| 881 | |
---|
| 882 | sorted_pair_node* a=*((sorted_pair_node**)ap); |
---|
| 883 | sorted_pair_node* b=*((sorted_pair_node**)bp); |
---|
| 884 | assume(a->i>a->j); |
---|
| 885 | assume(b->i>b->j); |
---|
| 886 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 887 | if(comp!=0) |
---|
| 888 | return comp; |
---|
| 889 | if (a->deg<b->deg) return -1; |
---|
| 890 | if (a->deg>b->deg) return 1; |
---|
| 891 | |
---|
| 892 | |
---|
| 893 | if (a->expected_length<b->expected_length) return -1; |
---|
| 894 | if (a->expected_length>b->expected_length) return 1; |
---|
| 895 | if (a->j>b->j) return 1; |
---|
| 896 | if (a->j<b->j) return -1; |
---|
| 897 | return 0; |
---|
| 898 | } |
---|
| 899 | |
---|
[9cbb7a3] | 900 | sorted_pair_node** add_to_basis_ideal_quotient(poly h, int i_pos, int j_pos,slimgb_alg* c, int* ip) |
---|
[4f858ce] | 901 | { |
---|
| 902 | |
---|
| 903 | assume(h!=NULL); |
---|
[6d7605] | 904 | #define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type)) |
---|
[4f858ce] | 905 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 906 | BOOLEAN R_found=FALSE; |
---|
| 907 | void* hp; |
---|
| 908 | |
---|
| 909 | ++(c->n); |
---|
| 910 | ++(c->S->ncols); |
---|
| 911 | int i,j; |
---|
| 912 | i=c->n-1; |
---|
[ec8a6b6] | 913 | sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 914 | int spc=0; |
---|
[6d7605] | 915 | if(c->n>c->array_lengths){ |
---|
| 916 | c->array_lengths=c->array_lengths*2; |
---|
| 917 | assume(c->array_lengths>=c->n); |
---|
| 918 | ENLARGE(c->T_deg, int); |
---|
| 919 | ENLARGE(c->tmp_pair_lm,poly); |
---|
| 920 | ENLARGE(c->tmp_spn,sorted_pair_node*); |
---|
| 921 | ENLARGE(c->rep,int); |
---|
| 922 | ENLARGE(c->short_Exps,long); |
---|
| 923 | ENLARGE(c->lengths,int); |
---|
| 924 | ENLARGE(c->states, char*); |
---|
| 925 | ENLARGE(c->gcd_of_terms,poly); |
---|
| 926 | ENLARGE(c->S->m,poly); |
---|
| 927 | } |
---|
[85eb7d] | 928 | if (c->T_deg_full) |
---|
| 929 | ENLARGE(c->T_deg_full,int); |
---|
[4f858ce] | 930 | c->T_deg[i]=pTotaldegree(h); |
---|
| 931 | if(c->T_deg_full){ |
---|
| 932 | c->T_deg_full[i]=pTotaldegree_full(h); |
---|
| 933 | } |
---|
[85eb7d] | 934 | |
---|
| 935 | |
---|
[4f858ce] | 936 | c->tmp_pair_lm[i]=pOne_Special(c->r); |
---|
[85eb7d] | 937 | |
---|
| 938 | |
---|
[ec8a6b6] | 939 | c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 940 | |
---|
| 941 | |
---|
| 942 | c->lengths[i]=pLength(h); |
---|
| 943 | |
---|
| 944 | c->gcd_of_terms[i]=gcd_of_terms(h,c->r); |
---|
| 945 | c->rep[i]=i; |
---|
[65c4dc] | 946 | if (i>0) |
---|
| 947 | c->states[i]=(char*) omalloc(i*sizeof(char)); |
---|
| 948 | else |
---|
| 949 | c->states[i]=NULL; |
---|
[85eb7d] | 950 | |
---|
| 951 | |
---|
[4f858ce] | 952 | c->S->m[i]=h; |
---|
| 953 | c->short_Exps[i]=p_GetShortExpVector(h,c->r); |
---|
[85eb7d] | 954 | #undef ENLARGE |
---|
[4f858ce] | 955 | for (j=0;j<i;j++){ |
---|
| 956 | |
---|
| 957 | //check product criterion |
---|
| 958 | |
---|
| 959 | c->states[i][j]=UNCALCULATED; |
---|
| 960 | assume(p_LmDivisibleBy(c->S->m[i],c->S->m[j],c->r)== |
---|
| 961 | p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)); |
---|
| 962 | if(!c->F4_mode) |
---|
| 963 | { |
---|
| 964 | assume(!(p_LmDivisibleBy(c->S->m[j],c->S->m[i],c->r))); |
---|
| 965 | } |
---|
| 966 | //lies I[i] under I[j] ? |
---|
| 967 | |
---|
| 968 | if ((c->lengths[i]==1) && (c->lengths[j]==1)) |
---|
| 969 | c->states[i][j]=HASTREP; |
---|
| 970 | else if (pHasNotCF(c->S->m[i],c->S->m[j])) |
---|
| 971 | { |
---|
| 972 | c->easy_product_crit++; |
---|
| 973 | c->states[i][j]=HASTREP; |
---|
| 974 | } |
---|
| 975 | else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c)) |
---|
| 976 | { |
---|
| 977 | c->states[i][j]=HASTREP; |
---|
| 978 | c->extended_product_crit++; |
---|
| 979 | //PrintS("E"); |
---|
| 980 | } |
---|
| 981 | // if (c->states[i][j]==UNCALCULATED){ |
---|
| 982 | |
---|
| 983 | |
---|
| 984 | // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r); |
---|
| 985 | // if (short_s) |
---|
| 986 | // { |
---|
[ec8a6b6] | 987 | sorted_pair_node* s=c->tmp_spn[j];//(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 988 | s->i=si_max(i,j); |
---|
| 989 | s->j=si_min(i,j); |
---|
| 990 | assume(s->j==j); |
---|
| 991 | s->expected_length=c->lengths[i]+c->lengths[j]-2; |
---|
| 992 | |
---|
| 993 | poly lm=c->tmp_pair_lm[j];//=pOne_Special(); |
---|
| 994 | |
---|
| 995 | pLcm(c->S->m[i], c->S->m[j], lm); |
---|
| 996 | pSetm(lm); |
---|
| 997 | s->deg=pTotaldegree(lm); |
---|
| 998 | if(c->T_deg_full) |
---|
| 999 | { |
---|
| 1000 | int t_i=c->T_deg_full[s->i]-c->T_deg[s->i]; |
---|
| 1001 | int t_j=c->T_deg_full[s->j]-c->T_deg[s->j]; |
---|
| 1002 | s->deg+=si_max(t_i,t_j); |
---|
| 1003 | //Print("\n max: %d\n",max(t_i,t_j)); |
---|
| 1004 | } |
---|
| 1005 | s->lcm_of_lm=lm; |
---|
| 1006 | // pDelete(&short_s); |
---|
| 1007 | //assume(lm!=NULL); |
---|
| 1008 | nodes[spc]=s; |
---|
| 1009 | spc++; |
---|
| 1010 | // } |
---|
| 1011 | //else |
---|
| 1012 | //{ |
---|
| 1013 | //c->states[i][j]=HASTREP; |
---|
| 1014 | //} |
---|
| 1015 | } |
---|
| 1016 | |
---|
| 1017 | assume(spc==i); |
---|
| 1018 | //now ideal quotient crit |
---|
| 1019 | qsort(nodes,spc,sizeof(sorted_pair_node*),iq_crit); |
---|
| 1020 | |
---|
[ec8a6b6] | 1021 | sorted_pair_node** nodes_final=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i); |
---|
[4f858ce] | 1022 | int spc_final=0; |
---|
| 1023 | j=0; |
---|
| 1024 | while(j<spc) |
---|
| 1025 | { |
---|
| 1026 | int lower=j; |
---|
| 1027 | int upper; |
---|
| 1028 | BOOLEAN has=FALSE; |
---|
| 1029 | for(upper=lower+1;upper<spc;upper++) |
---|
| 1030 | { |
---|
| 1031 | |
---|
| 1032 | if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm)) |
---|
| 1033 | { |
---|
| 1034 | break; |
---|
| 1035 | } |
---|
| 1036 | if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c)) |
---|
| 1037 | has=TRUE; |
---|
| 1038 | |
---|
| 1039 | } |
---|
| 1040 | upper=upper-1; |
---|
| 1041 | int z; |
---|
| 1042 | assume(spc_final<=j); |
---|
| 1043 | for(z=0;z<spc_final;z++) |
---|
| 1044 | { |
---|
| 1045 | if(p_LmDivisibleBy(nodes_final[z]->lcm_of_lm,nodes[lower]->lcm_of_lm,c->r)) |
---|
| 1046 | { |
---|
| 1047 | has=TRUE; |
---|
| 1048 | break; |
---|
| 1049 | } |
---|
| 1050 | } |
---|
| 1051 | |
---|
| 1052 | if(has) |
---|
| 1053 | { |
---|
| 1054 | for(;lower<=upper;lower++) |
---|
| 1055 | { |
---|
| 1056 | //free_sorted_pair_node(nodes[lower],c->r); |
---|
| 1057 | //omfree(nodes[lower]); |
---|
| 1058 | nodes[lower]=NULL; |
---|
| 1059 | } |
---|
| 1060 | j=upper+1; |
---|
| 1061 | continue; |
---|
| 1062 | } |
---|
| 1063 | else |
---|
| 1064 | { |
---|
| 1065 | nodes[lower]->lcm_of_lm=pCopy(nodes[lower]->lcm_of_lm); |
---|
| 1066 | nodes_final[spc_final++]=nodes[lower]; |
---|
[ec8a6b6] | 1067 | c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1068 | nodes[lower]=NULL; |
---|
| 1069 | for(lower=lower+1;lower<=upper;lower++) |
---|
| 1070 | { |
---|
| 1071 | // free_sorted_pair_node(nodes[lower],c->r); |
---|
| 1072 | //omfree(nodes[lower]); |
---|
| 1073 | nodes[lower]=NULL; |
---|
| 1074 | } |
---|
| 1075 | j=upper+1; |
---|
| 1076 | continue; |
---|
| 1077 | } |
---|
| 1078 | } |
---|
| 1079 | |
---|
| 1080 | // Print("i:%d,spc_final:%d",i,spc_final); |
---|
| 1081 | |
---|
| 1082 | |
---|
| 1083 | |
---|
| 1084 | |
---|
| 1085 | assume(spc_final<=spc); |
---|
| 1086 | omfree(nodes); |
---|
| 1087 | nodes=NULL; |
---|
| 1088 | |
---|
| 1089 | add_to_reductors(c, h, c->lengths[c->n-1]); |
---|
| 1090 | //i=posInS(c->strat,c->strat->sl,h,0 ecart); |
---|
| 1091 | |
---|
| 1092 | if (c->lengths[c->n-1]==1) |
---|
| 1093 | shorten_tails(c,c->S->m[c->n-1]); |
---|
| 1094 | //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths |
---|
| 1095 | |
---|
| 1096 | //for(i=c->strat->sl; i>0;i--) |
---|
| 1097 | // if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i); |
---|
| 1098 | if (c->Rcounter>50) { |
---|
| 1099 | c->Rcounter=0; |
---|
| 1100 | cleanS(c->strat,c); |
---|
| 1101 | } |
---|
| 1102 | if(!ip){ |
---|
[b75d13] | 1103 | qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),tgb_pair_better_gen2); |
---|
[4f858ce] | 1104 | |
---|
| 1105 | |
---|
[b75d13] | 1106 | c->apairs=spn_merge(c->apairs,c->pair_top+1,nodes_final,spc_final,c); |
---|
[4f858ce] | 1107 | c->pair_top+=spc_final; |
---|
| 1108 | clean_top_of_pair_list(c); |
---|
| 1109 | omfree(nodes_final); |
---|
| 1110 | return NULL; |
---|
| 1111 | } |
---|
| 1112 | { |
---|
| 1113 | *ip=spc_final; |
---|
| 1114 | return nodes_final; |
---|
| 1115 | } |
---|
| 1116 | |
---|
| 1117 | |
---|
| 1118 | |
---|
| 1119 | } |
---|
| 1120 | |
---|
| 1121 | |
---|
| 1122 | |
---|
| 1123 | |
---|
| 1124 | |
---|
| 1125 | |
---|
| 1126 | |
---|
[9cbb7a3] | 1127 | static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) |
---|
[4f858ce] | 1128 | { |
---|
| 1129 | m=nInit(1); |
---|
| 1130 | if (h==NULL) return NULL; |
---|
| 1131 | |
---|
| 1132 | assume(len==pLength(h)); |
---|
| 1133 | kStrategy strat=c->strat; |
---|
| 1134 | if (0 > strat->sl) |
---|
| 1135 | { |
---|
| 1136 | return h; |
---|
| 1137 | } |
---|
| 1138 | int j; |
---|
| 1139 | |
---|
| 1140 | LObject P(h); |
---|
| 1141 | P.SetShortExpVector(); |
---|
| 1142 | P.bucket = kBucketCreate(currRing); |
---|
| 1143 | // BOOLEAN corr=lenS_correct(strat); |
---|
| 1144 | kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/); |
---|
| 1145 | //int max_pos=simple_posInS(strat,P.p); |
---|
| 1146 | loop |
---|
| 1147 | { |
---|
| 1148 | |
---|
| 1149 | j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P); |
---|
| 1150 | if ((j>=0) && ((!n)||(strat->lenS[j]<=n))) |
---|
| 1151 | { |
---|
| 1152 | |
---|
| 1153 | |
---|
| 1154 | nNormalize(pGetCoeff(P.p)); |
---|
| 1155 | #ifdef KDEBUG |
---|
| 1156 | if (TEST_OPT_DEBUG) |
---|
| 1157 | { |
---|
| 1158 | PrintS("red:"); |
---|
| 1159 | wrp(h); |
---|
| 1160 | PrintS(" with "); |
---|
| 1161 | wrp(strat->S[j]); |
---|
| 1162 | } |
---|
| 1163 | #endif |
---|
| 1164 | |
---|
| 1165 | number coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 1166 | strat->lenS[j]/*pLength(strat->S[j])*/, |
---|
| 1167 | strat->kNoether); |
---|
| 1168 | number m2=nMult(m,coef); |
---|
| 1169 | nDelete(&m); |
---|
| 1170 | m=m2; |
---|
| 1171 | nDelete(&coef); |
---|
| 1172 | h = kBucketGetLm(P.bucket); |
---|
| 1173 | |
---|
| 1174 | if (h==NULL) { |
---|
| 1175 | len=0; |
---|
| 1176 | kBucketDestroy(&P.bucket); |
---|
| 1177 | return |
---|
| 1178 | NULL;} |
---|
| 1179 | P.p=h; |
---|
| 1180 | P.t_p=NULL; |
---|
| 1181 | P.SetShortExpVector(); |
---|
| 1182 | #ifdef KDEBUG |
---|
| 1183 | if (TEST_OPT_DEBUG) |
---|
| 1184 | { |
---|
| 1185 | PrintS("\nto:"); |
---|
| 1186 | wrp(h); |
---|
| 1187 | PrintLn(); |
---|
| 1188 | } |
---|
| 1189 | #endif |
---|
| 1190 | } |
---|
| 1191 | else |
---|
| 1192 | { |
---|
| 1193 | kBucketClear(P.bucket,&(P.p),&len); |
---|
| 1194 | kBucketDestroy(&P.bucket); |
---|
| 1195 | pNormalize(P.p); |
---|
| 1196 | assume(len==(pLength(P.p))); |
---|
| 1197 | return P.p; |
---|
| 1198 | } |
---|
| 1199 | } |
---|
| 1200 | } |
---|
| 1201 | |
---|
| 1202 | |
---|
| 1203 | static poly redTailShort(poly h, kStrategy strat){ |
---|
| 1204 | |
---|
| 1205 | int sl=strat->sl; |
---|
| 1206 | int i; |
---|
| 1207 | int len=pLength(h); |
---|
| 1208 | for(i=0;i<=strat->sl;i++){ |
---|
| 1209 | if(strat->lenS[i]>2) |
---|
| 1210 | break; |
---|
| 1211 | } |
---|
| 1212 | return(redNFTail(h,i-1,strat, len)); |
---|
| 1213 | } |
---|
| 1214 | |
---|
[9cbb7a3] | 1215 | static void line_of_extended_prod(int fixpos,slimgb_alg* c){ |
---|
[4f858ce] | 1216 | if (c->gcd_of_terms[fixpos]==NULL) |
---|
| 1217 | { |
---|
| 1218 | c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r); |
---|
| 1219 | if (c->gcd_of_terms[fixpos]) |
---|
| 1220 | { |
---|
| 1221 | int i; |
---|
| 1222 | for(i=0;i<fixpos;i++) |
---|
| 1223 | 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))) |
---|
| 1224 | { |
---|
| 1225 | c->states[fixpos][i]=HASTREP; |
---|
| 1226 | c->extended_product_crit++; |
---|
| 1227 | } |
---|
| 1228 | for(i=fixpos+1;i<c->n;i++) |
---|
| 1229 | 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))) |
---|
| 1230 | { c->states[i][fixpos]=HASTREP; |
---|
| 1231 | c->extended_product_crit++; |
---|
| 1232 | } |
---|
| 1233 | } |
---|
| 1234 | } |
---|
| 1235 | } |
---|
[9cbb7a3] | 1236 | static void c_S_element_changed_hook(int pos, slimgb_alg* c){ |
---|
[4f858ce] | 1237 | length_one_crit(c,pos, c->lengths[pos]); |
---|
| 1238 | line_of_extended_prod(pos,c); |
---|
| 1239 | } |
---|
| 1240 | class poly_tree_node { |
---|
| 1241 | public: |
---|
| 1242 | poly p; |
---|
| 1243 | poly_tree_node* l; |
---|
| 1244 | poly_tree_node* r; |
---|
| 1245 | int n; |
---|
| 1246 | poly_tree_node(int sn):l(NULL),r(NULL),n(sn){} |
---|
| 1247 | }; |
---|
| 1248 | class exp_number_builder{ |
---|
| 1249 | public: |
---|
| 1250 | poly_tree_node* top_level; |
---|
| 1251 | int n; |
---|
| 1252 | int get_n(poly p); |
---|
| 1253 | exp_number_builder():top_level(0),n(0){} |
---|
| 1254 | }; |
---|
| 1255 | int exp_number_builder::get_n(poly p){ |
---|
| 1256 | poly_tree_node** node=&top_level; |
---|
| 1257 | while(*node!=NULL){ |
---|
| 1258 | int c=pLmCmp(p,(*node)->p); |
---|
| 1259 | if (c==0) return (*node)->n; |
---|
| 1260 | if (c==-1) node=&((*node)->r); |
---|
| 1261 | else |
---|
| 1262 | node=&((*node)->l); |
---|
| 1263 | } |
---|
| 1264 | (*node)= new poly_tree_node(n); |
---|
| 1265 | n++; |
---|
| 1266 | (*node)->p=pLmInit(p); |
---|
| 1267 | return (*node)->n; |
---|
| 1268 | } |
---|
| 1269 | |
---|
| 1270 | //mac_polys exp are smaller iff they are greater by monomial ordering |
---|
| 1271 | //corresponding to solving linear equations notation |
---|
[196cdf] | 1272 | |
---|
[b553e5] | 1273 | //! obsolete |
---|
[4f858ce] | 1274 | struct int_poly_pair{ |
---|
| 1275 | poly p; |
---|
| 1276 | int n; |
---|
| 1277 | }; |
---|
| 1278 | |
---|
[196cdf] | 1279 | |
---|
[b553e5] | 1280 | //! obsolete |
---|
[4f858ce] | 1281 | void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset){ |
---|
| 1282 | if(!k) return; |
---|
| 1283 | t2ippa_rec(ip,ia,k->l,offset); |
---|
| 1284 | ip[offset]=k->p; |
---|
| 1285 | ia[k->n]=offset; |
---|
| 1286 | ++offset; |
---|
| 1287 | |
---|
| 1288 | t2ippa_rec(ip,ia,k->r,offset); |
---|
| 1289 | delete k; |
---|
| 1290 | } |
---|
[196cdf] | 1291 | |
---|
[b553e5] | 1292 | //! obsolete |
---|
[4f858ce] | 1293 | void t2ippa(poly* ip,int* ia,exp_number_builder & e){ |
---|
| 1294 | |
---|
| 1295 | int o=0; |
---|
| 1296 | t2ippa_rec(ip,ia,e.top_level,o); |
---|
| 1297 | } |
---|
| 1298 | int anti_poly_order(const void* a, const void* b){ |
---|
| 1299 | return -pLmCmp(((int_poly_pair*) a)->p,((int_poly_pair*) b)->p ); |
---|
| 1300 | } |
---|
[81306a] | 1301 | |
---|
[4f858ce] | 1302 | BOOLEAN is_valid_ro(red_object & ro){ |
---|
| 1303 | red_object r2=ro; |
---|
| 1304 | ro.validate(); |
---|
[bddc9d] | 1305 | if ((r2.p!=ro.p)||(r2.sev!=ro.sev)) return FALSE; |
---|
[4f858ce] | 1306 | return TRUE; |
---|
| 1307 | } |
---|
[196cdf] | 1308 | |
---|
| 1309 | //*obsolete |
---|
[9cbb7a3] | 1310 | void pre_comp(poly* p,int & pn,slimgb_alg* c){ |
---|
[4f858ce] | 1311 | if(!(pn)) |
---|
| 1312 | return; |
---|
[ec8a6b6] | 1313 | mac_poly* q=(mac_poly*) omalloc(pn*sizeof(mac_poly)); |
---|
[4f858ce] | 1314 | int i; |
---|
| 1315 | exp_number_builder e; |
---|
| 1316 | for(i=0;i<pn;i++){ |
---|
| 1317 | assume(p[i]!=NULL); |
---|
| 1318 | q[i]=new mac_poly_r(); |
---|
| 1319 | q[i]->exp=e.get_n(p[i]); |
---|
| 1320 | q[i]->coef=nCopy(p[i]->coef); |
---|
| 1321 | |
---|
| 1322 | mac_poly qa=q[i]; |
---|
| 1323 | poly pa=p[i]; |
---|
| 1324 | while(pa->next!=NULL){ |
---|
| 1325 | qa->next = new mac_poly_r(); |
---|
| 1326 | qa=qa->next; |
---|
| 1327 | pa=pa->next, |
---|
| 1328 | qa->exp=e.get_n(pa); |
---|
| 1329 | qa->coef=nCopy(pa->coef); |
---|
| 1330 | |
---|
| 1331 | |
---|
| 1332 | } |
---|
| 1333 | qa->next=NULL; |
---|
| 1334 | pDelete(&p[i]); |
---|
| 1335 | } |
---|
[ec8a6b6] | 1336 | poly* ip= (poly*)omalloc (e.n*sizeof(poly)); |
---|
| 1337 | int* ia=(int*) omalloc (e.n*sizeof(int)); |
---|
[4f858ce] | 1338 | t2ippa(ip,ia,e); |
---|
| 1339 | for(i=0;i<pn;i++){ |
---|
| 1340 | mac_poly mp=q[i]; |
---|
| 1341 | while(mp!=NULL){ |
---|
| 1342 | mp->exp=ia[mp->exp]; |
---|
| 1343 | mp=mp->next; |
---|
| 1344 | } |
---|
| 1345 | |
---|
| 1346 | } |
---|
| 1347 | //gaus reduction start |
---|
| 1348 | int col, row; |
---|
| 1349 | col=0; |
---|
| 1350 | row=0; |
---|
| 1351 | assume(pn>0); |
---|
| 1352 | while(row<pn-1){ |
---|
| 1353 | //row is the row where pivot should be |
---|
| 1354 | // row== pn-1 means we have only to act on one row so no red nec. |
---|
| 1355 | //we assume further all rows till the pn-1 row are non-zero |
---|
| 1356 | |
---|
| 1357 | //select column |
---|
| 1358 | int i; |
---|
| 1359 | col=q[row]->exp; |
---|
| 1360 | int found_in_row=row; |
---|
| 1361 | for(i=row;i<pn;i++){ |
---|
| 1362 | if(q[i]->exp<col){ |
---|
| 1363 | col=q[i]->exp; |
---|
| 1364 | found_in_row=i; |
---|
| 1365 | } |
---|
| 1366 | |
---|
| 1367 | } |
---|
| 1368 | //select pivot |
---|
| 1369 | int act_l=mac_length(q[found_in_row]); |
---|
| 1370 | for(i=row+1;i<pn;i++){ |
---|
| 1371 | if((q[i]->exp==col)&&(mac_length(q[i])<act_l)){ |
---|
| 1372 | found_in_row=i; |
---|
| 1373 | act_l=mac_length(q[i]);//should be optimized here |
---|
| 1374 | } |
---|
| 1375 | } |
---|
| 1376 | mac_poly h=q[row]; |
---|
| 1377 | q[row]=q[found_in_row]; |
---|
| 1378 | q[found_in_row]=h; |
---|
| 1379 | |
---|
| 1380 | //reduction |
---|
| 1381 | for(i=row+1;i<pn;i++){ |
---|
| 1382 | if(q[i]->exp==q[row]->exp){ |
---|
| 1383 | |
---|
| 1384 | number c1=nNeg(nCopy(q[i]->coef)); |
---|
| 1385 | number c2=q[row]->coef; |
---|
| 1386 | //use checkcoeff later |
---|
| 1387 | mac_mult_cons(q[i],c2); |
---|
| 1388 | q[i]=mac_p_add_ff_qq(q[i],c1,q[row]); |
---|
| 1389 | } |
---|
| 1390 | |
---|
| 1391 | |
---|
| 1392 | |
---|
| 1393 | } |
---|
| 1394 | for(i=row+1;i<pn;i++){ |
---|
| 1395 | if(q[i]==NULL){ |
---|
| 1396 | q[i]=q[pn-1]; |
---|
| 1397 | pn--; |
---|
| 1398 | if(i!=pn){i--;} |
---|
| 1399 | } |
---|
| 1400 | } |
---|
| 1401 | |
---|
| 1402 | row++; |
---|
| 1403 | } |
---|
| 1404 | |
---|
| 1405 | |
---|
| 1406 | //gaus reduction end |
---|
| 1407 | |
---|
| 1408 | for(i=0;i<pn;i++){ |
---|
| 1409 | poly pa; |
---|
| 1410 | mac_poly qa; |
---|
| 1411 | p[i]=pLmInit(ip[q[i]->exp]); |
---|
| 1412 | pSetCoeff(p[i],q[i]->coef); |
---|
| 1413 | pa=p[i]; |
---|
| 1414 | qa=q[i]; |
---|
| 1415 | while(qa->next!=NULL){ |
---|
| 1416 | qa=qa->next; |
---|
| 1417 | pa->next=pLmInit(ip[qa->exp]); |
---|
| 1418 | pa=pa->next; |
---|
| 1419 | pa->coef=qa->coef; |
---|
| 1420 | } |
---|
| 1421 | pa->next=NULL; |
---|
| 1422 | } |
---|
| 1423 | for(i=0;i<e.n;i++){ |
---|
| 1424 | pDelete(&ip[i]); |
---|
| 1425 | } |
---|
| 1426 | omfree(ip); |
---|
| 1427 | omfree(ia); |
---|
| 1428 | } |
---|
| 1429 | |
---|
[9cbb7a3] | 1430 | static void go_on (slimgb_alg* c){ |
---|
[4f858ce] | 1431 | //set limit of 1000 for multireductions, at the moment for |
---|
| 1432 | //programming reasons |
---|
| 1433 | int i=0; |
---|
| 1434 | c->average_length=0; |
---|
| 1435 | for(i=0;i<c->n;i++){ |
---|
| 1436 | c->average_length+=c->lengths[i]; |
---|
| 1437 | } |
---|
| 1438 | c->average_length=c->average_length/c->n; |
---|
| 1439 | i=0; |
---|
[ec8a6b6] | 1440 | poly* p=(poly*) omalloc((PAR_N+1)*sizeof(poly));//nullterminated |
---|
[4f858ce] | 1441 | |
---|
| 1442 | int curr_deg=-1; |
---|
| 1443 | while(i<PAR_N){ |
---|
| 1444 | sorted_pair_node* s=top_pair(c);//here is actually chain criterium done |
---|
| 1445 | if (!s) break; |
---|
| 1446 | if(curr_deg>=0){ |
---|
| 1447 | if (s->deg >curr_deg) break; |
---|
| 1448 | } |
---|
| 1449 | |
---|
| 1450 | else curr_deg=s->deg; |
---|
| 1451 | quick_pop_pair(c); |
---|
| 1452 | if(s->i>=0){ |
---|
| 1453 | //replace_pair(s->i,s->j,c); |
---|
| 1454 | if(s->i==s->j) { |
---|
| 1455 | free_sorted_pair_node(s,c->r); |
---|
| 1456 | continue; |
---|
| 1457 | } |
---|
| 1458 | } |
---|
| 1459 | poly h; |
---|
| 1460 | if(s->i>=0) |
---|
| 1461 | h=ksOldCreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r); |
---|
| 1462 | else |
---|
| 1463 | h=s->lcm_of_lm; |
---|
| 1464 | if(s->i>=0) |
---|
| 1465 | now_t_rep(s->j,s->i,c); |
---|
| 1466 | number coef; |
---|
| 1467 | int mlen=pLength(h); |
---|
| 1468 | h=redNF2(h,c,mlen,coef,2); |
---|
| 1469 | redTailShort(h,c->strat); |
---|
| 1470 | nDelete(&coef); |
---|
| 1471 | |
---|
| 1472 | free_sorted_pair_node(s,c->r); |
---|
| 1473 | if(!h) continue; |
---|
| 1474 | int len=pLength(h); |
---|
| 1475 | p[i]=h; |
---|
| 1476 | |
---|
| 1477 | i++; |
---|
| 1478 | } |
---|
| 1479 | p[i]=NULL; |
---|
| 1480 | // pre_comp(p,i,c); |
---|
| 1481 | if(i==0){ |
---|
| 1482 | omfree(p); |
---|
| 1483 | return; |
---|
| 1484 | } |
---|
[ec8a6b6] | 1485 | red_object* buf=(red_object*) omalloc(i*sizeof(red_object)); |
---|
[4f858ce] | 1486 | c->normal_forms+=i; |
---|
| 1487 | int j; |
---|
| 1488 | for(j=0;j<i;j++){ |
---|
| 1489 | buf[j].p=p[j]; |
---|
| 1490 | buf[j].sev=pGetShortExpVector(p[j]); |
---|
| 1491 | buf[j].bucket = kBucketCreate(currRing); |
---|
| 1492 | int len=pLength(p[j]); |
---|
| 1493 | kBucketInit(buf[j].bucket,buf[j].p,len); |
---|
| 1494 | } |
---|
| 1495 | omfree(p); |
---|
| 1496 | qsort(buf,i,sizeof(red_object),red_object_better_gen); |
---|
| 1497 | // Print("\ncurr_deg:%i\n",curr_deg); |
---|
| 1498 | if (TEST_OPT_PROT) |
---|
| 1499 | Print("M[%i, ",i); |
---|
| 1500 | #ifdef FIND_DETERMINISTIC |
---|
[ec8a6b6] | 1501 | c->modifiedS=(BOOLEAN*) omalloc((c->strat->sl+1)*sizeof(BOOLEAN)); |
---|
| 1502 | c->expandS=(poly*) omalloc((1)*sizeof(poly)); |
---|
[4f858ce] | 1503 | c->expandS[0]=NULL; |
---|
| 1504 | int z2; |
---|
| 1505 | for(z2=0;z2<=c->strat->sl;z2++) |
---|
| 1506 | c->modifiedS[z2]=FALSE; |
---|
| 1507 | #endif |
---|
| 1508 | multi_reduction(buf, i, c); |
---|
| 1509 | #ifdef TGB_DEBUG |
---|
| 1510 | { |
---|
| 1511 | int k; |
---|
| 1512 | for(k=0;k<i;k++) |
---|
| 1513 | { |
---|
| 1514 | assume(kFindDivisibleByInS_easy(c->strat,buf[k])<0); |
---|
| 1515 | int k2; |
---|
| 1516 | for(k2=0;k2<i;k2++) |
---|
| 1517 | { |
---|
| 1518 | if(k==k2) continue; |
---|
| 1519 | 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)); |
---|
| 1520 | } |
---|
| 1521 | } |
---|
| 1522 | } |
---|
| 1523 | #endif |
---|
| 1524 | //resort S |
---|
| 1525 | #ifdef FIND_DETERMINISTIC |
---|
| 1526 | for(z2=0;z2<=c->strat->sl;z2++) |
---|
| 1527 | { |
---|
| 1528 | if (c->modifiedS[z2]) |
---|
| 1529 | { |
---|
| 1530 | int qal; |
---|
| 1531 | if (c->strat->lenSw) |
---|
| 1532 | qal=c->strat->lenSw[z2]; |
---|
| 1533 | else |
---|
| 1534 | qal=c->strat->lenS[z2]; |
---|
| 1535 | int new_pos=simple_posInS(c->strat,c->strat->S[z2],qal); |
---|
| 1536 | if (new_pos<z2) |
---|
| 1537 | { |
---|
| 1538 | move_forward_in_S(z2,new_pos,c->strat); |
---|
| 1539 | } |
---|
| 1540 | } |
---|
| 1541 | } |
---|
| 1542 | for(z2=0;c->expandS[z2]!=NULL;z2++) |
---|
| 1543 | { |
---|
| 1544 | add_to_reductors(c,c->expandS[z2],pLength(c->expandS[z2])); |
---|
| 1545 | // PrintS("E"); |
---|
| 1546 | } |
---|
| 1547 | omfree(c->modifiedS); |
---|
| 1548 | c->modifiedS=NULL; |
---|
| 1549 | omfree(c->expandS); |
---|
| 1550 | c->expandS=NULL; |
---|
| 1551 | #endif |
---|
| 1552 | if (TEST_OPT_PROT) |
---|
| 1553 | Print("%i]",i); |
---|
| 1554 | // for(j=0;j<i;j++){ |
---|
| 1555 | // if(buf[j].p==NULL) PrintS("\n ZERO ALERT \n"); |
---|
| 1556 | // int z; |
---|
| 1557 | // for(z=0;z<j;z++){ |
---|
| 1558 | // if (pLmEqual(buf[z].p, buf[j].p)) |
---|
| 1559 | // PrintS("\n Critical Warning!!!! \n"); |
---|
| 1560 | |
---|
| 1561 | // } |
---|
| 1562 | // } |
---|
[ec8a6b6] | 1563 | int* ibuf=(int*) omalloc(i*sizeof(int)); |
---|
| 1564 | sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(i*sizeof(sorted_pair_node**)); |
---|
[4f858ce] | 1565 | for(j=0;j<i;j++) |
---|
| 1566 | { |
---|
| 1567 | int len; |
---|
| 1568 | poly p; |
---|
| 1569 | buf[j].flatten(); |
---|
| 1570 | kBucketClear(buf[j].bucket,&p, &len); |
---|
| 1571 | kBucketDestroy(&buf[j].bucket); |
---|
| 1572 | // delete buf[j]; |
---|
| 1573 | //remember to free res here |
---|
| 1574 | p=redTailShort(p, c->strat); |
---|
| 1575 | sbuf[j]=add_to_basis_ideal_quotient(p,-1,-1,c,ibuf+j); |
---|
| 1576 | //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j); |
---|
| 1577 | } |
---|
| 1578 | int sum=0; |
---|
| 1579 | for(j=0;j<i;j++){ |
---|
| 1580 | sum+=ibuf[j]; |
---|
| 1581 | } |
---|
[ec8a6b6] | 1582 | sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 1583 | int partsum=0; |
---|
| 1584 | for(j=0;j<i;j++) |
---|
| 1585 | { |
---|
| 1586 | memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*)); |
---|
| 1587 | omfree(sbuf[j]); |
---|
| 1588 | partsum+=ibuf[j]; |
---|
| 1589 | } |
---|
| 1590 | |
---|
[b75d13] | 1591 | qsort(big_sbuf,sum,sizeof(sorted_pair_node*),tgb_pair_better_gen2); |
---|
| 1592 | c->apairs=spn_merge(c->apairs,c->pair_top+1,big_sbuf,sum,c); |
---|
[4f858ce] | 1593 | c->pair_top+=sum; |
---|
| 1594 | clean_top_of_pair_list(c); |
---|
| 1595 | omfree(big_sbuf); |
---|
| 1596 | omfree(sbuf); |
---|
| 1597 | omfree(ibuf); |
---|
| 1598 | omfree(buf); |
---|
| 1599 | #ifdef TGB_DEBUG |
---|
| 1600 | int z; |
---|
| 1601 | for(z=1;z<=c->pair_top;z++) |
---|
| 1602 | { |
---|
| 1603 | assume(pair_better(c->apairs[z],c->apairs[z-1],c)); |
---|
| 1604 | } |
---|
| 1605 | #endif |
---|
| 1606 | return; |
---|
| 1607 | } |
---|
| 1608 | |
---|
| 1609 | static poly redNF (poly h,kStrategy strat, int &len) |
---|
| 1610 | { |
---|
| 1611 | len=0; |
---|
| 1612 | if (h==NULL) return NULL; |
---|
| 1613 | int j; |
---|
| 1614 | |
---|
| 1615 | len=pLength(h); |
---|
| 1616 | if (0 > strat->sl) |
---|
| 1617 | { |
---|
| 1618 | return h; |
---|
| 1619 | } |
---|
| 1620 | LObject P(h); |
---|
| 1621 | P.SetShortExpVector(); |
---|
| 1622 | P.bucket = kBucketCreate(currRing); |
---|
| 1623 | kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/); |
---|
| 1624 | //int max_pos=simple_posInS(strat,P.p); |
---|
| 1625 | loop |
---|
| 1626 | { |
---|
| 1627 | j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P); |
---|
| 1628 | if (j>=0) |
---|
| 1629 | { |
---|
| 1630 | nNormalize(pGetCoeff(P.p)); |
---|
| 1631 | #ifdef KDEBUG |
---|
| 1632 | if (TEST_OPT_DEBUG) |
---|
| 1633 | { |
---|
| 1634 | PrintS("red:"); |
---|
| 1635 | wrp(h); |
---|
| 1636 | PrintS(" with "); |
---|
| 1637 | wrp(strat->S[j]); |
---|
| 1638 | } |
---|
| 1639 | #endif |
---|
| 1640 | number coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 1641 | strat->lenS[j]/*pLength(strat->S[j])*/, |
---|
| 1642 | strat->kNoether); |
---|
| 1643 | nDelete(&coef); |
---|
| 1644 | h = kBucketGetLm(P.bucket); |
---|
| 1645 | if (h==NULL) return NULL; |
---|
| 1646 | P.p=h; |
---|
| 1647 | P.t_p=NULL; |
---|
| 1648 | P.SetShortExpVector(); |
---|
| 1649 | #ifdef KDEBUG |
---|
| 1650 | if (TEST_OPT_DEBUG) |
---|
| 1651 | { |
---|
| 1652 | PrintS("\nto:"); |
---|
| 1653 | wrp(h); |
---|
| 1654 | PrintLn(); |
---|
| 1655 | } |
---|
| 1656 | #endif |
---|
| 1657 | } |
---|
| 1658 | else |
---|
| 1659 | { |
---|
| 1660 | kBucketClear(P.bucket,&(P.p),&len); |
---|
| 1661 | kBucketDestroy(&P.bucket); |
---|
| 1662 | pNormalize(P.p); |
---|
| 1663 | return P.p; |
---|
| 1664 | } |
---|
| 1665 | } |
---|
| 1666 | } |
---|
[518fb78] | 1667 | |
---|
[4f858ce] | 1668 | #ifdef REDTAIL_S |
---|
| 1669 | |
---|
| 1670 | static poly redNFTail (poly h,const int sl,kStrategy strat, int len) |
---|
| 1671 | { |
---|
| 1672 | if (h==NULL) return NULL; |
---|
| 1673 | pTest(h); |
---|
| 1674 | if (0 > sl) |
---|
| 1675 | return h; |
---|
| 1676 | if (pNext(h)==NULL) return h; |
---|
| 1677 | |
---|
| 1678 | int j; |
---|
| 1679 | poly res=h; |
---|
| 1680 | poly act=res; |
---|
| 1681 | LObject P(pNext(h)); |
---|
| 1682 | pNext(res)=NULL; |
---|
| 1683 | P.bucket = kBucketCreate(currRing); |
---|
| 1684 | len--; |
---|
| 1685 | h=P.p; |
---|
| 1686 | if (len <=0) len=pLength(h); |
---|
| 1687 | kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/); |
---|
| 1688 | pTest(h); |
---|
| 1689 | loop |
---|
| 1690 | { |
---|
| 1691 | P.p=h; |
---|
| 1692 | P.t_p=NULL; |
---|
| 1693 | P.SetShortExpVector(); |
---|
| 1694 | loop |
---|
| 1695 | { |
---|
| 1696 | j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P); |
---|
| 1697 | if (j>=0) |
---|
| 1698 | { |
---|
| 1699 | #ifdef REDTAIL_PROT |
---|
| 1700 | PrintS("r"); |
---|
| 1701 | #endif |
---|
| 1702 | nNormalize(pGetCoeff(P.p)); |
---|
| 1703 | #ifdef KDEBUG |
---|
| 1704 | if (TEST_OPT_DEBUG) |
---|
| 1705 | { |
---|
| 1706 | PrintS("red tail:"); |
---|
| 1707 | wrp(h); |
---|
| 1708 | PrintS(" with "); |
---|
| 1709 | wrp(strat->S[j]); |
---|
| 1710 | } |
---|
| 1711 | #endif |
---|
| 1712 | number coef; |
---|
| 1713 | pTest(strat->S[j]); |
---|
| 1714 | coef=kBucketPolyRed(P.bucket,strat->S[j], |
---|
| 1715 | strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether); |
---|
| 1716 | pMult_nn(res,coef); |
---|
| 1717 | nDelete(&coef); |
---|
| 1718 | h = kBucketGetLm(P.bucket); |
---|
| 1719 | pTest(h); |
---|
| 1720 | if (h==NULL) |
---|
| 1721 | { |
---|
| 1722 | #ifdef REDTAIL_PROT |
---|
| 1723 | PrintS(" "); |
---|
| 1724 | #endif |
---|
| 1725 | kBucketDestroy(&P.bucket); |
---|
| 1726 | return res; |
---|
| 1727 | } |
---|
| 1728 | pTest(h); |
---|
| 1729 | P.p=h; |
---|
| 1730 | P.t_p=NULL; |
---|
| 1731 | P.SetShortExpVector(); |
---|
| 1732 | #ifdef KDEBUG |
---|
| 1733 | if (TEST_OPT_DEBUG) |
---|
| 1734 | { |
---|
| 1735 | PrintS("\nto tail:"); |
---|
| 1736 | wrp(h); |
---|
| 1737 | PrintLn(); |
---|
| 1738 | } |
---|
| 1739 | #endif |
---|
| 1740 | } |
---|
| 1741 | else |
---|
| 1742 | { |
---|
| 1743 | #ifdef REDTAIL_PROT |
---|
| 1744 | PrintS("n"); |
---|
| 1745 | #endif |
---|
| 1746 | break; |
---|
| 1747 | } |
---|
| 1748 | } /* end loop current mon */ |
---|
| 1749 | // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/); |
---|
| 1750 | //act->next=tmp;pIter(act); |
---|
| 1751 | act->next=kBucketExtractLm(P.bucket);pIter(act); |
---|
| 1752 | h = kBucketGetLm(P.bucket); |
---|
| 1753 | if (h==NULL) |
---|
| 1754 | { |
---|
| 1755 | #ifdef REDTAIL_PROT |
---|
| 1756 | PrintS(" "); |
---|
| 1757 | #endif |
---|
| 1758 | kBucketDestroy(&P.bucket); |
---|
| 1759 | return res; |
---|
| 1760 | } |
---|
| 1761 | pTest(h); |
---|
| 1762 | } |
---|
| 1763 | } |
---|
| 1764 | #endif |
---|
| 1765 | |
---|
| 1766 | |
---|
| 1767 | //try to fill, return FALSE iff queue is empty |
---|
| 1768 | |
---|
| 1769 | //transfers ownership of m to mat |
---|
| 1770 | void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m){ |
---|
| 1771 | assume(mat->mp[row]==NULL); |
---|
| 1772 | mat->mp[row]=m; |
---|
| 1773 | #ifdef TGB_DEBUG |
---|
| 1774 | mac_poly r=m; |
---|
| 1775 | while(r){ |
---|
| 1776 | assume(r->exp<mat->columns); |
---|
| 1777 | r=r->next; |
---|
| 1778 | } |
---|
| 1779 | #endif |
---|
| 1780 | } |
---|
| 1781 | poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index){ |
---|
| 1782 | poly p=NULL; |
---|
| 1783 | poly* set_this=&p; |
---|
| 1784 | mac_poly r=mat->mp[row]; |
---|
| 1785 | mat->mp[row]=NULL; |
---|
| 1786 | while(r) |
---|
| 1787 | { |
---|
| 1788 | (*set_this)=pLmInit(monoms[monom_index-1-r->exp]); |
---|
| 1789 | pSetCoeff((*set_this),r->coef); |
---|
| 1790 | set_this=&((*set_this)->next); |
---|
| 1791 | mac_poly old=r; |
---|
| 1792 | r=r->next; |
---|
| 1793 | delete old; |
---|
| 1794 | |
---|
| 1795 | } |
---|
| 1796 | return p; |
---|
| 1797 | |
---|
| 1798 | } |
---|
| 1799 | |
---|
| 1800 | |
---|
| 1801 | |
---|
| 1802 | |
---|
| 1803 | |
---|
| 1804 | |
---|
| 1805 | |
---|
| 1806 | |
---|
| 1807 | |
---|
| 1808 | |
---|
| 1809 | |
---|
| 1810 | static int poly_crit(const void* ap1, const void* ap2){ |
---|
| 1811 | poly p1,p2; |
---|
| 1812 | p1=*((poly*) ap1); |
---|
| 1813 | p2=*((poly*)ap2); |
---|
| 1814 | |
---|
| 1815 | int c=pLmCmp(p1,p2); |
---|
| 1816 | if (c !=0) return c; |
---|
| 1817 | int l1=pLength(p1); |
---|
| 1818 | int l2=pLength(p2); |
---|
| 1819 | if (l1<l2) return -1; |
---|
| 1820 | if (l1>l2) return 1; |
---|
| 1821 | return 0; |
---|
| 1822 | } |
---|
| 1823 | |
---|
| 1824 | ideal t_rep_gb(ring r,ideal arg_I, BOOLEAN F4_mode){ |
---|
| 1825 | if (TEST_OPT_PROT) |
---|
| 1826 | if (F4_mode) |
---|
| 1827 | PrintS("F4 Modus \n"); |
---|
| 1828 | |
---|
| 1829 | |
---|
| 1830 | //debug_Ideal=arg_debug_Ideal; |
---|
| 1831 | //if (debug_Ideal) PrintS("DebugIdeal received\n"); |
---|
| 1832 | // Print("Idelems %i \n----------\n",IDELEMS(arg_I)); |
---|
| 1833 | ideal I=idCompactify(arg_I); |
---|
| 1834 | if (idIs0(I)) return I; |
---|
| 1835 | |
---|
| 1836 | qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit); |
---|
| 1837 | //Print("Idelems %i \n----------\n",IDELEMS(I)); |
---|
[9cbb7a3] | 1838 | slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg)); |
---|
[4f858ce] | 1839 | |
---|
| 1840 | c->r=currRing; |
---|
| 1841 | c->is_homog=TRUE; |
---|
| 1842 | { |
---|
| 1843 | int hz; |
---|
| 1844 | for(hz=0;hz<IDELEMS(I);hz++){ |
---|
| 1845 | assume(I->m[hz]!=NULL); |
---|
| 1846 | int d=pTotaldegree(I->m[hz]); |
---|
| 1847 | poly t=I->m[hz]->next; |
---|
| 1848 | while(t) |
---|
| 1849 | { |
---|
| 1850 | if (d!=pTotaldegree(t,c->r)) |
---|
| 1851 | { |
---|
| 1852 | c->is_homog=FALSE; |
---|
| 1853 | break; |
---|
| 1854 | } |
---|
| 1855 | t=t->next; |
---|
| 1856 | } |
---|
| 1857 | if(!(c->is_homog)) break; |
---|
| 1858 | } |
---|
| 1859 | } |
---|
| 1860 | // Print("is homog:%d",c->is_homog); |
---|
| 1861 | void* h; |
---|
| 1862 | poly hp; |
---|
| 1863 | int i,j; |
---|
| 1864 | c->to_destroy=NULL; |
---|
| 1865 | c->easy_product_crit=0; |
---|
| 1866 | c->extended_product_crit=0; |
---|
| 1867 | if (rField_is_Zp(c->r)) |
---|
| 1868 | c->is_char0=FALSE; |
---|
| 1869 | else |
---|
| 1870 | c->is_char0=TRUE; |
---|
| 1871 | //not fully correct |
---|
| 1872 | |
---|
| 1873 | //(rChar()==0); |
---|
| 1874 | c->F4_mode=F4_mode; |
---|
| 1875 | c->reduction_steps=0; |
---|
| 1876 | c->last_index=-1; |
---|
| 1877 | |
---|
| 1878 | c->F=NULL; |
---|
| 1879 | c->F_minus=NULL; |
---|
| 1880 | |
---|
| 1881 | c->Rcounter=0; |
---|
| 1882 | |
---|
| 1883 | c->soon_free=NULL; |
---|
| 1884 | |
---|
| 1885 | c->tmp_lm=pOne(); |
---|
| 1886 | |
---|
| 1887 | c->normal_forms=0; |
---|
| 1888 | c->current_degree=1; |
---|
| 1889 | |
---|
| 1890 | c->max_pairs=5*I->idelems(); |
---|
| 1891 | |
---|
[ec8a6b6] | 1892 | c->apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*c->max_pairs); |
---|
[4f858ce] | 1893 | c->pair_top=-1; |
---|
| 1894 | |
---|
| 1895 | int n=I->idelems(); |
---|
[6d7605] | 1896 | c->array_lengths=n; |
---|
| 1897 | |
---|
[09ab660] | 1898 | |
---|
[4f858ce] | 1899 | i=0; |
---|
| 1900 | c->n=0; |
---|
[ec8a6b6] | 1901 | c->T_deg=(int*) omalloc(n*sizeof(int)); |
---|
[4f858ce] | 1902 | if((!(c->is_homog)) &&(pLexOrder)) |
---|
[ec8a6b6] | 1903 | c->T_deg_full=(int*) omalloc(n*sizeof(int)); |
---|
[4f858ce] | 1904 | else |
---|
| 1905 | c->T_deg_full=NULL; |
---|
[ec8a6b6] | 1906 | c->tmp_pair_lm=(poly*) omalloc(n*sizeof(poly)); |
---|
| 1907 | c->tmp_spn=(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*)); |
---|
[4f858ce] | 1908 | lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long)); |
---|
| 1909 | #ifdef HEAD_BIN |
---|
| 1910 | c->HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long)); |
---|
| 1911 | #endif |
---|
| 1912 | /* omUnGetSpecBin(&(c->HeadBin)); */ |
---|
[ec8a6b6] | 1913 | h=omalloc(n*sizeof(char*)); |
---|
[4f858ce] | 1914 | c->states=(char**) h; |
---|
[ec8a6b6] | 1915 | h=omalloc(n*sizeof(int)); |
---|
[4f858ce] | 1916 | c->lengths=(int*) h; |
---|
[ec8a6b6] | 1917 | h=omalloc(n*sizeof(int)); |
---|
| 1918 | c->gcd_of_terms=(poly*) omalloc(n*sizeof(poly)); |
---|
[4f858ce] | 1919 | c->rep=(int*) h; |
---|
[ec8a6b6] | 1920 | c->short_Exps=(long*) omalloc(n*sizeof(long)); |
---|
[4f858ce] | 1921 | c->S=idInit(n,1); |
---|
| 1922 | c->strat=new skStrategy; |
---|
| 1923 | c->strat->syzComp = 0; |
---|
| 1924 | initBuchMoraCrit(c->strat); |
---|
| 1925 | initBuchMoraPos(c->strat); |
---|
| 1926 | c->strat->initEcart = initEcartBBA; |
---|
| 1927 | c->strat->enterS = enterSBba; |
---|
| 1928 | c->strat->sl = -1; |
---|
| 1929 | i=n; |
---|
[6d7605] | 1930 | i=1;//some strange bug else |
---|
[4f858ce] | 1931 | /* initS(c->S,NULL,c->strat); */ |
---|
| 1932 | /* intS start: */ |
---|
| 1933 | // i=((i+IDELEMS(c->S)+15)/16)*16; |
---|
| 1934 | c->strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/ |
---|
| 1935 | c->strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long)); |
---|
| 1936 | /*initsevS(i);*/ |
---|
| 1937 | c->strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/ |
---|
| 1938 | c->strat->fromQ=NULL; |
---|
| 1939 | c->strat->Shdl=idInit(1,1); |
---|
| 1940 | c->strat->S=c->strat->Shdl->m; |
---|
| 1941 | c->strat->lenS=(int*)omAlloc0(i*sizeof(int)); |
---|
| 1942 | if((c->is_char0)||((pLexOrder) &&(!c->is_homog))) |
---|
| 1943 | c->strat->lenSw=(int*)omAlloc0(i*sizeof(int)); |
---|
| 1944 | else |
---|
| 1945 | c->strat->lenSw=NULL; |
---|
| 1946 | sorted_pair_node* si; |
---|
| 1947 | assume(n>0); |
---|
[65c4dc] | 1948 | add_to_basis_ideal_quotient(I->m[0],-1,-1,c,NULL); |
---|
[4f858ce] | 1949 | |
---|
| 1950 | assume(c->strat->sl==c->strat->Shdl->idelems()-1); |
---|
| 1951 | if(!(F4_mode)) |
---|
| 1952 | { |
---|
| 1953 | for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis |
---|
| 1954 | { |
---|
| 1955 | // add_to_basis(I->m[i],-1,-1,c); |
---|
[ec8a6b6] | 1956 | si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node)); |
---|
[4f858ce] | 1957 | si->i=-1; |
---|
| 1958 | si->j=-1; |
---|
| 1959 | si->expected_length=pLength(I->m[i]); |
---|
| 1960 | si->deg=pTotaldegree(I->m[i]); |
---|
| 1961 | if (!rField_is_Zp(c->r)){ |
---|
| 1962 | pCleardenom(I->m[i]); |
---|
| 1963 | } |
---|
| 1964 | si->lcm_of_lm=I->m[i]; |
---|
| 1965 | |
---|
| 1966 | // c->apairs[n-1-i]=si; |
---|
| 1967 | c->apairs[n-i-1]=si; |
---|
| 1968 | ++(c->pair_top); |
---|
| 1969 | } |
---|
| 1970 | } |
---|
| 1971 | else |
---|
| 1972 | { |
---|
| 1973 | for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis |
---|
[1577276] | 1974 | add_to_basis_ideal_quotient(I->m[i],-1,-1,c,NULL); |
---|
[4f858ce] | 1975 | } |
---|
| 1976 | |
---|
| 1977 | |
---|
| 1978 | while(c->pair_top>=0) |
---|
| 1979 | { |
---|
| 1980 | if(F4_mode) |
---|
| 1981 | go_on_F4(c); |
---|
| 1982 | else |
---|
| 1983 | go_on(c); |
---|
| 1984 | } |
---|
| 1985 | while(c->to_destroy) |
---|
| 1986 | { |
---|
| 1987 | pDelete(&(c->to_destroy->p)); |
---|
| 1988 | poly_list_node* old=c->to_destroy; |
---|
| 1989 | c->to_destroy=c->to_destroy->next; |
---|
| 1990 | omfree(old); |
---|
| 1991 | } |
---|
| 1992 | while(c->F) |
---|
| 1993 | { |
---|
| 1994 | for(i=0;i<c->F->size;i++){ |
---|
| 1995 | pDelete(&(c->F->mp[i].m)); |
---|
| 1996 | } |
---|
| 1997 | omfree(c->F->mp); |
---|
| 1998 | c->F->mp=NULL; |
---|
| 1999 | mp_array_list* old=c->F; |
---|
| 2000 | c->F=c->F->next; |
---|
| 2001 | omfree(old); |
---|
| 2002 | } |
---|
| 2003 | while(c->F_minus) |
---|
| 2004 | { |
---|
| 2005 | for(i=0;i<c->F_minus->size;i++){ |
---|
| 2006 | pDelete(&(c->F_minus->p[i])); |
---|
| 2007 | } |
---|
| 2008 | omfree(c->F_minus->p); |
---|
| 2009 | c->F_minus->p=NULL; |
---|
| 2010 | poly_array_list* old=c->F_minus; |
---|
| 2011 | c->F_minus=c->F_minus->next; |
---|
| 2012 | omfree(old); |
---|
| 2013 | } |
---|
[76b225] | 2014 | for(int z=1 /* zero length at 0 */;z<c->n;z++){ |
---|
[4f858ce] | 2015 | omfree(c->states[z]); |
---|
| 2016 | } |
---|
| 2017 | omfree(c->states); |
---|
| 2018 | omfree(c->lengths); |
---|
| 2019 | for(int z=0;z<c->n;z++) |
---|
| 2020 | { |
---|
| 2021 | pDelete(&c->tmp_pair_lm[z]); |
---|
| 2022 | omfree(c->tmp_spn[z]); |
---|
| 2023 | } |
---|
| 2024 | omfree(c->tmp_pair_lm); |
---|
| 2025 | omfree(c->tmp_spn); |
---|
| 2026 | |
---|
| 2027 | omfree(c->T_deg); |
---|
| 2028 | if(c->T_deg_full) |
---|
| 2029 | omfree(c->T_deg_full); |
---|
| 2030 | |
---|
| 2031 | omFree(c->strat->ecartS); |
---|
| 2032 | omFree(c->strat->sevS); |
---|
| 2033 | // initsevS(i); |
---|
| 2034 | omFree(c->strat->S_2_R); |
---|
| 2035 | |
---|
| 2036 | |
---|
| 2037 | omFree(c->strat->lenS); |
---|
| 2038 | |
---|
| 2039 | if(c->strat->lenSw) omFree(c->strat->lenSw); |
---|
| 2040 | |
---|
| 2041 | |
---|
| 2042 | |
---|
| 2043 | |
---|
| 2044 | for(i=0;i<c->n;i++){ |
---|
| 2045 | if(c->gcd_of_terms[i]) |
---|
| 2046 | pDelete(&(c->gcd_of_terms[i])); |
---|
| 2047 | } |
---|
| 2048 | omfree(c->gcd_of_terms); |
---|
| 2049 | |
---|
| 2050 | omfree(c->apairs); |
---|
| 2051 | if (TEST_OPT_PROT) |
---|
| 2052 | { |
---|
| 2053 | Print("calculated %d NFs\n",c->normal_forms); |
---|
| 2054 | Print("applied %i product crit, %i extended_product crit \n", c->easy_product_crit, c->extended_product_crit); |
---|
| 2055 | } |
---|
| 2056 | int deleted_form_c_s=0; |
---|
| 2057 | |
---|
| 2058 | for(i=0;i<=c->strat->sl;i++){ |
---|
| 2059 | if (!c->strat->S[i]) continue; |
---|
| 2060 | BOOLEAN found=FALSE; |
---|
| 2061 | for(j=0;j<c->n;j++){ |
---|
| 2062 | if (c->S->m[j]==c->strat->S[i]){ |
---|
| 2063 | found=TRUE; |
---|
| 2064 | break; |
---|
| 2065 | } |
---|
| 2066 | } |
---|
| 2067 | if(!found) pDelete(&c->strat->S[i]); |
---|
| 2068 | } |
---|
| 2069 | // for(i=0;i<c->n;i++){ |
---|
| 2070 | // if (c->rep[i]!=i){ |
---|
| 2071 | // // for(j=0;j<=c->strat->sl;j++){ |
---|
| 2072 | // // if(c->strat->S[j]==c->S->m[i]){ |
---|
| 2073 | // // c->strat->S[j]=NULL; |
---|
| 2074 | // // break; |
---|
| 2075 | // // } |
---|
| 2076 | // // } |
---|
| 2077 | // // PrintS("R_delete"); |
---|
| 2078 | // pDelete(&c->S->m[i]); |
---|
| 2079 | // } |
---|
| 2080 | // } |
---|
| 2081 | |
---|
[dd414d] | 2082 | |
---|
[4f858ce] | 2083 | for(i=0;i<c->n;i++) |
---|
| 2084 | { |
---|
| 2085 | assume(c->S->m[i]!=NULL); |
---|
| 2086 | for(j=0;j<c->n;j++) |
---|
| 2087 | { |
---|
| 2088 | if((c->S->m[j]==NULL)||(i==j)) |
---|
| 2089 | continue; |
---|
| 2090 | assume(p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], |
---|
| 2091 | c->S->m[i],~c->short_Exps[i], |
---|
| 2092 | c->r)==p_LmDivisibleBy(c->S->m[j], |
---|
| 2093 | c->S->m[i], |
---|
| 2094 | c->r)); |
---|
| 2095 | if (p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j], |
---|
| 2096 | c->S->m[i],~c->short_Exps[i], |
---|
| 2097 | c->r)) |
---|
| 2098 | { |
---|
| 2099 | pDelete(&c->S->m[i]); |
---|
| 2100 | break; |
---|
| 2101 | } |
---|
| 2102 | } |
---|
| 2103 | } |
---|
| 2104 | omfree(c->short_Exps); |
---|
| 2105 | omfree(c->rep); |
---|
| 2106 | for(i=0;i<I->idelems();i++) |
---|
| 2107 | { |
---|
| 2108 | I->m[i]=NULL; |
---|
| 2109 | } |
---|
| 2110 | idDelete(&I); |
---|
| 2111 | I=c->S; |
---|
| 2112 | |
---|
| 2113 | IDELEMS(I)=c->n; |
---|
| 2114 | |
---|
| 2115 | idSkipZeroes(I); |
---|
| 2116 | for(i=0;i<=c->strat->sl;i++) |
---|
| 2117 | c->strat->S[i]=NULL; |
---|
| 2118 | id_Delete(&c->strat->Shdl,c->r); |
---|
| 2119 | pDelete(&c->tmp_lm); |
---|
| 2120 | omUnGetSpecBin(&lm_bin); |
---|
| 2121 | delete c->strat; |
---|
| 2122 | omfree(c); |
---|
[227a50] | 2123 | //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func); |
---|
[4f858ce] | 2124 | return(I); |
---|
| 2125 | } |
---|
[9cbb7a3] | 2126 | void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c){ |
---|
[4f858ce] | 2127 | int i,j; |
---|
| 2128 | if (arg_i==arg_j){ |
---|
| 2129 | return; |
---|
| 2130 | } |
---|
| 2131 | if (arg_i>arg_j){ |
---|
| 2132 | i=arg_j; |
---|
| 2133 | j=arg_i; |
---|
| 2134 | } else { |
---|
| 2135 | i=arg_i; |
---|
| 2136 | j=arg_j; |
---|
| 2137 | } |
---|
| 2138 | c->states[j][i]=HASTREP; |
---|
| 2139 | } |
---|
[9cbb7a3] | 2140 | static void soon_t_rep(const int& arg_i, const int& arg_j, slimgb_alg* c) |
---|
[4f858ce] | 2141 | { |
---|
| 2142 | assume(0<=arg_i); |
---|
| 2143 | assume(0<=arg_j); |
---|
| 2144 | assume(arg_i<c->n); |
---|
| 2145 | assume(arg_j<c->n); |
---|
| 2146 | int i,j; |
---|
| 2147 | if (arg_i==arg_j){ |
---|
| 2148 | return; |
---|
| 2149 | } |
---|
| 2150 | if (arg_i>arg_j){ |
---|
| 2151 | i=arg_j; |
---|
| 2152 | j=arg_i; |
---|
| 2153 | } else { |
---|
| 2154 | i=arg_i; |
---|
| 2155 | j=arg_j; |
---|
| 2156 | } |
---|
| 2157 | if (! |
---|
| 2158 | (c->states[j][i]==HASTREP)) |
---|
| 2159 | c->states[j][i]=SOONTREP; |
---|
| 2160 | } |
---|
[9cbb7a3] | 2161 | static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state){ |
---|
[4f858ce] | 2162 | assume(0<=arg_i); |
---|
| 2163 | assume(0<=arg_j); |
---|
| 2164 | assume(arg_i<state->n); |
---|
| 2165 | assume(arg_j<state->n); |
---|
| 2166 | if (arg_i==arg_j) |
---|
| 2167 | { |
---|
| 2168 | return (TRUE); |
---|
| 2169 | } |
---|
| 2170 | if (arg_i>arg_j) |
---|
| 2171 | { |
---|
| 2172 | return (state->states[arg_i][arg_j]==HASTREP); |
---|
| 2173 | } else |
---|
| 2174 | { |
---|
| 2175 | return (state->states[arg_j][arg_i]==HASTREP); |
---|
| 2176 | } |
---|
| 2177 | } |
---|
| 2178 | static int pLcmDeg(poly a, poly b) |
---|
| 2179 | { |
---|
| 2180 | int i; |
---|
| 2181 | int n=0; |
---|
| 2182 | for (i=pVariables; i; i--) |
---|
| 2183 | { |
---|
| 2184 | n+=si_max( pGetExp(a,i), pGetExp(b,i)); |
---|
| 2185 | } |
---|
| 2186 | return n; |
---|
| 2187 | |
---|
| 2188 | } |
---|
| 2189 | |
---|
| 2190 | |
---|
| 2191 | |
---|
[9cbb7a3] | 2192 | static void shorten_tails(slimgb_alg* c, poly monom) |
---|
[4f858ce] | 2193 | { |
---|
| 2194 | return; |
---|
| 2195 | // BOOLEAN corr=lenS_correct(c->strat); |
---|
| 2196 | for(int i=0;i<c->n;i++) |
---|
| 2197 | { |
---|
| 2198 | //enter tail |
---|
| 2199 | if (c->rep[i]!=i) continue; |
---|
| 2200 | if (c->S->m[i]==NULL) continue; |
---|
| 2201 | poly tail=c->S->m[i]->next; |
---|
| 2202 | poly prev=c->S->m[i]; |
---|
| 2203 | BOOLEAN did_something=FALSE; |
---|
| 2204 | while((tail!=NULL)&& (pLmCmp(tail, monom)>=0)) |
---|
| 2205 | { |
---|
| 2206 | if (p_LmDivisibleBy(monom,tail,c->r)) |
---|
| 2207 | { |
---|
| 2208 | did_something=TRUE; |
---|
| 2209 | prev->next=tail->next; |
---|
| 2210 | tail->next=NULL; |
---|
| 2211 | p_Delete(& tail,c->r); |
---|
| 2212 | tail=prev; |
---|
| 2213 | //PrintS("Shortened"); |
---|
| 2214 | c->lengths[i]--; |
---|
| 2215 | } |
---|
| 2216 | prev=tail; |
---|
| 2217 | tail=tail->next; |
---|
| 2218 | } |
---|
| 2219 | if (did_something) |
---|
| 2220 | { |
---|
| 2221 | int new_pos; |
---|
| 2222 | int q; |
---|
| 2223 | q=pQuality(c->S->m[i],c,c->lengths[i]); |
---|
| 2224 | new_pos=simple_posInS(c->strat,c->S->m[i],q); |
---|
| 2225 | |
---|
| 2226 | int old_pos=-1; |
---|
| 2227 | //assume new_pos<old_pos |
---|
| 2228 | for (int z=0;z<=c->strat->sl;z++) |
---|
| 2229 | { |
---|
| 2230 | if (c->strat->S[z]==c->S->m[i]) |
---|
| 2231 | { |
---|
| 2232 | old_pos=z; |
---|
| 2233 | break; |
---|
| 2234 | } |
---|
| 2235 | } |
---|
| 2236 | if (old_pos== -1) |
---|
| 2237 | for (int z=new_pos-1;z>=0;z--) |
---|
| 2238 | { |
---|
| 2239 | if (c->strat->S[z]==c->S->m[i]) |
---|
| 2240 | { |
---|
| 2241 | old_pos=z; |
---|
| 2242 | break; |
---|
| 2243 | } |
---|
| 2244 | } |
---|
| 2245 | assume(old_pos>=0); |
---|
| 2246 | assume(new_pos<=old_pos); |
---|
| 2247 | assume(pLength(c->strat->S[old_pos])==c->lengths[i]); |
---|
| 2248 | c->strat->lenS[old_pos]=c->lengths[i]; |
---|
| 2249 | if (c->strat->lenSw) |
---|
| 2250 | c->strat->lenSw[old_pos]=q; |
---|
| 2251 | |
---|
| 2252 | if (new_pos<old_pos) |
---|
| 2253 | move_forward_in_S(old_pos,new_pos,c->strat); |
---|
| 2254 | |
---|
| 2255 | length_one_crit(c,i,c->lengths[i]); |
---|
| 2256 | } |
---|
| 2257 | } |
---|
| 2258 | } |
---|
[9cbb7a3] | 2259 | static sorted_pair_node* pop_pair(slimgb_alg* c){ |
---|
[4f858ce] | 2260 | clean_top_of_pair_list(c); |
---|
| 2261 | |
---|
| 2262 | if(c->pair_top<0) return NULL; |
---|
| 2263 | else return (c->apairs[c->pair_top--]); |
---|
| 2264 | } |
---|
[9cbb7a3] | 2265 | sorted_pair_node* top_pair(slimgb_alg* c){ |
---|
[4f858ce] | 2266 | super_clean_top_of_pair_list(c);//yeah, I know, it's odd that I use a different proc here |
---|
| 2267 | |
---|
| 2268 | if(c->pair_top<0) return NULL; |
---|
| 2269 | else return (c->apairs[c->pair_top]); |
---|
| 2270 | } |
---|
[9cbb7a3] | 2271 | sorted_pair_node* quick_pop_pair(slimgb_alg* c){ |
---|
[4f858ce] | 2272 | if(c->pair_top<0) return NULL; |
---|
| 2273 | else return (c->apairs[c->pair_top--]); |
---|
| 2274 | } |
---|
[9cbb7a3] | 2275 | static BOOLEAN no_pairs(slimgb_alg* c){ |
---|
[4f858ce] | 2276 | clean_top_of_pair_list(c); |
---|
| 2277 | return (c->pair_top==-1); |
---|
| 2278 | } |
---|
| 2279 | |
---|
| 2280 | |
---|
[9cbb7a3] | 2281 | static void super_clean_top_of_pair_list(slimgb_alg* c){ |
---|
[4f858ce] | 2282 | while((c->pair_top>=0) |
---|
| 2283 | && (c->apairs[c->pair_top]->i>=0) |
---|
| 2284 | && (good_has_t_rep(c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))) |
---|
| 2285 | { |
---|
| 2286 | |
---|
| 2287 | free_sorted_pair_node(c->apairs[c->pair_top],c->r); |
---|
| 2288 | c->pair_top--; |
---|
| 2289 | |
---|
| 2290 | } |
---|
| 2291 | } |
---|
[9cbb7a3] | 2292 | void clean_top_of_pair_list(slimgb_alg* c){ |
---|
[4f858ce] | 2293 | 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))){ |
---|
| 2294 | |
---|
| 2295 | free_sorted_pair_node(c->apairs[c->pair_top],c->r); |
---|
| 2296 | c->pair_top--; |
---|
| 2297 | |
---|
| 2298 | } |
---|
| 2299 | } |
---|
[9cbb7a3] | 2300 | static BOOLEAN state_is(calc_state state, const int & arg_i, const int & arg_j, slimgb_alg* c){ |
---|
[4f858ce] | 2301 | assume(0<=arg_i); |
---|
| 2302 | assume(0<=arg_j); |
---|
| 2303 | assume(arg_i<c->n); |
---|
| 2304 | assume(arg_j<c->n); |
---|
| 2305 | if (arg_i==arg_j) |
---|
| 2306 | { |
---|
| 2307 | return (TRUE); |
---|
| 2308 | } |
---|
| 2309 | if (arg_i>arg_j) |
---|
| 2310 | { |
---|
| 2311 | return (c->states[arg_i][arg_j]==state); |
---|
| 2312 | } |
---|
| 2313 | else return(c->states[arg_j][arg_i]==state); |
---|
| 2314 | } |
---|
[b75d13] | 2315 | void free_sorted_pair_node(sorted_pair_node* s, ring r){ |
---|
[4f858ce] | 2316 | if (s->i>=0) |
---|
| 2317 | p_Delete(&s->lcm_of_lm,r); |
---|
| 2318 | omfree(s); |
---|
| 2319 | } |
---|
[9cbb7a3] | 2320 | static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c){ |
---|
[4f858ce] | 2321 | if (a->deg<b->deg) return TRUE; |
---|
| 2322 | if (a->deg>b->deg) return FALSE; |
---|
| 2323 | |
---|
| 2324 | // if (a->expected_length<b->expected_length) return TRUE; |
---|
| 2325 | // if (a->expected_length>b->expected_length) return FALSE; |
---|
| 2326 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 2327 | if (comp==1) return FALSE; |
---|
| 2328 | if (-1==comp) return TRUE; |
---|
| 2329 | if (a->i+a->j<b->i+b->j) return TRUE; |
---|
| 2330 | if (a->i+a->j>b->i+b->j) return FALSE; |
---|
| 2331 | if (a->i<b->i) return TRUE; |
---|
| 2332 | if (a->i>b->i) return FALSE; |
---|
| 2333 | return TRUE; |
---|
| 2334 | } |
---|
| 2335 | |
---|
[b75d13] | 2336 | static int tgb_pair_better_gen(const void* ap,const void* bp){ |
---|
[4f858ce] | 2337 | |
---|
| 2338 | sorted_pair_node* a=*((sorted_pair_node**)ap); |
---|
| 2339 | sorted_pair_node* b=*((sorted_pair_node**)bp); |
---|
| 2340 | assume(a->i>a->j); |
---|
| 2341 | assume(b->i>b->j); |
---|
| 2342 | if (a->deg<b->deg) return -1; |
---|
| 2343 | if (a->deg>b->deg) return 1; |
---|
| 2344 | |
---|
| 2345 | |
---|
| 2346 | // if (a->expected_length<b->expected_length) return -1; |
---|
| 2347 | // if (a->expected_length>b->expected_length) return 1; |
---|
| 2348 | int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); |
---|
| 2349 | |
---|
| 2350 | if (comp==1) return 1; |
---|
| 2351 | if (-1==comp) return -1; |
---|
| 2352 | if (a->i+a->j<b->i+b->j) return -1; |
---|
| 2353 | if (a->i+a->j>b->i+b->j) return 1; |
---|
| 2354 | if (a->i<b->i) return -1; |
---|
| 2355 | if (a->i>b->i) return 1; |
---|
| 2356 | return 0; |
---|
| 2357 | } |
---|
| 2358 | |
---|
| 2359 | |
---|
| 2360 | static poly gcd_of_terms(poly p, ring r){ |
---|
| 2361 | int max_g_0=0; |
---|
| 2362 | assume(p!=NULL); |
---|
| 2363 | int i; |
---|
| 2364 | poly m=pOne(); |
---|
| 2365 | poly t; |
---|
| 2366 | for (i=pVariables; i; i--) |
---|
| 2367 | { |
---|
| 2368 | pSetExp(m,i, pGetExp(p,i)); |
---|
| 2369 | if (max_g_0==0) |
---|
| 2370 | if (pGetExp(m,i)>0) |
---|
| 2371 | max_g_0=i; |
---|
| 2372 | } |
---|
| 2373 | |
---|
| 2374 | t=p->next; |
---|
| 2375 | while (t!=NULL){ |
---|
| 2376 | |
---|
| 2377 | if (max_g_0==0) break; |
---|
| 2378 | for (i=max_g_0; i; i--) |
---|
| 2379 | { |
---|
| 2380 | pSetExp(m,i, si_min(pGetExp(t,i),pGetExp(m,i))); |
---|
| 2381 | if (max_g_0==i) |
---|
| 2382 | if (pGetExp(m,i)==0) |
---|
| 2383 | max_g_0=0; |
---|
| 2384 | if ((max_g_0==0) && (pGetExp(m,i)>0)){ |
---|
| 2385 | max_g_0=i; |
---|
| 2386 | } |
---|
| 2387 | } |
---|
| 2388 | t=t->next; |
---|
| 2389 | } |
---|
| 2390 | // for (i=pVariables;i;i--) |
---|
| 2391 | // { |
---|
| 2392 | // if(pGetExp(m,i)>0) |
---|
| 2393 | // return m; |
---|
| 2394 | // } |
---|
| 2395 | if (max_g_0>0) |
---|
| 2396 | return m; |
---|
| 2397 | pDelete(&m); |
---|
| 2398 | return NULL; |
---|
| 2399 | } |
---|
| 2400 | static inline BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m) |
---|
| 2401 | { |
---|
| 2402 | |
---|
| 2403 | if (pGetComp(p1) > 0 || pGetComp(p2) > 0) |
---|
| 2404 | return FALSE; |
---|
| 2405 | int i = 1; |
---|
| 2406 | loop |
---|
| 2407 | { |
---|
| 2408 | if ((pGetExp(p1, i)-pGetExp(m,i) >0) && (pGetExp(p2, i) -pGetExp(m,i)> 0)) return FALSE; |
---|
| 2409 | if (i == pVariables) return TRUE; |
---|
| 2410 | i++; |
---|
| 2411 | } |
---|
| 2412 | } |
---|
| 2413 | |
---|
| 2414 | |
---|
| 2415 | //for impl reasons may return false if the the normal product criterion matches |
---|
[9cbb7a3] | 2416 | static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c){ |
---|
[4f858ce] | 2417 | if(gcd1==NULL) return FALSE; |
---|
| 2418 | if(gcd2==NULL) return FALSE; |
---|
| 2419 | gcd1->next=gcd2; //may ordered incorrect |
---|
| 2420 | poly m=gcd_of_terms(gcd1,c->r); |
---|
| 2421 | gcd1->next=NULL; |
---|
| 2422 | if (m==NULL) return FALSE; |
---|
| 2423 | |
---|
| 2424 | BOOLEAN erg=pHasNotCFExtended(p1,p2,m); |
---|
| 2425 | pDelete(&m); |
---|
| 2426 | return erg; |
---|
| 2427 | } |
---|
| 2428 | static poly kBucketGcd(kBucket* b, ring r) |
---|
| 2429 | { |
---|
| 2430 | int s=0; |
---|
| 2431 | int i; |
---|
| 2432 | poly m, n; |
---|
| 2433 | BOOLEAN initialized=FALSE; |
---|
| 2434 | for (i=MAX_BUCKET-1;i>=0;i--) |
---|
| 2435 | { |
---|
| 2436 | if (b->buckets[i]!=NULL){ |
---|
| 2437 | if (!initialized){ |
---|
| 2438 | m=gcd_of_terms(b->buckets[i],r); |
---|
| 2439 | initialized=TRUE; |
---|
| 2440 | if (m==NULL) return NULL; |
---|
| 2441 | } |
---|
| 2442 | else |
---|
| 2443 | { |
---|
| 2444 | n=gcd_of_terms(b->buckets[i],r); |
---|
| 2445 | if (n==NULL) { |
---|
| 2446 | pDelete(&m); |
---|
| 2447 | return NULL; |
---|
| 2448 | } |
---|
| 2449 | n->next=m; |
---|
| 2450 | poly t=gcd_of_terms(n,r); |
---|
| 2451 | n->next=NULL; |
---|
| 2452 | pDelete(&m); |
---|
| 2453 | pDelete(&n); |
---|
| 2454 | m=t; |
---|
| 2455 | if (m==NULL) return NULL; |
---|
| 2456 | |
---|
| 2457 | } |
---|
| 2458 | } |
---|
| 2459 | } |
---|
| 2460 | return m; |
---|
| 2461 | } |
---|
| 2462 | |
---|
| 2463 | |
---|
| 2464 | |
---|
| 2465 | |
---|
[9cbb7a3] | 2466 | static inline int quality_of_pos_in_strat_S(int pos, slimgb_alg* c){ |
---|
[4f858ce] | 2467 | if (c->strat->lenSw!=NULL) return c->strat->lenSw[pos]; |
---|
| 2468 | return c->strat->lenS[pos]; |
---|
| 2469 | } |
---|
| 2470 | |
---|
[9cbb7a3] | 2471 | static void multi_reduction_lls_trick(red_object* los, int losl,slimgb_alg* c,find_erg & erg){ |
---|
[4f858ce] | 2472 | erg.expand=NULL; |
---|
| 2473 | BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS |
---|
| 2474 | if(erg.fromS){ |
---|
| 2475 | if(pLmEqual(c->strat->S[erg.reduce_by],los[erg.to_reduce_u].p)) |
---|
| 2476 | { |
---|
| 2477 | int i; |
---|
| 2478 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 2479 | int best=erg.to_reduce_u+1; |
---|
| 2480 | /* |
---|
| 2481 | for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){ |
---|
| 2482 | int qc=los[i].guess_quality(c); |
---|
| 2483 | if (qc<quality_a){ |
---|
| 2484 | best=i; |
---|
| 2485 | quality_a=qc; |
---|
| 2486 | } |
---|
| 2487 | } |
---|
| 2488 | if(best!=erg.to_reduce_u+1){*/ |
---|
| 2489 | int qc; |
---|
| 2490 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 2491 | if(qc<quality_a){ |
---|
| 2492 | los[best].flatten(); |
---|
| 2493 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 2494 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 2495 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 2496 | if(qc<quality_a){ |
---|
| 2497 | red_object h=los[erg.to_reduce_u]; |
---|
| 2498 | los[erg.to_reduce_u]=los[best]; |
---|
| 2499 | los[best]=h; |
---|
| 2500 | swap_roles=TRUE; |
---|
| 2501 | } |
---|
| 2502 | else |
---|
| 2503 | swap_roles=FALSE; |
---|
| 2504 | } |
---|
| 2505 | else{ |
---|
| 2506 | |
---|
| 2507 | swap_roles=FALSE; |
---|
| 2508 | } |
---|
| 2509 | |
---|
| 2510 | } |
---|
| 2511 | else |
---|
| 2512 | { |
---|
| 2513 | if (erg.to_reduce_u>erg.to_reduce_l){ |
---|
| 2514 | |
---|
| 2515 | int i; |
---|
| 2516 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 2517 | int best=erg.to_reduce_u+1; |
---|
| 2518 | int qc; |
---|
| 2519 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 2520 | assume(qc==los[best].guess_quality(c)); |
---|
| 2521 | if(qc<quality_a){ |
---|
| 2522 | los[best].flatten(); |
---|
| 2523 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 2524 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 2525 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 2526 | //(best!=erg.to_reduce_u+1) |
---|
| 2527 | if(qc<quality_a){ |
---|
| 2528 | red_object h=los[erg.to_reduce_l]; |
---|
| 2529 | los[erg.to_reduce_l]=los[best]; |
---|
| 2530 | los[best]=h; |
---|
| 2531 | erg.reduce_by=erg.to_reduce_l; |
---|
| 2532 | erg.fromS=FALSE; |
---|
| 2533 | erg.to_reduce_l++; |
---|
| 2534 | } |
---|
| 2535 | } |
---|
| 2536 | } |
---|
| 2537 | else |
---|
| 2538 | { |
---|
| 2539 | assume(erg.to_reduce_u==erg.to_reduce_l); |
---|
| 2540 | int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); |
---|
| 2541 | int qc=los[erg.to_reduce_u].guess_quality(c); |
---|
| 2542 | if(qc<quality_a){ |
---|
| 2543 | int best=erg.to_reduce_u; |
---|
| 2544 | los[best].flatten(); |
---|
| 2545 | int b_pos=kBucketCanonicalize(los[best].bucket); |
---|
| 2546 | los[best].p=los[best].bucket->buckets[b_pos]; |
---|
| 2547 | qc==pQuality(los[best].bucket->buckets[b_pos],c); |
---|
| 2548 | if(qc<quality_a){ |
---|
| 2549 | BOOLEAN exp=FALSE; |
---|
| 2550 | if(qc<=2) |
---|
| 2551 | exp=TRUE; |
---|
| 2552 | else { |
---|
| 2553 | if (qc<quality_a/2) |
---|
| 2554 | exp=TRUE; |
---|
| 2555 | else |
---|
| 2556 | if(erg.reduce_by<c->n/4) |
---|
| 2557 | exp=TRUE; |
---|
| 2558 | } |
---|
| 2559 | if (exp){ |
---|
| 2560 | poly clear_into; |
---|
| 2561 | los[erg.to_reduce_u].flatten(); |
---|
| 2562 | kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); |
---|
| 2563 | erg.expand=pCopy(clear_into); |
---|
| 2564 | kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); |
---|
| 2565 | if (TEST_OPT_PROT) |
---|
| 2566 | PrintS("e"); |
---|
| 2567 | |
---|
| 2568 | } |
---|
| 2569 | } |
---|
| 2570 | } |
---|
| 2571 | |
---|
| 2572 | |
---|
| 2573 | } |
---|
| 2574 | |
---|
| 2575 | swap_roles=FALSE; |
---|
| 2576 | return; |
---|
| 2577 | } |
---|
| 2578 | |
---|
| 2579 | } |
---|
| 2580 | else{ |
---|
| 2581 | if(erg.reduce_by>erg.to_reduce_u){ |
---|
| 2582 | //then lm(rb)>= lm(tru) so = |
---|
| 2583 | assume(erg.reduce_by==erg.to_reduce_u+1); |
---|
| 2584 | int best=erg.reduce_by; |
---|
| 2585 | int quality_a=los[erg.reduce_by].guess_quality(c); |
---|
| 2586 | int qc; |
---|
| 2587 | best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); |
---|
| 2588 | |
---|
| 2589 | int i; |
---|
| 2590 | if(qc<quality_a){ |
---|
| 2591 | red_object h=los[erg.reduce_by]; |
---|
| 2592 | los[erg.reduce_by]=los[best]; |
---|
| 2593 | los[best]=h; |
---|
| 2594 | } |
---|
| 2595 | swap_roles=FALSE; |
---|
| 2596 | return; |
---|
| 2597 | |
---|
| 2598 | |
---|
| 2599 | } |
---|
| 2600 | else |
---|
| 2601 | { |
---|
| 2602 | assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); |
---|
| 2603 | assume(erg.to_reduce_u==erg.to_reduce_l); |
---|
| 2604 | //further assume, that reduce_by is the above all other polys |
---|
| 2605 | //with same leading term |
---|
| 2606 | int il=erg.reduce_by; |
---|
| 2607 | int quality_a =los[erg.reduce_by].guess_quality(c); |
---|
| 2608 | int qc; |
---|
| 2609 | while((il>0) && pLmEqual(los[il-1].p,los[il].p)){ |
---|
| 2610 | il--; |
---|
| 2611 | qc=los[il].guess_quality(c); |
---|
| 2612 | if (qc<quality_a){ |
---|
| 2613 | quality_a=qc; |
---|
| 2614 | erg.reduce_by=il; |
---|
| 2615 | } |
---|
| 2616 | } |
---|
| 2617 | swap_roles=FALSE; |
---|
| 2618 | } |
---|
| 2619 | |
---|
| 2620 | } |
---|
| 2621 | if(swap_roles) |
---|
| 2622 | { |
---|
| 2623 | if (TEST_OPT_PROT) |
---|
| 2624 | PrintS("b"); |
---|
| 2625 | poly clear_into; |
---|
| 2626 | int dummy_len; |
---|
| 2627 | int new_length; |
---|
| 2628 | int bp=erg.to_reduce_u;//bucket_positon |
---|
| 2629 | //kBucketClear(los[bp].bucket,&clear_into,&new_length); |
---|
| 2630 | new_length=los[bp].clear_to_poly(); |
---|
| 2631 | clear_into=los[bp].p; |
---|
| 2632 | poly p=c->strat->S[erg.reduce_by]; |
---|
| 2633 | int j=erg.reduce_by; |
---|
| 2634 | int old_length=c->strat->lenS[j];// in view of S |
---|
| 2635 | los[bp].p=p; |
---|
| 2636 | kBucketInit(los[bp].bucket,p,old_length); |
---|
| 2637 | int qal=pQuality(clear_into,c,new_length); |
---|
| 2638 | int pos_in_c=-1; |
---|
| 2639 | int z; |
---|
| 2640 | int new_pos; |
---|
| 2641 | new_pos=simple_posInS(c->strat,clear_into,qal); |
---|
| 2642 | assume(new_pos<=j); |
---|
| 2643 | for (z=c->n;z;z--) |
---|
| 2644 | { |
---|
| 2645 | if(p==c->S->m[z-1]) |
---|
| 2646 | { |
---|
| 2647 | pos_in_c=z-1; |
---|
| 2648 | break; |
---|
| 2649 | } |
---|
| 2650 | } |
---|
| 2651 | if(pos_in_c>=0) |
---|
| 2652 | { |
---|
| 2653 | c->S->m[pos_in_c]=clear_into; |
---|
| 2654 | c->lengths[pos_in_c]=new_length; |
---|
| 2655 | if (c->T_deg_full) |
---|
| 2656 | c->T_deg_full[pos_in_c]=pTotaldegree_full(clear_into); |
---|
| 2657 | c_S_element_changed_hook(pos_in_c,c); |
---|
| 2658 | } |
---|
| 2659 | c->strat->S[j]=clear_into; |
---|
| 2660 | c->strat->lenS[j]=new_length; |
---|
| 2661 | assume(pLength(clear_into)==new_length); |
---|
| 2662 | if(c->strat->lenSw) |
---|
| 2663 | c->strat->lenSw[j]=qal; |
---|
| 2664 | if (!rField_is_Zp(c->r)) |
---|
| 2665 | { |
---|
| 2666 | pContent(clear_into); |
---|
| 2667 | pCleardenom(clear_into);//should be unnecessary |
---|
| 2668 | } |
---|
| 2669 | else |
---|
| 2670 | pNorm(clear_into); |
---|
| 2671 | #ifdef FIND_DETERMINISTIC |
---|
| 2672 | erg.reduce_by=j; |
---|
| 2673 | //resort later see diploma thesis, find_in_S must be deterministic |
---|
| 2674 | //during multireduction if spolys are only in the span of the |
---|
| 2675 | //input polys |
---|
| 2676 | #else |
---|
| 2677 | |
---|
| 2678 | if (new_pos<j) |
---|
| 2679 | { |
---|
| 2680 | move_forward_in_S(j,new_pos,c->strat); |
---|
| 2681 | erg.reduce_by=new_pos; |
---|
| 2682 | } |
---|
| 2683 | #endif |
---|
| 2684 | } |
---|
| 2685 | } |
---|
| 2686 | static int fwbw(red_object* los, int i){ |
---|
| 2687 | int i2=i; |
---|
| 2688 | int step=1; |
---|
| 2689 | |
---|
| 2690 | BOOLEAN bw=FALSE; |
---|
| 2691 | BOOLEAN incr=TRUE; |
---|
| 2692 | |
---|
| 2693 | while(1) |
---|
| 2694 | { |
---|
| 2695 | if(!bw) |
---|
| 2696 | { |
---|
| 2697 | step=si_min(i2,step); |
---|
| 2698 | if (step==0) break; |
---|
| 2699 | i2-=step; |
---|
| 2700 | |
---|
| 2701 | if(!pLmEqual(los[i].p,los[i2].p)) |
---|
| 2702 | { |
---|
| 2703 | bw=TRUE; |
---|
| 2704 | incr=FALSE; |
---|
| 2705 | } |
---|
| 2706 | else |
---|
| 2707 | { |
---|
| 2708 | if ((!incr) &&(step==1)) break; |
---|
| 2709 | } |
---|
| 2710 | |
---|
| 2711 | |
---|
| 2712 | } |
---|
| 2713 | else |
---|
| 2714 | { |
---|
| 2715 | |
---|
| 2716 | step=si_min(i-i2,step); |
---|
| 2717 | if (step==0) break; |
---|
| 2718 | i2+=step; |
---|
| 2719 | if(pLmEqual(los[i].p,los[i2].p)){ |
---|
| 2720 | if(step==1) break; |
---|
| 2721 | else |
---|
| 2722 | { |
---|
| 2723 | bw=FALSE; |
---|
| 2724 | } |
---|
| 2725 | } |
---|
| 2726 | |
---|
| 2727 | } |
---|
| 2728 | if (incr) |
---|
| 2729 | step*=2; |
---|
| 2730 | else |
---|
| 2731 | { |
---|
| 2732 | if (step%2==1) |
---|
| 2733 | step=(step+1)/2; |
---|
| 2734 | else |
---|
| 2735 | step/=2; |
---|
| 2736 | |
---|
| 2737 | } |
---|
| 2738 | } |
---|
| 2739 | return i2; |
---|
| 2740 | } |
---|
[9cbb7a3] | 2741 | static void multi_reduction_find(red_object* los, int losl,slimgb_alg* c,int startf,find_erg & erg){ |
---|
[4f858ce] | 2742 | kStrategy strat=c->strat; |
---|
| 2743 | |
---|
| 2744 | assume(startf<=losl); |
---|
| 2745 | assume((startf==losl-1)||(pLmCmp(los[startf].p,los[startf+1].p)==-1)); |
---|
| 2746 | int i=startf; |
---|
| 2747 | |
---|
| 2748 | int j; |
---|
| 2749 | while(i>=0){ |
---|
| 2750 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)<=0)); |
---|
| 2751 | assume(is_valid_ro(los[i])); |
---|
| 2752 | j=kFindDivisibleByInS_easy(strat,los[i]); |
---|
| 2753 | if(j>=0){ |
---|
| 2754 | |
---|
| 2755 | erg.to_reduce_u=i; |
---|
| 2756 | erg.reduce_by=j; |
---|
| 2757 | erg.fromS=TRUE; |
---|
| 2758 | int i2=fwbw(los,i); |
---|
| 2759 | assume(pLmEqual(los[i].p,los[i2].p)); |
---|
| 2760 | assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); |
---|
| 2761 | assume(i>=i2); |
---|
| 2762 | |
---|
| 2763 | // int i2; |
---|
| 2764 | // for(i2=i-1;i2>=0;i2--){ |
---|
| 2765 | // if(!pLmEqual(los[i].p,los[i2].p)) |
---|
| 2766 | // break; |
---|
| 2767 | // } |
---|
| 2768 | |
---|
| 2769 | // erg.to_reduce_l=i2+1; |
---|
| 2770 | erg.to_reduce_l=i2; |
---|
| 2771 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 2772 | return; |
---|
| 2773 | } |
---|
| 2774 | if (j<0){ |
---|
| 2775 | |
---|
| 2776 | //not reduceable, try to use this for reducing higher terms |
---|
| 2777 | int i2=fwbw(los,i); |
---|
| 2778 | assume(pLmEqual(los[i].p,los[i2].p)); |
---|
| 2779 | assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p))); |
---|
| 2780 | assume(i>=i2); |
---|
| 2781 | if(i2!=i){ |
---|
| 2782 | |
---|
| 2783 | erg.to_reduce_u=i-1; |
---|
| 2784 | erg.to_reduce_l=i2; |
---|
| 2785 | erg.reduce_by=i; |
---|
| 2786 | erg.fromS=FALSE; |
---|
| 2787 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 2788 | return; |
---|
| 2789 | } |
---|
| 2790 | if(!(c->is_homog)) |
---|
| 2791 | { |
---|
| 2792 | |
---|
| 2793 | for (i2=i+1;i2<losl;i2++){ |
---|
| 2794 | if (p_LmShortDivisibleBy(los[i].p,los[i].sev,los[i2].p,~los[i2].sev, |
---|
| 2795 | c->r)){ |
---|
| 2796 | int i3=i2; |
---|
| 2797 | while((i3+1<losl) && (pLmEqual(los[i2].p, los[i3+1].p))) |
---|
| 2798 | i3++; |
---|
| 2799 | erg.to_reduce_u=i3; |
---|
| 2800 | erg.to_reduce_l=i2; |
---|
| 2801 | erg.reduce_by=i; |
---|
| 2802 | erg.fromS=FALSE; |
---|
| 2803 | assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1)); |
---|
| 2804 | return; |
---|
| 2805 | } |
---|
| 2806 | // else {assume(!p_LmDivisibleBy(los[i].p, los[i2].p,c->r));} |
---|
| 2807 | } |
---|
| 2808 | } |
---|
| 2809 | i--; |
---|
| 2810 | } |
---|
| 2811 | } |
---|
| 2812 | erg.reduce_by=-1;//error code |
---|
| 2813 | return; |
---|
| 2814 | } |
---|
| 2815 | |
---|
| 2816 | // nicht reduzierbare eintraege in ergebnisliste schreiben |
---|
| 2817 | // nullen loeschen |
---|
| 2818 | // while(finde_groessten leitterm reduzierbar(c,erg)){ |
---|
| 2819 | |
---|
| 2820 | static int multi_reduction_clear_zeroes(red_object* los, int losl, int l, int u) |
---|
| 2821 | { |
---|
| 2822 | |
---|
| 2823 | |
---|
| 2824 | int deleted=0; |
---|
| 2825 | int i=l; |
---|
| 2826 | int last=-1; |
---|
| 2827 | while(i<=u) |
---|
| 2828 | { |
---|
| 2829 | |
---|
| 2830 | if(los[i].p==NULL){ |
---|
| 2831 | kBucketDestroy(&los[i].bucket); |
---|
| 2832 | // delete los[i];//here we assume los are constructed with new |
---|
| 2833 | //destroy resources, must be added here |
---|
| 2834 | if (last>=0) |
---|
| 2835 | { |
---|
| 2836 | memmove(los+(int)(last+1-deleted),los+(last+1),sizeof(red_object)*(i-1-last)); |
---|
| 2837 | } |
---|
| 2838 | last=i; |
---|
| 2839 | deleted++; |
---|
| 2840 | } |
---|
| 2841 | i++; |
---|
| 2842 | } |
---|
| 2843 | if((last>=0)&&(last!=losl-1)) |
---|
| 2844 | memmove(los+(int)(last+1-deleted),los+last+1,sizeof(red_object)*(losl-1-last)); |
---|
| 2845 | return deleted; |
---|
| 2846 | |
---|
| 2847 | } |
---|
| 2848 | |
---|
[9cbb7a3] | 2849 | static void sort_region_down(red_object* los, int l, int u, slimgb_alg* c) |
---|
[4f858ce] | 2850 | { |
---|
| 2851 | qsort(los+l,u-l+1,sizeof(red_object),red_object_better_gen); |
---|
| 2852 | int i; |
---|
| 2853 | |
---|
| 2854 | for(i=l;i<=u;i++) |
---|
| 2855 | { |
---|
| 2856 | BOOLEAN moved=FALSE; |
---|
| 2857 | int j; |
---|
| 2858 | for(j=i;j;j--) |
---|
| 2859 | { |
---|
| 2860 | if(pLmCmp(los[j].p,los[j-1].p)==-1){ |
---|
| 2861 | red_object h=los[j]; |
---|
| 2862 | los[j]=los[j-1]; |
---|
| 2863 | los[j-1]=h; |
---|
| 2864 | moved=TRUE; |
---|
| 2865 | } |
---|
| 2866 | else break; |
---|
| 2867 | } |
---|
| 2868 | if(!moved) return; |
---|
| 2869 | } |
---|
| 2870 | } |
---|
| 2871 | |
---|
| 2872 | //assume that los is ordered ascending by leading term, all non zero |
---|
[9cbb7a3] | 2873 | static void multi_reduction(red_object* los, int & losl, slimgb_alg* c) |
---|
[4f858ce] | 2874 | { |
---|
| 2875 | |
---|
| 2876 | //initialize; |
---|
| 2877 | assume(c->strat->sl>=0); |
---|
| 2878 | assume(losl>0); |
---|
| 2879 | int i; |
---|
| 2880 | for(i=0;i<losl;i++){ |
---|
| 2881 | los[i].sev=pGetShortExpVector(los[i].p); |
---|
| 2882 | //SetShortExpVector(); |
---|
| 2883 | los[i].p=kBucketGetLm(los[i].bucket); |
---|
| 2884 | } |
---|
| 2885 | |
---|
| 2886 | kStrategy strat=c->strat; |
---|
| 2887 | int curr_pos=losl-1; |
---|
| 2888 | |
---|
| 2889 | |
---|
| 2890 | // nicht reduzierbare einträge in ergebnisliste schreiben |
---|
| 2891 | // nullen loeschen |
---|
| 2892 | while(curr_pos>=0){ |
---|
| 2893 | |
---|
| 2894 | find_erg erg; |
---|
| 2895 | multi_reduction_find(los, losl,c,curr_pos,erg);//last argument should be curr_pos |
---|
| 2896 | // PrintS("\n erg:\n"); |
---|
| 2897 | // Print("upper:%i\n",erg.to_reduce_u); |
---|
| 2898 | // Print("lower:%i\n",erg.to_reduce_l); |
---|
| 2899 | // Print("reduce_by:%i\n",erg.reduce_by); |
---|
| 2900 | // Print("fromS:%i\n",erg.fromS); |
---|
| 2901 | if(erg.reduce_by<0) break; |
---|
| 2902 | |
---|
| 2903 | |
---|
| 2904 | |
---|
| 2905 | erg.expand=NULL; |
---|
| 2906 | int d=erg.to_reduce_u-erg.to_reduce_l+1; |
---|
| 2907 | //if ((!erg.fromS)&&(d>100)){ |
---|
[196cdf] | 2908 | |
---|
[4f858ce] | 2909 | multi_reduction_lls_trick(los,losl,c,erg); |
---|
| 2910 | int sum=0; |
---|
| 2911 | |
---|
| 2912 | |
---|
| 2913 | int i; |
---|
| 2914 | int len; |
---|
| 2915 | // wrp(los[erg.to_reduce_u].p); |
---|
| 2916 | //Print("\n"); |
---|
| 2917 | multi_reduce_step(erg,los,c); |
---|
[196cdf] | 2918 | |
---|
[4f858ce] | 2919 | // reduction_step *rs=create_reduction_step(erg, los, c); |
---|
| 2920 | // rs->reduce(los,erg.to_reduce_l,erg.to_reduce_u); |
---|
| 2921 | // finalize_reduction_step(rs); |
---|
| 2922 | |
---|
| 2923 | int deleted=multi_reduction_clear_zeroes(los, losl, erg.to_reduce_l, erg.to_reduce_u); |
---|
| 2924 | if(erg.fromS==FALSE) |
---|
| 2925 | curr_pos=si_max(erg.to_reduce_u,erg.reduce_by); |
---|
| 2926 | else |
---|
| 2927 | curr_pos=erg.to_reduce_u; |
---|
| 2928 | losl -= deleted; |
---|
| 2929 | curr_pos -= deleted; |
---|
| 2930 | |
---|
| 2931 | //Print("deleted %i \n",deleted); |
---|
| 2932 | sort_region_down(los, erg.to_reduce_l, erg.to_reduce_u-deleted, c); |
---|
| 2933 | // sort_region_down(los, 0, losl-1, c); |
---|
| 2934 | // qsort(los,losl,sizeof(red_object),red_object_better_gen); |
---|
| 2935 | if(erg.expand) |
---|
| 2936 | { |
---|
| 2937 | #ifdef FIND_DETERMINISTIC |
---|
| 2938 | int i; |
---|
| 2939 | for(i=0;c->expandS[i];i++); |
---|
[ec8a6b6] | 2940 | c->expandS=(poly*) omrealloc(c->expandS,(i+2)*sizeof(poly)); |
---|
[4f858ce] | 2941 | c->expandS[i]=erg.expand; |
---|
| 2942 | c->expandS[i+1]=NULL; |
---|
| 2943 | #else |
---|
| 2944 | add_to_reductors(c,erg.expand,erg.expand_length); |
---|
| 2945 | #endif |
---|
| 2946 | } |
---|
| 2947 | |
---|
| 2948 | } |
---|
| 2949 | return; |
---|
| 2950 | } |
---|
| 2951 | void red_object::flatten(){ |
---|
| 2952 | assume(p==kBucketGetLm(bucket)); |
---|
| 2953 | } |
---|
| 2954 | void red_object::validate(){ |
---|
[bddc9d] | 2955 | p=kBucketGetLm(bucket); |
---|
| 2956 | if(p) |
---|
[4f858ce] | 2957 | sev=pGetShortExpVector(p); |
---|
| 2958 | } |
---|
| 2959 | int red_object::clear_to_poly(){ |
---|
| 2960 | flatten(); |
---|
| 2961 | int l; |
---|
| 2962 | kBucketClear(bucket,&p,&l); |
---|
| 2963 | return l; |
---|
| 2964 | } |
---|
| 2965 | |
---|
| 2966 | |
---|
| 2967 | |
---|
| 2968 | |
---|
| 2969 | |
---|
| 2970 | void reduction_step::reduce(red_object* r, int l, int u){} |
---|
| 2971 | void simple_reducer::target_is_no_sum_reduce(red_object & ro){ |
---|
| 2972 | kBucketPolyRed(ro.bucket,p, |
---|
| 2973 | p_len, |
---|
| 2974 | c->strat->kNoether); |
---|
| 2975 | } |
---|
| 2976 | |
---|
[bddc9d] | 2977 | |
---|
[4f858ce] | 2978 | void simple_reducer::reduce(red_object* r, int l, int u){ |
---|
| 2979 | this->pre_reduce(r,l,u); |
---|
| 2980 | int i; |
---|
| 2981 | //debug start |
---|
| 2982 | int im; |
---|
| 2983 | // for(im=l;im<=u;im++) |
---|
| 2984 | // assume(is_valid_ro(r[im])); |
---|
| 2985 | |
---|
| 2986 | |
---|
| 2987 | //debug end |
---|
| 2988 | |
---|
| 2989 | for(i=l;i<=u;i++){ |
---|
| 2990 | |
---|
| 2991 | |
---|
| 2992 | |
---|
[bddc9d] | 2993 | this->target_is_no_sum_reduce(r[i]); |
---|
[4f858ce] | 2994 | |
---|
| 2995 | } |
---|
| 2996 | for(i=l;i<=u;i++){ |
---|
| 2997 | r[i].validate(); |
---|
| 2998 | #ifdef TGB_DEBUG |
---|
| 2999 | #endif |
---|
[bddc9d] | 3000 | } |
---|
[4f858ce] | 3001 | } |
---|
| 3002 | reduction_step::~reduction_step(){} |
---|
| 3003 | simple_reducer::~simple_reducer(){ |
---|
| 3004 | if(fill_back!=NULL) |
---|
| 3005 | { |
---|
| 3006 | kBucketInit(fill_back,p,p_len); |
---|
| 3007 | } |
---|
| 3008 | fill_back=NULL; |
---|
| 3009 | |
---|
| 3010 | } |
---|
[36b1aa] | 3011 | |
---|
[9cbb7a3] | 3012 | void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c){ |
---|
[4f858ce] | 3013 | static int id=0; |
---|
| 3014 | id++; |
---|
| 3015 | |
---|
| 3016 | int rn=erg.reduce_by; |
---|
| 3017 | poly red; |
---|
| 3018 | int red_len; |
---|
| 3019 | simple_reducer* pointer; |
---|
[27e091b] | 3020 | BOOLEAN work_on_copy=FALSE; |
---|
[4f858ce] | 3021 | if(erg.fromS){ |
---|
| 3022 | red=c->strat->S[rn]; |
---|
| 3023 | red_len=c->strat->lenS[rn]; |
---|
| 3024 | assume(red_len==pLength(red)); |
---|
| 3025 | } |
---|
| 3026 | else |
---|
| 3027 | { |
---|
| 3028 | r[rn].flatten(); |
---|
| 3029 | kBucketClear(r[rn].bucket,&red,&red_len); |
---|
| 3030 | if (!rField_is_Zp(c->r)) |
---|
| 3031 | { |
---|
| 3032 | pContent(red); |
---|
| 3033 | pCleardenom(red);//should be unnecessary |
---|
| 3034 | |
---|
| 3035 | } |
---|
| 3036 | pNormalize(red); |
---|
| 3037 | red_len=pLength(red); |
---|
| 3038 | } |
---|
| 3039 | if (erg.to_reduce_u-erg.to_reduce_l>5){ |
---|
[27e091b] | 3040 | work_on_copy=TRUE; |
---|
[4f858ce] | 3041 | // poly m=pOne(); |
---|
| 3042 | poly m=c->tmp_lm; |
---|
| 3043 | pSetCoeff(m,nInit(1)); |
---|
| 3044 | for(int i=1;i<=pVariables;i++) |
---|
| 3045 | pSetExp(m,i,(pGetExp(r[erg.to_reduce_l].p, i)-pGetExp(red,i))); |
---|
| 3046 | pSetm(m); |
---|
| 3047 | poly red_cp=ppMult_mm(red,m); |
---|
| 3048 | |
---|
| 3049 | if(!erg.fromS){ |
---|
| 3050 | kBucketInit(r[rn].bucket,red,red_len); |
---|
| 3051 | } |
---|
| 3052 | //now reduce the copy |
---|
[9cbb7a3] | 3053 | //static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n) |
---|
[4f858ce] | 3054 | redTailShort(red_cp,c->strat); |
---|
| 3055 | //number mul; |
---|
| 3056 | // red_len--; |
---|
| 3057 | // red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length); |
---|
| 3058 | // pSetCoeff(red_cp,nMult(red_cp->coef,mul)); |
---|
| 3059 | // nDelete(&mul); |
---|
| 3060 | // red_len++; |
---|
| 3061 | red=red_cp; |
---|
| 3062 | red_len=pLength(red); |
---|
| 3063 | // pDelete(&m); |
---|
| 3064 | |
---|
| 3065 | } |
---|
| 3066 | int i; |
---|
| 3067 | |
---|
| 3068 | |
---|
[27e091b] | 3069 | |
---|
[4f858ce] | 3070 | assume(red_len==pLength(red)); |
---|
[36b1aa] | 3071 | |
---|
| 3072 | pointer=new simple_reducer(red,red_len,c); |
---|
[4f858ce] | 3073 | |
---|
[27e091b] | 3074 | if ((!work_on_copy) && (!erg.fromS)) |
---|
[4f858ce] | 3075 | pointer->fill_back=r[rn].bucket; |
---|
| 3076 | else |
---|
| 3077 | pointer->fill_back=NULL; |
---|
| 3078 | pointer->reduction_id=id; |
---|
| 3079 | pointer->c=c; |
---|
| 3080 | |
---|
| 3081 | pointer->reduce(r,erg.to_reduce_l, erg.to_reduce_u); |
---|
[27e091b] | 3082 | if(work_on_copy) pDelete(&pointer->p); |
---|
[4f858ce] | 3083 | delete pointer; |
---|
| 3084 | |
---|
| 3085 | }; |
---|
| 3086 | |
---|
| 3087 | |
---|
| 3088 | |
---|
[bddc9d] | 3089 | |
---|
[4f858ce] | 3090 | void simple_reducer:: pre_reduce(red_object* r, int l, int u){} |
---|
[36b1aa] | 3091 | |
---|