My Project
Loading...
Searching...
No Matches
kstd2.cc File Reference
#include "kernel/mod2.h"
#include "kernel/GBEngine/kutil.h"
#include "misc/options.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/khstd.h"
#include "polys/kbuckets.h"
#include "polys/prCopy.h"
#include "polys/weight.h"
#include "misc/intvec.h"
#include "polys/nc/nc.h"
#include "polys/shiftop.h"

Go to the source code of this file.

Macros

#define GCD_SBA   1
 
#define PLURAL_INTERNAL_DECLARATIONS   1
 
#define STDZ_EXHANGE_DURING_REDUCTION   0
 
#define DEBUGF50   0
 
#define DEBUGF51   0
 
#define F5C   1
 
#define F5CTAILRED   1
 
#define SBA_INTERRED_START   0
 
#define SBA_TAIL_RED   1
 
#define SBA_PRODUCT_CRITERION   0
 
#define SBA_PRINT_ZERO_REDUCTIONS   0
 
#define SBA_PRINT_REDUCTION_STEPS   0
 
#define SBA_PRINT_OPERATIONS   0
 
#define SBA_PRINT_SIZE_G   0
 
#define SBA_PRINT_SIZE_SYZ   0
 
#define SBA_PRINT_PRODUCT_CRITERION   0
 

Functions

int kTestDivisibleByT0_Z (const kStrategy strat, const LObject *L)
 tests if T[0] divides the leading monomial of L, returns -1 if not
 
int kFindDivisibleByInT_Z (const kStrategy strat, const LObject *L, const int start)
 
static int kFindDivisibleByInS_Z (const kStrategy strat, LObject *L)
 
int kFindDivisibleByInT (const kStrategy strat, const LObject *L, const int start)
 return -1 if no divisor is found number of first divisor in T, otherwise
 
int kFindDivisibleByInT_ecart (const kStrategy strat, const LObject *L, const int ecart)
 
int kFindDivisibleByInS (const kStrategy strat, int *max_ind, LObject *L)
 return -1 if no divisor is found number of first divisor in S, otherwise
 
int kFindDivisibleByInS_noCF (const kStrategy strat, int *max_ind, LObject *L)
 
int kFindNextDivisibleByInS (const kStrategy strat, int start, int max_ind, LObject *L)
 
static long ind_fact_2 (long arg)
 
poly kFindZeroPoly (poly input_p, ring leadRing, ring tailRing)
 
int redRing_Z (LObject *h, kStrategy strat)
 
static int redRing_Z_S (LObject *h, kStrategy strat)
 
int redRing (LObject *h, kStrategy strat)
 
static int redRing_S (LObject *h, kStrategy strat)
 
int redHomog (LObject *h, kStrategy strat)
 
