Changeset d231ed in git
- Timestamp:
- Apr 11, 2011, 8:05:34 PM (13 years ago)
- Branches:
- (u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38077648e7239f98078663eb941c3c979511150a')
- Children:
- 4a40cb0d0ee918e78d0eb4e649077aa8b8174e55
- Parents:
- 4a7c16db46749a1ff4d60c3e2bec50c2b0df1b6c
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/tgb.cc
r4a7c16 rd231ed 1541 1541 if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm)) 1542 1542 { 1543 break;1543 break; 1544 1544 } 1545 1545 if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c)) … … 2865 2865 omfree(si_array); 2866 2866 } 2867 slimgb_alg::slimgb_alg(ideal I, int s syz_comp,BOOLEAN F4,int ddeg_pos)2868 { 2869 this->deg_pos=d deg_pos;2867 slimgb_alg::slimgb_alg(ideal I, int syz_comp,BOOLEAN F4,int deg_pos) 2868 { 2869 this->deg_pos=deg_pos; 2870 2870 lastCleanedDeg=-1; 2871 2871 completed=FALSE; … … 3003 3003 poly* array_arg=I->m; 3004 3004 array_arg++; 3005 introduceDelayedPairs(array_arg,n n-1);3005 introduceDelayedPairs(array_arg,n-1); 3006 3006 /* 3007 for (i=1;i<n n;i++)//the 1 is wanted, because first element is added to basis3007 for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis 3008 3008 { 3009 3009 // add_to_basis(I->m[i],-1,-1,c); … … 3022 3022 apairs[nn-i-1]=si; 3023 3023 ++(pair_top); 3024 }*/ 3024 } 3025 */ 3025 3026 } 3026 3027 else … … 3068 3069 } 3069 3070 } 3070 3071 3071 free_sorted_pair_node(s,r); 3072 3072 apairs[piter]=NULL; … … 3151 3151 // initsevS(i); 3152 3152 omFree(c->strat->S_2_R); 3153 3154 3153 omFree(c->strat->lenS); 3155 3154 … … 3168 3167 //Print("calculated %d NFs\n",c->normal_forms); 3169 3168 Print("\nNF:%i product criterion:%i, ext_product criterion:%i \n", c->normal_forms, c->easy_product_crit, c->extended_product_crit); 3170 3171 3172 3169 } 3173 3170 int deleted_form_c_s=0; … … 3239 3236 delete c->strat; 3240 3237 } 3241 ideal t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode){ 3242 3243 assume(r==currRing); 3244 ring orig_ring=r; 3245 int pos; 3246 ring new_ring=rAssure_TDeg(orig_ring,1,rVar(orig_ring),pos); 3247 3248 3249 ideal s_h; 3250 if (orig_ring != new_ring) 3251 { 3252 rChangeCurrRing(new_ring); 3253 s_h=idrCopyR_NoSort(arg_I,orig_ring); 3254 idTest(s_h); 3255 /*int i; 3256 3257 for(i=0;i<IDELEMS(s_h);i++){ 3258 poly p=s_h->m[i]; 3259 while(p){ 3238 ideal t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode) 3239 { 3240 assume(r==currRing); 3241 ring orig_ring=r; 3242 int pos; 3243 ring new_ring=rAssure_TDeg(orig_ring,1,rVar(orig_ring),pos); 3244 3245 ideal s_h; 3246 if (orig_ring != new_ring) 3247 { 3248 rChangeCurrRing(new_ring); 3249 s_h=idrCopyR_NoSort(arg_I,orig_ring); 3250 idTest(s_h); 3251 /*int i; 3252 3253 for(i=0;i<IDELEMS(s_h);i++) 3254 { 3255 poly p=s_h->m[i]; 3256 while(p) 3257 { 3260 3258 p_Setm(p,new_ring); 3261 3259 pIter(p); 3262 } 3263 }*/ 3264 } 3265 else 3266 { 3267 s_h = id_Copy(arg_I,orig_ring); 3268 } 3269 3270 ideal s_result=do_t_rep_gb(new_ring,s_h,syz_comp,F4_mode,pos); 3271 ideal result; 3272 if(orig_ring != new_ring) 3273 { 3274 3275 idTest(s_result); 3276 rChangeCurrRing(orig_ring); 3277 result = idrMoveR_NoSort(s_result, new_ring); 3278 3279 idTest(result); 3280 //rChangeCurrRing(new_ring); 3281 rKill(new_ring); 3282 //rChangeCurrRing(orig_ring); 3283 } 3284 else 3285 result=s_result; 3260 } 3261 } 3262 */ 3263 } 3264 else 3265 { 3266 s_h = id_Copy(arg_I,orig_ring); 3267 } 3268 3269 ideal s_result=do_t_rep_gb(new_ring,s_h,syz_comp,F4_mode,pos); 3270 ideal result; 3271 if(orig_ring != new_ring) 3272 { 3273 idTest(s_result); 3274 rChangeCurrRing(orig_ring); 3275 result = idrMoveR_NoSort(s_result, new_ring); 3276 3286 3277 idTest(result); 3287 return result; 3288 } 3289 3290 3278 //rChangeCurrRing(new_ring); 3279 rKill(new_ring); 3280 //rChangeCurrRing(orig_ring); 3281 } 3282 else 3283 result=s_result; 3284 idTest(result); 3285 return result; 3286 } 3291 3287 3292 3288 ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos){ 3293 3294 3289 // Print("QlogSize(0) %d, QlogSize(1) %d,QlogSize(-2) %d, QlogSize(5) %d\n", QlogSize(nlInit(0)),QlogSize(nlInit(1)),QlogSize(nlInit(-2)),QlogSize(nlInit(5))); 3295 3290 … … 3311 3306 } 3312 3307 3313 3314 3308 qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit); 3315 3309 //Print("Idelems %i \n----------\n",IDELEMS(I)); … … 3318 3312 slimgb_alg* c=new slimgb_alg(I, syz_comp,F4_mode,deg_pos); 3319 3313 3320 3321 3314 while ((c->pair_top>=0) && ((!(TEST_OPT_DEGBOUND)) || (c->apairs[c->pair_top]->deg<=Kstd1_deg))) 3322 3315 { … … 3324 3317 if(F4_mode) 3325 3318 go_on_F4(c); 3326 3327 3319 else 3328 3320 #endif … … 3344 3336 return(I); 3345 3337 } 3346 void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c){ 3338 void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c) 3339 { 3347 3340 int i,j; 3348 if (arg_i==arg_j){ 3341 if (arg_i==arg_j) 3342 { 3349 3343 return; 3350 3344 } 3351 if (arg_i>arg_j){ 3345 if (arg_i>arg_j) 3346 { 3352 3347 i=arg_j; 3353 3348 j=arg_i; 3354 } else { 3349 } 3350 else 3351 { 3355 3352 i=arg_i; 3356 3353 j=arg_j; … … 3359 3356 } 3360 3357 3361 static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state){ 3358 static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state) 3359 { 3362 3360 assume(0<=arg_i); 3363 3361 assume(0<=arg_j); … … 3371 3369 { 3372 3370 return (state->states[arg_i][arg_j]==HASTREP); 3373 } else 3371 } 3372 else 3374 3373 { 3375 3374 return (state->states[arg_j][arg_i]==HASTREP); … … 3385 3384 } 3386 3385 return n; 3387 3388 } 3389 3390 3386 } 3391 3387 3392 3388 static void shorten_tails(slimgb_alg* c, poly monom) … … 3397 3393 { 3398 3394 //enter tail 3399 3400 3395 if (c->S->m[i]==NULL) continue; 3401 3396 poly tail=c->S->m[i]->next; … … 3457 3452 } 3458 3453 } 3459 static sorted_pair_node* pop_pair(slimgb_alg* c){ 3454 static sorted_pair_node* pop_pair(slimgb_alg* c) 3455 { 3460 3456 clean_top_of_pair_list(c); 3461 3457 … … 3463 3459 else return (c->apairs[c->pair_top--]); 3464 3460 } 3465 void slimgb_alg::cleanDegs(int lower, int upper){ 3461 void slimgb_alg::cleanDegs(int lower, int upper) 3462 { 3466 3463 assume(is_homog); 3467 3464 int deg; 3468 if (TEST_OPT_PROT){ 3465 if (TEST_OPT_PROT) 3466 { 3469 3467 PrintS("C"); 3470 3468 } 3471 for(deg=lower;deg<=upper;deg++){ 3469 for(deg=lower;deg<=upper;deg++) 3470 { 3472 3471 int i; 3473 for(i=0;i<n;i++){ 3474 if (T_deg[i]==deg){ 3475 poly h; 3476 h=S->m[i]; 3477 h=redNFTail(h,strat->sl,strat,lengths[i]); 3478 if (!rField_is_Zp(r)) 3472 for(i=0;i<n;i++) 3473 { 3474 if (T_deg[i]==deg) 3475 { 3476 poly h; 3477 h=S->m[i]; 3478 h=redNFTail(h,strat->sl,strat,lengths[i]); 3479 if (!rField_is_Zp(r)) 3480 { 3481 p_Cleardenom(h,r); 3482 //p_Content(h,r); 3483 } 3484 else pNorm(h); 3485 //TODO:GCD of TERMS 3486 poly got=::gcd_of_terms(h,r); 3487 p_Delete(&gcd_of_terms[i],r); 3488 gcd_of_terms[i]=got; 3489 int len=pLength(h); 3490 wlen_type wlen=pQuality(h,this,len); 3491 if (weighted_lengths) 3492 weighted_lengths[i]=wlen; 3493 lengths[i]=len; 3494 assume(h==S->m[i]); 3495 int j; 3496 for(j=0;j<=strat->sl;j++) 3497 { 3498 if (h==strat->S[j]) 3479 3499 { 3480 p_Cleardenom(h,r); 3481 //p_Content(h,r); 3482 3483 } 3484 else pNorm(h); 3485 //TODO:GCD of TERMS 3486 poly got=::gcd_of_terms(h,r); 3487 p_Delete(&gcd_of_terms[i],r); 3488 gcd_of_terms[i]=got; 3489 int len=pLength(h); 3490 wlen_type wlen=pQuality(h,this,len); 3491 if (weighted_lengths) 3492 weighted_lengths[i]=wlen; 3493 lengths[i]=len; 3494 assume(h==S->m[i]); 3495 int j; 3496 for(j=0;j<=strat->sl;j++){ 3497 if (h==strat->S[j]){ 3498 int new_pos=simple_posInS(strat, h,len, wlen); 3499 if (strat->lenS){ 3500 strat->lenS[j]=len; 3501 } 3502 if (strat->lenSw){ 3503 strat->lenSw[j]=wlen; 3504 } 3505 if (new_pos<j){ 3506 move_forward_in_S(j,new_pos,strat); 3507 }else{ 3508 if (new_pos>j) 3509 new_pos=new_pos-1;//is identical with one element 3510 if (new_pos>j) 3511 move_backward_in_S(j,new_pos,strat); 3512 } 3513 break; 3500 int new_pos=simple_posInS(strat, h,len, wlen); 3501 if (strat->lenS) 3502 { 3503 strat->lenS[j]=len; 3514 3504 } 3505 if (strat->lenSw) 3506 { 3507 strat->lenSw[j]=wlen; 3508 } 3509 if (new_pos<j) 3510 { 3511 move_forward_in_S(j,new_pos,strat); 3512 } 3513 else 3514 { 3515 if (new_pos>j) 3516 new_pos=new_pos-1;//is identical with one element 3517 if (new_pos>j) 3518 move_backward_in_S(j,new_pos,strat); 3519 } 3520 break; 3515 3521 } 3516 3522 } 3517 3518 } 3519 3523 } 3524 } 3520 3525 } 3521 3526 { 3522 3527 int i,j; 3523 for(i=0;i<this->n;i++){ 3524 for(j=0;j<i;j++){ 3525 if (T_deg[i]+T_deg[j]<=upper){ 3528 for(i=0;i<this->n;i++) 3529 { 3530 for(j=0;j<i;j++) 3531 { 3532 if (T_deg[i]+T_deg[j]<=upper) 3533 { 3526 3534 now_t_rep(i,j,this); 3527 3535 } … … 3532 3540 //TODO mark pairs 3533 3541 } 3534 sorted_pair_node* top_pair(slimgb_alg* c){ 3535 while(c->pair_top>=0){ 3542 sorted_pair_node* top_pair(slimgb_alg* c) 3543 { 3544 while(c->pair_top>=0) 3545 { 3536 3546 super_clean_top_of_pair_list(c);//yeah, I know, it's odd that I use a different proc here 3537 if ((c->is_homog)&&(c->pair_top>=0)&&(c->apairs[c->pair_top]->deg>=c->lastCleanedDeg+2)){ 3547 if ((c->is_homog)&&(c->pair_top>=0)&&(c->apairs[c->pair_top]->deg>=c->lastCleanedDeg+2)) 3548 { 3538 3549 int upper=c->apairs[c->pair_top]->deg-1; 3539 3550 c->cleanDegs(c->lastCleanedDeg+1,upper); 3540 3551 c->lastCleanedDeg=upper; 3541 } else{ 3552 } 3553 else 3554 { 3542 3555 break; 3543 3556 } 3544 3545 } 3546 3547 3557 } 3548 3558 if(c->pair_top<0) return NULL; 3549 3559 else return (c->apairs[c->pair_top]); 3550 3560 } 3551 sorted_pair_node* quick_pop_pair(slimgb_alg* c){ 3561 sorted_pair_node* quick_pop_pair(slimgb_alg* c) 3562 { 3552 3563 if(c->pair_top<0) return NULL; 3553 3564 else return (c->apairs[c->pair_top--]); 3554 3565 } 3555 3566 3556 3557 3558 static void super_clean_top_of_pair_list(slimgb_alg* c){ 3567 static void super_clean_top_of_pair_list(slimgb_alg* c) 3568 { 3559 3569 while((c->pair_top>=0) 3560 3570 && (c->apairs[c->pair_top]->i>=0) 3561 3571 && (good_has_t_rep(c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))) 3562 3572 { 3563 3564 3573 free_sorted_pair_node(c->apairs[c->pair_top],c->r); 3565 3574 c->pair_top--; 3566 3567 3568 } 3569 void clean_top_of_pair_list(slimgb_alg* c){3570 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))) {3571 3575 } 3576 } 3577 void clean_top_of_pair_list(slimgb_alg* c) 3578 { 3579 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))) 3580 { 3572 3581 free_sorted_pair_node(c->apairs[c->pair_top],c->r); 3573 3582 c->pair_top--; 3574 3575 3576 } 3577 static BOOLEAN state_is(calc_state state, const int & arg_i, const int & arg_j, slimgb_alg* c){3583 } 3584 } 3585 static BOOLEAN state_is(calc_state state, const int & arg_i, const int & arg_j, slimgb_alg* c) 3586 { 3578 3587 assume(0<=arg_i); 3579 3588 assume(0<=arg_j); … … 3591 3600 } 3592 3601 3593 3594 void free_sorted_pair_node(sorted_pair_node* s, ring r){3602 void free_sorted_pair_node(sorted_pair_node* s, ring r) 3603 { 3595 3604 if (s->i>=0) 3596 3605 p_Delete(&s->lcm_of_lm,r); 3597 3606 omfree(s); 3598 3607 } 3599 static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c){ 3608 static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c) 3609 { 3600 3610 if (a->deg<b->deg) return TRUE; 3601 3611 if (a->deg>b->deg) return FALSE; 3602 3603 3612 3604 3613 int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); … … 3614 3623 } 3615 3624 3616 static int tgb_pair_better_gen(const void* ap,const void* bp) {3617 3625 static int tgb_pair_better_gen(const void* ap,const void* bp) 3626 { 3618 3627 sorted_pair_node* a=*((sorted_pair_node**)ap); 3619 3628 sorted_pair_node* b=*((sorted_pair_node**)bp); … … 3623 3632 if (a->deg>b->deg) return 1; 3624 3633 3625 3626 3627 int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); 3634 int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm); 3628 3635 3629 3636 if (comp==1) return 1; 3630 3637 if (-1==comp) return -1; 3631 3638 if (a->expected_length<b->expected_length) return -1; 3632 3639 if (a->expected_length>b->expected_length) return 1; 3633 3640 if (a->i+a->j<b->i+b->j) return -1; 3634 3641 if (a->i+a->j>b->i+b->j) return 1; 3635 3642 if (a->i<b->i) return -1; 3636 3643 if (a->i>b->i) return 1; 3637 3644 return 0; 3638 3645 } 3639 3646 3640 3641 static poly gcd_of_terms(poly p, ring r){3647 static poly gcd_of_terms(poly p, ring r) 3648 { 3642 3649 int max_g_0=0; 3643 3650 assume(p!=NULL); … … 3647 3654 for (i=pVariables; i; i--) 3648 3655 { 3649 pSetExp(m,i, pGetExp(p,i)); 3650 if (max_g_0==0) 3651 if (pGetExp(m,i)>0) 3652 max_g_0=i; 3653 } 3654 3656 pSetExp(m,i, pGetExp(p,i)); 3657 if (max_g_0==0) 3658 if (pGetExp(m,i)>0) 3659 max_g_0=i; 3660 } 3655 3661 t=p->next; 3656 while (t!=NULL) {3657 3662 while (t!=NULL) 3663 { 3658 3664 if (max_g_0==0) break; 3659 3665 for (i=max_g_0; i; i--) … … 3661 3667 pSetExp(m,i, si_min(pGetExp(t,i),pGetExp(m,i))); 3662 3668 if (max_g_0==i) 3663 if (pGetExp(m,i)==0) 3664 max_g_0=0; 3665 if ((max_g_0==0) && (pGetExp(m,i)>0)){ 3666 max_g_0=i; 3669 if (pGetExp(m,i)==0) 3670 max_g_0=0; 3671 if ((max_g_0==0) && (pGetExp(m,i)>0)) 3672 { 3673 max_g_0=i; 3667 3674 } 3668 3675 } … … 3677 3684 static inline BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m) 3678 3685 { 3679 3680 3686 if (pGetComp(p1) > 0 || pGetComp(p2) > 0) 3681 3687 return FALSE; … … 3691 3697 3692 3698 //for impl reasons may return false if the the normal product criterion matches 3693 static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c){ 3699 static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c) 3700 { 3694 3701 if (c->nc) 3695 3702 return FALSE; 3696 3703 if(gcd1==NULL) return FALSE; 3697 3698 3699 3700 3701 3702 3703 3704 3705 3704 if(gcd2==NULL) return FALSE; 3705 gcd1->next=gcd2; //may ordered incorrect 3706 poly m=gcd_of_terms(gcd1,c->r); 3707 gcd1->next=NULL; 3708 if (m==NULL) return FALSE; 3709 3710 BOOLEAN erg=pHasNotCFExtended(p1,p2,m); 3711 pDelete(&m); 3712 return erg; 3706 3713 } 3707 3714 static poly kBucketGcd(kBucket* b, ring r) … … 3713 3720 for (i=MAX_BUCKET-1;i>=0;i--) 3714 3721 { 3715 if (b->buckets[i]!=NULL){ 3716 if (!initialized){ 3717 m=gcd_of_terms(b->buckets[i],r); 3718 initialized=TRUE; 3719 if (m==NULL) return NULL; 3722 if (b->buckets[i]!=NULL) 3723 { 3724 if (!initialized) 3725 { 3726 m=gcd_of_terms(b->buckets[i],r); 3727 initialized=TRUE; 3728 if (m==NULL) return NULL; 3720 3729 } 3721 3730 else 3722 {3723 n=gcd_of_terms(b->buckets[i],r);3724 if (n==NULL) {3725 pDelete(&m);3726 return NULL;3727 }3728 n->next=m;3729 poly t=gcd_of_terms(n,r);3730 n->next=NULL;3731 pDelete(&m);3732 pDelete(&n);3733 m=t;3734 if (m==NULL) return NULL;3735 3736 }3731 { 3732 n=gcd_of_terms(b->buckets[i],r); 3733 if (n==NULL) 3734 { 3735 pDelete(&m); 3736 return NULL; 3737 } 3738 n->next=m; 3739 poly t=gcd_of_terms(n,r); 3740 n->next=NULL; 3741 pDelete(&m); 3742 pDelete(&n); 3743 m=t; 3744 if (m==NULL) return NULL; 3745 } 3737 3746 } 3738 3747 } … … 3740 3749 } 3741 3750 3742 3743 3744 3745 static inline wlen_type quality_of_pos_in_strat_S(int pos, slimgb_alg* c){ 3751 static inline wlen_type quality_of_pos_in_strat_S(int pos, slimgb_alg* c) 3752 { 3746 3753 if (c->strat->lenSw!=NULL) return c->strat->lenSw[pos]; 3747 3754 return c->strat->lenS[pos]; … … 3761 3768 #endif 3762 3769 3763 static void multi_reduction_lls_trick(red_object* los, int losl,slimgb_alg* c,find_erg & erg){ 3770 static void multi_reduction_lls_trick(red_object* los, int losl,slimgb_alg* c,find_erg & erg) 3771 { 3764 3772 erg.expand=NULL; 3765 3773 BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS 3766 if(erg.fromS){ 3774 if(erg.fromS) 3775 { 3767 3776 if(pLmEqual(c->strat->S[erg.reduce_by],los[erg.to_reduce_u].p)) 3768 3777 { … … 3778 3787 } 3779 3788 } 3780 if(best!=erg.to_reduce_u+1){*/ 3789 if(best!=erg.to_reduce_u+1){ 3790 */ 3781 3791 wlen_type qc; 3782 3792 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3783 if(qc<quality_a){ 3784 los[best].flatten(); 3785 int b_pos=kBucketCanonicalize(los[best].bucket); 3786 los[best].p=los[best].bucket->buckets[b_pos]; 3787 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3788 if(qc<quality_a){ 3789 red_object h=los[erg.to_reduce_u]; 3790 los[erg.to_reduce_u]=los[best]; 3791 los[best]=h; 3792 swap_roles=TRUE; 3793 } 3794 else 3795 swap_roles=FALSE; 3796 } 3797 else{ 3798 3799 swap_roles=FALSE; 3800 } 3801 3802 } 3803 else 3804 { 3805 if (erg.to_reduce_u>erg.to_reduce_l){ 3806 3807 int i; 3808 wlen_type quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); 3809 #ifdef HAVE_PLURAL 3810 if ((c->nc) && (!(rIsSCA(c->r)))) 3811 quality_a=quality_of_pos_in_strat_S_mult_high(erg.reduce_by, los[erg.to_reduce_u].p, c); 3812 #endif 3813 int best=erg.to_reduce_u+1; 3814 wlen_type qc; 3815 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3816 assume(qc==los[best].guess_quality(c)); 3817 if(qc<quality_a){ 3818 los[best].flatten(); 3819 int b_pos=kBucketCanonicalize(los[best].bucket); 3820 los[best].p=los[best].bucket->buckets[b_pos]; 3821 qc==pQuality(los[best].bucket->buckets[b_pos],c); 3822 //(best!=erg.to_reduce_u+1) 3823 if(qc<quality_a){ 3824 red_object h=los[erg.to_reduce_u]; 3825 los[erg.to_reduce_u]=los[best]; 3826 los[best]=h; 3827 erg.reduce_by=erg.to_reduce_u; 3828 erg.fromS=FALSE; 3829 erg.to_reduce_u--; 3830 } 3831 } 3793 if(qc<quality_a) 3794 { 3795 los[best].flatten(); 3796 int b_pos=kBucketCanonicalize(los[best].bucket); 3797 los[best].p=los[best].bucket->buckets[b_pos]; 3798 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3799 if(qc<quality_a) 3800 { 3801 red_object h=los[erg.to_reduce_u]; 3802 los[erg.to_reduce_u]=los[best]; 3803 los[best]=h; 3804 swap_roles=TRUE; 3805 } 3806 else 3807 swap_roles=FALSE; 3832 3808 } 3833 3809 else 3834 3810 { 3835 assume(erg.to_reduce_u==erg.to_reduce_l); 3836 wlen_type quality_a= 3837 quality_of_pos_in_strat_S(erg.reduce_by,c); 3838 wlen_type qc=los[erg.to_reduce_u].guess_quality(c); 3839 if (qc<0) PrintS("Wrong wlen_type"); 3840 if(qc<quality_a){ 3841 int best=erg.to_reduce_u; 3842 los[best].flatten(); 3843 int b_pos=kBucketCanonicalize(los[best].bucket); 3844 los[best].p=los[best].bucket->buckets[b_pos]; 3845 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3846 assume(qc>=0); 3847 if(qc<quality_a){ 3848 BOOLEAN exp=FALSE; 3849 if(qc<=2){ 3850 //Print("\n qc is %lld \n",qc); 3851 exp=TRUE; 3852 } 3853 3854 else { 3855 if (qc<quality_a/2) 3856 exp=TRUE; 3857 else 3858 if(erg.reduce_by<c->n/4) 3859 exp=TRUE; 3860 } 3861 if (exp){ 3862 poly clear_into; 3863 los[erg.to_reduce_u].flatten(); 3864 kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); 3865 erg.expand=pCopy(clear_into); 3866 kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); 3867 if (TEST_OPT_PROT) 3868 PrintS("e"); 3869 3870 } 3871 } 3872 } 3873 3874 3875 } 3876 3877 swap_roles=FALSE; 3878 return; 3879 } 3880 3881 } 3882 else{ 3883 if(erg.reduce_by>erg.to_reduce_u){ 3884 //then lm(rb)>= lm(tru) so = 3885 assume(erg.reduce_by==erg.to_reduce_u+1); 3886 int best=erg.reduce_by; 3887 wlen_type quality_a=los[erg.reduce_by].guess_quality(c); 3888 wlen_type qc; 3889 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3890 3891 int i; 3892 if(qc<quality_a){ 3893 red_object h=los[erg.reduce_by]; 3894 los[erg.reduce_by]=los[best]; 3895 los[best]=h; 3896 } 3897 swap_roles=FALSE; 3898 return; 3899 3900 3811 swap_roles=FALSE; 3812 } 3901 3813 } 3902 3814 else 3903 3815 { 3904 assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); 3905 assume(erg.to_reduce_u==erg.to_reduce_l); 3906 //further assume, that reduce_by is the above all other polys 3907 //with same leading term 3908 int il=erg.reduce_by; 3909 wlen_type quality_a =los[erg.reduce_by].guess_quality(c); 3910 wlen_type qc; 3911 while((il>0) && pLmEqual(los[il-1].p,los[il].p)){ 3912 il--; 3913 qc=los[il].guess_quality(c); 3914 if (qc<quality_a){ 3915 quality_a=qc; 3916 erg.reduce_by=il; 3917 } 3918 } 3919 swap_roles=FALSE; 3920 } 3921 3922 } 3923 if(swap_roles) 3924 { 3925 if (TEST_OPT_PROT) 3926 PrintS("b"); 3927 poly clear_into; 3928 int dummy_len; 3929 int new_length; 3930 int bp=erg.to_reduce_u;//bucket_positon 3931 //kBucketClear(los[bp].bucket,&clear_into,&new_length); 3932 new_length=los[bp].clear_to_poly(); 3933 clear_into=los[bp].p; 3934 poly p=c->strat->S[erg.reduce_by]; 3935 int j=erg.reduce_by; 3936 int old_length=c->strat->lenS[j];// in view of S 3937 los[bp].p=p; 3938 if (c->eliminationProblem){ 3816 if (erg.to_reduce_u>erg.to_reduce_l) 3817 { 3818 int i; 3819 wlen_type quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c); 3820 #ifdef HAVE_PLURAL 3821 if ((c->nc) && (!(rIsSCA(c->r)))) 3822 quality_a=quality_of_pos_in_strat_S_mult_high(erg.reduce_by, los[erg.to_reduce_u].p, c); 3823 #endif 3824 int best=erg.to_reduce_u+1; 3825 wlen_type qc; 3826 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3827 assume(qc==los[best].guess_quality(c)); 3828 if(qc<quality_a) 3829 { 3830 los[best].flatten(); 3831 int b_pos=kBucketCanonicalize(los[best].bucket); 3832 los[best].p=los[best].bucket->buckets[b_pos]; 3833 qc==pQuality(los[best].bucket->buckets[b_pos],c); 3834 //(best!=erg.to_reduce_u+1) 3835 if(qc<quality_a) 3836 { 3837 red_object h=los[erg.to_reduce_u]; 3838 los[erg.to_reduce_u]=los[best]; 3839 los[best]=h; 3840 erg.reduce_by=erg.to_reduce_u; 3841 erg.fromS=FALSE; 3842 erg.to_reduce_u--; 3843 } 3844 } 3845 } 3846 else 3847 { 3848 assume(erg.to_reduce_u==erg.to_reduce_l); 3849 wlen_type quality_a= 3850 quality_of_pos_in_strat_S(erg.reduce_by,c); 3851 wlen_type qc=los[erg.to_reduce_u].guess_quality(c); 3852 if (qc<0) PrintS("Wrong wlen_type"); 3853 if(qc<quality_a) 3854 { 3855 int best=erg.to_reduce_u; 3856 los[best].flatten(); 3857 int b_pos=kBucketCanonicalize(los[best].bucket); 3858 los[best].p=los[best].bucket->buckets[b_pos]; 3859 qc=pQuality(los[best].bucket->buckets[b_pos],c); 3860 assume(qc>=0); 3861 if(qc<quality_a) 3862 { 3863 BOOLEAN exp=FALSE; 3864 if(qc<=2) 3865 { 3866 //Print("\n qc is %lld \n",qc); 3867 exp=TRUE; 3868 } 3869 else 3870 { 3871 if (qc<quality_a/2) 3872 exp=TRUE; 3873 else 3874 if(erg.reduce_by<c->n/4) 3875 exp=TRUE; 3876 } 3877 if (exp) 3878 { 3879 poly clear_into; 3880 los[erg.to_reduce_u].flatten(); 3881 kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length); 3882 erg.expand=pCopy(clear_into); 3883 kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length); 3884 if (TEST_OPT_PROT) PrintS("e"); 3885 } 3886 } 3887 } 3888 } 3889 swap_roles=FALSE; 3890 return; 3891 } 3892 } 3893 else 3894 { 3895 if(erg.reduce_by>erg.to_reduce_u) 3896 { 3897 //then lm(rb)>= lm(tru) so = 3898 assume(erg.reduce_by==erg.to_reduce_u+1); 3899 int best=erg.reduce_by; 3900 wlen_type quality_a=los[erg.reduce_by].guess_quality(c); 3901 wlen_type qc; 3902 best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c); 3903 3904 int i; 3905 if(qc<quality_a) 3906 { 3907 red_object h=los[erg.reduce_by]; 3908 los[erg.reduce_by]=los[best]; 3909 los[best]=h; 3910 } 3911 swap_roles=FALSE; 3912 return; 3913 } 3914 else 3915 { 3916 assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p)); 3917 assume(erg.to_reduce_u==erg.to_reduce_l); 3918 //further assume, that reduce_by is the above all other polys 3919 //with same leading term 3920 int il=erg.reduce_by; 3921 wlen_type quality_a =los[erg.reduce_by].guess_quality(c); 3922 wlen_type qc; 3923 while((il>0) && pLmEqual(los[il-1].p,los[il].p)) 3924 { 3925 il--; 3926 qc=los[il].guess_quality(c); 3927 if (qc<quality_a) 3928 { 3929 quality_a=qc; 3930 erg.reduce_by=il; 3931 } 3932 } 3933 swap_roles=FALSE; 3934 } 3935 } 3936 if(swap_roles) 3937 { 3938 if (TEST_OPT_PROT) PrintS("b"); 3939 poly clear_into; 3940 int dummy_len; 3941 int new_length; 3942 int bp=erg.to_reduce_u;//bucket_positon 3943 //kBucketClear(los[bp].bucket,&clear_into,&new_length); 3944 new_length=los[bp].clear_to_poly(); 3945 clear_into=los[bp].p; 3946 poly p=c->strat->S[erg.reduce_by]; 3947 int j=erg.reduce_by; 3948 int old_length=c->strat->lenS[j];// in view of S 3949 los[bp].p=p; 3950 if (c->eliminationProblem) 3951 { 3939 3952 los[bp].sugar=c->pTotaldegree_full(p); 3940 } 3941 kBucketInit(los[bp].bucket,p,old_length); 3942 wlen_type qal=pQuality(clear_into,c,new_length); 3943 int pos_in_c=-1; 3944 int z; 3945 int new_pos; 3946 new_pos=simple_posInS(c->strat,clear_into,new_length, qal); 3947 assume(new_pos<=j); 3948 for (z=c->n;z;z--) 3949 { 3950 if(p==c->S->m[z-1]) 3951 { 3952 pos_in_c=z-1; 3953 break; 3954 } 3955 } 3956 3957 int tdeg_full=-1; 3958 int tdeg=-1; 3959 if(pos_in_c>=0) 3960 { 3961 #ifdef TGB_RESORT_PAIRS 3962 c->used_b=TRUE; 3963 c->replaced[pos_in_c]=TRUE; 3964 #endif 3965 tdeg=c->T_deg[pos_in_c]; 3966 c->S->m[pos_in_c]=clear_into; 3967 c->lengths[pos_in_c]=new_length; 3968 c->weighted_lengths[pos_in_c]=qal; 3969 if (c->gcd_of_terms[pos_in_c]==NULL) 3970 c->gcd_of_terms[pos_in_c]=gcd_of_terms(clear_into,c->r); 3971 if (c->T_deg_full) 3972 tdeg_full=c->T_deg_full[pos_in_c]=c->pTotaldegree_full(clear_into); 3973 else tdeg_full=tdeg; 3974 c_S_element_changed_hook(pos_in_c,c); 3975 } else { 3976 if (c->eliminationProblem){ 3977 tdeg_full=c->pTotaldegree_full(clear_into); 3978 tdeg=c->pTotaldegree(clear_into); 3979 } 3980 } 3981 c->strat->S[j]=clear_into; 3982 c->strat->lenS[j]=new_length; 3983 3984 assume(pLength(clear_into)==new_length); 3985 if(c->strat->lenSw!=NULL) 3986 c->strat->lenSw[j]=qal; 3987 if (!rField_is_Zp(c->r)) 3988 { 3989 p_Cleardenom(clear_into,c->r);//should be unnecessary 3990 //p_Content(clear_into, c->r); 3991 } 3992 else 3993 pNorm(clear_into); 3953 } 3954 kBucketInit(los[bp].bucket,p,old_length); 3955 wlen_type qal=pQuality(clear_into,c,new_length); 3956 int pos_in_c=-1; 3957 int z; 3958 int new_pos; 3959 new_pos=simple_posInS(c->strat,clear_into,new_length, qal); 3960 assume(new_pos<=j); 3961 for (z=c->n;z;z--) 3962 { 3963 if(p==c->S->m[z-1]) 3964 { 3965 pos_in_c=z-1; 3966 break; 3967 } 3968 } 3969 3970 int tdeg_full=-1; 3971 int tdeg=-1; 3972 if(pos_in_c>=0) 3973 { 3974 #ifdef TGB_RESORT_PAIRS 3975 c->used_b=TRUE; 3976 c->replaced[pos_in_c]=TRUE; 3977 #endif 3978 tdeg=c->T_deg[pos_in_c]; 3979 c->S->m[pos_in_c]=clear_into; 3980 c->lengths[pos_in_c]=new_length; 3981 c->weighted_lengths[pos_in_c]=qal; 3982 if (c->gcd_of_terms[pos_in_c]==NULL) 3983 c->gcd_of_terms[pos_in_c]=gcd_of_terms(clear_into,c->r); 3984 if (c->T_deg_full) 3985 tdeg_full=c->T_deg_full[pos_in_c]=c->pTotaldegree_full(clear_into); 3986 else tdeg_full=tdeg; 3987 c_S_element_changed_hook(pos_in_c,c); 3988 } 3989 else 3990 { 3991 if (c->eliminationProblem) 3992 { 3993 tdeg_full=c->pTotaldegree_full(clear_into); 3994 tdeg=c->pTotaldegree(clear_into); 3995 } 3996 } 3997 c->strat->S[j]=clear_into; 3998 c->strat->lenS[j]=new_length; 3999 4000 assume(pLength(clear_into)==new_length); 4001 if(c->strat->lenSw!=NULL) 4002 c->strat->lenSw[j]=qal; 4003 if (!rField_is_Zp(c->r)) 4004 { 4005 p_Cleardenom(clear_into,c->r);//should be unnecessary 4006 //p_Content(clear_into, c->r); 4007 } 4008 else 4009 pNorm(clear_into); 3994 4010 #ifdef FIND_DETERMINISTIC 3995 erg.reduce_by=j;3996 //resort later see diploma thesis, find_in_S must be deterministic3997 //during multireduction if spolys are only in the span of the3998 //input polys4011 erg.reduce_by=j; 4012 //resort later see diploma thesis, find_in_S must be deterministic 4013 //during multireduction if spolys are only in the span of the 4014 //input polys 3999 4015 #else 4000 4001 if (new_pos<j) 4002 { 4003 if (c->strat->honey) c->strat->ecartS[j]=tdeg_full-tdeg; 4004 move_forward_in_S(j,new_pos,c->strat); 4005 erg.reduce_by=new_pos; 4006 } 4016 if (new_pos<j) 4017 { 4018 if (c->strat->honey) c->strat->ecartS[j]=tdeg_full-tdeg; 4019 move_forward_in_S(j,new_pos,c->strat); 4020 erg.reduce_by=new_pos; 4021 } 4007 4022 #endif 4008 }4023 } 4009 4024 } 4010 4025 static int fwbw(red_object* los, int i){
Note: See TracChangeset
for help on using the changeset viewer.