2983{
2984
2985
2986
2987
2988
2989
2990
2991#if SBA_PRINT_ZERO_REDUCTIONS
2992 long zeroreductions = 0;
2993#endif
2994#if SBA_PRINT_PRODUCT_CRITERION
2995 long product_criterion = 0;
2996#endif
2997#if SBA_PRINT_SIZE_G
2998 int size_g = 0;
2999 int size_g_non_red = 0;
3000#endif
3001#if SBA_PRINT_SIZE_SYZ
3002 long size_syz = 0;
3003#endif
3004
3005#if SBA_PRINT_REDUCTION_STEPS
3006 sba_reduction_steps = 0;
3007 sba_interreduction_steps = 0;
3008#endif
3009#if SBA_PRINT_OPERATIONS
3010 sba_operations = 0;
3011 sba_interreduction_operations = 0;
3012#endif
3013
3018 {
3020 if (sRing!=currRingOld)
3021 {
3024 }
3025 }
3026 ideal F;
3027
3028
3029
3031 {
3032 #if 1
3037 {
3038 poly dummy;
3039 dummy =
pCopy(F->m[0]);
3041 F->m[
i] = F->m[
i+1];
3043 }
3044 #else
3046
3048 int pos;
3050 {
3052 {
3055 }
3057 {
3060 }
3061 poly dummy;
3062 dummy =
pCopy(F->m[0]);
3064 F->m[
i] = F->m[
i+1];
3066 }
3067 else
3068 {
3070 {
3073 }
3074 }
3075 #endif
3076
3077 }
3078 else
3079 {
3082 for (
int i=0;
i<
sort->length();++
i)
3085 {
3086
3087
3088 int nrmon = 0;
3090 {
3091
3093 {
3096 {
3097 F->m[
j] = F->m[
j-1];
3098 }
3100 nrmon++;
3101 }
3102
3103 }
3104 }
3105 }
3106
3111#if SBA_INTERRED_START
3113#endif
3114#if F5DEBUG
3115 printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
3117 printf(
"ordSgn = %d\n",
currRing->OrdSgn);
3118 printf("\n");
3119#endif
3120 int srmax,lrmax, red_result = 1;
3121 int olddeg,reduc;
3122 int hilbeledeg=1,hilbcount=0,minimcnt=0;
3126
3131
3136 reduc = olddeg = lrmax = 0;
3137#ifndef NO_BUCKETS
3140#endif
3141
3142
3143
3144
3145
3146
3148
3149#ifdef HAVE_TAIL_RING
3152#endif
3154 {
3158 }
3159
3161 {
3163 {
3164
3165
3167 strat->
enterS(strat->
L[strat->
Ll-(
i)], strat->
sl+1, strat, strat->
tl);
3168 }
3171 }
3173#ifdef KDEBUG
3174
3175#endif
3176
3177 while (strat->
Ll >= 0)
3178 {
3179 if (strat->
Ll > lrmax) lrmax =strat->
Ll;
3180 #ifdef KDEBUG
3182 #endif
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3204 {
3206#if F5C
3207
3208
3209 f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
3210 lrmax, reduc,
Q,
w, hilb );
3211#endif
3212
3214 }
3215
3216
3217
3218
3219
3220 strat->
P = strat->
L[strat->
Ll];
3222
3225
3226 if (!strat->
rewCrit2(strat->
P.sig, ~strat->
P.sevSig, strat->
P.GetLmCurrRing(), strat, strat->
P.checked+1))
3227 {
3228
3229#ifdef DEBUGF5
3230 PrintS(
"SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
3231 PrintS(
"-------------------------------------------------\n");
3236 PrintS(
"-------------------------------------------------\n");
3237#endif
3239 {
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3252
3253
3256 {
3258
3259
3261 {
3263 break;
3264 }
3265 }
3266
3269
3270 }
3271 else if (strat->
P.p1 ==
NULL)
3272 {
3273 if (strat->
minim > 0)
3275
3278 }
3279 if (strat->
P.p ==
NULL && strat->
P.t_p ==
NULL)
3280 {
3281 red_result = 0;
3282 }
3283 else
3284 {
3285
3286#ifdef DEBUGF5
3287 PrintS(
"Poly before red: ");
3290#endif
3291#if SBA_PRODUCT_CRITERION
3292 if (strat->
P.prod_crit)
3293 {
3294#if SBA_PRINT_PRODUCT_CRITERION
3295 product_criterion++;
3296#endif
3297 int pos =
posInSyz(strat, strat->
P.sig);
3300 red_result = 2;
3301 }
3302 else
3303 {
3304 red_result = strat->
red(&strat->
P,strat);
3305 }
3306#else
3307 red_result = strat->
red(&strat->
P,strat);
3308#endif
3309 }
3310 }
3311 else
3312 {
3313
3314
3315
3316
3317 red_result = 2;
3318 }
3320 {
3322 {
3323 strat->
P.p =
pNeg(strat->
P.p);
3324 strat->
P.sig =
pNeg(strat->
P.sig);
3325 }
3327 if(strat->
P.sig !=
NULL)
3329 if(strat->
P.p !=
NULL)
3331 }
3332
3334 {
3335
3336 red_result =
redRing(&strat->
P,strat);
3337 if(red_result == 0)
3338 {
3341 strat->
P.sig =
NULL;
3342 }
3343 else
3344 {
3345 strat->
enterS(strat->
P, 0, strat, strat->
tl);
3348 break;
3349 }
3350 }
3352 {
3354 break;
3355 }
3356
3358
3359
3360#ifdef DEBUGF5
3361 if (red_result != 0)
3362 {
3363 PrintS(
"Poly after red: ");
3365 pWrite(strat->
P.GetLmCurrRing());
3367 printf("%d\n",red_result);
3368 }
3369#endif
3371 {
3372 if(strat->
P.p !=
NULL)
3374 &olddeg,&reduc,strat, red_result);
3375 else
3377 &olddeg,&reduc,strat, red_result);
3378 }
3379
3381 {
3383 }
3384
3385 if (red_result == 1)
3386 {
3387
3388 strat->
P.GetP(strat->
lmBin);
3389
3390
3391
3392 (strat->
P).FDeg = (strat->
P).pFDeg();
3393
3394
3395
3397
3398
3400
3401
3402
3403
3404 int pos = strat->
sl+1;
3405
3406
3407
3408 poly beforetailred;
3410 beforetailred =
pCopy(strat->
P.sig);
3411#if SBA_TAIL_RED
3413 {
3415 strat->
P.p =
redtailSba(&(strat->
P),pos-1,strat, withT);
3416 }
3417 else
3418 {
3420 {
3422 {
3423 strat->
P.pCleardenom();
3425 {
3426 strat->
P.p =
redtailSba(&(strat->
P),pos-1,strat, withT);
3427 strat->
P.pCleardenom();
3428 }
3429 }
3430 else
3431 {
3434 strat->
P.p =
redtailSba(&(strat->
P),pos-1,strat, withT);
3435 }
3436 }
3437 }
3438
3439
3440
3442 {
3443 strat->
enterS(strat->
P, 0, strat, strat->
tl);
3444 break;
3445 }
3446#endif
3448 {
3449 if(strat->
P.sig ==
NULL ||
pLtCmp(beforetailred,strat->
P.sig) == 1)
3450 {
3452
3453 red_result =
redRing(&strat->
P,strat);
3454 if(red_result == 0)
3455 {
3456
3459 }
3460 else
3461 {
3462 strat->
enterS(strat->
P, 0, strat, strat->
tl);
3463 break;
3464 }
3465 }
3467
3468 if(strat->
P.p ==
NULL)
3469 goto case_when_red_result_changed;
3470 }
3471
3472
3474 {
3475 for (
int jj = 0; jj<strat->
tl+1; jj++)
3476 {
3478 {
3479 strat->
T[jj].is_sigsafe =
FALSE;
3480 }
3481 }
3482 }
3483 else
3484 {
3485 for (
int jj = 0; jj<strat->
tl+1; jj++)
3486 {
3487 strat->
T[jj].is_sigsafe =
FALSE;
3488 }
3489 }
3490#ifdef KDEBUG
3492#endif
3493
3494
3496 {
3497 if (strat->
minim==1)
3498 {
3501 }
3502 else
3503 {
3504 strat->
M->m[minimcnt]=strat->
P.p2;
3506 }
3508 pNext(strat->
M->m[minimcnt])
3512 minimcnt++;
3513 }
3514
3515
3516
3518 strat->
T[strat->
tl].is_sigsafe =
FALSE;
3519
3520
3521
3522
3523
3526 else
3529 break;
3532 strat->
enterS(strat->
P, pos, strat, strat->
tl);
3534 {
3536 for (
int tk=0; tk<strat->
sl+1; tk++)
3537 {
3539 {
3540
3542 break;
3543 }
3544 }
3545
3546 if (overwrite)
3547 {
3553
3557 for(
int ps=0;ps<strat->
sl+1;ps++)
3558 {
3559
3562 {
3565 (strat->
syzmax)*
sizeof(
unsigned long),
3567 *sizeof(unsigned long));
3569 }
3571
3572
3575
3576
3577
3578
3579
3580
3581
3582
3586
3587
3591 }
3592 }
3593 }
3594
3595
3597 {
3599 unsigned max_cmp =
IDELEMS(F);
3603 int pos;
3605
3606
3608 {
3609 for (
int i=0;
i<strat->
sl; ++
i)
3610 {
3616
3619 }
3621 }
3622 else
3623 {
3624
3625
3626 for (
unsigned i=cmp+1;
i<=max_cmp; ++
i)
3627 {
3628 pos = -1;
3629 for (
int j=0;
j<strat->
sl; ++
j)
3630 {
3632 {
3634 break;
3635 }
3636 }
3637 if (pos != -1)
3638 {
3641
3648 {
3650 {
3653 }
3654 }
3655 else
3656 {
3659 }
3660 }
3661 }
3662
3663 }
3664 }
3665
3666#if DEBUGF50
3667 printf("---------------------------\n");
3668 Print(
" %d. ELEMENT ADDED TO GCURR:\n",strat->
sl+1);
3671#endif
3672
3673
3674
3675
3676
3677
3678#if 0
3680 if (pl==1)
3681 {
3682
3683
3684 }
3685 else if (pl==2)
3686 {
3687
3688
3689 }
3690#endif
3691 if (hilb!=
NULL)
khCheck(
Q,
w,hilb,hilbeledeg,hilbcount,strat);
3692
3694 if (strat->
sl>srmax) srmax = strat->
sl;
3695 }
3696 else
3697 {
3698 case_when_red_result_changed:
3699
3700
3701
3702
3703
3704 if (red_result!=2)
3705 {
3706#if SBA_PRINT_ZERO_REDUCTIONS
3707 zeroreductions++;
3708#endif
3710 {
3711
3712 }
3713 else
3714 {
3715 int pos =
posInSyz(strat, strat->
P.sig);
3717
3718 #ifdef DEBUGF5
3719 Print(
"ADDING STUFF TO SYZ : ");
3720
3722 #endif
3723 }
3724 }
3726 {
3728 }
3729 }
3730
3731#ifdef KDEBUG
3733#endif
3735 }
3736 #if 0
3738 printf("\nSigDrop!\n");
3739 else
3740 printf("\nEnded with no SigDrop\n");
3741 #endif
3742
3744 {
3745
3746 if(strat->
P.sig !=
NULL)
3748
3749 #ifdef KDEBUG
3751 #endif
3752 }
3753#ifdef KDEBUG
3755#endif
3756
3758 {
3760 {
3764 {
3767 {
3771 }
3773 }
3774 }
3775 }
3776
3778 {
3781 {
3782
3783
3784
3785#ifdef HAVE_TAIL_RING
3787 {
3793 }
3795#endif
3797 }
3798 }
3800
3801#if SBA_PRINT_SIZE_SYZ
3802
3803 size_syz = strat->
syzl;
3804#endif
3805
3806
3807
3808
3809
3810
3811
3812
3813
3816#if SBA_PRINT_SIZE_G
3818#endif
3821
3824 {
3825
3826
3828 #if 1
3829
3830 for(;
k>=0 && (strat->
L[
k].p1 !=
NULL || strat->
L[
k].p2 !=
NULL);
k--)
3831 {
3832
3834 }
3835 #endif
3836
3837
3838
3839
3840 for(;
k>=0 && strat->
L[
k].p1 ==
NULL && strat->
L[
k].p2 ==
NULL;
k--)
3841 {
3842
3843 strat->
enterS(strat->
L[
k], strat->
sl+1, strat, strat->
tl);
3844
3845 }
3846 }
3847
3848 #if 0
3850 {
3851 for(
k=strat->
sl;
k>=0;
k--)
3852 {
3856 }
3857 }
3858 #endif
3859
3860
3861
3862
3864 {
3875 }
3882
3883#if SBA_PRINT_SIZE_G
3885#endif
3886#ifdef DEBUGF5
3887 printf(
"SIZE OF SHDL: %d\n",
IDELEMS(strat->
Shdl));
3888 int oo = 0;
3890 {
3891 printf(" %d. ",oo+1);
3893 oo++;
3894 }
3895#endif
3896#if SBA_PRINT_ZERO_REDUCTIONS
3897 printf("----------------------------------------------------------\n");
3898 printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3899 zeroreductions = 0;
3900#endif
3901#if SBA_PRINT_REDUCTION_STEPS
3902 printf("----------------------------------------------------------\n");
3903 printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3904#endif
3905#if SBA_PRINT_OPERATIONS
3906 printf("OPERATIONS: %ld\n",sba_operations);
3907#endif
3908#if SBA_PRINT_REDUCTION_STEPS
3909 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3910 printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3911#endif
3912#if SBA_PRINT_OPERATIONS
3913 printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3914#endif
3915#if SBA_PRINT_REDUCTION_STEPS
3916 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3917 printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3918 sba_interreduction_steps = 0;
3919 sba_reduction_steps = 0;
3920#endif
3921#if SBA_PRINT_OPERATIONS
3922 printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3923 sba_interreduction_operations = 0;
3924 sba_operations = 0;
3925#endif
3926#if SBA_PRINT_SIZE_G
3927 printf("----------------------------------------------------------\n");
3928 printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3929 size_g = 0;
3930 size_g_non_red = 0;
3931#endif
3932#if SBA_PRINT_SIZE_SYZ
3933 printf("SIZE OF SYZ: %ld\n",size_syz);
3934 printf("----------------------------------------------------------\n");
3935 size_syz = 0;
3936#endif
3937#if SBA_PRINT_PRODUCT_CRITERION
3938 printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3939 product_criterion = 0;
3940#endif
3941 return (strat->
Shdl);
3942}
static void sort(int **points, int sizePoints)
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
ideal kInterRed(ideal F, const ideal Q)
void initSba(ideal F, kStrategy strat)
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, bigintmat *hilb)
void initSbaPos(kStrategy strat)
void enterSyz(LObject &p, kStrategy strat, int atT)
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
void messageStatSBA(int hilbcount, kStrategy strat)
void initSyzRules(kStrategy strat)
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
int posInSyz(const kStrategy strat, poly sig)
void exitSba(kStrategy strat)
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
void initSbaCrit(kStrategy strat)
#define __p_GetComp(p, r)
#define omRealloc0Size(addr, o_size, size)
void pEnlargeSet(poly **p, int l, int increment)
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
static void p_SetExpV(poly p, int *ev, const ring r)
static int p_LmCmp(poly p, poly q, const ring r)
static void p_GetExpV(poly p, int *ev, const ring r)
void rChangeCurrRing(ring r)
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
void rWrite(ring r, BOOLEAN details)
void rDelete(ring r)
unconditionally deletes fields in r
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
int F1(int a1, int &r1)
F1.