KINLINE int ksReducePolyTailSig (LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
 
int redSig (LObject *h, kStrategy strat)
 
int redSigRing (LObject *h, kStrategy strat)
 
poly redtailSba (LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
 
int redLazy (LObject *h, kStrategy strat)
 
int redHoney (LObject *h, kStrategy strat)
 
poly redNF (poly h, int &max_ind, int nonorm, kStrategy strat)
 
poly redNFBound (poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
 
void kDebugPrint (kStrategy strat)
 
ideal bba (ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
 
ideal sba (ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
 
poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
 
poly kNF2Bound (ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
 
ideal kNF2 (ideal F, ideal Q, ideal q, kStrategy strat, int lazyReduce)
 
ideal kNF2Bound (ideal F, ideal Q, ideal q, int bound, kStrategy strat, int lazyReduce)
 
void f5c (kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, intvec *hilb)
 
ideal bbaShift (ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
 
ideal rightgb (ideal F, const ideal Q)
 
int redFirstShift (LObject *h, kStrategy strat)
 

Variables

VAR int(* test_PosInT )(const TSet T, const int tl, LObject &h)
 
VAR int(* test_PosInL )(const LSet set, const int length, LObject *L, const kStrategy strat)
 

Macro Definition Documentation

◆ DEBUGF50

#define DEBUGF50   0

Definition at line 26 of file kstd2.cc.

◆ DEBUGF51

#define DEBUGF51   0

Definition at line 27 of file kstd2.cc.

◆ F5C

#define F5C   1

Definition at line 34 of file kstd2.cc.

◆ F5CTAILRED

#define F5CTAILRED   1

Definition at line 36 of file kstd2.cc.

◆ GCD_SBA

#define GCD_SBA   1

Definition at line 12 of file kstd2.cc.

◆ PLURAL_INTERNAL_DECLARATIONS

#define PLURAL_INTERNAL_DECLARATIONS   1

Definition at line 18 of file kstd2.cc.

◆ SBA_INTERRED_START

#define SBA_INTERRED_START   0

Definition at line 39 of file kstd2.cc.

◆ SBA_PRINT_OPERATIONS

#define SBA_PRINT_OPERATIONS   0

Definition at line 44 of file kstd2.cc.

◆ SBA_PRINT_PRODUCT_CRITERION

#define SBA_PRINT_PRODUCT_CRITERION   0

Definition at line 47 of file kstd2.cc.

◆ SBA_PRINT_REDUCTION_STEPS

#define SBA_PRINT_REDUCTION_STEPS   0

Definition at line 43 of file kstd2.cc.

◆ SBA_PRINT_SIZE_G

#define SBA_PRINT_SIZE_G   0

Definition at line 45 of file kstd2.cc.

◆ SBA_PRINT_SIZE_SYZ

#define SBA_PRINT_SIZE_SYZ   0

Definition at line 46 of file kstd2.cc.

◆ SBA_PRINT_ZERO_REDUCTIONS

#define SBA_PRINT_ZERO_REDUCTIONS   0

Definition at line 42 of file kstd2.cc.

◆ SBA_PRODUCT_CRITERION

#define SBA_PRODUCT_CRITERION   0

Definition at line 41 of file kstd2.cc.

◆ SBA_TAIL_RED

#define SBA_TAIL_RED   1

Definition at line 40 of file kstd2.cc.

◆ STDZ_EXHANGE_DURING_REDUCTION

#define STDZ_EXHANGE_DURING_REDUCTION   0

Definition at line 21 of file kstd2.cc.

Function Documentation

◆ bba()

ideal bba ( ideal F,
ideal Q,
intvec * w,
intvec * hilb,
kStrategy strat )

Definition at line 2622 of file kstd2.cc.

2623{
2624 int red_result = 1;
2625 int olddeg,reduc;
2626 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2627 BOOLEAN withT = FALSE;
2628 BITSET save;
2629 SI_SAVE_OPT1(save);
2630
2631 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2633 initBuchMoraPosRing(strat);
2634 else
2635 initBuchMoraPos(strat);
2636 initHilbCrit(F,Q,&hilb,strat);
2637 initBba(strat);
2638 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2639 /*Shdl=*/initBuchMora(F, Q,strat);
2640 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2641 reduc = olddeg = 0;
2642
2643#ifndef NO_BUCKETS
2645 strat->use_buckets = 1;
2646#endif
2647 // redtailBBa against T for inhomogeneous input
2648 if (!TEST_OPT_OLDSTD)
2649 withT = ! strat->homog;
2650
2651 // strat->posInT = posInT_pLength;
2652 kTest_TS(strat);
2653
2654#ifdef HAVE_TAIL_RING
2655 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2657#endif
2658 if (BVERBOSE(23))
2659 {
2660 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2661 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2662 kDebugPrint(strat);
2663 }
2664
2665
2666#ifdef KDEBUG
2667 //kDebugPrint(strat);
2668#endif
2669 /* compute------------------------------------------------------- */
2670 while (strat->Ll >= 0)
2671 {
2672 #ifdef KDEBUG
2673 if (TEST_OPT_DEBUG) messageSets(strat);
2674 #endif
2675 if (siCntrlc)
2676 {
2677 while (strat->Ll >= 0)
2678 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2679 strat->noClearS=TRUE;
2680 }
2682 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2683 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2684 {
2685 /*
2686 *stops computation if
2687 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2688 *a predefined number Kstd1_deg
2689 */
2690 while ((strat->Ll >= 0)
2691 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2692 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2693 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2694 )
2695 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2696 if (strat->Ll<0) break;
2697 else strat->noClearS=TRUE;
2698 }
2699 if (strat->Ll== 0) strat->interpt=TRUE;
2700 /* picks the last element from the lazyset L */
2701 strat->P = strat->L[strat->Ll];
2702 strat->Ll--;
2703
2704 if (pNext(strat->P.p) == strat->tail)
2705 {
2706 // deletes the short spoly
2708 pLmDelete(strat->P.p);
2709 else
2710 pLmFree(strat->P.p);
2711 strat->P.p = NULL;
2712 poly m1 = NULL, m2 = NULL;
2713
2714 // check that spoly creation is ok
2715 while (strat->tailRing != currRing &&
2716 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2717 {
2718 assume(m1 == NULL && m2 == NULL);
2719 // if not, change to a ring where exponents are at least
2720 // large enough
2721 if (!kStratChangeTailRing(strat))
2722 {
2723 WerrorS("OVERFLOW...");
2724 break;
2725 }
2726 }
2727 // create the real one
2728 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2729 strat->tailRing, m1, m2, strat->R);
2730 }
2731 else if (strat->P.p1 == NULL)
2732 {
2733 if (strat->minim > 0)
2734 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2735 // for input polys, prepare reduction
2736 strat->P.PrepareRed(strat->use_buckets);
2737 }
2738
2739 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2740 {
2741 red_result = 0;
2742 }
2743 else
2744 {
2745 if (TEST_OPT_PROT)
2746 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2747 &olddeg,&reduc,strat, red_result);
2748
2749 /* reduction of the element chosen from L */
2750 red_result = strat->red(&strat->P,strat);
2751 if (errorreported) break;
2752 }
2753
2754 if (strat->overflow)
2755 {
2756 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2757 }
2758
2759 // reduction to non-zero new poly
2760 if (red_result == 1)
2761 {
2762 // get the polynomial (canonicalize bucket, make sure P.p is set)
2763 strat->P.GetP(strat->lmBin);
2764 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2765 // but now, for entering S, T, we reset it
2766 // in the inhomogeneous case: FDeg == pFDeg
2767 if (strat->homog) strat->initEcart(&(strat->P));
2768
2769 /* statistic */
2770 if (TEST_OPT_PROT) PrintS("s");
2771
2772 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2773
2774 // reduce the tail and normalize poly
2775 // in the ring case we cannot expect LC(f) = 1,
2776 strat->redTailChange=FALSE;
2777
2778 /* if we are computing over Z we always want to try and cut down
2779 * the coefficients in the tail terms */
2781 {
2782 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2783 }
2784
2786 {
2787 strat->P.pCleardenom();
2789 {
2790 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2791 strat->P.pCleardenom();
2792 if (strat->redTailChange) { strat->P.t_p=NULL; }
2793 }
2794 }
2795 else
2796 {
2797 strat->P.pNorm();
2799 {
2800 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2801 if (strat->redTailChange) { strat->P.t_p=NULL; }
2802 }
2803 }
2804
2805#ifdef KDEBUG
2806 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2807#endif /* KDEBUG */
2808
2809 // min_std stuff
2810 if ((strat->P.p1==NULL) && (strat->minim>0))
2811 {
2812 if (strat->minim==1)
2813 {
2814 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2815 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2816 }
2817 else
2818 {
2819 strat->M->m[minimcnt]=strat->P.p2;
2820 strat->P.p2=NULL;
2821 }
2822 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2823 pNext(strat->M->m[minimcnt])
2824 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2825 strat->tailRing, currRing,
2826 currRing->PolyBin);
2827 minimcnt++;
2828 }
2829
2830 // enter into S, L, and T
2831 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2832 {
2833 strat->P.SetShortExpVector();
2834 enterT(strat->P, strat);
2836 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2837 else
2838 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2839 // posInS only depends on the leading term
2840 strat->enterS(strat->P, pos, strat, strat->tl);
2841#if 0
2842 int pl=pLength(strat->P.p);
2843 if (pl==1)
2844 {
2845 //if (TEST_OPT_PROT)
2846 //PrintS("<1>");
2847 }
2848 else if (pl==2)
2849 {
2850 //if (TEST_OPT_PROT)
2851 //PrintS("<2>");
2852 }
2853#endif
2854 }
2855 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2856// Print("[%d]",hilbeledeg);
2857 kDeleteLcm(&strat->P);
2858 if (strat->s_poly!=NULL)
2859 {
2860 // the only valid entries are: strat->P.p,
2861 // strat->tailRing (read-only, keep it)
2862 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2863 if (strat->s_poly(strat))
2864 {
2865 // we are called AFTER enterS, i.e. if we change P
2866 // we have to add it also to S/T
2867 // and add pairs
2868 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2869 enterT(strat->P, strat);
2871 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2872 else
2873 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2874 strat->enterS(strat->P, pos, strat, strat->tl);
2875 }
2876 }
2877 }
2878 else if (strat->P.p1 == NULL && strat->minim > 0)
2879 {
2880 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2881 }
2882
2883#ifdef KDEBUG
2884 strat->P.Init();
2885#endif /* KDEBUG */
2886 kTest_TS(strat);
2887 }
2888#ifdef KDEBUG
2889 if (TEST_OPT_DEBUG) messageSets(strat);
2890#endif /* KDEBUG */
2891
2892 if (TEST_OPT_SB_1)
2893 {
2895 {
2896 int k=1;
2897 int j;
2898 while(k<=strat->sl)
2899 {
2900 j=0;
2901 loop
2902 {
2903 if (j>=k) break;
2904 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2905 j++;
2906 }
2907 k++;
2908 }
2909 }
2910 }
2911 /* complete reduction of the standard basis--------- */
2912 if (TEST_OPT_REDSB)
2913 {
2914 completeReduce(strat);
2915 if (strat->completeReduce_retry)
2916 {
2917 // completeReduce needed larger exponents, retry
2918 // to reduce with S (instead of T)
2919 // and in currRing (instead of strat->tailRing)
2920#ifdef HAVE_TAIL_RING
2921 if(currRing->bitmask>strat->tailRing->bitmask)
2922 {
2924 cleanT(strat);strat->tailRing=currRing;
2925 int i;
2926 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2927 completeReduce(strat);
2928 }
2929 if (strat->completeReduce_retry)
2930#endif
2931 Werror("exponent bound is %ld",currRing->bitmask);
2932 }
2933 }
2934 else if (TEST_OPT_PROT) PrintLn();
2935 /* release temp data-------------------------------- */
2936 exitBuchMora(strat);
2937 /* postprocessing for GB over ZZ --------------------*/
2938 if (!errorreported)
2939 {
2941 {
2942 for(int i = 0;i<=strat->sl;i++)
2943 {
2944 if(!nGreaterZero(pGetCoeff(strat->S[i])))
2945 {
2946 strat->S[i] = pNeg(strat->S[i]);
2947 }
2948 }
2949 finalReduceByMon(strat);
2950 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2951 {
2952 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2953 {
2954 strat->S[i] = pNeg(strat->Shdl->m[i]);
2955 }
2956 }
2957 }
2958 //else if (rField_is_Ring(currRing))
2959 // finalReduceByMon(strat);
2960 }
2961// if (TEST_OPT_WEIGHTM)
2962// {
2963// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2964// if (ecartWeights)
2965// {
2966// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2967// ecartWeights=NULL;
2968// }
2969// }
2970 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2971 SI_RESTORE_OPT1(save);
2972 /* postprocessing for GB over Q-rings ------------------*/
2973 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2974
2975 idTest(strat->Shdl);
2976
2977 return (strat->Shdl);
2978}
int BOOLEAN
Definition auxiliary.h:87
#define TRUE
Definition auxiliary.h:100
#define FALSE
Definition auxiliary.h:96
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
int syzComp
Definition kutil.h:354
int * S_2_R
Definition kutil.h:342
ring tailRing
Definition kutil.h:343
int Ll
Definition kutil.h:351
omBin lmBin
Definition kutil.h:344
char honey
Definition kutil.h:375
polyset S
Definition kutil.h:306
int minim
Definition kutil.h:357
TObject ** R
Definition kutil.h:340
ideal M
Definition kutil.h:305
int tl
Definition kutil.h:350
poly tail
Definition kutil.h:334
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:284
ideal Shdl
Definition kutil.h:303
pShallowCopyDeleteProc p_shallow_copy_delete
Definition kutil.h:338
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:286
char use_buckets
Definition kutil.h:381
char interpt
Definition kutil.h:369
char redTailChange
Definition kutil.h:397
char completeReduce_retry
Definition kutil.h:401
void(* initEcart)(TObject *L)
Definition kutil.h:280
LObject P
Definition kutil.h:302
char noClearS
Definition kutil.h:400
char overflow
Definition kutil.h:402
LSet L
Definition kutil.h:327
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:281
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:278
int sl
Definition kutil.h:348
unsigned long * sevS
Definition kutil.h:322
char homog
Definition kutil.h:370
s_poly_proc_t s_poly
Definition kutil.h:300
const CanonicalForm & w
Definition facAbsFact.cc:51
int j
Definition facHensel.cc:110
VAR short errorreported
Definition feFopen.cc:23
void WerrorS(const char *s)
Definition feFopen.cc:24
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
#define idTest(id)
Definition ideals.h:47
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition kInline.h:1209
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition kInline.h:1232
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
Definition khstd.cc:28
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition kspoly.cc:1203
void initBba(kStrategy strat)
Definition kstd1.cc:1682
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:52
VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kstd2.cc:83
void kDebugPrint(kStrategy strat)
Definition kutil.cc:11500
VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition kstd2.cc:82
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7465
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9745
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9137
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1071
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4492
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:7142
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition kutil.cc:9411
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9574
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10960
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9830
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4668
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10479
void cleanT(kStrategy strat)
Definition kutil.cc:563
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10073
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4462
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1213
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11053
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9429
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10279
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9659
void messageSets(kStrategy strat)
Definition kutil.cc:7538
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7506
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition kutil.cc:10868
static void kDeleteLcm(LObject *P)
Definition kutil.h:869
#define assume(x)
Definition mod2.h:387
#define pNext(p)
Definition monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
#define nGreaterZero(n)
Definition numbers.h:27
#define NULL
Definition omList.c:12
VAR BOOLEAN siCntrlc
Definition options.c:14
#define TEST_OPT_IDLIFT
Definition options.h:131
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
#define BVERBOSE(a)
Definition options.h:35
#define TEST_OPT_REDTAIL
Definition options.h:118
#define SI_SAVE_OPT1(A)
Definition options.h:21
#define SI_RESTORE_OPT1(A)
Definition options.h:24
#define TEST_OPT_OLDSTD
Definition options.h:125
#define TEST_OPT_REDSB
Definition options.h:106
#define TEST_OPT_DEGBOUND
Definition options.h:115
#define TEST_OPT_SB_1
Definition options.h:121
#define TEST_OPT_PROT
Definition options.h:105
#define TEST_OPT_DEBUG
Definition options.h:110
#define TEST_OPT_CONTENTSB
Definition options.h:129
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
static int pLength(poly a)
Definition p_polys.h:190
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:846
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
#define pNeg(p)
Definition polys.h:198
#define pGetComp(p)
Component.
Definition polys.h:37
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:76
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:70
void PrintS(const char *s)
Definition reporter.cc:284
void PrintLn()
Definition reporter.cc:310
void Werror(const char *fmt,...)
Definition reporter.cc:189
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:514
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:767
#define rField_is_Ring(R)
Definition ring.h:490
ideal idInit(int idsize, int rank)
initialise an ideal / module
#define IDELEMS(i)
#define Q
Definition sirandom.c:26
#define BITSET
Definition structs.h:16
#define loop
Definition structs.h:75

◆ bbaShift()

ideal bbaShift ( ideal F,
ideal Q,
intvec * w,
intvec * hilb,
kStrategy strat )

Definition at line 4590 of file kstd2.cc.

4591{
4592 int red_result = 1;
4593 int olddeg,reduc;
4594 int hilbeledeg=1,hilbcount=0,minimcnt=0;
4595 BOOLEAN withT = TRUE; // currently only T contains the shifts
4596 BITSET save;
4597 SI_SAVE_OPT1(save);
4598
4599 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4601 initBuchMoraPosRing(strat);
4602 else
4603 initBuchMoraPos(strat);
4604 initHilbCrit(F,Q,&hilb,strat);
4605 initBba(strat);
4606 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4607 /*Shdl=*/initBuchMora(F, Q,strat);
4608 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4609 reduc = olddeg = 0;
4610
4611#ifndef NO_BUCKETS
4613 strat->use_buckets = 1;
4614#endif
4615 // redtailBBa against T for inhomogeneous input
4616 // if (!TEST_OPT_OLDSTD)
4617 // withT = ! strat->homog;
4618
4619 // strat->posInT = posInT_pLength;
4620 kTest_TS(strat);
4621
4622#ifdef HAVE_TAIL_RING
4623 // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4624 // kStratInitChangeTailRing(strat);
4625 strat->tailRing=currRing;
4626#endif
4627 if (BVERBOSE(23))
4628 {
4629 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4630 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4631 kDebugPrint(strat);
4632 }
4633
4634#ifdef KDEBUG
4635 //kDebugPrint(strat);
4636#endif
4637 /* compute------------------------------------------------------- */
4638 while (strat->Ll >= 0)
4639 {
4640 #ifdef KDEBUG
4641 if (TEST_OPT_DEBUG) messageSets(strat);
4642 #endif
4643 if (siCntrlc)
4644 {
4645 while (strat->Ll >= 0)
4646 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4647 strat->noClearS=TRUE;
4648 }
4650 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4651 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4652 {
4653 /*
4654 *stops computation if
4655 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4656 *a predefined number Kstd1_deg
4657 */
4658 while ((strat->Ll >= 0)
4659 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4660 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4661 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4662 )
4663 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4664 if (strat->Ll<0) break;
4665 else strat->noClearS=TRUE;
4666 }
4667 if (strat->Ll== 0) strat->interpt=TRUE;
4668 /* picks the last element from the lazyset L */
4669 strat->P = strat->L[strat->Ll];
4670 strat->Ll--;
4671
4672 if (pNext(strat->P.p) == strat->tail)
4673 {
4674 // deletes the short spoly
4676 pLmDelete(strat->P.p);
4677 else
4678 pLmFree(strat->P.p);
4679 strat->P.p = NULL;
4680 poly m1 = NULL, m2 = NULL;
4681
4682 // check that spoly creation is ok
4683 while (strat->tailRing != currRing &&
4684 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4685 {
4686 assume(m1 == NULL && m2 == NULL);
4687 // if not, change to a ring where exponents are at least
4688 // large enough
4689 if (!kStratChangeTailRing(strat))
4690 {
4691 WerrorS("OVERFLOW...");
4692 break;
4693 }
4694 }
4695 // create the real one
4696 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4697 strat->tailRing, m1, m2, strat->R);
4698 }
4699 else if (strat->P.p1 == NULL)
4700 {
4701 if (strat->minim > 0)
4702 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4703 // for input polys, prepare reduction
4704 strat->P.PrepareRed(strat->use_buckets);
4705 }
4706
4707 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4708 {
4709 red_result = 0;
4710 }
4711 else
4712 {
4713 if (TEST_OPT_PROT)
4714 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4715 &olddeg,&reduc,strat, red_result);
4716
4717 /* reduction of the element chosen from L */
4718 red_result = strat->red(&strat->P,strat);
4719 if (errorreported) break;
4720 }
4721
4722 if (strat->overflow)
4723 {
4724 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4725 }
4726
4727 // reduction to non-zero new poly
4728 if (red_result == 1)
4729 {
4730 // get the polynomial (canonicalize bucket, make sure P.p is set)
4731 strat->P.GetP(strat->lmBin);
4732 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4733 // but now, for entering S, T, we reset it
4734 // in the inhomogeneous case: FDeg == pFDeg
4735 if (strat->homog) strat->initEcart(&(strat->P));
4736
4737 /* statistic */
4738 if (TEST_OPT_PROT) PrintS("s");
4739
4740 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4741
4742 // reduce the tail and normalize poly
4743 // in the ring case we cannot expect LC(f) = 1,
4744 strat->redTailChange=FALSE;
4745
4746 /* if we are computing over Z we always want to try and cut down
4747 * the coefficients in the tail terms */
4749 {
4750 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4751 }
4752
4754 {
4755 strat->P.pCleardenom();
4757 {
4758 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4759 strat->P.pCleardenom();
4760 if (strat->redTailChange)
4761 {
4762 strat->P.t_p=NULL;
4763 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4764 }
4765 }
4766 }
4767 else
4768 {
4769 strat->P.pNorm();
4771 {
4772 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4773 if (strat->redTailChange)
4774 {
4775 strat->P.t_p=NULL;
4776 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4777 }
4778 }
4779 }
4780
4781#ifdef KDEBUG
4782 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4783#endif /* KDEBUG */
4784
4785 // min_std stuff
4786 if ((strat->P.p1==NULL) && (strat->minim>0))
4787 {
4788 if (strat->minim==1)
4789 {
4790 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4791 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4792 }
4793 else
4794 {
4795 strat->M->m[minimcnt]=strat->P.p2;
4796 strat->P.p2=NULL;
4797 }
4798 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4799 pNext(strat->M->m[minimcnt])
4800 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4801 strat->tailRing, currRing,
4802 currRing->PolyBin);
4803 minimcnt++;
4804 }
4805
4806
4807 // enter into S, L, and T
4808 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4809 {
4810 enterT(strat->P, strat);
4811 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4812 // posInS only depends on the leading term
4813 strat->enterS(strat->P, pos, strat, strat->tl);
4814 if (!strat->rightGB)
4815 enterTShift(strat->P, strat);
4816 }
4817
4818 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4819// Print("[%d]",hilbeledeg);
4820 kDeleteLcm(&strat->P);
4821 if (strat->s_poly!=NULL)
4822 {
4823 // the only valid entries are: strat->P.p,
4824 // strat->tailRing (read-only, keep it)
4825 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4826 if (strat->s_poly(strat))
4827 {
4828 // we are called AFTER enterS, i.e. if we change P
4829 // we have to add it also to S/T
4830 // and add pairs
4831 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4832 enterT(strat->P, strat);
4833 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4834 strat->enterS(strat->P, pos, strat, strat->tl);
4835 if (!strat->rightGB)
4836 enterTShift(strat->P,strat);
4837 }
4838 }
4839 }
4840 else if (strat->P.p1 == NULL && strat->minim > 0)
4841 {
4842 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4843 }
4844#ifdef KDEBUG
4845 strat->P.Init();
4846#endif /* KDEBUG */
4847 kTest_TS(strat);
4848 }
4849#ifdef KDEBUG
4850 if (TEST_OPT_DEBUG) messageSets(strat);
4851#endif /* KDEBUG */
4852 /* shift case: look for elt's in S such that they are divisible by elt in T */
4853 if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4854 {
4856 {
4857 for (int k = 0; k <= strat->sl; ++k)
4858 {
4859 if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4860 for (int j = 0; j<=strat->tl; ++j)
4861 {
4862 if (strat->T[j].p!=NULL)
4863 {
4864 // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4865 assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4866 assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4867 if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4868 {
4869 if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4870 { // check whether LM is different
4871 deleteInS(k, strat);
4872 --k;
4873 break;
4874 }
4875 }
4876 }
4877 }
4878 }
4879 }
4880 }
4881 /* complete reduction of the standard basis--------- */
4882 if (TEST_OPT_REDSB)
4883 {
4884 completeReduce(strat, TRUE); //shift: withT = TRUE
4885 if (strat->completeReduce_retry)
4886 {
4887 // completeReduce needed larger exponents, retry
4888 // to reduce with S (instead of T)
4889 // and in currRing (instead of strat->tailRing)
4890#ifdef HAVE_TAIL_RING
4891 if(currRing->bitmask>strat->tailRing->bitmask)
4892 {
4894 cleanT(strat);strat->tailRing=currRing;
4895 int i;
4896 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4897 WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4898 completeReduce(strat);
4899 }
4900 if (strat->completeReduce_retry)
4901#endif
4902 Werror("exponent bound is %ld",currRing->bitmask);
4903 }
4904 }
4905 else if (TEST_OPT_PROT) PrintLn();
4906
4907 /* release temp data-------------------------------- */
4908 exitBuchMora(strat);
4909 /* postprocessing for GB over ZZ --------------------*/
4910 if (!errorreported)
4911 {
4913 {
4914 for(int i = 0;i<=strat->sl;i++)
4915 {
4916 if(!nGreaterZero(pGetCoeff(strat->S[i])))
4917 {
4918 strat->S[i] = pNeg(strat->S[i]);
4919 }
4920 }
4921 finalReduceByMon(strat);
4922 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4923 {
4924 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4925 {
4926 strat->S[i] = pNeg(strat->Shdl->m[i]);
4927 }
4928 }
4929 }
4930 //else if (rField_is_Ring(currRing))
4931 // finalReduceByMon(strat);
4932 }
4933// if (TEST_OPT_WEIGHTM)
4934// {
4935// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4936// if (ecartWeights)
4937// {
4938// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4939// ecartWeights=NULL;
4940// }
4941// }
4942 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4943 SI_RESTORE_OPT1(save);
4944 /* postprocessing for GB over Q-rings ------------------*/
4945 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4946
4947 idTest(strat->Shdl);
4948
4949 return (strat->Shdl);
4950}
TSet T
Definition kutil.h:326
char rightGB
Definition kutil.h:367
unsigned long * sevT
Definition kutil.h:325
intset fromQ
Definition kutil.h:321
#define WarnS
Definition emacs.cc:78
void enterTShift(LObject p, kStrategy strat, int atT)
Definition kutil.cc:12978
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:12948
void deleteInS(int i, kStrategy strat)
Definition kutil.cc:1137
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition polys.h:146
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition polys.h:152
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition polys.h:105

◆ f5c()

void f5c ( kStrategy strat,
int & olddeg,
int & minimcnt,
int & hilbeledeg,
int & hilbcount,
int & srmax,
int & lrmax,
int & reduc,
ideal Q,
intvec * w,
intvec * hilb )

Definition at line 4278 of file kstd2.cc.

4281{
4282 int Ll_old, red_result = 1;
4283 int pos = 0;
4284 hilbeledeg=1;
4285 hilbcount=0;
4286 minimcnt=0;
4287 srmax = 0; // strat->sl is 0 at this point
4288 reduc = olddeg = lrmax = 0;
4289 // we cannot use strat->T anymore
4290 //cleanT(strat);
4291 //strat->tl = -1;
4292 Ll_old = strat->Ll;
4293 while (strat->tl >= 0)
4294 {
4295 if(!strat->T[strat->tl].is_redundant)
4296 {
4297 LObject h;
4298 h.p = strat->T[strat->tl].p;
4299 h.tailRing = strat->T[strat->tl].tailRing;
4300 h.t_p = strat->T[strat->tl].t_p;
4301 if (h.p!=NULL)
4302 {
4303 if (currRing->OrdSgn==-1)
4304 {
4305 cancelunit(&h);
4306 deleteHC(&h, strat);
4307 }
4308 if (h.p!=NULL)
4309 {
4311 {
4312 h.pCleardenom(); // also does remove Content
4313 }
4314 else
4315 {
4316 h.pNorm();
4317 }
4318 strat->initEcart(&h);
4320 pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4321 else
4322 pos = strat->Ll+1;
4323 h.sev = pGetShortExpVector(h.p);
4324 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4325 }
4326 }
4327 }
4328 strat->tl--;
4329 }
4330 strat->sl = -1;
4331#if 0
4332//#ifdef HAVE_TAIL_RING
4333 if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4335#endif
4336 //enterpairs(pOne(),0,0,-1,strat,strat->tl);
4337 //strat->sl = -1;
4338 /* picks the last element from the lazyset L */
4339 while (strat->Ll>Ll_old)
4340 {
4341 strat->P = strat->L[strat->Ll];
4342 strat->Ll--;
4343//#if 1
4344#ifdef DEBUGF5
4345 PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4346 PrintS("-------------------------------------------------\n");
4347 pWrite(pHead(strat->P.p));
4348 pWrite(pHead(strat->P.p1));
4349 pWrite(pHead(strat->P.p2));
4350 printf("%d\n",strat->tl);
4351 PrintS("-------------------------------------------------\n");
4352#endif
4353 if (pNext(strat->P.p) == strat->tail)
4354 {
4355 // deletes the short spoly
4357 pLmDelete(strat->P.p);
4358 else
4359 pLmFree(strat->P.p);
4360
4361 // TODO: needs some masking
4362 // TODO: masking needs to vanish once the signature
4363 // sutff is completely implemented
4364 strat->P.p = NULL;
4365 poly m1 = NULL, m2 = NULL;
4366
4367 // check that spoly creation is ok
4368 while (strat->tailRing != currRing &&
4369 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4370 {
4371 assume(m1 == NULL && m2 == NULL);
4372 // if not, change to a ring where exponents are at least
4373 // large enough
4374 if (!kStratChangeTailRing(strat))
4375 {
4376 WerrorS("OVERFLOW...");
4377 break;
4378 }
4379 }
4380 // create the real one
4381 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4382 strat->tailRing, m1, m2, strat->R);
4383 }
4384 else if (strat->P.p1 == NULL)
4385 {
4386 if (strat->minim > 0)
4387 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4388 // for input polys, prepare reduction
4390 strat->P.PrepareRed(strat->use_buckets);
4391 }
4392
4393 if (strat->P.p == NULL && strat->P.t_p == NULL)
4394 {
4395 red_result = 0;
4396 }
4397 else
4398 {
4399 if (TEST_OPT_PROT)
4400 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4401 &olddeg,&reduc,strat, red_result);
4402
4403#ifdef DEBUGF5
4404 PrintS("Poly before red: ");
4405 pWrite(strat->P.p);
4406#endif
4407 /* complete reduction of the element chosen from L */
4408 red_result = strat->red2(&strat->P,strat);
4409 if (errorreported) break;
4410 }
4411
4412 if (strat->overflow)
4413 {
4414 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4415 }
4416
4417 // reduction to non-zero new poly
4418 if (red_result == 1)
4419 {
4420 // get the polynomial (canonicalize bucket, make sure P.p is set)
4421 strat->P.GetP(strat->lmBin);
4422 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4423 // but now, for entering S, T, we reset it
4424 // in the inhomogeneous case: FDeg == pFDeg
4425 if (strat->homog) strat->initEcart(&(strat->P));
4426
4427 /* statistic */
4428 if (TEST_OPT_PROT) PrintS("s");
4429 int pos;
4430 #if 1
4432 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4433 else
4434 pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4435 #else
4436 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4437 #endif
4438 // reduce the tail and normalize poly
4439 // in the ring case we cannot expect LC(f) = 1,
4440#if F5CTAILRED
4441 BOOLEAN withT = TRUE;
4443 {
4444 strat->P.pCleardenom();
4446 {
4447 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4448 strat->P.pCleardenom();
4449 }
4450 }
4451 else
4452 {
4453 strat->P.pNorm();
4455 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4456 }
4457#endif
4458#ifdef KDEBUG
4459 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4460#endif /* KDEBUG */
4461
4462 // min_std stuff
4463 if ((strat->P.p1==NULL) && (strat->minim>0))
4464 {
4465 if (strat->minim==1)
4466 {
4467 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4468 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4469 }
4470 else
4471 {
4472 strat->M->m[minimcnt]=strat->P.p2;
4473 strat->P.p2=NULL;
4474 }
4475 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4476 pNext(strat->M->m[minimcnt])
4477 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4478 strat->tailRing, currRing,
4479 currRing->PolyBin);
4480 minimcnt++;
4481 }
4482
4483 // enter into S, L, and T
4484 // here we need to recompute new signatures, but those are trivial ones
4485 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4486 {
4487 enterT(strat->P, strat);
4488 // posInS only depends on the leading term
4489 strat->enterS(strat->P, pos, strat, strat->tl);
4490//#if 1
4491#ifdef DEBUGF5
4492 PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4493 pWrite(pHead(strat->S[strat->sl]));
4494 pWrite(strat->sig[strat->sl]);
4495#endif
4496 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4497 }
4498 // Print("[%d]",hilbeledeg);
4499 kDeleteLcm(&strat->P);
4500 if (strat->sl>srmax) srmax = strat->sl;
4501 }
4502 else
4503 {
4504 // adds signature of the zero reduction to
4505 // strat->syz. This is the leading term of
4506 // syzygy and can be used in syzCriterion()
4507 // the signature is added if and only if the
4508 // pair was not detected by the rewritten criterion in strat->red = redSig
4509 if (strat->P.p1 == NULL && strat->minim > 0)
4510 {
4511 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4512 }
4513 }
4514
4515#ifdef KDEBUG
4516 strat->P.Init();
4517#endif /* KDEBUG */
4518 }
4519 int cc = 0;
4520 while (cc<strat->tl+1)
4521 {
4522 strat->T[cc].sig = pOne();
4523 p_SetComp(strat->T[cc].sig,cc+1,currRing);
4524 strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4525 strat->sig[cc] = strat->T[cc].sig;
4526 strat->sevSig[cc] = strat->T[cc].sevSig;
4527 strat->T[cc].is_sigsafe = TRUE;
4528 cc++;
4529 }
4530 strat->max_lower_index = strat->tl;
4531 // set current signature index of upcoming iteration step
4532 // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4533 // the corresponding syzygy rules correctly
4534 strat->currIdx = cc+1;
4535 for (int cd=strat->Ll; cd>=0; cd--)
4536 {
4537 p_SetComp(strat->L[cd].sig,cc+1,currRing);
4538 cc++;
4539 }
4540 for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4541 strat->Shdl->m[cc] = NULL;
4542 #if 0
4543 printf("\nAfter f5c sorting\n");
4544 for(int i=0;i<=strat->sl;i++)
4545 pWrite(pHead(strat->S[i]));
4546 getchar();
4547 #endif
4548//#if 1
4549#if DEBUGF5
4550 PrintS("------------------- STRAT S ---------------------\n");
4551 cc = 0;
4552 while (cc<strat->tl+1)
4553 {
4554 pWrite(pHead(strat->S[cc]));
4555 pWrite(strat->sig[cc]);
4556 printf("- - - - - -\n");
4557 cc++;
4558 }
4559 PrintS("-------------------------------------------------\n");
4560 PrintS("------------------- STRAT T ---------------------\n");
4561 cc = 0;
4562 while (cc<strat->tl+1)
4563 {
4564 pWrite(pHead(strat->T[cc].p));
4565 pWrite(strat->T[cc].sig);
4566 printf("- - - - - -\n");
4567 cc++;
4568 }
4569 PrintS("-------------------------------------------------\n");
4570 PrintS("------------------- STRAT L ---------------------\n");
4571 cc = 0;
4572 while (cc<strat->Ll+1)
4573 {
4574 pWrite(pHead(strat->L[cc].p));
4575 pWrite(pHead(strat->L[cc].p1));
4576 pWrite(pHead(strat->L[cc].p2));
4577 pWrite(strat->L[cc].sig);
4578 printf("- - - - - -\n");
4579 cc++;
4580 }
4581 PrintS("-------------------------------------------------\n");
4582 printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4583#endif
4584
4585}
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
int currIdx
Definition kutil.h:317
int(* red2)(LObject *L, kStrategy strat)
Definition kutil.h:279
unsigned long * sevSig
Definition kutil.h:324
int max_lower_index
Definition kutil.h:318
polyset sig
Definition kutil.h:308
int Lmax
Definition kutil.h:351
STATIC_VAR Poly * h
Definition janet.cc:971
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1274
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition kutil.cc:4769
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition kutil.cc:291
int posInLF5CRing(const LSet set, int start, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5880
void cancelunit(LObject *L, BOOLEAN inNF)
Definition kutil.cc:370
class sLObject LObject
Definition kutil.h:58
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:247
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:67
void pWrite(poly p)
Definition polys.h:308
#define pOne()
Definition polys.h:315

◆ ind_fact_2()

static long ind_fact_2 ( long arg)
static

Definition at line 600 of file kstd2.cc.

601{
602 if (arg <= 0) return 0;
603 long ind = 0;
604 if (arg%2 == 1) { arg--; }
605 while (arg > 0)
606 {
607 ind += SI_LOG2_LONG(arg);
608 arg = arg - 2;
609 }
610 return ind;
611}
static int SI_LOG2_LONG(long v)
Definition si_log2.h:22

◆ kDebugPrint()

void kDebugPrint ( kStrategy strat)

Definition at line 11500 of file kutil.cc.

11501{
11502 printf("red: ");
11503 if (strat->red==redFirst) printf("redFirst\n");
11504 else if (strat->red==redHoney) printf("redHoney\n");
11505 else if (strat->red==redEcart) printf("redEcart\n");
11506 else if (strat->red==redHomog) printf("redHomog\n");
11507 else if (strat->red==redLazy) printf("redLazy\n");
11508 else if (strat->red==redLiftstd) printf("redLiftstd\n");
11509 else printf("%p\n",(void*)strat->red);
11510 printf("posInT: ");
11511 if (strat->posInT==posInT0) printf("posInT0\n");
11512 else if (strat->posInT==posInT1) printf("posInT1\n");
11513 else if (strat->posInT==posInT11) printf("posInT11\n");
11514 else if (strat->posInT==posInT110) printf("posInT110\n");
11515 else if (strat->posInT==posInT13) printf("posInT13\n");
11516 else if (strat->posInT==posInT15) printf("posInT15\n");
11517 else if (strat->posInT==posInT17) printf("posInT17\n");
11518 else if (strat->posInT==posInT17_c) printf("posInT17_c\n");
11519 else if (strat->posInT==posInT19) printf("posInT19\n");
11520 else if (strat->posInT==posInT2) printf("posInT2\n");
11521 else if (strat->posInT==posInT11Ring) printf("posInT11Ring\n");
11522 else if (strat->posInT==posInT110Ring) printf("posInT110Ring\n");
11523 else if (strat->posInT==posInT15Ring) printf("posInT15Ring\n");
11524 else if (strat->posInT==posInT17Ring) printf("posInT17Ring\n");
11525 else if (strat->posInT==posInT17_cRing) printf("posInT17_cRing\n");
11526#ifdef HAVE_MORE_POS_IN_T
11527 else if (strat->posInT==posInT_EcartFDegpLength) printf("posInT_EcartFDegpLength\n");
11528 else if (strat->posInT==posInT_FDegpLength) printf("posInT_FDegpLength\n");
11529 else if (strat->posInT==posInT_pLength) printf("posInT_pLength\n");
11530#endif
11531 else if (strat->posInT==posInT_EcartpLength) printf("posInT_EcartpLength\n");
11532 else printf("%p\n",(void*)strat->posInT);
11533 printf("posInL: ");
11534 if (strat->posInL==posInL0) printf("posInL0\n");
11535 else if (strat->posInL==posInL10) printf("posInL10\n");
11536 else if (strat->posInL==posInL11) printf("posInL11\n");
11537 else if (strat->posInL==posInL110) printf("posInL110\n");
11538 else if (strat->posInL==posInL13) printf("posInL13\n");
11539 else if (strat->posInL==posInL15) printf("posInL15\n");
11540 else if (strat->posInL==posInL17) printf("posInL17\n");
11541 else if (strat->posInL==posInL17_c) printf("posInL17_c\n");
11542 else if (strat->posInL==posInL0) printf("posInL0Ring\n");
11543 else if (strat->posInL==posInL11Ring) printf("posInL11Ring\n");
11544 else if (strat->posInL==posInL11Ringls) printf("posInL11Ringls\n");
11545 else if (strat->posInL==posInL110Ring) printf("posInL110Ring\n");
11546 else if (strat->posInL==posInL15Ring) printf("posInL15Ring\n");
11547 else if (strat->posInL==posInL17Ring) printf("posInL17Ring\n");
11548 else if (strat->posInL==posInL17_cRing) printf("posInL17_cRing\n");
11549 else if (strat->posInL==posInLSpecial) printf("posInLSpecial\n");
11550 else printf("%p\n",(void*)strat->posInL);
11551 printf("enterS: ");
11552 if (strat->enterS==enterSBba) printf("enterSBba\n");
11553 else if (strat->enterS==enterSMora) printf("enterSMora\n");
11554 else if (strat->enterS==enterSMoraNF) printf("enterSMoraNF\n");
11555 else printf("%p\n",(void*)strat->enterS);
11556 printf("initEcart: ");
11557 if (strat->initEcart==initEcartBBA) printf("initEcartBBA\n");
11558 else if (strat->initEcart==initEcartNormal) printf("initEcartNormal\n");
11559 else printf("%p\n",(void*)strat->initEcart);
11560 printf("initEcartPair: ");
11561 if (strat->initEcartPair==initEcartPairBba) printf("initEcartPairBba\n");
11562 else if (strat->initEcartPair==initEcartPairMora) printf("initEcartPairMora\n");
11563 else printf("%p\n",(void*)strat->initEcartPair);
11564 printf("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11565 strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11566 printf("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11567 strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11568 printf("chainCrit: ");
11569 if (strat->chainCrit==chainCritNormal) printf("chainCritNormal\n");
11570 else if (strat->chainCrit==chainCritOpt_1) printf("chainCritOpt_1\n");
11571 else printf("%p\n",(void*)strat->chainCrit);
11572 printf("posInLDependsOnLength=%d\n",
11573 strat->posInLDependsOnLength);
11574 printf("%s\n",showOption());
11575 printf("LDeg: ");
11576 if (currRing->pLDeg==pLDeg0) printf("pLDeg0");
11577 else if (currRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11578 else if (currRing->pLDeg==pLDegb) printf("pLDegb");
11579 else if (currRing->pLDeg==pLDeg1) printf("pLDeg1");
11580 else if (currRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11581 else if (currRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11582 else if (currRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11583 else if (currRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11584 else if (currRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11585 else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11586 else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11587 else if (currRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11588 else printf("? (%lx)", (long)currRing->pLDeg);
11589 printf(" / ");
11590 if (strat->tailRing->pLDeg==pLDeg0) printf("pLDeg0");
11591 else if (strat->tailRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11592 else if (strat->tailRing->pLDeg==pLDegb) printf("pLDegb");
11593 else if (strat->tailRing->pLDeg==pLDeg1) printf("pLDeg1");
11594 else if (strat->tailRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11595 else if (strat->tailRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11596 else if (strat->tailRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11597 else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11598 else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11599 else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11600 else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11601 else if (strat->tailRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11602 else printf("? (%lx)", (long)strat->tailRing->pLDeg);
11603 printf("\n");
11604 printf("currRing->pFDeg: ");
11605 if (currRing->pFDeg==p_Totaldegree) printf("p_Totaldegree");
11606 else if (currRing->pFDeg==p_WFirstTotalDegree) printf("pWFirstTotalDegree");
11607 else if (currRing->pFDeg==p_Deg) printf("p_Deg");
11608 else if (currRing->pFDeg==kHomModDeg) printf("kHomModDeg");
11609 else if (currRing->pFDeg==totaldegreeWecart) printf("totaldegreeWecart");
11610 else if (currRing->pFDeg==p_WTotaldegree) printf("p_WTotaldegree");
11611 else printf("? (%lx)", (long)currRing->pFDeg);
11612 printf("\n");
11613 printf(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11615 printf(" degBound: %d\n", Kstd1_deg);
11616
11617 if( ecartWeights != NULL )
11618 {
11619 printf("ecartWeights: ");
11620 for (int i = rVar(currRing); i > 0; i--)
11621 printf("%hd ", ecartWeights[i]);
11622 printf("\n");
11624 }
11625
11626#ifndef SING_NDEBUG
11628#endif
11629}
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:291
char noTailReduction
Definition kutil.h:376
int ak
Definition kutil.h:353
char sugarCrit
Definition kutil.h:375
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:287
char Gebauer
Definition kutil.h:376
int LazyPass
Definition kutil.h:353
int LazyDegree
Definition kutil.h:353
char posInLDependsOnLength
Definition kutil.h:387
int redLiftstd(LObject *h, kStrategy strat)
Definition kLiftstd.cc:167
long kHomModDeg(poly p, const ring r)
Definition kstd1.cc:2419
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition kstd1.cc:1361
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2114
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1154
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1909
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6301
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6414
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6060
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5283
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:795
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5846
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition kutil.cc:4958
int posInT1(const TSet set, const int length, LObject &p)
Definition kutil.cc:4901
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5076
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1674
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:5151
int posInT0(const TSet, const int length, LObject &)
Definition kutil.cc:4890
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4930
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6147
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6101
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11466
int posInT13(const TSet set, const int length, LObject &p)
Definition kutil.cc:5122
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1320
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5616
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3450
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:4994
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6182
int posInT17_c(const TSet set, const int length, LObject &p)
Definition kutil.cc:5389
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11375
int posInT15(const TSet set, const int length, LObject &p)
Definition kutil.cc:5189
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5572
VAR int Kstd1_deg
Definition kutil.cc:245
void initEcartNormal(TObject *h)
Definition kutil.cc:1298
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5914
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6257
int posInT110(const TSet set, const int length, LObject &p)
Definition kutil.cc:5034
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6217
int posInT19(const TSet set, const int length, LObject &p)
Definition kutil.cc:5515
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5243
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5344
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1621
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition kutil.cc:5450
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6350
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11429
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3209
void initEcartBBA(TObject *h)
Definition kutil.cc:1306
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5804
char * showOption()
Definition misc_ip.cc:711
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1313
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8788
#define TEST_OPT_WEIGHTM
Definition options.h:123
long pLDegb(poly p, int *l, const ring r)
Definition p_polys.cc:812
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition p_polys.cc:976
long p_WFirstTotalDegree(poly p, const ring r)
Definition p_polys.cc:595
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition p_polys.cc:1039
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition p_polys.cc:1069
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition p_polys.cc:942
long pLDeg1(poly p, int *l, const ring r)
Definition p_polys.cc:842
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition p_polys.cc:911
long p_WTotaldegree(poly p, const ring r)
Definition p_polys.cc:612
long pLDeg1c(poly p, int *l, const ring r)
Definition p_polys.cc:878
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition p_polys.cc:1006
long pLDeg0c(poly p, int *l, const ring r)
Definition p_polys.cc:771
long pLDeg0(poly p, int *l, const ring r)
Definition p_polys.cc:740
long p_Deg(poly a, const ring r)
Definition p_polys.cc:586
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1521
void rDebugPrint(const ring r)
Definition ring.cc:4153
static int rGetCurrSyzLimit(const ring r)
Definition ring.h:728
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition ring.h:725
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:597
long totaldegreeWecart(poly p, ring r)
Definition weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition weight.cc:247
EXTERN_VAR short * ecartWeights
Definition weight.h:12

◆ kFindDivisibleByInS()

int kFindDivisibleByInS ( const kStrategy strat,
int * max_ind,
LObject * L )

return -1 if no divisor is found number of first divisor in S, otherwise

Definition at line 468 of file kstd2.cc.

469{
470 unsigned long not_sev = ~L->sev;
471 poly p = L->GetLmCurrRing();
472 int j = 0;
473
474 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
475
477#if 1
478 int ende;
479 if (is_Ring
480 || (strat->ak>0)
481 || currRing->pLexOrder)
482 ende=strat->sl;
483 else
484 {
485 ende=posInS(strat,*max_ind,p,0)+1;
486 if (ende>(*max_ind)) ende=(*max_ind);
487 }
488#else
489 int ende=strat->sl;
490#endif
491 if(is_Ring)
492 {
493 loop
494 {
495 if (j > ende) return -1;
496#if defined(PDEBUG) || defined(PDIV_DEBUG)
497 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
498 p, not_sev, currRing))
499#else
500 if ( !(strat->sevS[j] & not_sev) &&
501 p_LmDivisibleBy(strat->S[j], p, currRing))
502#endif
503 {
504 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
505 return j;
506 }
507 j++;
508 }
509 }
510 else
511 {
512 loop
513 {
514 if (j > ende) return -1;
515#if defined(PDEBUG) || defined(PDIV_DEBUG)
516 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
517 p, not_sev, currRing))
518#else
519 if ( !(strat->sevS[j] & not_sev) &&
520 p_LmDivisibleBy(strat->S[j], p, currRing))
521#endif
522 {
523 return j;
524 }
525 j++;
526 }
527 }
528}
int p
Definition cfModGcd.cc:4086
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition coeffs.h:748
#define pAssume(cond)
Definition monomials.h:90
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition p_polys.cc:4830
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition p_polys.h:1924
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1905

◆ kFindDivisibleByInS_noCF()

int kFindDivisibleByInS_noCF ( const kStrategy strat,
int * max_ind,
LObject * L )

Definition at line 531 of file kstd2.cc.

532{
533 unsigned long not_sev = ~L->sev;
534 poly p = L->GetLmCurrRing();
535 int j = 0;
536
537 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
538
540#if 1
541 int ende;
542 if (is_Ring
543 || (strat->ak>0)
544 || currRing->pLexOrder)
545 ende=strat->sl;
546 else
547 {
548 ende=posInS(strat,*max_ind,p,0)+1;
549 if (ende>(*max_ind)) ende=(*max_ind);
550 }
551#else
552 int ende=strat->sl;
553#endif
554 loop
555 {
556 if (j > ende) return -1;
557#if defined(PDEBUG) || defined(PDIV_DEBUG)
558 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
559 p, not_sev, currRing))
560#else
561 if ( !(strat->sevS[j] & not_sev) &&
562 p_LmDivisibleBy(strat->S[j], p, currRing))
563#endif
564 {
565 return j;
566 }
567 j++;
568 }
569}

◆ kFindDivisibleByInS_Z()

static int kFindDivisibleByInS_Z ( const kStrategy strat,
LObject * L )
static

Definition at line 276 of file kstd2.cc.

277{
278 unsigned long not_sev = ~L->sev;
279 int j = 0;
280 int o = -1;
281
282 const polyset S=strat->S;
283 const unsigned long* sevS=strat->sevS;
284 number rest, orest, mult;
285 L->GetP();
286 if (L->p!=NULL)
287 {
288 const ring r=currRing;
289 const poly p=L->p;
290 orest = pGetCoeff(p);
291
292 pAssume(~not_sev == p_GetShortExpVector(p, r));
293
294 loop
295 {
296 if (j > strat->sl) return o;
297#if defined(PDEBUG) || defined(PDIV_DEBUG)
298 if (p_LmShortDivisibleBy(S[j], sevS[j],p, not_sev, r))
299#else
300 if (!(sevS[j] & not_sev) && p_LmDivisibleBy(S[j], p, r))
301#endif
302 {
303 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(S[j]), &rest, r->cf);
304 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
305 {
306 o = j;
307 orest = rest;
308 }
309 }
310 j++;
311 }
312 }
313 else
314 {
315 return -1;
316 }
317}
static FORCE_INLINE number n_EucNorm(number a, const coeffs r)
Definition coeffs.h:676
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition coeffs.h:682
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition coeffs.h:515
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:468
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:647
poly * polyset
Definition polys.h:259

◆ kFindDivisibleByInT()

int kFindDivisibleByInT ( const kStrategy strat,
const LObject * L,
const int start )

return -1 if no divisor is found number of first divisor in T, otherwise

Definition at line 321 of file kstd2.cc.

322{
323 unsigned long not_sev = ~L->sev;
324 int j = start;
325
326 const TSet T=strat->T;
327 const unsigned long* sevT=strat->sevT;
328 const ring r=currRing;
329 const BOOLEAN is_Ring=rField_is_Ring(r);
330 if (L->p!=NULL)
331 {
332 const poly p=L->p;
333
334 pAssume(~not_sev == p_GetShortExpVector(p, r));
335
336 if(is_Ring)
337 {
338 loop
339 {
340 if (j > strat->tl) return -1;
341#if defined(PDEBUG) || defined(PDIV_DEBUG)
342 if ((T[j].p!=NULL)
343 && p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
344#else
345 if (!(sevT[j] & not_sev)
346 && (T[j].p!=NULL)
347 && p_LmDivisibleBy(T[j].p, p, r))
348#endif
349 {
350 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
351 return j;
352 }
353 j++;
354 }
355 }
356 else
357 {
358 loop
359 {
360 if (j > strat->tl) return -1;
361#if defined(PDEBUG) || defined(PDIV_DEBUG)
362 if ((T[j].p!=NULL)
363 && p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
364#else
365 if (!(sevT[j] & not_sev)
366 && (T[j].p!=NULL)
367 && p_LmDivisibleBy(T[j].p, p, r))
368#endif
369 {
370 return j;
371 }
372 j++;
373 }
374 }
375 }
376 else
377 {
378 const poly p=L->t_p;
379 const ring r=strat->tailRing;
380 if(is_Ring)
381 {
382 loop
383 {
384 if (j > strat->tl) return -1;
385#if defined(PDEBUG) || defined(PDIV_DEBUG)
386 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
387 p, not_sev, r))
388#else
389 if (!(sevT[j] & not_sev) &&
390 p_LmDivisibleBy(T[j].t_p, p, r))
391#endif
392 {
393 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
394 return j;
395 }
396 j++;
397 }
398 }
399 else
400 {
401 loop
402 {
403 if (j > strat->tl) return -1;
404#if defined(PDEBUG) || defined(PDIV_DEBUG)
405 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
406 p, not_sev, r))
407#else
408 if (!(sevT[j] & not_sev) &&
409 p_LmDivisibleBy(T[j].t_p, p, r))
410#endif
411 {
412 return j;
413 }
414 j++;
415 }
416 }
417 }
418}
STATIC_VAR jList * T
Definition janet.cc:30
TObject * TSet
Definition kutil.h:59

◆ kFindDivisibleByInT_ecart()

int kFindDivisibleByInT_ecart ( const kStrategy strat,
const LObject * L,
const int ecart )

Definition at line 420 of file kstd2.cc.

421{
422 if (TEST_OPT_LENGTH)
423 {
424 int r=-1; // found, but bad ecart
425 int j=-2; // found, good ecart
426 int jj=-1; // current search
427 loop
428 {
429 jj=kFindDivisibleByInT(strat,L,jj+1);
430 if (jj== -1)
431 {
432 if (j<0) return r; // nothing with good ecart
433 else return j; // end of search, return best found
434 }
435 else if (r<0) r=jj; // save bad ecart found
436 if (strat->T[jj].ecart<=ecart) // good enough
437 {
438 if (strat->T[jj].pLength<=0)
439 strat->T[jj].pLength=strat->T[jj].GetpLength();
440 if (j== -2) j=jj; // first found
441 else if (strat->T[j].pLength > strat->T[jj].pLength) // jj better then j
442 j=jj;
443 if (strat->T[j].pLength<=2) return j; // length already minimal
444 }
445 }
446 }
447 else
448 {
449 int r=-1;
450 int jj=-1;
451 loop
452 {
453 jj=kFindDivisibleByInT(strat,L,jj+1);
454 if (jj== -1)
455 {
456 return r; // nothing found
457 }
458 else if (r== -1) r=jj;
459 if (strat->T[jj].ecart<=ecart) // good enough
460 {
461 return jj;
462 }
463 }
464 }
465}
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition kstd2.cc:321
#define TEST_OPT_LENGTH
Definition options.h:132

◆ kFindDivisibleByInT_Z()

int kFindDivisibleByInT_Z ( const kStrategy strat,
const LObject * L,
const int start )

Definition at line 213 of file kstd2.cc.

214{
215 unsigned long not_sev = ~L->sev;
216 int j = start;
217 int o = -1;
218
219 const TSet T=strat->T;
220 const unsigned long* sevT=strat->sevT;
221 number rest, orest, mult;
222 if (L->p!=NULL)
223 {
224 const ring r=currRing;
225 const poly p=L->p;
226 orest = pGetCoeff(p);
227
228 pAssume(~not_sev == p_GetShortExpVector(p, r));
229
230 loop
231 {
232 if (j > strat->tl) return o;
233#if defined(PDEBUG) || defined(PDIV_DEBUG)
234 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
235#else
236 if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
237#endif
238 {
239 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
240 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
241 {
242 o = j;
243 orest = rest;
244 }
245 }
246 j++;
247 }
248 }
249 else
250 {
251 const ring r=strat->tailRing;
252 const poly p=L->t_p;
253 orest = pGetCoeff(p);
254 loop
255 {
256 if (j > strat->tl) return o;
257#if defined(PDEBUG) || defined(PDIV_DEBUG)
258 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
259 p, not_sev, r))
260#else
261 if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
262#endif
263 {
264 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
265 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
266 {
267 o = j;
268 orest = rest;
269 }
270 }
271 j++;
272 }
273 }
274}

◆ kFindNextDivisibleByInS()

int kFindNextDivisibleByInS ( const kStrategy strat,
int start,
int max_ind,
LObject * L )

Definition at line 571 of file kstd2.cc.

572{
573 unsigned long not_sev = ~L->sev;
574 poly p = L->GetLmCurrRing();
575 int j = start;
576
577 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
578#if 1
579 int ende=max_ind;
580#else
581 int ende=strat->sl;
582#endif
583 loop
584 {
585 if (j > ende) return -1;
586#if defined(PDEBUG) || defined(PDIV_DEBUG)
587 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
588 p, not_sev, currRing))
589#else
590 if ( !(strat->sevS[j] & not_sev) &&
591 p_LmDivisibleBy(strat->S[j], p, currRing))
592#endif
593 {
594 return j;
595 }
596 j++;
597 }
598}

◆ kFindZeroPoly()

poly kFindZeroPoly ( poly input_p,
ring leadRing,
ring tailRing )

Definition at line 613 of file kstd2.cc.

614{
615 // m = currRing->ch
616
617 if (input_p == NULL) return NULL;
618
619 poly p = input_p;
620 poly zeroPoly = NULL;
621 unsigned long a = (unsigned long) pGetCoeff(p);
622
623 int k_ind2 = 0;
624 int a_ind2 = SI_LOG2_LONG(a);
625
626 // unsigned long k = 1;
627 // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
628 for (int i = 1; i <= leadRing->N; i++)
629 {
630 k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
631 }
632
633 a = (unsigned long) pGetCoeff(p);
634
635 number tmp1;
636 poly tmp2, tmp3;
637 poly lead_mult = p_ISet(1, tailRing);
638 if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
639 {
640 int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
641 int s_exp;
642 zeroPoly = p_ISet(a, tailRing);
643 for (int i = 1; i <= leadRing->N; i++)
644 {
645 s_exp = p_GetExp(p, i,leadRing);
646 if (s_exp % 2 != 0)
647 {
648 s_exp = s_exp - 1;
649 }
650 while ( (0 < SI_LOG2_LONG(s_exp)) && (SI_LOG2_LONG(s_exp) <= too_much) )
651 {
652 too_much = too_much - SI_LOG2_LONG(s_exp);
653 s_exp = s_exp - 2;
654 }
655 p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
656 for (int j = 1; j <= s_exp; j++)
657 {
658 tmp1 = nInit(j);
659 tmp2 = p_ISet(1, tailRing);
660 p_SetExp(tmp2, i, 1, tailRing);
661 p_Setm(tmp2, tailRing);
662 if (nIsZero(tmp1))
663 { // should nowbe obsolet, test ! TODO OLIVER
664 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
665 }
666 else
667 {
668 tmp3 = p_NSet(nCopy(tmp1), tailRing);
669 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
670 }
671 }
672 }
673 p_Setm(lead_mult, tailRing);
674 zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
675 tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
676 for (int i = 1; i <= leadRing->N; i++)
677 {
678 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
679 }
680 p_Setm(tmp2, leadRing);
681 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
682 pNext(tmp2) = zeroPoly;
683 return tmp2;
684 }
685/* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
686 if (1 == 0 && alpha_k <= a)
687 { // Temporarily disabled, reducing coefficients not compatible with std TODO Oliver
688 zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
689 for (int i = 1; i <= leadRing->N; i++)
690 {
691 for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
692 {
693 tmp1 = nInit(j);
694 tmp2 = p_ISet(1, tailRing);
695 p_SetExp(tmp2, i, 1, tailRing);
696 p_Setm(tmp2, tailRing);
697 if (nIsZero(tmp1))
698 {
699 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
700 }
701 else
702 {
703 tmp3 = p_ISet((unsigned long) tmp1, tailRing);
704 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
705 }
706 }
707 }
708 tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
709 for (int i = 1; i <= leadRing->N; i++)
710 {
711 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
712 }
713 p_Setm(tmp2, leadRing);
714 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
715 pNext(tmp2) = zeroPoly;
716 return tmp2;
717 } */
718 return NULL;
719}
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition coeffs.h:448
CFList tmp1
Definition facFqBivar.cc:75
CFList tmp2
Definition facFqBivar.cc:75
static long ind_fact_2(long arg)
Definition kstd2.cc:600
#define nIsZero(n)
Definition numbers.h:19
#define nCopy(n)
Definition numbers.h:15
#define nInit(i)
Definition numbers.h:24
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition p_polys.cc:1298
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition p_polys.cc:1474
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:936
static poly p_Mult_q(poly p, poly q, const ring r)
Definition p_polys.h:1118
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition p_polys.h:488
static void p_Setm(poly p, const ring r)
Definition p_polys.h:233
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition p_polys.h:469
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1051
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition p_polys.h:755
#define pSetExp(p, i, v)
Definition polys.h:42

◆ kNF2() [1/2]

ideal kNF2 ( ideal F,
ideal Q,
ideal q,
kStrategy strat,
int lazyReduce )

Definition at line 4103 of file kstd2.cc.

4104{
4105 assume(!idIs0(q));
4106 assume(!(idIs0(F)&&(Q==NULL)));
4107// lazy_reduce flags: can be combined by |
4108//#define KSTD_NF_LAZY 1
4109 // do only a reduction of the leading term
4110//#define KSTD_NF_NONORM 4
4111 // only global: avoid normalization, return a multiply of NF
4112 poly p;
4113 int i;
4114 ideal res;
4115 int max_ind;
4116
4117 //if (idIs0(q))
4118 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4119 //if ((idIs0(F))&&(Q==NULL))
4120 // return idCopy(q); /*F=0*/
4121 //strat->ak = idRankFreeModule(F);
4122 /*- creating temp data structures------------------- -*/
4123 BITSET save1;
4124 SI_SAVE_OPT1(save1);
4126 initBuchMoraCrit(strat);
4127 strat->initEcart = initEcartBBA;
4128#ifdef HAVE_SHIFTBBA
4129 if (rIsLPRing(currRing))
4130 {
4131 strat->enterS = enterSBbaShift;
4132 }
4133 else
4134#endif
4135 {
4136 strat->enterS = enterSBba;
4137 }
4138 /*- set S -*/
4139 strat->sl = -1;
4140#ifndef NO_BUCKETS
4142#endif
4143 /*- init local data struct.---------------------------------------- -*/
4144 /*Shdl=*/initS(F,Q,strat);
4145 /*- compute------------------------------------------------------- -*/
4146 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4147 for (i=IDELEMS(q)-1; i>=0; i--)
4148 {
4149 if (q->m[i]!=NULL)
4150 {
4151 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4152 p = redNF(pCopy(q->m[i]),max_ind,
4153 (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4154 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4155 {
4156 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4158 {
4159 p = redtailBba_NF(p,strat);
4160 }
4161 else
4162 {
4163 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4164 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4165 }
4166 }
4167 res->m[i]=p;
4168 }
4169 //else
4170 // res->m[i]=NULL;
4171 }
4172 /*- release temp data------------------------------- -*/
4173 assume(strat->L==NULL); /* strat->L unused */
4174 assume(strat->B==NULL); /* strat->B unused */
4175 omFree(strat->sevS);
4176 omFree(strat->ecartS);
4177 assume(strat->T==NULL);//omfree(strat->T);
4178 assume(strat->sevT==NULL);//omfree(strat->sevT);
4179 assume(strat->R==NULL);//omfree(strat->R);
4180 omfree(strat->S_2_R);
4181 omfree(strat->fromQ);
4182 strat->fromQ=NULL;
4183 idDelete(&strat->Shdl);
4184 SI_RESTORE_OPT1(save1);
4185 if (TEST_OPT_PROT) PrintLn();
4186 return res;
4187}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
intset ecartS
Definition kutil.h:309
LSet B
Definition kutil.h:328
CanonicalForm res
Definition facAbsFact.cc:60
#define idDelete(H)
delete an ideal
Definition ideals.h:29
#define KSTD_NF_LAZY
Definition kstd1.h:17
#define KSTD_NF_NONORM
Definition kstd1.h:21
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition kstd2.cc:2315
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7588
poly redtailBba_NF(poly p, kStrategy strat)
Definition kutil.cc:7352
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8888
#define omfree(addr)
#define omFree(addr)
VAR unsigned si_opt_1
Definition options.c:5
#define OPT_INTSTRATEGY
Definition options.h:93
#define OPT_REDTAIL
Definition options.h:92
#define Sy_bit(x)
Definition options.h:31
#define pCopy(p)
return a copy of the poly
Definition polys.h:185
#define mflush()
Definition reporter.h:58
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:405
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:416

◆ kNF2() [2/2]

poly kNF2 ( ideal F,
ideal Q,
poly q,
kStrategy strat,
int lazyReduce )

Definition at line 3942 of file kstd2.cc.

3943{
3944 assume(q!=NULL);
3945 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3946
3947// lazy_reduce flags: can be combined by |
3948//#define KSTD_NF_LAZY 1
3949 // do only a reduction of the leading term
3950//#define KSTD_NF_NONORM 4
3951 // only global: avoid normalization, return a multiply of NF
3952//#define KSTD_NF_NOLF 8
3953 // avoid PrintLn with OPT_PROT
3954
3955 poly p;
3956
3957 //if ((idIs0(F))&&(Q==NULL))
3958 // return pCopy(q); /*F=0*/
3959 //strat->ak = idRankFreeModule(F);
3960 /*- creating temp data structures------------------- -*/
3961 BITSET save1;
3962 SI_SAVE_OPT1(save1);
3964 initBuchMoraCrit(strat);
3965 strat->initEcart = initEcartBBA;
3966#ifdef HAVE_SHIFTBBA
3967 if (rIsLPRing(currRing))
3968 {
3969 strat->enterS = enterSBbaShift;
3970 }
3971 else
3972#endif
3973 {
3974 strat->enterS = enterSBba;
3975 }
3976#ifndef NO_BUCKETS
3978#endif
3979 /*- set S -*/
3980 strat->sl = -1;
3981 /*- init local data struct.---------------------------------------- -*/
3982 /*Shdl=*/initS(F,Q,strat);
3983 /*- compute------------------------------------------------------- -*/
3984 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3985 //{
3986 // for (i=strat->sl;i>=0;i--)
3987 // pNorm(strat->S[i]);
3988 //}
3989 kTest(strat);
3990 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3991 if (BVERBOSE(23)) kDebugPrint(strat);
3992 int max_ind;
3993 p = redNF(pCopy(q),max_ind,(lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
3994 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3995 {
3996 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3998 {
3999 p = redtailBba_NF(p,strat);
4000 }
4001 else if (rField_is_Ring(currRing))
4002 {
4003 p = redtailBba_Ring(p,max_ind,strat);
4004 }
4005 else
4006 {
4007 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4008 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4009 }
4010 }
4011 /*- release temp data------------------------------- -*/
4012 assume(strat->L==NULL); /* strat->L unused */
4013 assume(strat->B==NULL); /* strat->B unused */
4014 omFree(strat->sevS);
4015 omFree(strat->ecartS);
4016 assume(strat->T==NULL);//omfree(strat->T);
4017 assume(strat->sevT==NULL);//omfree(strat->sevT);
4018 assume(strat->R==NULL);//omfree(strat->R);
4019 omfree(strat->S_2_R);
4020 omfree(strat->fromQ);
4021 strat->fromQ=NULL;
4022 idDelete(&strat->Shdl);
4023 SI_RESTORE_OPT1(save1);
4024 if (TEST_OPT_PROT && ((lazyReduce &KSTD_NF_NOLF)==0)) PrintLn();
4025 return p;
4026}
KINLINE poly redtailBba_Ring(poly p, int pos, kStrategy strat)
Definition kInline.h:1221
#define KSTD_NF_NOLF
Definition kstd1.h:23
BOOLEAN kTest(kStrategy strat)
Definition kutil.cc:1010
static BOOLEAN rField_is_Zn(const ring r)
Definition ring.h:517

◆ kNF2Bound() [1/2]

ideal kNF2Bound ( ideal F,
ideal Q,
ideal q,
int bound,
kStrategy strat,
int lazyReduce )

Definition at line 4189 of file kstd2.cc.

4190{
4191 assume(!idIs0(q));
4192 assume(!(idIs0(F)&&(Q==NULL)));
4193// lazy_reduce flags: can be combined by |
4194//#define KSTD_NF_LAZY 1
4195 // do only a reduction of the leading term
4196//#define KSTD_NF_NONORM 4
4197 // only global: avoid normalization, return a multiply of NF
4198 poly p;
4199 int i;
4200 ideal res;
4201 int max_ind;
4202
4203 //if (idIs0(q))
4204 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4205 //if ((idIs0(F))&&(Q==NULL))
4206 // return idCopy(q); /*F=0*/
4207 //strat->ak = idRankFreeModule(F);
4208 /*- creating temp data structures------------------- -*/
4209 BITSET save1;
4210 SI_SAVE_OPT1(save1);
4212 initBuchMoraCrit(strat);
4213 strat->initEcart = initEcartBBA;
4214 strat->enterS = enterSBba;
4215 /*- set S -*/
4216 strat->sl = -1;
4217#ifndef NO_BUCKETS
4219#endif
4220 /*- init local data struct.---------------------------------------- -*/
4221 /*Shdl=*/initS(F,Q,strat);
4222 /*- compute------------------------------------------------------- -*/
4223 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4224 for (i=IDELEMS(q)-1; i>=0; i--)
4225 {
4226 if (q->m[i]!=NULL)
4227 {
4228 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4229 p = redNFBound(pCopy(q->m[i]),max_ind,
4230 (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat,bound);
4231 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4232 {
4233 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4235 {
4236 p = redtailBba_Z(p,max_ind,strat);
4237 }
4238 else if (rField_is_Ring(currRing))
4239 {
4240 p = redtailBba_Ring(p,max_ind,strat);
4241 }
4242 else
4243 {
4244 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4245 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4246 }
4247 }
4248 res->m[i]=p;
4249 }
4250 //else
4251 // res->m[i]=NULL;
4252 }
4253 /*- release temp data------------------------------- -*/
4254 assume(strat->L==NULL); /* strat->L unused */
4255 assume(strat->B==NULL); /* strat->B unused */
4256 omFree(strat->sevS);
4257 omFree(strat->ecartS);
4258 assume(strat->T==NULL);//omfree(strat->T);
4259 assume(strat->sevT==NULL);//omfree(strat->sevT);
4260 assume(strat->R==NULL);//omfree(strat->R);
4261 omfree(strat->S_2_R);
4262 omfree(strat->fromQ);
4263 strat->fromQ=NULL;
4264 idDelete(&strat->Shdl);
4265 SI_RESTORE_OPT1(save1);
4266 if (TEST_OPT_PROT) PrintLn();
4267 return res;
4268}
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
KINLINE poly redtailBbaBound(poly p, int pos, kStrategy strat, int bound, BOOLEAN normalize)
Definition kInline.h:1215
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
Definition kInline.h:1226
poly redNFBound(poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
Definition kstd2.cc:2511

◆ kNF2Bound() [2/2]

poly kNF2Bound ( ideal F,
ideal Q,
poly q,
int bound,
kStrategy strat,
int lazyReduce )

Definition at line 4028 of file kstd2.cc.

4029{
4030 assume(q!=NULL);
4031 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
4032
4033// lazy_reduce flags: can be combined by |
4034//#define KSTD_NF_LAZY 1
4035 // do only a reduction of the leading term
4036//#define KSTD_NF_NONORM 4
4037 // only global: avoid normalization, return a multiply of NF
4038 poly p;
4039
4040 //if ((idIs0(F))&&(Q==NULL))
4041 // return pCopy(q); /*F=0*/
4042 //strat->ak = idRankFreeModule(F);
4043 /*- creating temp data structures------------------- -*/
4044 BITSET save1;
4045 SI_SAVE_OPT1(save1);
4047 initBuchMoraCrit(strat);
4048 strat->initEcart = initEcartBBA;
4049 strat->enterS = enterSBba;
4050#ifndef NO_BUCKETS
4052#endif
4053 /*- set S -*/
4054 strat->sl = -1;
4055 /*- init local data struct.---------------------------------------- -*/
4056 /*Shdl=*/initS(F,Q,strat);
4057 /*- compute------------------------------------------------------- -*/
4058 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
4059 //{
4060 // for (i=strat->sl;i>=0;i--)
4061 // pNorm(strat->S[i]);
4062 //}
4063 kTest(strat);
4064 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
4065 if (BVERBOSE(23)) kDebugPrint(strat);
4066 int max_ind;
4067 p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
4068 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4069 {
4070 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4072 {
4073 p = redtailBba_Z(p,max_ind,strat);
4074 }
4075 else if (rField_is_Ring(currRing))
4076 {
4077 p = redtailBba_Ring(p,max_ind,strat);
4078 }
4079 else
4080 {
4081 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4082 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4083 //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4084 }
4085 }
4086 /*- release temp data------------------------------- -*/
4087 assume(strat->L==NULL); /* strat->L unused */
4088 assume(strat->B==NULL); /* strat->B unused */
4089 omFree(strat->sevS);
4090 omFree(strat->ecartS);
4091 assume(strat->T==NULL);//omfree(strat->T);
4092 assume(strat->sevT==NULL);//omfree(strat->sevT);
4093 assume(strat->R==NULL);//omfree(strat->R);
4094 omfree(strat->S_2_R);
4095 omfree(strat->fromQ);
4096 strat->fromQ=NULL;
4097 idDelete(&strat->Shdl);
4098 SI_RESTORE_OPT1(save1);
4099 if (TEST_OPT_PROT) PrintLn();
4100 return p;
4101}

◆ ksReducePolyTailSig()

KINLINE int ksReducePolyTailSig ( LObject * PR,
TObject * PW,
LObject * Red,
kStrategy strat )

Definition at line 1335 of file kstd2.cc.

1336{
1337 BOOLEAN ret;
1338 number coef;
1339 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1341 Red->HeadNormalize();
1342 /*
1343 printf("------------------------\n");
1344 pWrite(Red->GetLmCurrRing());
1345 */
1347 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1348 else
1349 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1350 if (!ret)
1351 {
1352 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1353 {
1354 PR->Mult_nn(coef);
1355 // HANNES: mark for Normalize
1356 }
1357 n_Delete(&coef, currRing->cf);
1358 }
1359 return ret;
1360}
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:459
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:472
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:737
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:943

◆ kTestDivisibleByT0_Z()

int kTestDivisibleByT0_Z ( const kStrategy strat,
const LObject * L )

tests if T[0] divides the leading monomial of L, returns -1 if not

Definition at line 146 of file kstd2.cc.

147{
148 if (strat->tl < 1)
149 return -1;
150
151 unsigned long not_sev = ~L->sev;
152 const unsigned long sevT0 = strat->sevT[0];
153 number orest,rest,mult;
154 if (L->p!=NULL)
155 {
156 const poly T0p = strat->T[0].p;
157 const ring r = currRing;
158 const poly p = L->p;
159 orest = pGetCoeff(p);
160
161 pAssume(~not_sev == p_GetShortExpVector(p, r));
162
163#if defined(PDEBUG) || defined(PDIV_DEBUG)
164 if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
165#else
166 if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
167#endif
168 {
169 if (n_QuotRem!=ndQuotRem) /*euclidean ring*/
170 {
171 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
172 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
173 {
174 n_Delete(&mult,r->cf);
175 n_Delete(&rest,r->cf);
176 return 0;
177 }
178 n_Delete(&mult,r->cf);
179 n_Delete(&rest,r->cf);
180 }
181 }
182 }
183 else
184 {
185 const poly T0p = strat->T[0].t_p;
186 const ring r = strat->tailRing;
187 const poly p = L->t_p;
188 orest = pGetCoeff(p);
189#if defined(PDEBUG) || defined(PDIV_DEBUG)
190 if (p_LmShortDivisibleBy(T0p, sevT0,
191 p, not_sev, r))
192#else
193 if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
194#endif
195 {
196 if (n_QuotRem!=ndQuotRem) /*euclidean ring*/
197 {
198 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
199 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
200 {
201 n_Delete(&mult,r->cf);
202 n_Delete(&rest,r->cf);
203 return 0;
204 }
205 n_Delete(&mult,r->cf);
206 n_Delete(&rest,r->cf);
207 }
208 }
209 }
210 return -1;
211}
number ndQuotRem(number a, number b, number *r, const coeffs R)
Definition numbers.cc:350

◆ redFirstShift()

int redFirstShift ( LObject * h,
kStrategy strat )

Definition at line 4970 of file kstd2.cc.

4971{
4972 if (h->IsNull()) return 0;
4973
4974 int at, reddeg,d;
4975 int pass = 0;
4976 int j = 0;
4977
4978 if (! strat->homog)
4979 {
4980 d = h->GetpFDeg() + h->ecart;
4981 reddeg = strat->LazyDegree+d;
4982 }
4983 h->SetShortExpVector();
4984 loop
4985 {
4986 j = kFindDivisibleByInT(strat, h);
4987 if (j < 0)
4988 {
4989 h->SetDegStuffReturnLDeg(strat->LDegLast);
4990 return 1;
4991 }
4992
4994 strat->T[j].pNorm();
4995#ifdef KDEBUG
4996 if (TEST_OPT_DEBUG)
4997 {
4998 PrintS("reduce ");
4999 h->wrp();
5000 PrintS(" with ");
5001 strat->T[j].wrp();
5002 }
5003#endif
5004 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
5005
5006#ifdef KDEBUG
5007 if (TEST_OPT_DEBUG)
5008 {
5009 PrintS("\nto ");
5010 wrp(h->p);
5011 PrintLn();
5012 }
5013#endif
5014 if (h->IsNull())
5015 {
5016 kDeleteLcm(h);
5017 h->Clear();
5018 return 0;
5019 }
5020 h->SetShortExpVector();
5021
5022#if 0
5023 if ((strat->syzComp!=0) && !strat->honey)
5024 {
5025 if ((strat->syzComp>0) &&
5026 (h->Comp() > strat->syzComp))
5027 {
5028 assume(h->MinComp() > strat->syzComp);
5029#ifdef KDEBUG
5030 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
5031#endif
5032 if (strat->homog)
5033 h->SetDegStuffReturnLDeg(strat->LDegLast);
5034 return -2;
5035 }
5036 }
5037#endif
5038 if (!strat->homog)
5039 {
5040 if (!TEST_OPT_OLDSTD && strat->honey)
5041 {
5042 h->SetpFDeg();
5043 if (strat->T[j].ecart <= h->ecart)
5044 h->ecart = d - h->GetpFDeg();
5045 else
5046 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
5047
5048 d = h->GetpFDeg() + h->ecart;
5049 }
5050 else
5051 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
5052 /*- try to reduce the s-polynomial -*/
5053 pass++;
5054 /*
5055 *test whether the polynomial should go to the lazyset L
5056 *-if the degree jumps
5057 *-if the number of pre-defined reductions jumps
5058 */
5059 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
5060 && ((d >= reddeg) || (pass > strat->LazyPass)))
5061 {
5062 h->SetLmCurrRing();
5063 if (strat->posInLDependsOnLength)
5064 h->SetLength(strat->length_pLength);
5065 at = strat->posInL(strat->L,strat->Ll,h,strat);
5066 if (at <= strat->Ll)
5067 {
5068 //int dummy=strat->sl;
5069 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
5070 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
5071 if (kFindDivisibleByInT(strat, h) < 0)
5072 return 1;
5073 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
5074#ifdef KDEBUG
5075 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
5076#endif
5077 h->Clear();
5078 return -1;
5079 }
5080 }
5081 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
5082 {
5083 reddeg = d+1;
5084 Print(".%d",d);mflush();
5085 }
5086 }
5087 }
5088}
KINLINE poly kNoetherTail()
Definition kInline.h:66
char LDegLast
Definition kutil.h:383
char length_pLength
Definition kutil.h:385
#define Print
Definition emacs.cc:80
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition kspoly.cc:187
#define TEST_OPT_REDTHROUGH
Definition options.h:124
void wrp(poly p)
Definition polys.h:310

◆ redHomog()

int redHomog ( LObject * h,
kStrategy strat )

Definition at line 1154 of file kstd2.cc.

1155{
1156 if (strat->tl<0) return 1;
1157 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1158 assume(h->FDeg == h->pFDeg());
1159
1160 poly h_p;
1161 int i,j,at,pass,cnt,ii;
1162 // long reddeg,d;
1163 int li;
1164 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1165
1166 pass = j = 0;
1167 cnt = RED_CANONICALIZE;
1168 h->SetShortExpVector();
1169 h_p = h->GetLmTailRing();
1170 h->PrepareRed(strat->use_buckets);
1171 loop
1172 {
1173 j = kFindDivisibleByInT(strat, h);
1174 if (j < 0) return 1;
1175
1176 li = strat->T[j].pLength;
1177 ii = j;
1178 /*
1179 * the polynomial to reduce with (up to the moment) is;
1180 * pi with length li
1181 */
1182 i = j;
1183#if 1
1184 if (test_opt_length)
1185 {
1186 if (li<=0) li=strat->T[j].GetpLength();
1187 if (li>2)
1188 {
1189 unsigned long not_sev = ~ h->sev;
1190 loop
1191 {
1192 /*- search the shortest possible with respect to length -*/
1193 i++;
1194 if (i > strat->tl)
1195 break;
1196 if ((strat->T[i].pLength < li)
1197 &&
1198 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1199 h_p, not_sev, strat->tailRing))
1200 {
1201 /*
1202 * the polynomial to reduce with is now;
1203 */
1204 li = strat->T[i].pLength;
1205 if (li<=0) li=strat->T[i].GetpLength();
1206 ii = i;
1207 if (li<3) break;
1208 }
1209 }
1210 }
1211 }
1212#endif
1213
1214 /*
1215 * end of search: have to reduce with pi
1216 */
1217#ifdef KDEBUG
1218 if (TEST_OPT_DEBUG)
1219 {
1220 PrintS("red:");
1221 h->wrp();
1222 PrintS(" with ");
1223 strat->T[ii].wrp();
1224 }
1225#endif
1226 assume(strat->fromT == FALSE);
1227
1228 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1229#if SBA_PRINT_REDUCTION_STEPS
1230 sba_interreduction_steps++;
1231#endif
1232#if SBA_PRINT_OPERATIONS
1233 sba_interreduction_operations += pLength(strat->T[ii].p);
1234#endif
1235
1236#ifdef KDEBUG
1237 if (TEST_OPT_DEBUG)
1238 {
1239 PrintS("\nto ");
1240 h->wrp();
1241 PrintLn();
1242 }
1243#endif
1244
1245 h_p = h->GetLmTailRing();
1246 if (h_p == NULL)
1247 {
1248 kDeleteLcm(h);
1249 return 0;
1250 }
1252 {
1253 if (h->p!=NULL)
1254 {
1255 if(p_GetComp(h->p,currRing)>strat->syzComp)
1256 {
1257 h->Delete();
1258 return 0;
1259 }
1260 }
1261 else if (h->t_p!=NULL)
1262 {
1263 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1264 {
1265 h->Delete();
1266 return 0;
1267 }
1268 }
1269 }
1270 #if 0
1271 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1272 {
1273 if (h->p!=NULL)
1274 {
1275 if(p_GetComp(h->p,currRing)>strat->syzComp)
1276 {
1277 return 1;
1278 }
1279 }
1280 else if (h->t_p!=NULL)
1281 {
1282 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1283 {
1284 return 1;
1285 }
1286 }
1287 }
1288 #endif
1289 h->SetShortExpVector();
1290 /*
1291 * try to reduce the s-polynomial h
1292 *test first whether h should go to the lazyset L
1293 *-if the degree jumps
1294 *-if the number of pre-defined reductions jumps
1295 */
1296 cnt--;
1297 pass++;
1298 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1299 {
1300 h->SetLmCurrRing();
1301 at = strat->posInL(strat->L,strat->Ll,h,strat);
1302 if (at <= strat->Ll)
1303 {
1304#ifdef HAVE_SHIFTBBA
1305 if (rIsLPRing(currRing))
1306 {
1307 if (kFindDivisibleByInT(strat, h) < 0)
1308 return 1;
1309 }
1310 else
1311#endif
1312 {
1313 int dummy=strat->sl;
1314 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1315 return 1;
1316 }
1317 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1318#ifdef KDEBUG
1319 if (TEST_OPT_DEBUG)
1320 Print(" lazy: -> L%d\n",at);
1321#endif
1322 h->Clear();
1323 return -1;
1324 }
1325 }
1326 else if (UNLIKELY(cnt==0))
1327 {
1328 h->CanonicalizeP();
1329 cnt=RED_CANONICALIZE;
1330 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1331 }
1332 }
1333}
#define UNLIKELY(X)
Definition auxiliary.h:404
char fromT
Definition kutil.h:377
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition kstd2.cc:468
#define RED_CANONICALIZE
Definition kutil.h:36
#define p_GetComp(p, r)
Definition monomials.h:64
#define TEST_OPT_REDTAIL_SYZ
Definition options.h:119

◆ redHoney()

int redHoney ( LObject * h,
kStrategy strat )

Definition at line 2114 of file kstd2.cc.

2115{
2116 if (strat->tl<0) return 1;
2117 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
2118 assume(h->FDeg == h->pFDeg());
2119 poly h_p;
2120 int i,j,at,pass,ei, ii, h_d;
2121 long reddeg,d;
2122 int li;
2123 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
2124
2125 pass = j = 0;
2126 d = reddeg = h->GetpFDeg() + h->ecart;
2127 h->SetShortExpVector();
2128 h_p = h->GetLmTailRing();
2129
2130 h->PrepareRed(strat->use_buckets);
2131 loop
2132 {
2133 j=kFindDivisibleByInT_ecart(strat, h, h->ecart);
2134 if (j < 0) return 1;
2135
2136 ii = j;
2137 ei = strat->T[ii].ecart;
2138 /*
2139 * the polynomial to reduce with (up to the moment) is;
2140 * pi with ecart ei (T[ii])
2141 */
2142
2143 /*
2144 * end of search: have to reduce with pi
2145 */
2146 if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
2147 {
2148 h->GetTP(); // clears bucket
2149 h->SetLmCurrRing();
2150 /*
2151 * It is not possible to reduce h with smaller ecart;
2152 * if possible h goes to the lazy-set L,i.e
2153 * if its position in L would be not the last one
2154 */
2155 if (strat->Ll >= 0) /* L is not empty */
2156 {
2157 at = strat->posInL(strat->L,strat->Ll,h,strat);
2158 if(at <= strat->Ll)
2159 /*- h will not become the next element to reduce -*/
2160 {
2161 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2162#ifdef KDEBUG
2163 if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
2164#endif
2165 h->Clear();
2166 return -1;
2167 }
2168 }
2169 }
2170#ifdef KDEBUG
2171 if (TEST_OPT_DEBUG)
2172 {
2173 PrintS("red:");
2174 h->wrp();
2175 Print("\nwith T[%d]:",ii);
2176 strat->T[ii].wrp();
2177 }
2178#endif
2179 assume(strat->fromT == FALSE);
2180
2181 ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
2182#if SBA_PRINT_REDUCTION_STEPS
2183 sba_interreduction_steps++;
2184#endif
2185#if SBA_PRINT_OPERATIONS
2186 sba_interreduction_operations += strat->T[ii].pLength;
2187#endif
2188#ifdef KDEBUG
2189 if (TEST_OPT_DEBUG)
2190 {
2191 PrintS("\nto:");
2192 h->wrp();
2193 PrintLn();
2194 }
2195#endif
2196 if(h->IsNull())
2197 {
2198 kDeleteLcm(h);
2199 h->Clear();
2200 return 0;
2201 }
2203 {
2204 if (h->p!=NULL)
2205 {
2206 if(p_GetComp(h->p,currRing)>strat->syzComp)
2207 {
2208 h->Delete();
2209 return 0;
2210 }
2211 }
2212 else if (h->t_p!=NULL)
2213 {
2214 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2215 {
2216 h->Delete();
2217 return 0;
2218 }
2219 }
2220 }
2221 else
2222 if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
2223 {
2224 if (h->p!=NULL)
2225 {
2226 if(p_GetComp(h->p,currRing)>strat->syzComp)
2227 {
2228 return 1;
2229 }
2230 }
2231 else if (h->t_p!=NULL)
2232 {
2233 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2234 {
2235 return 1;
2236 }
2237 }
2238 }
2239 h->SetShortExpVector();
2240 h_d = h->SetpFDeg();
2241 /* compute the ecart */
2242 if (ei <= h->ecart)
2243 h->ecart = d-h_d;
2244 else
2245 h->ecart = d-h_d+ei-h->ecart;
2246
2247 /*
2248 * try to reduce the s-polynomial h
2249 *test first whether h should go to the lazyset L
2250 *-if the degree jumps
2251 *-if the number of pre-defined reductions jumps
2252 */
2253 pass++;
2254 d = h_d + h->ecart;
2256 && (strat->Ll >= 0)
2257 && ((d > reddeg) || (pass > strat->LazyPass))))
2258 {
2259 h->GetTP(); // clear bucket
2260 h->SetLmCurrRing();
2261 at = strat->posInL(strat->L,strat->Ll,h,strat);
2262 if (at <= strat->Ll)
2263 {
2264#ifdef HAVE_SHIFTBBA
2265 if (rIsLPRing(currRing))
2266 {
2267 if (kFindDivisibleByInT(strat, h) < 0)
2268 return 1;
2269 }
2270 else
2271#endif
2272 {
2273 int dummy=strat->sl;
2274 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2275 return 1;
2276 }
2277 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2278#ifdef KDEBUG
2279 if (TEST_OPT_DEBUG)
2280 Print(" degree jumped: -> L%d\n",at);
2281#endif
2282 h->Clear();
2283 return -1;
2284 }
2285 }
2286 else if (d > reddeg)
2287 {
2288 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2289 {
2290 if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2291 {
2292 strat->overflow=TRUE;
2293 //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2294 h->GetP();
2295 at = strat->posInL(strat->L,strat->Ll,h,strat);
2296 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2297 h->Clear();
2298 return -1;
2299 }
2300 }
2301 else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
2302 {
2303 //h->wrp(); Print("<%d>\n",h->GetpLength());
2304 reddeg = d;
2305 Print(".%ld",d); mflush();
2306 }
2307 }
2308 }
2309}
int kFindDivisibleByInT_ecart(const kStrategy strat, const LObject *L, const int ecart)
Definition kstd2.cc:420

◆ redLazy()

int redLazy ( LObject * h,
kStrategy strat )

TEST_OPT_REDTHROUGH &&

Definition at line 1909 of file kstd2.cc.

1910{
1911 if (strat->tl<0) return 1;
1912 int at,i,ii,li;
1913 int j = 0;
1914 int pass = 0;
1915 int cnt = RED_CANONICALIZE;
1916 assume(h->pFDeg() == h->FDeg);
1917 long reddeg = h->GetpFDeg();
1918 long d;
1919 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1920
1921 h->SetShortExpVector();
1922 poly h_p = h->GetLmTailRing();
1923 h->PrepareRed(strat->use_buckets);
1924 loop
1925 {
1926 j = kFindDivisibleByInT(strat, h);
1927 if (j < 0) return 1;
1928
1929 li = strat->T[j].pLength;
1930 ii = j;
1931 /*
1932 * the polynomial to reduce with (up to the moment) is;
1933 * pi with length li
1934 */
1935
1936 i = j;
1937#if 1
1938 if (test_opt_length)
1939 {
1940 if (li<=0) li=strat->T[j].GetpLength();
1941 if(li>2)
1942 {
1943 unsigned long not_sev = ~ h->sev;
1944 loop
1945 {
1946 /*- search the shortest possible with respect to length -*/
1947 i++;
1948 if (i > strat->tl)
1949 break;
1950 if ((strat->T[i].pLength < li)
1951 &&
1952 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1953 h_p, not_sev, strat->tailRing))
1954 {
1955 /*
1956 * the polynomial to reduce with is now;
1957 */
1958 li = strat->T[i].pLength;
1959 if (li<=0) li=strat->T[i].GetpLength();
1960 ii = i;
1961 if (li<3) break;
1962 }
1963 }
1964 }
1965 }
1966#endif
1967
1968 /*
1969 * end of search: have to reduce with pi
1970 */
1971
1972
1973#ifdef KDEBUG
1974 if (TEST_OPT_DEBUG)
1975 {
1976 PrintS("red:");
1977 h->wrp();
1978 PrintS(" with ");
1979 strat->T[ii].wrp();
1980 }
1981#endif
1982
1983 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1984#if SBA_PRINT_REDUCTION_STEPS
1985 sba_interreduction_steps++;
1986#endif
1987#if SBA_PRINT_OPERATIONS
1988 sba_interreduction_operations += pLength(strat->T[ii].p);
1989#endif
1990
1991#ifdef KDEBUG
1992 if (TEST_OPT_DEBUG)
1993 {
1994 PrintS("\nto ");
1995 h->wrp();
1996 PrintLn();
1997 }
1998#endif
1999
2000 h_p=h->GetLmTailRing();
2001
2002 if (h_p == NULL)
2003 {
2004 kDeleteLcm(h);
2005 return 0;
2006 }
2008 {
2009 if (h->p!=NULL)
2010 {
2011 if(p_GetComp(h->p,currRing)>strat->syzComp)
2012 {
2013 h->Delete();
2014 return 0;
2015 }
2016 }
2017 else if (h->t_p!=NULL)
2018 {
2019 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2020 {
2021 h->Delete();
2022 return 0;
2023 }
2024 }
2025 }
2026 #if 0
2027 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
2028 {
2029 if (h->p!=NULL)
2030 {
2031 if(p_GetComp(h->p,currRing)>strat->syzComp)
2032 {
2033 return 1;
2034 }
2035 }
2036 else if (h->t_p!=NULL)
2037 {
2038 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2039 {
2040 return 1;
2041 }
2042 }
2043 }
2044 #endif
2045 h->SetShortExpVector();
2046 d = h->SetpFDeg();
2047 /*- try to reduce the s-polynomial -*/
2048 cnt--;
2049 pass++;
2050 if (//!TEST_OPT_REDTHROUGH &&
2051 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
2052 {
2053 h->SetLmCurrRing();
2054 at = strat->posInL(strat->L,strat->Ll,h,strat);
2055 if (at <= strat->Ll)
2056 {
2057#if 1
2058#ifdef HAVE_SHIFTBBA
2059 if (rIsLPRing(currRing))
2060 {
2061 if (kFindDivisibleByInT(strat, h) < 0)
2062 return 1;
2063 }
2064 else
2065#endif
2066 {
2067 int dummy=strat->sl;
2068 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2069 return 1;
2070 }
2071#endif
2072#ifdef KDEBUG
2073 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
2074#endif
2075 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2076 h->Clear();
2077 return -1;
2078 }
2079 }
2080 else if (d != reddeg)
2081 {
2082 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2083 {
2084 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
2085 {
2086 strat->overflow=TRUE;
2087 //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2088 h->GetP();
2089 at = strat->posInL(strat->L,strat->Ll,h,strat);
2090 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2091 h->Clear();
2092 return -1;
2093 }
2094 }
2095 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
2096 {
2097 Print(".%ld",d);mflush();
2098 reddeg = d;
2099 }
2100 }
2101 else if (UNLIKELY(cnt==0))
2102 {
2103 h->CanonicalizeP();
2104 cnt=RED_CANONICALIZE;
2105 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
2106 }
2107 }
2108}

◆ redNF()

poly redNF ( poly h,
int & max_ind,
int nonorm,
kStrategy strat )

Definition at line 2315 of file kstd2.cc.

2316{
2317 if (h==NULL) return NULL;
2318 int j,j_ring;
2319 int cnt=REDNF_CANONICALIZE;
2320 max_ind=strat->sl;
2321
2322 if (0 > strat->sl)
2323 {
2324 return h;
2325 }
2326 LObject P(h);
2327 P.SetShortExpVector();
2328 P.t_p=NULL;
2329 BOOLEAN is_ring = rField_is_Ring(currRing);
2330 if(is_ring) nonorm=TRUE;
2331#ifdef KDEBUG
2332// if (TEST_OPT_DEBUG)
2333// {
2334// PrintS("redNF: starting S:\n");
2335// for( j = 0; j <= max_ind; j++ )
2336// {
2337// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2338// pWrite(strat->S[j]);
2339// }
2340// };
2341#endif
2342 if (rField_is_Z(currRing))
2343 {
2344 redRing_Z_S(&P,strat);
2345 if (P.bucket!=NULL)
2346 {
2347 P.p=kBucketClear(P.bucket);
2348 kBucketDestroy(&P.bucket);
2349 }
2350 return P.p;
2351 }
2352 else if (rField_is_Ring(currRing))
2353 {
2354 redRing_S(&P,strat);
2355 if (P.bucket!=NULL)
2356 {
2357 P.p=kBucketClear(P.bucket);
2358 kBucketDestroy(&P.bucket);
2359 }
2360 return P.p;
2361 }
2362
2363 P.bucket = kBucketCreate(currRing);
2364 kBucketInit(P.bucket,P.p,pLength(P.p));
2365 kbTest(P.bucket);
2366 P.p=kBucketGetLm(P.bucket);
2367 loop
2368 {
2369 j_ring=j=kFindDivisibleByInS_noCF(strat,&max_ind,&P);
2370 while ((j>=0)
2371 && (nonorm)
2372 && (!n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[j]),currRing->cf)))
2373 j=kFindNextDivisibleByInS(strat,j+1,max_ind,&P);
2374 if (j>=0)
2375 {
2376 int sl=pSize(strat->S[j]);
2377 int jj=j;
2378 loop
2379 {
2380 int sll;
2381 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2382 if (jj<0) break;
2383 if ((!nonorm)
2384 || (n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[jj]),currRing->cf)))
2385 {
2386 sll=pSize(strat->S[jj]);
2387 if (sll<sl)
2388 {
2389 #ifdef KDEBUG
2390 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2391 #endif
2392 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2393 j=jj;
2394 sl=sll;
2395 }
2396 }
2397 }
2398 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2399 {
2400 pNorm(strat->S[j]);
2401 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2402 }
2403 nNormalize(pGetCoeff(P.p));
2404#ifdef KDEBUG
2405 if (TEST_OPT_DEBUG)
2406 {
2407 PrintS("red:");
2408 wrp(P.p);
2409 PrintS(" with ");
2410 wrp(strat->S[j]);
2411 }
2412#endif
2413#ifdef HAVE_PLURAL
2415 {
2416 number coef;
2417 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
2418 nDelete(&coef);
2419 }
2420 else
2421#endif
2422 {
2423 kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),
2424 strat->kNoether);
2425 }
2426 cnt--;
2427 if (cnt==0)
2428 {
2429 kBucketCanonicalize(P.bucket);
2431 }
2432 P.p=kBucketGetLm(P.bucket);
2433 //P.t_p=NULL;
2434#ifdef KDEBUG
2435 if (TEST_OPT_DEBUG)
2436 {
2437 PrintS("\nto:");
2438 wrp(P.p);
2439 PrintLn();
2440 }
2441#endif
2442 if (P.p==NULL)
2443 {
2444 kBucketDestroy(&P.bucket);
2445 return NULL;
2446 }
2447 kbTest(P.bucket);
2448 P.SetShortExpVector();
2449 }
2450 else if (is_ring && (j_ring>=0) && (currRing->cf->cfQuotRem!=ndQuotRem))
2451 {
2452 number r;
2453 number n=n_QuotRem(pGetCoeff(P.p),pGetCoeff(strat->S[j_ring]),&r,currRing->cf);
2454 if(!n_IsZero(n,currRing->cf))
2455 {
2456 poly lm=kBucketGetLm(P.bucket);
2457 poly m=p_Head(lm,currRing);
2458 p_ExpVectorSub(m,strat->S[j_ring],currRing);
2459 if (p_GetComp(strat->S[j_ring], currRing) != p_GetComp(lm, currRing))
2460 {
2462 }
2464 p_Setm(m,currRing);
2465#ifdef KDEBUG
2466 if (TEST_OPT_DEBUG)
2467 {
2468 PrintS("redi (coeff):");
2469 wrp(P.p);
2470 PrintS(" with ");
2471 wrp(strat->S[j]);
2472 }
2473#endif
2474 int l=-1;
2475 kBucket_Minus_m_Mult_p(P.bucket,m,strat->S[j_ring],&l);
2476 P.p=kBucketGetLm(P.bucket);
2478#ifdef KDEBUG
2479 if (TEST_OPT_DEBUG)
2480 {
2481 PrintS("\nto:");
2482 wrp(P.p);
2483 PrintLn();
2484 }
2485#endif
2486 }
2487 else
2488 {
2489 n_Delete(&n,currRing->cf);
2490 }
2491 n_Delete(&r,currRing->cf);
2492 P.p=kBucketClear(P.bucket);
2493 kBucketDestroy(&P.bucket);
2494 pNormalize(P.p);
2495 return P.p;
2496 }
2497 else
2498 {
2499 P.p=kBucketClear(P.bucket);
2500 kBucketDestroy(&P.bucket);
2501 pNormalize(P.p);
2502 return P.p;
2503 }
2504 }
2505}
int l
Definition cfEzgcd.cc:100
int m
Definition cfEzgcd.cc:128
poly kNoether
Definition kutil.h:329
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition kbuckets.cc:197
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition kbuckets.cc:722
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
void kBucketPolyRedNF(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition kbuckets.cc:1188
const poly kBucketGetLm(kBucket_pt bucket)
Definition kbuckets.cc:506
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition kstd2.cc:571
int kFindDivisibleByInS_noCF(const kStrategy strat, int *max_ind, LObject *L)
Definition kstd2.cc:531
static int redRing_S(LObject *h, kStrategy strat)
Definition kstd2.cc:1094
static int redRing_Z_S(LObject *h, kStrategy strat)
Definition kstd2.cc:882
#define REDNF_CANONICALIZE
Definition kutil.h:37
static void nc_kBucketPolyRed_NF(kBucket_pt b, poly p, number *c, BOOLEAN reduce)
Definition nc.h:275
#define nDelete(n)
Definition numbers.h:16
#define nIsOne(n)
Definition numbers.h:25
#define nNormalize(n)
Definition numbers.h:30
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition p_polys.h:1454
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:412
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition p_polys.h:860
void pNorm(poly p)
Definition polys.h:362
#define pNormalize(p)
Definition polys.h:317
#define pSize(p)
Definition polys.h:318

◆ redNFBound()

poly redNFBound ( poly h,
int & max_ind,
int nonorm,
kStrategy strat,
int bound )

Definition at line 2511 of file kstd2.cc.

2512{
2513 h = pJet(h,bound);
2514 if (h==NULL) return NULL;
2515 int j;
2516 max_ind=strat->sl;
2517
2518 if (0 > strat->sl)
2519 {
2520 return h;
2521 }
2522 LObject P(h);
2523 P.SetShortExpVector();
2524 P.bucket = kBucketCreate(currRing);
2525 kBucketInit(P.bucket,P.p,pLength(P.p));
2526 kbTest(P.bucket);
2527 BOOLEAN is_ring = rField_is_Ring(currRing);
2528
2529 loop
2530 {
2531 j=kFindDivisibleByInS(strat,&max_ind,&P);
2532 if (j>=0)
2533 {
2534 if (!is_ring)
2535 {
2536 int sl=pSize(strat->S[j]);
2537 int jj=j;
2538 loop
2539 {
2540 int sll;
2541 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2542 if (jj<0) break;
2543 sll=pSize(strat->S[jj]);
2544 if (sll<sl)
2545 {
2546 #ifdef KDEBUG
2547 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2548 #endif
2549 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2550 j=jj;
2551 sl=sll;
2552 }
2553 }
2554 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2555 {
2556 pNorm(strat->S[j]);
2557 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2558 }
2559 }
2560 nNormalize(pGetCoeff(P.p));
2561#ifdef KDEBUG
2562 if (TEST_OPT_DEBUG)
2563 {
2564 PrintS("red:");
2565 wrp(h);
2566 PrintS(" with ");
2567 wrp(strat->S[j]);
2568 }
2569#endif
2570#ifdef HAVE_PLURAL
2572 {
2573 number coef;
2574 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
2575 nDelete(&coef);
2576 }
2577 else
2578#endif
2579 {
2580 kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2581 P.p = kBucketClear(P.bucket);
2582 P.p = pJet(P.p,bound);
2583 if(!P.IsNull())
2584 {
2585 kBucketDestroy(&P.bucket);
2586 P.SetShortExpVector();
2587 P.bucket = kBucketCreate(currRing);
2588 kBucketInit(P.bucket,P.p,pLength(P.p));
2589 }
2590 }
2591 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2592 if (h==NULL)
2593 {
2594 kBucketDestroy(&P.bucket);
2595 return NULL;
2596 }
2597 kbTest(P.bucket);
2598 P.p=h;
2599 P.t_p=NULL;
2600 P.SetShortExpVector();
2601#ifdef KDEBUG
2602 if (TEST_OPT_DEBUG)
2603 {
2604 PrintS("\nto:");
2605 wrp(h);
2606 PrintLn();
2607 }
2608#endif
2609 }
2610 else
2611 {
2612 P.p=kBucketClear(P.bucket);
2613 kBucketDestroy(&P.bucket);
2614 pNormalize(P.p);
2615 return P.p;
2616 }
2617 }
2618}
#define pJet(p, m)
Definition polys.h:367

◆ redRing()

int redRing ( LObject * h,
kStrategy strat )

Definition at line 992 of file kstd2.cc.

993{
994 if (strat->tl<0) return 1;
995 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
996
997 int at/*,i*/;
998 long d;
999 int j = 0;
1000 int pass = 0;
1001 // poly zeroPoly = NULL;
1002
1003// TODO warum SetpFDeg notwendig?
1004 h->SetpFDeg();
1005 assume(h->pFDeg() == h->FDeg);
1006 long reddeg = h->GetpFDeg();
1007
1008 h->SetShortExpVector();
1009 loop
1010 {
1011 j = kFindDivisibleByInT(strat, h);
1012 if (j < 0)
1013 {
1014 // over ZZ: cleanup coefficients by complete reduction with monomials
1015 postReduceByMon(h, strat);
1016 if(h->p == NULL)
1017 {
1018 kDeleteLcm(h);
1019 h->Clear();
1020 return 0;
1021 }
1022 if(nIsZero(pGetCoeff(h->p))) return 2;
1023 j = kFindDivisibleByInT(strat, h);
1024 if(j < 0)
1025 {
1026 if(strat->tl >= 0)
1027 h->i_r1 = strat->tl;
1028 else
1029 h->i_r1 = -1;
1030 if (h->GetLmTailRing() == NULL)
1031 {
1032 kDeleteLcm(h);
1033 h->Clear();
1034 return 0;
1035 }
1036 return 1;
1037 }
1038 }
1039 //printf("\nFound one: ");pWrite(strat->T[j].p);
1040 //enterT(*h, strat);
1041 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
1042 //printf("\nAfter small red: ");pWrite(h->p);
1043 if (h->GetLmTailRing() == NULL)
1044 {
1045 kDeleteLcm(h);
1046 h->Clear();
1047 return 0;
1048 }
1049 h->SetShortExpVector();
1050 d = h->SetpFDeg();
1051 /*- try to reduce the s-polynomial -*/
1052 pass++;
1053 if (!TEST_OPT_REDTHROUGH &&
1054 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1055 {
1056 h->SetLmCurrRing();
1057 if (strat->posInLDependsOnLength)
1058 h->SetLength(strat->length_pLength);
1059 at = strat->posInL(strat->L,strat->Ll,h,strat);
1060 if (at <= strat->Ll)
1061 {
1062#ifdef KDEBUG
1063 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1064#endif
1065 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
1066 h->Clear();
1067 return -1;
1068 }
1069 }
1070 if (d != reddeg)
1071 {
1072 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1073 {
1074 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1075 {
1076 strat->overflow=TRUE;
1077 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1078 h->GetP();
1079 at = strat->posInL(strat->L,strat->Ll,h,strat);
1080 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1081 h->Clear();
1082 return -1;
1083 }
1084 }
1085 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1086 {
1087 Print(".%ld",d);mflush();
1088 reddeg = d;
1089 }
1090 }
1091 }
1092}
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition kutil.cc:10703

◆ redRing_S()

static int redRing_S ( LObject * h,
kStrategy strat )
static

Definition at line 1094 of file kstd2.cc.

1095{
1096 if (strat->sl<0) return 1;
1097 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
1098
1099 int j = 0;
1100 int pass = 0;
1101 // poly zeroPoly = NULL;
1102
1103 h->SetpFDeg();
1104 assume(h->pFDeg() == h->FDeg);
1105 int max_ind;
1106
1107 h->SetShortExpVector();
1108 loop
1109 {
1110 max_ind=strat->sl;
1111 j = kFindDivisibleByInS(strat, &max_ind, h);
1112 if (j < 0)
1113 {
1114 // over ZZ: cleanup coefficients by complete reduction with monomials
1115 postReduceByMon(h, strat);
1116 if(h->p == NULL)
1117 {
1118 h->Clear();
1119 return 0;
1120 }
1121 if(nIsZero(pGetCoeff(h->p))) return 2;
1122 max_ind=strat->sl;
1123 j = kFindDivisibleByInS(strat, &max_ind,h);
1124 if(j < 0)
1125 {
1126 if (h->GetLmTailRing() == NULL)
1127 {
1128 h->Clear();
1129 return 0;
1130 }
1131 return 1;
1132 }
1133 }
1134 //printf("\nFound one: ");pWrite(strat->T[j].p);
1135 //enterT(*h, strat);
1136 TObject tj(strat->S[j]);
1137 ksReducePoly(h, &tj, NULL, NULL, NULL, strat); // with debug output
1138 //printf("\nAfter small red: ");pWrite(h->p);
1139 if (h->GetLmTailRing() == NULL)
1140 {
1141 h->Clear();
1142 return 0;
1143 }
1144 h->SetShortExpVector();
1145 /*- try to reduce the s-polynomial -*/
1146 pass++;
1147 }
1148}
class sTObject TObject
Definition kutil.h:57

◆ redRing_Z()

int redRing_Z ( LObject * h,
kStrategy strat )

Definition at line 724 of file kstd2.cc.

725{
726 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
727 if (strat->tl<0) return 1;
728
729 int at;
730 long d;
731 int j = 0;
732 int pass = 0;
733
734// TODO warum SetpFDeg notwendig?
735 h->SetpFDeg();
736 assume(h->pFDeg() == h->FDeg);
737 long reddeg = h->GetpFDeg();
738
739 h->SetShortExpVector();
740 loop
741 {
742 /* check if a reducer of the lead term exists */
743 j = kFindDivisibleByInT(strat, h);
744 if (j < 0)
745 {
746#if STDZ_EXCHANGE_DURING_REDUCTION
747 /* check if a reducer with the same lead monomial exists */
748 j = kFindSameLMInT_Z(strat, h);
749 if (j < 0)
750 {
751#endif
752 /* check if a reducer of the lead monomial exists, by the above
753 * check this is a real divisor of the lead monomial */
754 j = kFindDivisibleByInT_Z(strat, h);
755 if (j < 0)
756 {
757 // over ZZ: cleanup coefficients by complete reduction with monomials
759 postReduceByMon(h, strat);
760 if(h->p == NULL)
761 {
762 if (h->lcm!=NULL) pLmDelete(h->lcm);
763 h->Clear();
764 return 0;
765 }
766 if(nIsZero(pGetCoeff(h->p))) return 2;
767 j = kFindDivisibleByInT(strat, h);
768 if(j < 0)
769 {
770 if(strat->tl >= 0)
771 h->i_r1 = strat->tl;
772 else
773 h->i_r1 = -1;
774 if (h->GetLmTailRing() == NULL)
775 {
776 if (h->lcm!=NULL) pLmDelete(h->lcm);
777 h->Clear();
778 return 0;
779 }
780 return 1;
781 }
782 }
783 else
784 {
785 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
786 * => we try to cut down the lead coefficient at least */
787 /* first copy T[j] in order to multiply it with a coefficient later on */
788 number mult, rest;
789 TObject tj = strat->T[j];
790 tj.Copy();
791 /* tj.max_exp = strat->T[j].max_exp; */
792 /* compute division with remainder of lc(h) and lc(T[j]) */
793 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
794 &rest, currRing->cf);
795 /* set corresponding new lead coefficient already. we do not
796 * remove the lead term in ksReducePolyLC, but only apply
797 * a lead coefficient reduction */
798 tj.Mult_nn(mult);
799 ksReducePolyLC(h, &tj, NULL, &rest, strat);
800 tj.Delete();
801 tj.Clear();
802 }
803#if STDZ_EXCHANGE_DURING_REDUCTION
804 }
805 else
806 {
807 /* same lead monomial but lead coefficients do not divide each other:
808 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
809 LObject h2 = *h;
810 h2.Copy();
811
812 ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
813 ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
815 {
816 redtailBbaAlsoLC_Z(&h2, j, strat);
817 }
818 /* replace h2 for tj in L (already generated pairs with tj), S and T */
819 replaceInLAndSAndT(h2, j, strat);
820 }
821#endif
822 }
823 else
824 {
825 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat);
826 }
827 /* printf("\nAfter small red: ");pWrite(h->p); */
828 if (h->GetLmTailRing() == NULL)
829 {
830 if (h->lcm!=NULL) pLmDelete(h->lcm);
831#ifdef KDEBUG
832 h->lcm=NULL;
833#endif
834 h->Clear();
835 return 0;
836 }
837 h->SetShortExpVector();
838 d = h->SetpFDeg();
839 /*- try to reduce the s-polynomial -*/
840 pass++;
841 if (!TEST_OPT_REDTHROUGH &&
842 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
843 {
844 h->SetLmCurrRing();
845 if (strat->posInLDependsOnLength)
846 h->SetLength(strat->length_pLength);
847 at = strat->posInL(strat->L,strat->Ll,h,strat);
848 if (at <= strat->Ll)
849 {
850#ifdef KDEBUG
851 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
852#endif
853 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
854 h->Clear();
855 return -1;
856 }
857 }
858 if (d != reddeg)
859 {
860 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
861 {
862 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
863 {
864 strat->overflow=TRUE;
865 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
866 h->GetP();
867 at = strat->posInL(strat->L,strat->Ll,h,strat);
868 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
869 h->Clear();
870 return -1;
871 }
872 }
873 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
874 {
875 Print(".%ld",d);mflush();
876 reddeg = d;
877 }
878 }
879 }
880}
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start)
Definition kstd2.cc:213
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition kutil.cc:9046
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start=0)
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)

◆ redRing_Z_S()

static int redRing_Z_S ( LObject * h,
kStrategy strat )
static

Definition at line 882 of file kstd2.cc.

883{
884 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
885 if (strat->sl<0) return 1;
886
887 int j = 0;
888 int pass = 0;
889
890// TODO warum SetpFDeg notwendig?
891 h->SetpFDeg();
892 assume(h->pFDeg() == h->FDeg);
893 h->SetShortExpVector();
894 int max_ind=strat->sl;
895
896 loop
897 {
898 /* check if a reducer of the lead term exists */
899 max_ind=strat->sl;
900 j = kFindDivisibleByInS(strat,&max_ind, h);
901 if (j < 0)
902 {
903#if STDZ_EXCHANGE_DURING_REDUCTION
904 /* check if a reducer with the same lead monomial exists */
905 j = kFindSameLMInT_Z(strat, h);
906 if (j < 0)
907 {
908#endif
909 /* check if a reducer of the lead monomial exists, by the above
910 * check this is a real divisor of the lead monomial */
911 j = kFindDivisibleByInS_Z(strat, h);
912 if (j < 0)
913 {
914 // over ZZ: cleanup coefficients by complete reduction with monomials
916 postReduceByMon(h, strat);
917 if(h->p == NULL)
918 {
919 h->Clear();
920 return 0;
921 }
922 if(nIsZero(pGetCoeff(h->p))) return 2;
923 max_ind=strat->sl;
924 j = kFindDivisibleByInS(strat, &max_ind, h);
925 if(j < 0)
926 {
927 if (h->GetLmTailRing() == NULL)
928 {
929 h->Clear();
930 return 0;
931 }
932 return 1;
933 }
934 }
935 else
936 {
937 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
938 * => we try to cut down the lead coefficient at least */
939 /* first copy T[j] in order to multiply it with a coefficient later on */
940 number mult, rest;
941 TObject tj(pCopy(strat->S[j]));
942 /* compute division with remainder of lc(h) and lc(S[j]) */
943 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->S[j]),
944 &rest, currRing->cf);
945 /* set corresponding new lead coefficient already. we do not
946 * remove the lead term in ksReducePolyLC, but only apply
947 * a lead coefficient reduction */
948 tj.Mult_nn(mult);
949 ksReducePolyLC(h, &tj, NULL, &rest, strat);
950 tj.Delete();
951 tj.Clear();
952 }
953#if STDZ_EXCHANGE_DURING_REDUCTION
954 }
955 else
956 {
957 /* same lead monomial but lead coefficients do not divide each other:
958 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
959 LObject h2 = *h;
960 h2.Copy();
961 TObject tj(strat->S[j]);
962
963 ksReducePolyZ(h, &tj, NULL, NULL, strat);
964 ksReducePolyGCD(&h2, &tj, NULL, NULL, strat);
966 {
967 redtailBbaAlsoLC_Z_S(&h2, j, strat);
968 }
969 /* replace h2 for tj in L (already generated pairs with tj), S and T */
970 replaceInLAndSAndT(h2, j, strat);
971 }
972#endif
973 }
974 else
975 {
976 TObject tj(strat->S[j]);
977 ksReducePoly(h, &tj, NULL, NULL, NULL, strat);
978 }
979 /* printf("\nAfter small red: ");pWrite(h->p); */
980 if (h->GetLmCurrRing() == NULL)
981 {
982 h->Clear();
983 return 0;
984 }
985 h->SetShortExpVector();
986 h->SetpFDeg();
987 /*- try to reduce the s-polynomial -*/
988 pass++;
989 }
990}
static int kFindDivisibleByInS_Z(const kStrategy strat, LObject *L)
Definition kstd2.cc:276

◆ redSig()

int redSig ( LObject * h,
kStrategy strat )

Definition at line 1373 of file kstd2.cc.

1374{
1375 if (strat->tl<0) return 1;
1376 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1377 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1378 assume(h->FDeg == h->pFDeg());
1379//#if 1
1380#ifdef DEBUGF5
1381 PrintS("------- IN REDSIG -------\n");
1382 Print("p: ");
1383 pWrite(pHead(h->p));
1384 PrintS("p1: ");
1385 pWrite(pHead(h->p1));
1386 PrintS("p2: ");
1387 pWrite(pHead(h->p2));
1388 PrintS("---------------------------\n");
1389#endif
1390 poly h_p;
1391 int i,j,at,pass, ii;
1392 int start=0;
1393 int sigSafe;
1394 unsigned long not_sev;
1395 // long reddeg,d;
1396 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1397 int li;
1398
1399 pass = j = 0;
1400 h->SetShortExpVector();
1401 h_p = h->GetLmTailRing();
1402 not_sev = ~ h->sev;
1403 loop
1404 {
1405 j = kFindDivisibleByInT(strat, h, start);
1406 if (j < 0)
1407 {
1408 return 1;
1409 }
1410
1411 li = strat->T[j].pLength;
1412 if (li<=0) li=strat->T[j].GetpLength();
1413 ii = j;
1414 /*
1415 * the polynomial to reduce with (up to the moment) is;
1416 * pi with length li
1417 */
1418 i = j;
1419#if 1
1420 if (test_opt_length)
1421 loop
1422 {
1423 /*- search the shortest possible with respect to length -*/
1424 i++;
1425 if (i > strat->tl)
1426 break;
1427 if (li==1)
1428 break;
1429 if ((strat->T[i].pLength < li)
1430 &&
1431 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1432 h_p, not_sev, strat->tailRing))
1433 {
1434 /*
1435 * the polynomial to reduce with is now;
1436 */
1437 li = strat->T[i].pLength;
1438 if (li<=0) li=strat->T[i].GetpLength();
1439 ii = i;
1440 }
1441 }
1442 start = ii+1;
1443#endif
1444
1445 /*
1446 * end of search: have to reduce with pi
1447 */
1448#ifdef KDEBUG
1449 if (TEST_OPT_DEBUG)
1450 {
1451 PrintS("red:");
1452 h->wrp();
1453 PrintS(" with ");
1454 strat->T[ii].wrp();
1455 }
1456#endif
1457 assume(strat->fromT == FALSE);
1458//#if 1
1459#ifdef DEBUGF5
1460 Print("BEFORE REDUCTION WITH %d:\n",ii);
1461 PrintS("--------------------------------\n");
1462 pWrite(h->sig);
1463 pWrite(strat->T[ii].sig);
1464 pWrite(h->GetLmCurrRing());
1465 pWrite(pHead(h->p1));
1466 pWrite(pHead(h->p2));
1467 pWrite(pHead(strat->T[ii].p));
1468 PrintS("--------------------------------\n");
1469 printf("INDEX OF REDUCER T: %d\n",ii);
1470#endif
1471 sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1472#if SBA_PRINT_REDUCTION_STEPS
1473 if (sigSafe != 3)
1474 sba_reduction_steps++;
1475#endif
1476#if SBA_PRINT_OPERATIONS
1477 if (sigSafe != 3)
1478 sba_operations += pLength(strat->T[ii].p);
1479#endif
1480 // if reduction has taken place, i.e. the reduction was sig-safe
1481 // otherwise start is already at the next position and the loop
1482 // searching reducers in T goes on from index start
1483//#if 1
1484#ifdef DEBUGF5
1485 Print("SigSAFE: %d\n",sigSafe);
1486#endif
1487 if (sigSafe != 3)
1488 {
1489 // start the next search for reducers in T from the beginning
1490 start = 0;
1491#ifdef KDEBUG
1492 if (TEST_OPT_DEBUG)
1493 {
1494 PrintS("\nto ");
1495 h->wrp();
1496 PrintLn();
1497 }
1498#endif
1499
1500 h_p = h->GetLmTailRing();
1501 if (h_p == NULL)
1502 {
1503 kDeleteLcm(h);
1504 return 0;
1505 }
1506 h->SetShortExpVector();
1507 not_sev = ~ h->sev;
1508 /*
1509 * try to reduce the s-polynomial h
1510 *test first whether h should go to the lazyset L
1511 *-if the degree jumps
1512 *-if the number of pre-defined reductions jumps
1513 */
1514 pass++;
1515 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1516 {
1517 h->SetLmCurrRing();
1518 at = strat->posInL(strat->L,strat->Ll,h,strat);
1519 if (at <= strat->Ll)
1520 {
1521 int dummy=strat->sl;
1522 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1523 {
1524 return 1;
1525 }
1526 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1527#ifdef KDEBUG
1528 if (TEST_OPT_DEBUG)
1529 Print(" lazy: -> L%d\n",at);
1530#endif
1531 h->Clear();
1532 return -1;
1533 }
1534 }
1535 }
1536 }
1537}

◆ redSigRing()

int redSigRing ( LObject * h,
kStrategy strat )

Definition at line 1540 of file kstd2.cc.

1541{
1542 //Since reduce is really bad for SBA we use the following idea:
1543 // We first check if we can build a gcd pair between h and S
1544 //where the sig remains the same and replace h by this gcd poly
1546 #if GCD_SBA
1547 while(sbaCheckGcdPair(h,strat))
1548 {
1549 h->sev = pGetShortExpVector(h->p);
1550 }
1551 #endif
1552 poly beforeredsig;
1553 beforeredsig = pCopy(h->sig);
1554
1555 if (strat->tl<0) return 1;
1556 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1557 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1558 assume(h->FDeg == h->pFDeg());
1559//#if 1
1560#ifdef DEBUGF5
1561 Print("------- IN REDSIG -------\n");
1562 Print("p: ");
1563 pWrite(pHead(h->p));
1564 Print("p1: ");
1565 pWrite(pHead(h->p1));
1566 Print("p2: ");
1567 pWrite(pHead(h->p2));
1568 Print("---------------------------\n");
1569#endif
1570 poly h_p;
1571 int i,j,at,pass, ii;
1572 int start=0;
1573 int sigSafe;
1574 unsigned long not_sev;
1575 // long reddeg,d;
1576 int li;
1577 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1578
1579 pass = j = 0;
1580 h->SetShortExpVector();
1581 h_p = h->GetLmTailRing();
1582 not_sev = ~ h->sev;
1583 loop
1584 {
1585 j = kFindDivisibleByInT(strat, h, start);
1586 if (j < 0)
1587 {
1588 #if GCD_SBA
1589 while(sbaCheckGcdPair(h,strat))
1590 {
1591 h->sev = pGetShortExpVector(h->p);
1592 h->is_redundant = FALSE;
1593 start = 0;
1594 }
1595 #endif
1596 // over ZZ: cleanup coefficients by complete reduction with monomials
1597 postReduceByMonSig(h, strat);
1598 if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
1599 j = kFindDivisibleByInT(strat, h,start);
1600 if(j < 0)
1601 {
1602 if(strat->tl >= 0)
1603 h->i_r1 = strat->tl;
1604 else
1605 h->i_r1 = -1;
1606 if (h->GetLmTailRing() == NULL)
1607 {
1608 kDeleteLcm(h);
1609 h->Clear();
1610 return 0;
1611 }
1612 //Check for sigdrop after reduction
1613 if(pLtCmp(beforeredsig,h->sig) == 1)
1614 {
1615 strat->sigdrop = TRUE;
1616 //Reduce it as much as you can
1617 int red_result = redRing(h,strat);
1618 if(red_result == 0)
1619 {
1620 //It reduced to 0, cancel the sigdrop
1621 strat->sigdrop = FALSE;
1622 p_Delete(&h->sig,currRing);h->sig = NULL;
1623 return 0;
1624 }
1625 else
1626 {
1627 //strat->enterS(*h, strat->sl+1, strat, strat->tl);
1628 return 0;
1629 }
1630 }
1631 p_Delete(&beforeredsig,currRing);
1632 return 1;
1633 }
1634 }
1635
1636 li = strat->T[j].pLength;
1637 if (li<=0) li=strat->T[j].GetpLength();
1638 ii = j;
1639 /*
1640 * the polynomial to reduce with (up to the moment) is;
1641 * pi with length li
1642 */
1643 i = j;
1644 if (test_opt_length)
1645 loop
1646 {
1647 /*- search the shortest possible with respect to length -*/
1648 i++;
1649 if (i > strat->tl)
1650 break;
1651 if (li==1)
1652 break;
1653 if ((strat->T[i].pLength < li)
1654 && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1655 && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1656 h_p, not_sev, strat->tailRing))
1657 {
1658 /*
1659 * the polynomial to reduce with is now;
1660 */
1661 li = strat->T[i].pLength;
1662 if (li<=0) li=strat->T[i].GetpLength();
1663 ii = i;
1664 }
1665 }
1666
1667 start = ii+1;
1668
1669 /*
1670 * end of search: have to reduce with pi
1671 */
1672#ifdef KDEBUG
1673 if (TEST_OPT_DEBUG)
1674 {
1675 PrintS("red:");
1676 h->wrp();
1677 PrintS(" with ");
1678 strat->T[ii].wrp();
1679 }
1680#endif
1681 assume(strat->fromT == FALSE);
1682//#if 1
1683#ifdef DEBUGF5
1684 Print("BEFORE REDUCTION WITH %d:\n",ii);
1685 Print("--------------------------------\n");
1686 pWrite(h->sig);
1687 pWrite(strat->T[ii].sig);
1688 pWrite(h->GetLmCurrRing());
1689 pWrite(pHead(h->p1));
1690 pWrite(pHead(h->p2));
1691 pWrite(pHead(strat->T[ii].p));
1692 Print("--------------------------------\n");
1693 printf("INDEX OF REDUCER T: %d\n",ii);
1694#endif
1695 sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1696 if(h->p == NULL && h->sig == NULL)
1697 {
1698 //Trivial case catch
1699 strat->sigdrop = FALSE;
1700 }
1701 #if 0
1702 //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1703 //In some cases this proves to be very bad
1704 if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1705 {
1706 int red_result = redRing(h,strat);
1707 if(red_result == 0)
1708 {
1709 pDelete(&h->sig);h->sig = NULL;
1710 return 0;
1711 }
1712 else
1713 {
1714 strat->sigdrop = TRUE;
1715 return 1;
1716 }
1717 }
1718 #endif
1719 if(strat->sigdrop)
1720 return 1;
1721#if SBA_PRINT_REDUCTION_STEPS
1722 if (sigSafe != 3)
1723 sba_reduction_steps++;
1724#endif
1725#if SBA_PRINT_OPERATIONS
1726 if (sigSafe != 3)
1727 sba_operations += pLength(strat->T[ii].p);
1728#endif
1729 // if reduction has taken place, i.e. the reduction was sig-safe
1730 // otherwise start is already at the next position and the loop
1731 // searching reducers in T goes on from index start
1732//#if 1
1733#ifdef DEBUGF5
1734 Print("SigSAFE: %d\n",sigSafe);
1735#endif
1736 if (sigSafe != 3)
1737 {
1738 // start the next search for reducers in T from the beginning
1739 start = 0;
1740#ifdef KDEBUG
1741 if (TEST_OPT_DEBUG)
1742 {
1743 PrintS("\nto ");
1744 h->wrp();
1745 PrintLn();
1746 }
1747#endif
1748
1749 h_p = h->GetLmTailRing();
1750 if (h_p == NULL)
1751 {
1752 kDeleteLcm(h);
1753 return 0;
1754 }
1755 h->SetShortExpVector();
1756 not_sev = ~ h->sev;
1757 /*
1758 * try to reduce the s-polynomial h
1759 *test first whether h should go to the lazyset L
1760 *-if the degree jumps
1761 *-if the number of pre-defined reductions jumps
1762 */
1763 pass++;
1764 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1765 {
1766 h->SetLmCurrRing();
1767 at = strat->posInL(strat->L,strat->Ll,h,strat);
1768 if (at <= strat->Ll)
1769 {
1770 int dummy=strat->sl;
1771 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1772 {
1773 return 1;
1774 }
1775 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1776#ifdef KDEBUG
1777 if (TEST_OPT_DEBUG)
1778 Print(" lazy: -> L%d\n",at);
1779#endif
1780 h->Clear();
1781 return -1;
1782 }
1783 }
1784 }
1785 }
1786}
bool sigdrop
Definition kutil.h:358
int redRing(LObject *h, kStrategy strat)
Definition kstd2.cc:992
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition kutil.cc:10779
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition kutil.cc:1693
#define pLtCmp(p, q)
Definition polys.h:123
#define pDelete(p_ptr)
Definition polys.h:186

◆ redtailSba()

poly redtailSba ( LObject * L,
int pos,
kStrategy strat,
BOOLEAN withT,
BOOLEAN normalize )

Definition at line 1789 of file kstd2.cc.

1790{
1791 strat->redTailChange=FALSE;
1792 if (strat->noTailReduction) return L->GetLmCurrRing();
1793 poly h, p;
1794 p = h = L->GetLmTailRing();
1795 if ((h==NULL) || (pNext(h)==NULL))
1796 return L->GetLmCurrRing();
1797
1798 TObject* With;
1799 // placeholder in case strat->tl < 0
1800 TObject With_s(strat->tailRing);
1801
1802 LObject Ln(pNext(h), strat->tailRing);
1803 Ln.sig = L->sig;
1804 Ln.sevSig = L->sevSig;
1805 Ln.pLength = L->GetpLength() - 1;
1806
1807 pNext(h) = NULL;
1808 if (L->p != NULL) pNext(L->p) = NULL;
1809 L->pLength = 1;
1810
1811 Ln.PrepareRed(strat->use_buckets);
1812
1813 int cnt=REDTAIL_CANONICALIZE;
1814 while(!Ln.IsNull())
1815 {
1816 loop
1817 {
1818 if(rField_is_Ring(currRing) && strat->sigdrop)
1819 break;
1820 Ln.SetShortExpVector();
1821 if (withT)
1822 {
1823 int j;
1824 j = kFindDivisibleByInT(strat, &Ln);
1825 if (j < 0) break;
1826 With = &(strat->T[j]);
1827 }
1828 else
1829 {
1830 With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1831 if (With == NULL) break;
1832 }
1833 cnt--;
1834 if (cnt==0)
1835 {
1837 /*poly tmp=*/Ln.CanonicalizeP();
1839 {
1840 Ln.Normalize();
1841 //pNormalize(tmp);
1842 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1843 }
1844 }
1846 {
1847 With->pNorm();
1848 }
1849 strat->redTailChange=TRUE;
1850 int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1852 L->sig = Ln.sig;
1853 //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1854 // I delete it an then set Ln.sig. Hence L->sig is lost
1855#if SBA_PRINT_REDUCTION_STEPS
1856 if (ret != 3)
1857 sba_reduction_steps++;
1858#endif
1859#if SBA_PRINT_OPERATIONS
1860 if (ret != 3)
1861 sba_operations += pLength(With->p);
1862#endif
1863 if (ret)
1864 {
1865 // reducing the tail would violate the exp bound
1866 // set a flag and hope for a retry (in bba)
1868 if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1869 do
1870 {
1871 pNext(h) = Ln.LmExtractAndIter();
1872 pIter(h);
1873 L->pLength++;
1874 } while (!Ln.IsNull());
1875 goto all_done;
1876 }
1877 if (Ln.IsNull()) goto all_done;
1878 if (! withT) With_s.Init(currRing);
1879 if(rField_is_Ring(currRing) && strat->sigdrop)
1880 {
1881 //Cannot break the loop here so easily
1882 break;
1883 }
1884 }
1885 pNext(h) = Ln.LmExtractAndIter();
1886 pIter(h);
1888 pNormalize(h);
1889 L->pLength++;
1890 }
1891 all_done:
1892 Ln.Delete();
1893 if (L->p != NULL) pNext(L->p) = pNext(p);
1894
1895 if (strat->redTailChange)
1896 {
1897 L->length = 0;
1898 }
1899 //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1900 //L->Normalize(); // HANNES: should have a test
1901 kTest_L(L,strat);
1902 return L->GetLmCurrRing();
1903}
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition kstd2.cc:1335
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition kutil.cc:6699
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:924
#define REDTAIL_CANONICALIZE
Definition kutil.h:38
#define pIter(p)
Definition monomials.h:37
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027

◆ rightgb()

ideal rightgb ( ideal F,
const ideal Q )

Definition at line 4954 of file kstd2.cc.

4955{
4957 assume(idIsInV(F));
4958 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4959 idSkipZeroes(RS); // is this even necessary?
4960 assume(idIsInV(RS));
4961 return(RS);
4962}
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition kstd1.cc:2982
#define idIsInV(I)
Definition shiftop.h:49
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
@ testHomog
Definition structs.h:38

◆ sba()

ideal sba ( ideal F0,
ideal Q,
intvec * w,
intvec * hilb,
kStrategy strat )

Definition at line 2980 of file kstd2.cc.

2981{
2982 // ring order stuff:
2983 // in sba we have (until now) two possibilities:
2984 // 1. an incremental computation w.r.t. (C,monomial order)
2985 // 2. a (possibly non-incremental) computation w.r.t. the
2986 // induced Schreyer order.
2987 // The corresponding orders are computed in sbaRing(), depending
2988 // on the flag strat->sbaOrder
2989#if SBA_PRINT_ZERO_REDUCTIONS
2990 long zeroreductions = 0;
2991#endif
2992#if SBA_PRINT_PRODUCT_CRITERION
2993 long product_criterion = 0;
2994#endif
2995#if SBA_PRINT_SIZE_G
2996 int size_g = 0;
2997 int size_g_non_red = 0;
2998#endif
2999#if SBA_PRINT_SIZE_SYZ
3000 long size_syz = 0;
3001#endif
3002 // global variable
3003#if SBA_PRINT_REDUCTION_STEPS
3004 sba_reduction_steps = 0;
3005 sba_interreduction_steps = 0;
3006#endif
3007#if SBA_PRINT_OPERATIONS
3008 sba_operations = 0;
3009 sba_interreduction_operations = 0;
3010#endif
3011
3012 ideal F1 = F0;
3013 ring sRing, currRingOld;
3014 currRingOld = currRing;
3015 if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
3016 {
3017 sRing = sbaRing(strat);
3018 if (sRing!=currRingOld)
3019 {
3020 rChangeCurrRing (sRing);
3021 F1 = idrMoveR (F0, currRingOld, currRing);
3022 }
3023 }
3024 ideal F;
3025 // sort ideal F
3026 //Put the SigDrop element on the correct position (think of sbaEnterS)
3027 //We also sort them
3028 if(rField_is_Ring(currRing) && strat->sigdrop)
3029 {
3030 #if 1
3031 F = idInit(IDELEMS(F1),F1->rank);
3032 for (int i=0; i<IDELEMS(F1);++i)
3033 F->m[i] = F1->m[i];
3034 if(strat->sbaEnterS >= 0)
3035 {
3036 poly dummy;
3037 dummy = pCopy(F->m[0]); //the sigdrop element
3038 for(int i = 0;i<strat->sbaEnterS;i++)
3039 F->m[i] = F->m[i+1];
3040 F->m[strat->sbaEnterS] = dummy;
3041 }
3042 #else
3043 F = idInit(1,F1->rank);
3044 //printf("\nBefore the initial block sorting:\n");idPrint(F1);
3045 F->m[0] = F1->m[0];
3046 int pos;
3047 if(strat->sbaEnterS >= 0)
3048 {
3049 for(int i=1;i<=strat->sbaEnterS;i++)
3050 {
3051 pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
3052 idInsertPolyOnPos(F,F1->m[i],pos);
3053 }
3054 for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
3055 {
3056 pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
3057 idInsertPolyOnPos(F,F1->m[i],pos);
3058 }
3059 poly dummy;
3060 dummy = pCopy(F->m[0]); //the sigdrop element
3061 for(int i = 0;i<strat->sbaEnterS;i++)
3062 F->m[i] = F->m[i+1];
3063 F->m[strat->sbaEnterS] = dummy;
3064 }
3065 else
3066 {
3067 for(int i=1;i<IDELEMS(F1);i++)
3068 {
3069 pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
3070 idInsertPolyOnPos(F,F1->m[i],pos);
3071 }
3072 }
3073 #endif
3074 //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
3075 }
3076 else
3077 {
3078 F = idInit(IDELEMS(F1),F1->rank);
3079 intvec *sort = idSort(F1);
3080 for (int i=0; i<sort->length();++i)
3081 F->m[i] = F1->m[(*sort)[i]-1];
3083 {
3084 // put the monomials after the sbaEnterS polynomials
3085 //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
3086 int nrmon = 0;
3087 for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
3088 {
3089 //pWrite(F->m[i]);
3090 if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
3091 {
3092 poly mon = F->m[i];
3093 for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
3094 {
3095 F->m[j] = F->m[j-1];
3096 }
3097 F->m[j] = mon;
3098 nrmon++;
3099 }
3100 //idPrint(F);
3101 }
3102 }
3103 }
3104 //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
3106 strat->sigdrop = FALSE;
3107 strat->nrsyzcrit = 0;
3108 strat->nrrewcrit = 0;
3109#if SBA_INTERRED_START
3110 F = kInterRed(F,NULL);
3111#endif
3112#if F5DEBUG
3113 printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
3114 rWrite (currRing);
3115 printf("ordSgn = %d\n",currRing->OrdSgn);
3116 printf("\n");
3117#endif
3118 int srmax,lrmax, red_result = 1;
3119 int olddeg,reduc;
3120 int hilbeledeg=1,hilbcount=0,minimcnt=0;
3121 LObject L;
3122 BOOLEAN withT = TRUE;
3123 strat->max_lower_index = 0;
3124 //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3125 initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
3126 initSbaPos(strat);
3127 initHilbCrit(F,Q,&hilb,strat);
3128 initSba(F,strat);
3129 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3130 /*Shdl=*/initSbaBuchMora(F, Q,strat);
3131 idTest(strat->Shdl);
3132 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
3133 srmax = strat->sl;
3134 reduc = olddeg = lrmax = 0;
3135#ifndef NO_BUCKETS
3137 strat->use_buckets = 1;
3138#endif
3139
3140 // redtailBBa against T for inhomogeneous input
3141 // if (!TEST_OPT_OLDSTD)
3142 // withT = ! strat->homog;
3143
3144 // strat->posInT = posInT_pLength;
3145 kTest_TS(strat);
3146
3147#ifdef HAVE_TAIL_RING
3148 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
3150#endif
3151 if (BVERBOSE(23))
3152 {
3153 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
3154 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
3155 kDebugPrint(strat);
3156 }
3157 // We add the elements directly in S from the previous loop
3158 if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
3159 {
3160 for(int i = 0;i<strat->sbaEnterS;i++)
3161 {
3162 //Update: now the element is at the correct place
3163 //i+1 because on the 0 position is the sigdrop element
3164 enterT(strat->L[strat->Ll-(i)],strat);
3165 strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
3166 }
3167 strat->Ll = strat->Ll - strat->sbaEnterS;
3168 strat->sbaEnterS = -1;
3169 }
3170 kTest_TS(strat);
3171#ifdef KDEBUG
3172 //kDebugPrint(strat);
3173#endif
3174 /* compute------------------------------------------------------- */
3175 while (strat->Ll >= 0)
3176 {
3177 if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
3178 #ifdef KDEBUG
3179 if (TEST_OPT_DEBUG) messageSets(strat);
3180 #endif
3181 if (strat->Ll== 0) strat->interpt=TRUE;
3182 /*
3183 if (TEST_OPT_DEGBOUND
3184 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3185 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
3186 {
3187
3188 //stops computation if
3189 // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
3190 //a predefined number Kstd1_deg
3191 while ((strat->Ll >= 0)
3192 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
3193 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3194 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
3195 )
3196 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
3197 if (strat->Ll<0) break;
3198 else strat->noClearS=TRUE;
3199 }
3200 */
3201 if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
3202 {
3203 strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
3204#if F5C
3205 // 1. interreduction of the current standard basis
3206 // 2. generation of new principal syzygy rules for syzCriterion
3207 f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
3208 lrmax, reduc, Q, w, hilb );
3209#endif
3210 // initialize new syzygy rules for the next iteration step
3211 initSyzRules(strat);
3212 }
3213 /*********************************************************************
3214 * interrreduction step is done, we can go on with the next iteration
3215 * step of the signature-based algorithm
3216 ********************************************************************/
3217 /* picks the last element from the lazyset L */
3218 strat->P = strat->L[strat->Ll];
3219 strat->Ll--;
3220
3222 strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
3223 /* reduction of the element chosen from L */
3224 if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
3225 {
3226 //#if 1
3227#ifdef DEBUGF5
3228 PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
3229 PrintS("-------------------------------------------------\n");
3230 pWrite(strat->P.sig);
3231 pWrite(pHead(strat->P.p));
3232 pWrite(pHead(strat->P.p1));
3233 pWrite(pHead(strat->P.p2));
3234 PrintS("-------------------------------------------------\n");
3235#endif
3236 if (pNext(strat->P.p) == strat->tail)
3237 {
3238 // deletes the short spoly
3239 /*
3240 if (rField_is_Ring(currRing))
3241 pLmDelete(strat->P.p);
3242 else
3243 pLmFree(strat->P.p);
3244*/
3245 // TODO: needs some masking
3246 // TODO: masking needs to vanish once the signature
3247 // sutff is completely implemented
3248 strat->P.p = NULL;
3249 poly m1 = NULL, m2 = NULL;
3250
3251 // check that spoly creation is ok
3252 while (strat->tailRing != currRing &&
3253 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3254 {
3255 assume(m1 == NULL && m2 == NULL);
3256 // if not, change to a ring where exponents are at least
3257 // large enough
3258 if (!kStratChangeTailRing(strat))
3259 {
3260 WerrorS("OVERFLOW...");
3261 break;
3262 }
3263 }
3264 // create the real one
3265 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3266 strat->tailRing, m1, m2, strat->R);
3267
3268 }
3269 else if (strat->P.p1 == NULL)
3270 {
3271 if (strat->minim > 0)
3272 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3273 // for input polys, prepare reduction
3275 strat->P.PrepareRed(strat->use_buckets);
3276 }
3277 if (strat->P.p == NULL && strat->P.t_p == NULL)
3278 {
3279 red_result = 0;
3280 }
3281 else
3282 {
3283 //#if 1
3284#ifdef DEBUGF5
3285 PrintS("Poly before red: ");
3286 pWrite(pHead(strat->P.p));
3287 pWrite(strat->P.sig);
3288#endif
3289#if SBA_PRODUCT_CRITERION
3290 if (strat->P.prod_crit)
3291 {
3292#if SBA_PRINT_PRODUCT_CRITERION
3293 product_criterion++;
3294#endif
3295 int pos = posInSyz(strat, strat->P.sig);
3296 enterSyz(strat->P, strat, pos);
3297 kDeleteLcm(&strat->P);
3298 red_result = 2;
3299 }
3300 else
3301 {
3302 red_result = strat->red(&strat->P,strat);
3303 }
3304#else
3305 red_result = strat->red(&strat->P,strat);
3306#endif
3307 }
3308 }
3309 else
3310 {
3311 /*
3312 if (strat->P.lcm != NULL)
3313 pLmFree(strat->P.lcm);
3314 */
3315 red_result = 2;
3316 }
3318 {
3319 if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3320 {
3321 strat->P.p = pNeg(strat->P.p);
3322 strat->P.sig = pNeg(strat->P.sig);
3323 }
3324 strat->P.pLength = pLength(strat->P.p);
3325 if(strat->P.sig != NULL)
3326 strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3327 if(strat->P.p != NULL)
3328 strat->P.sev = pGetShortExpVector(strat->P.p);
3329 }
3330 //sigdrop case
3331 if(rField_is_Ring(currRing) && strat->sigdrop)
3332 {
3333 //First reduce it as much as one can
3334 red_result = redRing(&strat->P,strat);
3335 if(red_result == 0)
3336 {
3337 strat->sigdrop = FALSE;
3338 pDelete(&strat->P.sig);
3339 strat->P.sig = NULL;
3340 }
3341 else
3342 {
3343 strat->enterS(strat->P, 0, strat, strat->tl);
3344 if (TEST_OPT_PROT)
3345 PrintS("-");
3346 break;
3347 }
3348 }
3349 if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3350 {
3351 strat->sigdrop = TRUE;
3352 break;
3353 }
3354
3355 if (errorreported) break;
3356
3357//#if 1
3358#ifdef DEBUGF5
3359 if (red_result != 0)
3360 {
3361 PrintS("Poly after red: ");
3362 pWrite(pHead(strat->P.p));
3363 pWrite(strat->P.GetLmCurrRing());
3364 pWrite(strat->P.sig);
3365 printf("%d\n",red_result);
3366 }
3367#endif
3368 if (TEST_OPT_PROT)
3369 {
3370 if(strat->P.p != NULL)
3371 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3372 &olddeg,&reduc,strat, red_result);
3373 else
3374 message((strat->honey ? strat->P.ecart : 0),
3375 &olddeg,&reduc,strat, red_result);
3376 }
3377
3378 if (strat->overflow)
3379 {
3380 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3381 }
3382 // reduction to non-zero new poly
3383 if (red_result == 1)
3384 {
3385 // get the polynomial (canonicalize bucket, make sure P.p is set)
3386 strat->P.GetP(strat->lmBin);
3387
3388 // sig-safe computations may lead to wrong FDeg computation, thus we need
3389 // to recompute it to make sure everything is alright
3390 (strat->P).FDeg = (strat->P).pFDeg();
3391 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3392 // but now, for entering S, T, we reset it
3393 // in the inhomogeneous case: FDeg == pFDeg
3394 if (strat->homog) strat->initEcart(&(strat->P));
3395
3396 /* statistic */
3397 if (TEST_OPT_PROT) PrintS("s");
3398
3399 //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3400 // in F5E we know that the last reduced element is already the
3401 // the one with highest signature
3402 int pos = strat->sl+1;
3403
3404 // reduce the tail and normalize poly
3405 // in the ring case we cannot expect LC(f) = 1,
3406 poly beforetailred;
3408 beforetailred = pCopy(strat->P.sig);
3409#if SBA_TAIL_RED
3411 {
3413 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3414 }
3415 else
3416 {
3417 if (strat->sbaOrder != 2)
3418 {
3420 {
3421 strat->P.pCleardenom();
3423 {
3424 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3425 strat->P.pCleardenom();
3426 }
3427 }
3428 else
3429 {
3430 strat->P.pNorm();
3432 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3433 }
3434 }
3435 }
3436 // It may happen that we have lost the sig in redtailsba
3437 // It cannot reduce to 0 since here we are doing just tail reduction.
3438 // Best case scenerio: remains the leading term
3439 if(rField_is_Ring(currRing) && strat->sigdrop)
3440 {
3441 strat->enterS(strat->P, 0, strat, strat->tl);
3442 break;
3443 }
3444#endif
3446 {
3447 if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
3448 {
3449 strat->sigdrop = TRUE;
3450 //Reduce it as much as you can
3451 red_result = redRing(&strat->P,strat);
3452 if(red_result == 0)
3453 {
3454 //It reduced to 0, cancel the sigdrop
3455 strat->sigdrop = FALSE;
3456 p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3457 }
3458 else
3459 {
3460 strat->enterS(strat->P, 0, strat, strat->tl);
3461 break;
3462 }
3463 }
3464 p_Delete(&beforetailred,currRing);
3465 // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3466 if(strat->P.p == NULL)
3467 goto case_when_red_result_changed;
3468 }
3469 // remove sigsafe label since it is no longer valid for the next element to
3470 // be reduced
3471 if (strat->sbaOrder == 1)
3472 {
3473 for (int jj = 0; jj<strat->tl+1; jj++)
3474 {
3475 if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3476 {
3477 strat->T[jj].is_sigsafe = FALSE;
3478 }
3479 }
3480 }
3481 else
3482 {
3483 for (int jj = 0; jj<strat->tl+1; jj++)
3484 {
3485 strat->T[jj].is_sigsafe = FALSE;
3486 }
3487 }
3488#ifdef KDEBUG
3489 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3490#endif /* KDEBUG */
3491
3492 // min_std stuff
3493 if ((strat->P.p1==NULL) && (strat->minim>0))
3494 {
3495 if (strat->minim==1)
3496 {
3497 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3498 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3499 }
3500 else
3501 {
3502 strat->M->m[minimcnt]=strat->P.p2;
3503 strat->P.p2=NULL;
3504 }
3505 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3506 pNext(strat->M->m[minimcnt])
3507 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3508 strat->tailRing, currRing,
3509 currRing->PolyBin);
3510 minimcnt++;
3511 }
3512
3513 // enter into S, L, and T
3514 //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3515 enterT(strat->P, strat);
3516 strat->T[strat->tl].is_sigsafe = FALSE;
3517 /*
3518 printf("hier\n");
3519 pWrite(strat->P.GetLmCurrRing());
3520 pWrite(strat->P.sig);
3521 */
3523 superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3524 else
3525 enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3526 if(rField_is_Ring(currRing) && strat->sigdrop)
3527 break;
3529 strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3530 strat->enterS(strat->P, pos, strat, strat->tl);
3531 if(strat->sbaOrder != 1)
3532 {
3533 BOOLEAN overwrite = FALSE;
3534 for (int tk=0; tk<strat->sl+1; tk++)
3535 {
3536 if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3537 {
3538 //printf("TK %d / %d\n",tk,strat->sl);
3539 overwrite = FALSE;
3540 break;
3541 }
3542 }
3543 //printf("OVERWRITE %d\n",overwrite);
3544 if (overwrite)
3545 {
3546 int cmp = pGetComp(strat->P.sig);
3547 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3548 p_GetExpV (strat->P.p,vv,currRing);
3549 p_SetExpV (strat->P.sig, vv,currRing);
3550 p_SetComp (strat->P.sig,cmp,currRing);
3551
3552 strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3553 int i;
3554 LObject Q;
3555 for(int ps=0;ps<strat->sl+1;ps++)
3556 {
3557
3558 strat->newt = TRUE;
3559 if (strat->syzl == strat->syzmax)
3560 {
3561 pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3562 strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3563 (strat->syzmax)*sizeof(unsigned long),
3564 ((strat->syzmax)+setmaxTinc)
3565 *sizeof(unsigned long));
3566 strat->syzmax += setmaxTinc;
3567 }
3568 Q.sig = pCopy(strat->P.sig);
3569 // add LM(F->m[i]) to the signature to get a Schreyer order
3570 // without changing the underlying polynomial ring at all
3571 if (strat->sbaOrder == 0)
3572 p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3573 // since p_Add_q() destroys all input
3574 // data we need to recreate help
3575 // each time
3576 // ----------------------------------------------------------
3577 // in the Schreyer order we always know that the multiplied
3578 // module monomial strat->P.sig gives the leading monomial of
3579 // the corresponding principal syzygy
3580 // => we do not need to compute the "real" syzygy completely
3581 poly help = p_Copy(strat->sig[ps],currRing);
3582 p_ExpVectorAdd (help,strat->P.p,currRing);
3583 Q.sig = p_Add_q(Q.sig,help,currRing);
3584 //printf("%d. SYZ ",i+1);
3585 //pWrite(strat->syz[i]);
3586 Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3587 i = posInSyz(strat, Q.sig);
3588 enterSyz(Q, strat, i);
3589 }
3590 }
3591 }
3592 // deg - idx - lp/rp
3593 // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3594 if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3595 {
3596 int cmp = pGetComp(strat->P.sig);
3597 unsigned max_cmp = IDELEMS(F);
3598 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3599 p_GetExpV (strat->P.p,vv,currRing);
3600 LObject Q;
3601 int pos;
3602 int idx = __p_GetComp(strat->P.sig,currRing);
3603 //printf("++ -- adding syzygies -- ++\n");
3604 // if new element is the first one in this index
3605 if (strat->currIdx < idx)
3606 {
3607 for (int i=0; i<strat->sl; ++i)
3608 {
3609 Q.sig = p_Copy(strat->P.sig,currRing);
3610 p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3611 poly help = p_Copy(strat->sig[i],currRing);
3612 p_ExpVectorAdd(help,strat->P.p,currRing);
3613 Q.sig = p_Add_q(Q.sig,help,currRing);
3614 //pWrite(Q.sig);
3615 pos = posInSyz(strat, Q.sig);
3616 enterSyz(Q, strat, pos);
3617 }
3618 strat->currIdx = idx;
3619 }
3620 else
3621 {
3622 // if the element is not the first one in the given index we build all
3623 // possible syzygies with elements of higher index
3624 for (unsigned i=cmp+1; i<=max_cmp; ++i)
3625 {
3626 pos = -1;
3627 for (int j=0; j<strat->sl; ++j)
3628 {
3629 if (__p_GetComp(strat->sig[j],currRing) == i)
3630 {
3631 pos = j;
3632 break;
3633 }
3634 }
3635 if (pos != -1)
3636 {
3637 Q.sig = p_One(currRing);
3638 p_SetExpV(Q.sig, vv, currRing);
3639 // F->m[i-1] corresponds to index i
3640 p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3641 p_SetComp(Q.sig, i, currRing);
3642 poly help = p_Copy(strat->P.sig,currRing);
3643 p_ExpVectorAdd(help,strat->S[pos],currRing);
3644 Q.sig = p_Add_q(Q.sig,help,currRing);
3645 if (strat->sbaOrder == 0)
3646 {
3647 if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3648 {
3649 pos = posInSyz(strat, Q.sig);
3650 enterSyz(Q, strat, pos);
3651 }
3652 }
3653 else
3654 {
3655 pos = posInSyz(strat, Q.sig);
3656 enterSyz(Q, strat, pos);
3657 }
3658 }
3659 }
3660 //printf("++ -- done adding syzygies -- ++\n");
3661 }
3662 }
3663//#if 1
3664#if DEBUGF50
3665 printf("---------------------------\n");
3666 Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3667 PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3668 PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3669#endif
3670 /*
3671 if (newrules)
3672 {
3673 newrules = FALSE;
3674 }
3675 */
3676#if 0
3677 int pl=pLength(strat->P.p);
3678 if (pl==1)
3679 {
3680 //if (TEST_OPT_PROT)
3681 //PrintS("<1>");
3682 }
3683 else if (pl==2)
3684 {
3685 //if (TEST_OPT_PROT)
3686 //PrintS("<2>");
3687 }
3688#endif
3689 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3690// Print("[%d]",hilbeledeg);
3691 kDeleteLcm(&strat->P);
3692 if (strat->sl>srmax) srmax = strat->sl;
3693 }
3694 else
3695 {
3696 case_when_red_result_changed:
3697 // adds signature of the zero reduction to
3698 // strat->syz. This is the leading term of
3699 // syzygy and can be used in syzCriterion()
3700 // the signature is added if and only if the
3701 // pair was not detected by the rewritten criterion in strat->red = redSig
3702 if (red_result!=2)
3703 {
3704#if SBA_PRINT_ZERO_REDUCTIONS
3705 zeroreductions++;
3706#endif
3707 if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3708 {
3709 //Catch the case when p = 0, sig = 0
3710 }
3711 else
3712 {
3713 int pos = posInSyz(strat, strat->P.sig);
3714 enterSyz(strat->P, strat, pos);
3715 //#if 1
3716 #ifdef DEBUGF5
3717 Print("ADDING STUFF TO SYZ : ");
3718 //pWrite(strat->P.p);
3719 pWrite(strat->P.sig);
3720 #endif
3721 }
3722 }
3723 if (strat->P.p1 == NULL && strat->minim > 0)
3724 {
3725 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3726 }
3727 }
3728
3729#ifdef KDEBUG
3730 strat->P.Init();
3731#endif /* KDEBUG */
3732 kTest_TS(strat);
3733 }
3734 #if 0
3735 if(strat->sigdrop)
3736 printf("\nSigDrop!\n");
3737 else
3738 printf("\nEnded with no SigDrop\n");
3739 #endif
3740// Clean strat->P for the next sba call
3741 if(rField_is_Ring(currRing) && strat->sigdrop)
3742 {
3743 //This is used to know how many elements can we directly add to S in the next run
3744 if(strat->P.sig != NULL)
3745 strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3746 //else we already set it at the beginning of the loop
3747 #ifdef KDEBUG
3748 strat->P.Init();
3749 #endif /* KDEBUG */
3750 }
3751#ifdef KDEBUG
3752 if (TEST_OPT_DEBUG) messageSets(strat);
3753#endif /* KDEBUG */
3754
3755 if (TEST_OPT_SB_1)
3756 {
3758 {
3759 int k=1;
3760 int j;
3761 while(k<=strat->sl)
3762 {
3763 j=0;
3764 loop
3765 {
3766 if (j>=k) break;
3767 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3768 j++;
3769 }
3770 k++;
3771 }
3772 }
3773 }
3774 /* complete reduction of the standard basis--------- */
3775 if (TEST_OPT_REDSB)
3776 {
3777 completeReduce(strat);
3778 if (strat->completeReduce_retry)
3779 {
3780 // completeReduce needed larger exponents, retry
3781 // to reduce with S (instead of T)
3782 // and in currRing (instead of strat->tailRing)
3783#ifdef HAVE_TAIL_RING
3784 if(currRing->bitmask>strat->tailRing->bitmask)
3785 {
3787 cleanT(strat);strat->tailRing=currRing;
3788 int i;
3789 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3790 completeReduce(strat);
3791 }
3792 if (strat->completeReduce_retry)
3793#endif
3794 Werror("exponent bound is %ld",currRing->bitmask);
3795 }
3796 }
3797 else if (TEST_OPT_PROT) PrintLn();
3798
3799#if SBA_PRINT_SIZE_SYZ
3800 // that is correct, syzl is counting one too far
3801 size_syz = strat->syzl;
3802#endif
3803// if (TEST_OPT_WEIGHTM)
3804// {
3805// pRestoreDegProcs(pFDegOld, pLDegOld);
3806// if (ecartWeights)
3807// {
3808// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3809// ecartWeights=NULL;
3810// }
3811// }
3812 if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3813 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3814#if SBA_PRINT_SIZE_G
3815 size_g_non_red = IDELEMS(strat->Shdl);
3816#endif
3818 exitSba(strat);
3819 // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3820 int k;
3822 {
3823 //for(k = strat->sl;k>=0;k--)
3824 // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3825 k = strat->Ll;
3826 #if 1
3827 // 1 - adds just the unused ones, 0 - adds everything
3828 for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3829 {
3830 //printf("\nDeleted k = %i, %p\n",k,strat->L[k].p);pWrite(strat->L[k].p);pWrite(strat->L[k].p1);pWrite(strat->L[k].p2);
3831 deleteInL(strat->L,&strat->Ll,k,strat);
3832 }
3833 #endif
3834 //for(int kk = strat->sl;kk>=0;kk--)
3835 // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3836 //idPrint(strat->Shdl);
3837 //printf("\nk = %i\n",k);
3838 for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3839 {
3840 //printf("\nAdded k = %i\n",k);
3841 strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3842 //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3843 }
3844 }
3845 // Find the "sigdrop element" and put the same signature as the previous one - do we really need this?? - now i put it on the 0 position - no more comparing needed
3846 #if 0
3847 if(strat->sigdrop && rField_is_Ring(currRing))
3848 {
3849 for(k=strat->sl;k>=0;k--)
3850 {
3851 printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3852 if(strat->sig[k] == NULL)
3853 strat->sig[k] = pCopy(strat->sig[k-1]);
3854 }
3855 }
3856 #endif
3857 //Never do this - you will damage S
3858 //idSkipZeroes(strat->Shdl);
3859 //idPrint(strat->Shdl);
3860
3861 if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3862 {
3863 rChangeCurrRing (currRingOld);
3864 F0 = idrMoveR (F1, sRing, currRing);
3865 strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3866 rChangeCurrRing (sRing);
3868 exitSba(strat);
3869 rChangeCurrRing (currRingOld);
3870 if(strat->tailRing == sRing)
3871 strat->tailRing = currRing;
3872 rDelete (sRing);
3873 }
3874 if(rField_is_Ring(currRing) && !strat->sigdrop)
3875 id_DelDiv(strat->Shdl, currRing);
3877 id_DelDiv(strat->Shdl, currRing);
3878 idSkipZeroes(strat->Shdl);
3879 idTest(strat->Shdl);
3880
3881#if SBA_PRINT_SIZE_G
3882 size_g = IDELEMS(strat->Shdl);
3883#endif
3884#ifdef DEBUGF5
3885 printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3886 int oo = 0;
3887 while (oo<IDELEMS(strat->Shdl))
3888 {
3889 printf(" %d. ",oo+1);
3890 pWrite(pHead(strat->Shdl->m[oo]));
3891 oo++;
3892 }
3893#endif
3894#if SBA_PRINT_ZERO_REDUCTIONS
3895 printf("----------------------------------------------------------\n");
3896 printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3897 zeroreductions = 0;
3898#endif
3899#if SBA_PRINT_REDUCTION_STEPS
3900 printf("----------------------------------------------------------\n");
3901 printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3902#endif
3903#if SBA_PRINT_OPERATIONS
3904 printf("OPERATIONS: %ld\n",sba_operations);
3905#endif
3906#if SBA_PRINT_REDUCTION_STEPS
3907 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3908 printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3909#endif
3910#if SBA_PRINT_OPERATIONS
3911 printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3912#endif
3913#if SBA_PRINT_REDUCTION_STEPS
3914 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3915 printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3916 sba_interreduction_steps = 0;
3917 sba_reduction_steps = 0;
3918#endif
3919#if SBA_PRINT_OPERATIONS
3920 printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3921 sba_interreduction_operations = 0;
3922 sba_operations = 0;
3923#endif
3924#if SBA_PRINT_SIZE_G
3925 printf("----------------------------------------------------------\n");
3926 printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3927 size_g = 0;
3928 size_g_non_red = 0;
3929#endif
3930#if SBA_PRINT_SIZE_SYZ
3931 printf("SIZE OF SYZ: %ld\n",size_syz);
3932 printf("----------------------------------------------------------\n");
3933 size_syz = 0;
3934#endif
3935#if SBA_PRINT_PRODUCT_CRITERION
3936 printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3937 product_criterion = 0;
3938#endif
3939 return (strat->Shdl);
3940}
static void sort(int **points, int sizePoints)
unsigned long * sevSyz
Definition kutil.h:323
int nrsyzcrit
Definition kutil.h:359
int nrrewcrit
Definition kutil.h:360
int syzmax
Definition kutil.h:349
int blockred
Definition kutil.h:363
int syzl
Definition kutil.h:349
unsigned sbaOrder
Definition kutil.h:316
int blockredmax
Definition kutil.h:364
polyset syz
Definition kutil.h:307
char newt
Definition kutil.h:399
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
int sbaEnterS
Definition kutil.h:361
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition ideals.h:187
ideal kInterRed(ideal F, const ideal Q)
Definition kstd1.cc:3809
void initSba(ideal F, kStrategy strat)
Definition kstd1.cc:1742
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition kstd2.cc:1789
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, intvec *hilb)
Definition kstd2.cc:4278
void initSbaPos(kStrategy strat)
Definition kutil.cc:9856
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9337
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4518
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4475
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
Definition kutil.cc:11081
void messageStatSBA(int hilbcount, kStrategy strat)
Definition kutil.cc:7519
void initSyzRules(kStrategy strat)
Definition kutil.cc:7929
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9958
int posInSyz(const kStrategy strat, poly sig)
Definition kutil.cc:5763
void exitSba(kStrategy strat)
Definition kutil.cc:10033
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
Definition kutil.cc:4846
void initSbaCrit(kStrategy strat)
Definition kutil.cc:9492
#define setmaxTinc
Definition kutil.h:34
#define help
Definition libparse.cc:1230
#define __p_GetComp(p, r)
Definition monomials.h:63
#define omAlloc(size)
#define omRealloc0Size(addr, o_size, size)
poly p_One(const ring r)
Definition p_polys.cc:1314
void pEnlargeSet(poly **p, int l, int increment)
Definition p_polys.cc:3717
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition p_polys.h:1425
static void p_SetExpV(poly p, int *ev, const ring r)
Definition p_polys.h:1558
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1594
static void p_GetExpV(poly p, int *ev, const ring r)
Definition p_polys.h:1534
void rChangeCurrRing(ring r)
Definition polys.cc:15
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:248
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:261
void rWrite(ring r, BOOLEAN details)
Definition ring.cc:227
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:452
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.

Variable Documentation

◆ test_PosInL

VAR int(* test_PosInL) (const LSet set, const int length, LObject *L, const kStrategy strat) ( const LSet set,
const int length,
LObject * L,
const kStrategy strat )

Definition at line 83 of file kstd2.cc.

◆ test_PosInT

VAR int(* test_PosInT) (const TSet T, const int tl, LObject &h) ( const TSet T,
const int tl,
LObject & h )

Definition at line 82 of file kstd2.cc.