My Project
Macros | Functions | Variables
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 More...
 
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 More...
 
int kFindDivisibleByInS (const kStrategy strat, int *max_ind, LObject *L)
 return -1 if no divisor is found number of first divisor in S, otherwise More...
 
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, 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 2642 of file kstd2.cc.

2643 {
2644  int red_result = 1;
2645  int olddeg,reduc;
2646  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2647  BOOLEAN withT = FALSE;
2648  BITSET save;
2649  SI_SAVE_OPT1(save);
2650 
2651  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2653  initBuchMoraPosRing(strat);
2654  else
2655  initBuchMoraPos(strat);
2656  initHilbCrit(F,Q,&hilb,strat);
2657  initBba(strat);
2658  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2659  /*Shdl=*/initBuchMora(F, Q,strat);
2660  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2661  reduc = olddeg = 0;
2662 
2663 #ifndef NO_BUCKETS
2664  if (!TEST_OPT_NOT_BUCKETS)
2665  strat->use_buckets = 1;
2666 #endif
2667  // redtailBBa against T for inhomogeneous input
2668  if (!TEST_OPT_OLDSTD)
2669  withT = ! strat->homog;
2670 
2671  // strat->posInT = posInT_pLength;
2672  kTest_TS(strat);
2673 
2674 #ifdef HAVE_TAIL_RING
2675  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2676  kStratInitChangeTailRing(strat);
2677 #endif
2678  if (BVERBOSE(23))
2679  {
2680  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2681  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2682  kDebugPrint(strat);
2683  }
2684 
2685 
2686 #ifdef KDEBUG
2687  //kDebugPrint(strat);
2688 #endif
2689  /* compute------------------------------------------------------- */
2690  while (strat->Ll >= 0)
2691  {
2692  #ifdef KDEBUG
2693  if (TEST_OPT_DEBUG) messageSets(strat);
2694  #endif
2695  if (siCntrlc)
2696  {
2697  while (strat->Ll >= 0)
2698  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2699  strat->noClearS=TRUE;
2700  }
2701  if (TEST_OPT_DEGBOUND
2702  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2703  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2704  {
2705  /*
2706  *stops computation if
2707  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2708  *a predefined number Kstd1_deg
2709  */
2710  while ((strat->Ll >= 0)
2711  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2712  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2713  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2714  )
2715  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2716  if (strat->Ll<0) break;
2717  else strat->noClearS=TRUE;
2718  }
2719  if (strat->Ll== 0) strat->interpt=TRUE;
2720  /* picks the last element from the lazyset L */
2721  strat->P = strat->L[strat->Ll];
2722  strat->Ll--;
2723 
2724  if (pNext(strat->P.p) == strat->tail)
2725  {
2726  // deletes the short spoly
2727  if (rField_is_Ring(currRing))
2728  pLmDelete(strat->P.p);
2729  else
2730  pLmFree(strat->P.p);
2731  strat->P.p = NULL;
2732  poly m1 = NULL, m2 = NULL;
2733 
2734  // check that spoly creation is ok
2735  while (strat->tailRing != currRing &&
2736  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2737  {
2738  assume(m1 == NULL && m2 == NULL);
2739  // if not, change to a ring where exponents are at least
2740  // large enough
2741  if (!kStratChangeTailRing(strat))
2742  {
2743  WerrorS("OVERFLOW...");
2744  break;
2745  }
2746  }
2747  // create the real one
2748  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2749  strat->tailRing, m1, m2, strat->R);
2750  }
2751  else if (strat->P.p1 == NULL)
2752  {
2753  if (strat->minim > 0)
2754  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2755  // for input polys, prepare reduction
2756  strat->P.PrepareRed(strat->use_buckets);
2757  }
2758 
2759  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2760  {
2761  red_result = 0;
2762  }
2763  else
2764  {
2765  if (TEST_OPT_PROT)
2766  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2767  &olddeg,&reduc,strat, red_result);
2768 
2769  /* reduction of the element chosen from L */
2770  red_result = strat->red(&strat->P,strat);
2771  if (errorreported) break;
2772  }
2773 
2774  if (strat->overflow)
2775  {
2776  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2777  }
2778 
2779  // reduction to non-zero new poly
2780  if (red_result == 1)
2781  {
2782  // get the polynomial (canonicalize bucket, make sure P.p is set)
2783  strat->P.GetP(strat->lmBin);
2784  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2785  // but now, for entering S, T, we reset it
2786  // in the inhomogeneous case: FDeg == pFDeg
2787  if (strat->homog) strat->initEcart(&(strat->P));
2788 
2789  /* statistic */
2790  if (TEST_OPT_PROT) PrintS("s");
2791 
2792  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2793 
2794  // reduce the tail and normalize poly
2795  // in the ring case we cannot expect LC(f) = 1,
2796  strat->redTailChange=FALSE;
2797 
2798  /* if we are computing over Z we always want to try and cut down
2799  * the coefficients in the tail terms */
2801  {
2802  redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2803  }
2804 
2806  {
2807  strat->P.pCleardenom();
2809  {
2810  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2811  strat->P.pCleardenom();
2812  if (strat->redTailChange) { strat->P.t_p=NULL; }
2813  }
2814  }
2815  else
2816  {
2817  strat->P.pNorm();
2819  {
2820  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2821  if (strat->redTailChange) { strat->P.t_p=NULL; }
2822  }
2823  }
2824 
2825 #ifdef KDEBUG
2826  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2827 #endif /* KDEBUG */
2828 
2829  // min_std stuff
2830  if ((strat->P.p1==NULL) && (strat->minim>0))
2831  {
2832  if (strat->minim==1)
2833  {
2834  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2835  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2836  }
2837  else
2838  {
2839  strat->M->m[minimcnt]=strat->P.p2;
2840  strat->P.p2=NULL;
2841  }
2842  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2843  pNext(strat->M->m[minimcnt])
2844  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2845  strat->tailRing, currRing,
2846  currRing->PolyBin);
2847  minimcnt++;
2848  }
2849 
2850  // enter into S, L, and T
2851  if (((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2852  && ((!TEST_OPT_IDELIM) || (p_Deg(strat->P.p,currRing) > 0)))
2853  {
2854  strat->P.SetShortExpVector();
2855  enterT(strat->P, strat);
2856  if (rField_is_Ring(currRing))
2857  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2858  else
2859  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2860  // posInS only depends on the leading term
2861  strat->enterS(strat->P, pos, strat, strat->tl);
2862 #if 0
2863  int pl=pLength(strat->P.p);
2864  if (pl==1)
2865  {
2866  //if (TEST_OPT_PROT)
2867  //PrintS("<1>");
2868  }
2869  else if (pl==2)
2870  {
2871  //if (TEST_OPT_PROT)
2872  //PrintS("<2>");
2873  }
2874 #endif
2875  }
2876  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2877 // Print("[%d]",hilbeledeg);
2878  kDeleteLcm(&strat->P);
2879  if (strat->s_poly!=NULL)
2880  {
2881  // the only valid entries are: strat->P.p,
2882  // strat->tailRing (read-only, keep it)
2883  // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2884  if (strat->s_poly(strat))
2885  {
2886  // we are called AFTER enterS, i.e. if we change P
2887  // we have to add it also to S/T
2888  // and add pairs
2889  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2890  enterT(strat->P, strat);
2891  if (rField_is_Ring(currRing))
2892  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2893  else
2894  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2895  strat->enterS(strat->P, pos, strat, strat->tl);
2896  }
2897  }
2898  }
2899  else if (strat->P.p1 == NULL && strat->minim > 0)
2900  {
2901  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2902  }
2903 
2904 #ifdef KDEBUG
2905  memset(&(strat->P), 0, sizeof(strat->P));
2906 #endif /* KDEBUG */
2907  kTest_TS(strat);
2908  }
2909 #ifdef KDEBUG
2910  if (TEST_OPT_DEBUG) messageSets(strat);
2911 #endif /* KDEBUG */
2912 
2913  if (TEST_OPT_SB_1)
2914  {
2915  if(!rField_is_Ring(currRing))
2916  {
2917  int k=1;
2918  int j;
2919  while(k<=strat->sl)
2920  {
2921  j=0;
2922  loop
2923  {
2924  if (j>=k) break;
2925  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2926  j++;
2927  }
2928  k++;
2929  }
2930  }
2931  }
2932  /* complete reduction of the standard basis--------- */
2933  if (TEST_OPT_REDSB)
2934  {
2935  completeReduce(strat);
2936  if (strat->completeReduce_retry)
2937  {
2938  // completeReduce needed larger exponents, retry
2939  // to reduce with S (instead of T)
2940  // and in currRing (instead of strat->tailRing)
2941 #ifdef HAVE_TAIL_RING
2942  if(currRing->bitmask>strat->tailRing->bitmask)
2943  {
2944  strat->completeReduce_retry=FALSE;
2945  cleanT(strat);strat->tailRing=currRing;
2946  int i;
2947  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2948  completeReduce(strat);
2949  }
2950  if (strat->completeReduce_retry)
2951 #endif
2952  Werror("exponent bound is %ld",currRing->bitmask);
2953  }
2954  }
2955  else if (TEST_OPT_PROT) PrintLn();
2956  /* release temp data-------------------------------- */
2957  exitBuchMora(strat);
2958  /* postprocessing for GB over ZZ --------------------*/
2959  if (!errorreported)
2960  {
2961  if(rField_is_Z(currRing))
2962  {
2963  for(int i = 0;i<=strat->sl;i++)
2964  {
2965  if(!nGreaterZero(pGetCoeff(strat->S[i])))
2966  {
2967  strat->S[i] = pNeg(strat->S[i]);
2968  }
2969  }
2970  finalReduceByMon(strat);
2971  for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2972  {
2973  if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2974  {
2975  strat->S[i] = pNeg(strat->Shdl->m[i]);
2976  }
2977  }
2978  }
2979  //else if (rField_is_Ring(currRing))
2980  // finalReduceByMon(strat);
2981  }
2982 // if (TEST_OPT_WEIGHTM)
2983 // {
2984 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2985 // if (ecartWeights)
2986 // {
2987 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2988 // ecartWeights=NULL;
2989 // }
2990 // }
2991  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2992  SI_RESTORE_OPT1(save);
2993  /* postprocessing for GB over Q-rings ------------------*/
2994  if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2995 
2996  idTest(strat->Shdl);
2997 
2998  return (strat->Shdl);
2999 }
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 * 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:377
unsigned syzComp
Definition: kutil.h:354
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:383
char interpt
Definition: kutil.h:371
char redTailChange
Definition: kutil.h:399
char completeReduce_retry
Definition: kutil.h:403
void(* initEcart)(TObject *L)
Definition: kutil.h:280
LObject P
Definition: kutil.h:302
char noClearS
Definition: kutil.h:402
char overflow
Definition: kutil.h:404
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:372
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
STATIC_VAR jList * Q
Definition: janet.cc:30
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1214
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition: kInline.h:1239
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:1208
void initBba(kStrategy strat)
Definition: kstd1.cc:1689
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
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:11560
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:7512
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9800
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9178
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1073
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4509
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7188
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9458
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9627
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11021
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:9885
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4685
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10534
void cleanT(kStrategy strat)
Definition: kutil.cc:565
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10128
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4478
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1215
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11114
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9476
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10340
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9713
void messageSets(kStrategy strat)
Definition: kutil.cc:7585
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7553
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:10928
static void kDeleteLcm(LObject *P)
Definition: kutil.h:880
#define assume(x)
Definition: mod2.h:389
#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:130
#define TEST_OPT_INTSTRATEGY
Definition: options.h:111
#define BVERBOSE(a)
Definition: options.h:35
#define TEST_OPT_REDTAIL
Definition: options.h:117
#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:124
#define TEST_OPT_REDSB
Definition: options.h:105
#define TEST_OPT_DEGBOUND
Definition: options.h:114
#define TEST_OPT_SB_1
Definition: options.h:120
#define TEST_OPT_PROT
Definition: options.h:104
#define TEST_OPT_IDELIM
Definition: options.h:131
#define TEST_OPT_DEBUG
Definition: options.h:109
#define TEST_OPT_CONTENTSB
Definition: options.h:128
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:106
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static int pLength(poly a)
Definition: p_polys.h:188
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844
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:509
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:760
#define rField_is_Ring(R)
Definition: ring.h:485
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
#define IDELEMS(i)
Definition: simpleideals.h:23
#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 4608 of file kstd2.cc.

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

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

555 {
556  if (arg <= 0) return 0;
557  long ind = 0;
558  if (arg%2 == 1) { arg--; }
559  while (arg > 0)
560  {
561  ind += SI_LOG2_LONG(arg);
562  arg = arg - 2;
563  }
564  return ind;
565 }
static int SI_LOG2_LONG(long v)
Definition: si_log2.h:22

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11560 of file kutil.cc.

11561 {
11562  printf("red: ");
11563  if (strat->red==redFirst) printf("redFirst\n");
11564  else if (strat->red==redHoney) printf("redHoney\n");
11565  else if (strat->red==redEcart) printf("redEcart\n");
11566  else if (strat->red==redHomog) printf("redHomog\n");
11567  else if (strat->red==redLazy) printf("redLazy\n");
11568  else if (strat->red==redLiftstd) printf("redLiftstd\n");
11569  else printf("%p\n",(void*)strat->red);
11570  printf("posInT: ");
11571  if (strat->posInT==posInT0) printf("posInT0\n");
11572  else if (strat->posInT==posInT1) printf("posInT1\n");
11573  else if (strat->posInT==posInT11) printf("posInT11\n");
11574  else if (strat->posInT==posInT110) printf("posInT110\n");
11575  else if (strat->posInT==posInT13) printf("posInT13\n");
11576  else if (strat->posInT==posInT15) printf("posInT15\n");
11577  else if (strat->posInT==posInT17) printf("posInT17\n");
11578  else if (strat->posInT==posInT17_c) printf("posInT17_c\n");
11579  else if (strat->posInT==posInT19) printf("posInT19\n");
11580  else if (strat->posInT==posInT2) printf("posInT2\n");
11581  #ifdef HAVE_RINGS
11582  else if (strat->posInT==posInT11Ring) printf("posInT11Ring\n");
11583  else if (strat->posInT==posInT110Ring) printf("posInT110Ring\n");
11584  else if (strat->posInT==posInT15Ring) printf("posInT15Ring\n");
11585  else if (strat->posInT==posInT17Ring) printf("posInT17Ring\n");
11586  else if (strat->posInT==posInT17_cRing) printf("posInT17_cRing\n");
11587  #endif
11588 #ifdef HAVE_MORE_POS_IN_T
11589  else if (strat->posInT==posInT_EcartFDegpLength) printf("posInT_EcartFDegpLength\n");
11590  else if (strat->posInT==posInT_FDegpLength) printf("posInT_FDegpLength\n");
11591  else if (strat->posInT==posInT_pLength) printf("posInT_pLength\n");
11592 #endif
11593  else if (strat->posInT==posInT_EcartpLength) printf("posInT_EcartpLength\n");
11594  else printf("%p\n",(void*)strat->posInT);
11595  printf("posInL: ");
11596  if (strat->posInL==posInL0) printf("posInL0\n");
11597  else if (strat->posInL==posInL10) printf("posInL10\n");
11598  else if (strat->posInL==posInL11) printf("posInL11\n");
11599  else if (strat->posInL==posInL110) printf("posInL110\n");
11600  else if (strat->posInL==posInL13) printf("posInL13\n");
11601  else if (strat->posInL==posInL15) printf("posInL15\n");
11602  else if (strat->posInL==posInL17) printf("posInL17\n");
11603  else if (strat->posInL==posInL17_c) printf("posInL17_c\n");
11604  #ifdef HAVE_RINGS
11605  else if (strat->posInL==posInL0) printf("posInL0Ring\n");
11606  else if (strat->posInL==posInL11Ring) printf("posInL11Ring\n");
11607  else if (strat->posInL==posInL11Ringls) printf("posInL11Ringls\n");
11608  else if (strat->posInL==posInL110Ring) printf("posInL110Ring\n");
11609  else if (strat->posInL==posInL15Ring) printf("posInL15Ring\n");
11610  else if (strat->posInL==posInL17Ring) printf("posInL17Ring\n");
11611  else if (strat->posInL==posInL17_cRing) printf("posInL17_cRing\n");
11612  #endif
11613  else if (strat->posInL==posInLSpecial) printf("posInLSpecial\n");
11614  else printf("%p\n",(void*)strat->posInL);
11615  printf("enterS: ");
11616  if (strat->enterS==enterSBba) printf("enterSBba\n");
11617  else if (strat->enterS==enterSMora) printf("enterSMora\n");
11618  else if (strat->enterS==enterSMoraNF) printf("enterSMoraNF\n");
11619  else printf("%p\n",(void*)strat->enterS);
11620  printf("initEcart: ");
11621  if (strat->initEcart==initEcartBBA) printf("initEcartBBA\n");
11622  else if (strat->initEcart==initEcartNormal) printf("initEcartNormal\n");
11623  else printf("%p\n",(void*)strat->initEcart);
11624  printf("initEcartPair: ");
11625  if (strat->initEcartPair==initEcartPairBba) printf("initEcartPairBba\n");
11626  else if (strat->initEcartPair==initEcartPairMora) printf("initEcartPairMora\n");
11627  else printf("%p\n",(void*)strat->initEcartPair);
11628  printf("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11629  strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11630  printf("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11631  strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11632  printf("chainCrit: ");
11633  if (strat->chainCrit==chainCritNormal) printf("chainCritNormal\n");
11634  else if (strat->chainCrit==chainCritOpt_1) printf("chainCritOpt_1\n");
11635  else printf("%p\n",(void*)strat->chainCrit);
11636  printf("posInLDependsOnLength=%d\n",
11637  strat->posInLDependsOnLength);
11638  printf("%s\n",showOption());
11639  printf("LDeg: ");
11640  if (currRing->pLDeg==pLDeg0) printf("pLDeg0");
11641  else if (currRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11642  else if (currRing->pLDeg==pLDegb) printf("pLDegb");
11643  else if (currRing->pLDeg==pLDeg1) printf("pLDeg1");
11644  else if (currRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11645  else if (currRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11646  else if (currRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11647  else if (currRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11648  else if (currRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11649  else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11650  else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11651  else if (currRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11652  else printf("? (%lx)", (long)currRing->pLDeg);
11653  printf(" / ");
11654  if (strat->tailRing->pLDeg==pLDeg0) printf("pLDeg0");
11655  else if (strat->tailRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11656  else if (strat->tailRing->pLDeg==pLDegb) printf("pLDegb");
11657  else if (strat->tailRing->pLDeg==pLDeg1) printf("pLDeg1");
11658  else if (strat->tailRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11659  else if (strat->tailRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11660  else if (strat->tailRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11661  else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11662  else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11663  else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11664  else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11665  else if (strat->tailRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11666  else printf("? (%lx)", (long)strat->tailRing->pLDeg);
11667  printf("\n");
11668  printf("currRing->pFDeg: ");
11669  if (currRing->pFDeg==p_Totaldegree) printf("p_Totaldegree");
11670  else if (currRing->pFDeg==p_WFirstTotalDegree) printf("pWFirstTotalDegree");
11671  else if (currRing->pFDeg==p_Deg) printf("p_Deg");
11672  else if (currRing->pFDeg==kHomModDeg) printf("kHomModDeg");
11673  else if (currRing->pFDeg==totaldegreeWecart) printf("totaldegreeWecart");
11674  else if (currRing->pFDeg==p_WTotaldegree) printf("p_WTotaldegree");
11675  else printf("? (%lx)", (long)currRing->pFDeg);
11676  printf("\n");
11677  printf(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11678  if(TEST_OPT_DEGBOUND)
11679  printf(" degBound: %d\n", Kstd1_deg);
11680 
11681  if( ecartWeights != NULL )
11682  {
11683  printf("ecartWeights: ");
11684  for (int i = rVar(currRing); i > 0; i--)
11685  printf("%hd ", ecartWeights[i]);
11686  printf("\n");
11688  }
11689 
11690 #ifndef SING_NDEBUG
11692 #endif
11693 }
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:291
char noTailReduction
Definition: kutil.h:378
int ak
Definition: kutil.h:353
char sugarCrit
Definition: kutil.h:377
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:287
char Gebauer
Definition: kutil.h:378
int LazyPass
Definition: kutil.h:353
int LazyDegree
Definition: kutil.h:353
char posInLDependsOnLength
Definition: kutil.h:389
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:167
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1365
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2434
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:2088
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:1121
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1881
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6339
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6454
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6093
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5306
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:797
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5876
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4975
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4918
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5096
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1681
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5172
int posInT0(const TSet, const int length, LObject &)
Definition: kutil.cc:4907
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4947
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6182
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6135
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11526
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5143
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1326
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5643
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3458
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5012
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6217
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5414
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11435
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5210
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5599
VAR int Kstd1_deg
Definition: kutil.cc:247
void initEcartNormal(TObject *h)
Definition: kutil.cc:1304
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5946
char * showOption()
Definition: misc_ip.cc:709
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6294
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5053
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6253
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5542
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5265
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5368
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1628
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5476
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6389
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11489
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3217
void initEcartBBA(TObject *h)
Definition: kutil.cc:1312
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5833
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1319
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:8829
#define TEST_OPT_WEIGHTM
Definition: options.h:122
long pLDegb(poly p, int *l, const ring r)
Definition: p_polys.cc:811
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:975
long p_WFirstTotalDegree(poly p, const ring r)
Definition: p_polys.cc:596
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1038
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1068
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:941
long pLDeg1(poly p, int *l, const ring r)
Definition: p_polys.cc:841
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:910
long p_WTotaldegree(poly p, const ring r)
Definition: p_polys.cc:613
long pLDeg1c(poly p, int *l, const ring r)
Definition: p_polys.cc:877
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1005
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:770
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:739
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1505
void rDebugPrint(const ring r)
Definition: ring.cc:4122
static int rGetCurrSyzLimit(const ring r)
Definition: ring.h:723
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition: ring.h:720
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592
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 421 of file kstd2.cc.

422 {
423  unsigned long not_sev = ~L->sev;
424  poly p = L->GetLmCurrRing();
425  int j = 0;
426 
427  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
428 
430 #if 1
431  int ende;
432  if (is_Ring
433  || (strat->ak>0)
434  || currRing->pLexOrder)
435  ende=strat->sl;
436  else
437  {
438  ende=posInS(strat,*max_ind,p,0)+1;
439  if (ende>(*max_ind)) ende=(*max_ind);
440  }
441 #else
442  int ende=strat->sl;
443 #endif
444  if(is_Ring)
445  {
446  loop
447  {
448  if (j > ende) return -1;
449 #if defined(PDEBUG) || defined(PDIV_DEBUG)
450  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
451  p, not_sev, currRing))
452 #else
453  if ( !(strat->sevS[j] & not_sev) &&
454  p_LmDivisibleBy(strat->S[j], p, currRing))
455 #endif
456  {
457  if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
458  return j;
459  }
460  j++;
461  }
462  }
463  else
464  {
465  loop
466  {
467  if (j > ende) return -1;
468 #if defined(PDEBUG) || defined(PDIV_DEBUG)
469  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
470  p, not_sev, currRing))
471 #else
472  if ( !(strat->sevS[j] & not_sev) &&
473  p_LmDivisibleBy(strat->S[j], p, currRing))
474 #endif
475  {
476  return j;
477  }
478  j++;
479  }
480  }
481 }
int p
Definition: cfModGcd.cc:4078
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:750
#define pAssume(cond)
Definition: monomials.h:90
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4776
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1908
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1889

◆ kFindDivisibleByInS_noCF()

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

Definition at line 484 of file kstd2.cc.

485 {
486  unsigned long not_sev = ~L->sev;
487  poly p = L->GetLmCurrRing();
488  int j = 0;
489 
490  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
491 
493 #if 1
494  int ende;
495  if (is_Ring
496  || (strat->ak>0)
497  || currRing->pLexOrder)
498  ende=strat->sl;
499  else
500  {
501  ende=posInS(strat,*max_ind,p,0)+1;
502  if (ende>(*max_ind)) ende=(*max_ind);
503  }
504 #else
505  int ende=strat->sl;
506 #endif
507  loop
508  {
509  if (j > ende) return -1;
510 #if defined(PDEBUG) || defined(PDIV_DEBUG)
511  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
512  p, not_sev, currRing))
513 #else
514  if ( !(strat->sevS[j] & not_sev) &&
515  p_LmDivisibleBy(strat->S[j], p, currRing))
516 #endif
517  {
518  return j;
519  }
520  j++;
521  }
522 }

◆ 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:672
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition: coeffs.h:678
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:508
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
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_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 524 of file kstd2.cc.

525 {
526  unsigned long not_sev = ~L->sev;
527  poly p = L->GetLmCurrRing();
528  int j = start;
529 
530  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
531 #if 1
532  int ende=max_ind;
533 #else
534  int ende=strat->sl;
535 #endif
536  loop
537  {
538  if (j > ende) return -1;
539 #if defined(PDEBUG) || defined(PDIV_DEBUG)
540  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
541  p, not_sev, currRing))
542 #else
543  if ( !(strat->sevS[j] & not_sev) &&
544  p_LmDivisibleBy(strat->S[j], p, currRing))
545 #endif
546  {
547  return j;
548  }
549  j++;
550  }
551 }

◆ kFindZeroPoly()

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

Definition at line 569 of file kstd2.cc.

570 {
571  // m = currRing->ch
572 
573  if (input_p == NULL) return NULL;
574 
575  poly p = input_p;
576  poly zeroPoly = NULL;
577  unsigned long a = (unsigned long) pGetCoeff(p);
578 
579  int k_ind2 = 0;
580  int a_ind2 = SI_LOG2_LONG(a);
581 
582  // unsigned long k = 1;
583  // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
584  for (int i = 1; i <= leadRing->N; i++)
585  {
586  k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
587  }
588 
589  a = (unsigned long) pGetCoeff(p);
590 
591  number tmp1;
592  poly tmp2, tmp3;
593  poly lead_mult = p_ISet(1, tailRing);
594  if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
595  {
596  int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
597  int s_exp;
598  zeroPoly = p_ISet(a, tailRing);
599  for (int i = 1; i <= leadRing->N; i++)
600  {
601  s_exp = p_GetExp(p, i,leadRing);
602  if (s_exp % 2 != 0)
603  {
604  s_exp = s_exp - 1;
605  }
606  while ( (0 < SI_LOG2_LONG(s_exp)) && (SI_LOG2_LONG(s_exp) <= too_much) )
607  {
608  too_much = too_much - SI_LOG2_LONG(s_exp);
609  s_exp = s_exp - 2;
610  }
611  p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
612  for (int j = 1; j <= s_exp; j++)
613  {
614  tmp1 = nInit(j);
615  tmp2 = p_ISet(1, tailRing);
616  p_SetExp(tmp2, i, 1, tailRing);
617  p_Setm(tmp2, tailRing);
618  if (nIsZero(tmp1))
619  { // should nowbe obsolet, test ! TODO OLIVER
620  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
621  }
622  else
623  {
624  tmp3 = p_NSet(nCopy(tmp1), tailRing);
625  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
626  }
627  }
628  }
629  p_Setm(lead_mult, tailRing);
630  zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
631  tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
632  for (int i = 1; i <= leadRing->N; i++)
633  {
634  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
635  }
636  p_Setm(tmp2, leadRing);
637  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
638  pNext(tmp2) = zeroPoly;
639  return tmp2;
640  }
641 /* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
642  if (1 == 0 && alpha_k <= a)
643  { // Temporarily disabled, reducing coefficients not compatible with std TODO Oliver
644  zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
645  for (int i = 1; i <= leadRing->N; i++)
646  {
647  for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
648  {
649  tmp1 = nInit(j);
650  tmp2 = p_ISet(1, tailRing);
651  p_SetExp(tmp2, i, 1, tailRing);
652  p_Setm(tmp2, tailRing);
653  if (nIsZero(tmp1))
654  {
655  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
656  }
657  else
658  {
659  tmp3 = p_ISet((unsigned long) tmp1, tailRing);
660  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
661  }
662  }
663  }
664  tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
665  for (int i = 1; i <= leadRing->N; i++)
666  {
667  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
668  }
669  p_Setm(tmp2, leadRing);
670  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
671  pNext(tmp2) = zeroPoly;
672  return tmp2;
673  } */
674  return NULL;
675 }
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:441
CFList tmp1
Definition: facFqBivar.cc:72
CFList tmp2
Definition: facFqBivar.cc:72
static long ind_fact_2(long arg)
Definition: kstd2.cc:554
#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:1297
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1469
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1112
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:486
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
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:467
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1049
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:753
#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 4123 of file kstd2.cc.

4124 {
4125  assume(!idIs0(q));
4126  assume(!(idIs0(F)&&(Q==NULL)));
4127 // lazy_reduce flags: can be combined by |
4128 //#define KSTD_NF_LAZY 1
4129  // do only a reduction of the leading term
4130 //#define KSTD_NF_NONORM 4
4131  // only global: avoid normalization, return a multiply of NF
4132  poly p;
4133  int i;
4134  ideal res;
4135  int max_ind;
4136 
4137  //if (idIs0(q))
4138  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4139  //if ((idIs0(F))&&(Q==NULL))
4140  // return idCopy(q); /*F=0*/
4141  //strat->ak = idRankFreeModule(F);
4142  /*- creating temp data structures------------------- -*/
4143  BITSET save1;
4144  SI_SAVE_OPT1(save1);
4146  initBuchMoraCrit(strat);
4147  strat->initEcart = initEcartBBA;
4148 #ifdef HAVE_SHIFTBBA
4149  if (rIsLPRing(currRing))
4150  {
4151  strat->enterS = enterSBbaShift;
4152  }
4153  else
4154 #endif
4155  {
4156  strat->enterS = enterSBba;
4157  }
4158  /*- set S -*/
4159  strat->sl = -1;
4160 #ifndef NO_BUCKETS
4162 #endif
4163  /*- init local data struct.---------------------------------------- -*/
4164  /*Shdl=*/initS(F,Q,strat);
4165  /*- compute------------------------------------------------------- -*/
4166  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4167  for (i=IDELEMS(q)-1; i>=0; i--)
4168  {
4169  if (q->m[i]!=NULL)
4170  {
4171  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4172  p = redNF(pCopy(q->m[i]),max_ind,
4173  (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4174  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4175  {
4176  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4177  if (rField_is_Ring(currRing))
4178  {
4179  p = redtailBba_NF(p,strat);
4180  }
4181  else
4182  {
4184  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4185  }
4186  }
4187  res->m[i]=p;
4188  }
4189  //else
4190  // res->m[i]=NULL;
4191  }
4192  /*- release temp data------------------------------- -*/
4193  assume(strat->L==NULL); /* strat->L unused */
4194  assume(strat->B==NULL); /* strat->B unused */
4195  omFree(strat->sevS);
4196  omFree(strat->ecartS);
4197  assume(strat->T==NULL);//omfree(strat->T);
4198  assume(strat->sevT==NULL);//omfree(strat->sevT);
4199  assume(strat->R==NULL);//omfree(strat->R);
4200  omfree(strat->S_2_R);
4201  omfree(strat->fromQ);
4202  idDelete(&strat->Shdl);
4203  SI_RESTORE_OPT1(save1);
4204  if (TEST_OPT_PROT) PrintLn();
4205  return res;
4206 }
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:2325
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7635
poly redtailBba_NF(poly p, kStrategy strat)
Definition: kutil.cc:7398
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:8929
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omFree(addr)
Definition: omAllocDecl.h:261
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:400
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411

◆ kNF2() [2/2]

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

Definition at line 3967 of file kstd2.cc.

3968 {
3969  assume(q!=NULL);
3970  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3971 
3972 // lazy_reduce flags: can be combined by |
3973 //#define KSTD_NF_LAZY 1
3974  // do only a reduction of the leading term
3975 //#define KSTD_NF_NONORM 4
3976  // only global: avoid normalization, return a multiply of NF
3977  poly p;
3978 
3979  //if ((idIs0(F))&&(Q==NULL))
3980  // return pCopy(q); /*F=0*/
3981  //strat->ak = idRankFreeModule(F);
3982  /*- creating temp data structures------------------- -*/
3983  BITSET save1;
3984  SI_SAVE_OPT1(save1);
3986  initBuchMoraCrit(strat);
3987  strat->initEcart = initEcartBBA;
3988 #ifdef HAVE_SHIFTBBA
3989  if (rIsLPRing(currRing))
3990  {
3991  strat->enterS = enterSBbaShift;
3992  }
3993  else
3994 #endif
3995  {
3996  strat->enterS = enterSBba;
3997  }
3998 #ifndef NO_BUCKETS
4000 #endif
4001  /*- set S -*/
4002  strat->sl = -1;
4003  /*- init local data struct.---------------------------------------- -*/
4004  /*Shdl=*/initS(F,Q,strat);
4005  /*- compute------------------------------------------------------- -*/
4006  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
4007  //{
4008  // for (i=strat->sl;i>=0;i--)
4009  // pNorm(strat->S[i]);
4010  //}
4011  kTest(strat);
4012  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
4013  if (BVERBOSE(23)) kDebugPrint(strat);
4014  int max_ind;
4015  p = redNF(pCopy(q),max_ind,(lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4016  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4017  {
4018  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4020  {
4021  p = redtailBba_NF(p,strat);
4022  }
4023  else if (rField_is_Ring(currRing))
4024  {
4025  p = redtailBba_Ring(p,max_ind,strat);
4026  }
4027  else
4028  {
4030  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4031  }
4032  }
4033  /*- release temp data------------------------------- -*/
4034  assume(strat->L==NULL); /* strat->L unused */
4035  assume(strat->B==NULL); /* strat->B unused */
4036  omFree(strat->sevS);
4037  omFree(strat->ecartS);
4038  assume(strat->T==NULL);//omfree(strat->T);
4039  assume(strat->sevT==NULL);//omfree(strat->sevT);
4040  assume(strat->R==NULL);//omfree(strat->R);
4041  omfree(strat->S_2_R);
4042  omfree(strat->fromQ);
4043  idDelete(&strat->Shdl);
4044  SI_RESTORE_OPT1(save1);
4045  if (TEST_OPT_PROT) PrintLn();
4046  return p;
4047 }
KINLINE poly redtailBba_Ring(poly p, int pos, kStrategy strat)
Definition: kInline.h:1227
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1012
static BOOLEAN rField_is_Zn(const ring r)
Definition: ring.h:512

◆ kNF2Bound() [1/2]

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

Definition at line 4208 of file kstd2.cc.

4209 {
4210  assume(!idIs0(q));
4211  assume(!(idIs0(F)&&(Q==NULL)));
4212 // lazy_reduce flags: can be combined by |
4213 //#define KSTD_NF_LAZY 1
4214  // do only a reduction of the leading term
4215 //#define KSTD_NF_NONORM 4
4216  // only global: avoid normalization, return a multiply of NF
4217  poly p;
4218  int i;
4219  ideal res;
4220  int max_ind;
4221 
4222  //if (idIs0(q))
4223  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4224  //if ((idIs0(F))&&(Q==NULL))
4225  // return idCopy(q); /*F=0*/
4226  //strat->ak = idRankFreeModule(F);
4227  /*- creating temp data structures------------------- -*/
4228  BITSET save1;
4229  SI_SAVE_OPT1(save1);
4231  initBuchMoraCrit(strat);
4232  strat->initEcart = initEcartBBA;
4233  strat->enterS = enterSBba;
4234  /*- set S -*/
4235  strat->sl = -1;
4236 #ifndef NO_BUCKETS
4238 #endif
4239  /*- init local data struct.---------------------------------------- -*/
4240  /*Shdl=*/initS(F,Q,strat);
4241  /*- compute------------------------------------------------------- -*/
4242  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4243  for (i=IDELEMS(q)-1; i>=0; i--)
4244  {
4245  if (q->m[i]!=NULL)
4246  {
4247  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4248  p = redNFBound(pCopy(q->m[i]),max_ind,
4249  (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat,bound);
4250  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4251  {
4252  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4254  {
4255  p = redtailBba_Z(p,max_ind,strat);
4256  }
4257  else if (rField_is_Ring(currRing))
4258  {
4259  p = redtailBba_Ring(p,max_ind,strat);
4260  }
4261  else
4262  {
4264  p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4265  }
4266  }
4267  res->m[i]=p;
4268  }
4269  //else
4270  // res->m[i]=NULL;
4271  }
4272  /*- release temp data------------------------------- -*/
4273  assume(strat->L==NULL); /* strat->L unused */
4274  assume(strat->B==NULL); /* strat->B unused */
4275  omFree(strat->sevS);
4276  omFree(strat->ecartS);
4277  assume(strat->T==NULL);//omfree(strat->T);
4278  assume(strat->sevT==NULL);//omfree(strat->sevT);
4279  assume(strat->R==NULL);//omfree(strat->R);
4280  omfree(strat->S_2_R);
4281  omfree(strat->fromQ);
4282  idDelete(&strat->Shdl);
4283  SI_RESTORE_OPT1(save1);
4284  if (TEST_OPT_PROT) PrintLn();
4285  return res;
4286 }
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:1220
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
Definition: kInline.h:1232
poly redNFBound(poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
Definition: kstd2.cc:2525

◆ kNF2Bound() [2/2]

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

Definition at line 4049 of file kstd2.cc.

4050 {
4051  assume(q!=NULL);
4052  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
4053 
4054 // lazy_reduce flags: can be combined by |
4055 //#define KSTD_NF_LAZY 1
4056  // do only a reduction of the leading term
4057 //#define KSTD_NF_NONORM 4
4058  // only global: avoid normalization, return a multiply of NF
4059  poly p;
4060 
4061  //if ((idIs0(F))&&(Q==NULL))
4062  // return pCopy(q); /*F=0*/
4063  //strat->ak = idRankFreeModule(F);
4064  /*- creating temp data structures------------------- -*/
4065  BITSET save1;
4066  SI_SAVE_OPT1(save1);
4068  initBuchMoraCrit(strat);
4069  strat->initEcart = initEcartBBA;
4070  strat->enterS = enterSBba;
4071 #ifndef NO_BUCKETS
4073 #endif
4074  /*- set S -*/
4075  strat->sl = -1;
4076  /*- init local data struct.---------------------------------------- -*/
4077  /*Shdl=*/initS(F,Q,strat);
4078  /*- compute------------------------------------------------------- -*/
4079  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
4080  //{
4081  // for (i=strat->sl;i>=0;i--)
4082  // pNorm(strat->S[i]);
4083  //}
4084  kTest(strat);
4085  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
4086  if (BVERBOSE(23)) kDebugPrint(strat);
4087  int max_ind;
4088  p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
4089  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4090  {
4091  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4093  {
4094  p = redtailBba_Z(p,max_ind,strat);
4095  }
4096  else if (rField_is_Ring(currRing))
4097  {
4098  p = redtailBba_Ring(p,max_ind,strat);
4099  }
4100  else
4101  {
4103  p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4104  //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4105  }
4106  }
4107  /*- release temp data------------------------------- -*/
4108  assume(strat->L==NULL); /* strat->L unused */
4109  assume(strat->B==NULL); /* strat->B unused */
4110  omFree(strat->sevS);
4111  omFree(strat->ecartS);
4112  assume(strat->T==NULL);//omfree(strat->T);
4113  assume(strat->sevT==NULL);//omfree(strat->sevT);
4114  assume(strat->R==NULL);//omfree(strat->R);
4115  omfree(strat->S_2_R);
4116  omfree(strat->fromQ);
4117  idDelete(&strat->Shdl);
4118  SI_RESTORE_OPT1(save1);
4119  if (TEST_OPT_PROT) PrintLn();
4120  return p;
4121 }

◆ ksReducePolyTailSig()

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

Definition at line 1305 of file kstd2.cc.

1306 {
1307  BOOLEAN ret;
1308  number coef;
1309  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1310  if(!rField_is_Ring(currRing))
1311  Red->HeadNormalize();
1312  /*
1313  printf("------------------------\n");
1314  pWrite(Red->GetLmCurrRing());
1315  */
1317  ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1318  else
1319  ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1320  if (!ret)
1321  {
1322  if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1323  {
1324  PR->Mult_nn(coef);
1325  // HANNES: mark for Normalize
1326  }
1327  n_Delete(&coef, currRing->cf);
1328  }
1329  return ret;
1330 }
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:465
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:742
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:948

◆ 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:357

◆ redFirstShift()

int redFirstShift ( LObject h,
kStrategy  strat 
)

Definition at line 4988 of file kstd2.cc.

4989 {
4990  if (h->IsNull()) return 0;
4991 
4992  int at, reddeg,d;
4993  int pass = 0;
4994  int j = 0;
4995 
4996  if (! strat->homog)
4997  {
4998  d = h->GetpFDeg() + h->ecart;
4999  reddeg = strat->LazyDegree+d;
5000  }
5001  h->SetShortExpVector();
5002  loop
5003  {
5004  j = kFindDivisibleByInT(strat, h);
5005  if (j < 0)
5006  {
5007  h->SetDegStuffReturnLDeg(strat->LDegLast);
5008  return 1;
5009  }
5010 
5011  if (!TEST_OPT_INTSTRATEGY)
5012  strat->T[j].pNorm();
5013 #ifdef KDEBUG
5014  if (TEST_OPT_DEBUG)
5015  {
5016  PrintS("reduce ");
5017  h->wrp();
5018  PrintS(" with ");
5019  strat->T[j].wrp();
5020  }
5021 #endif
5022  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
5023 
5024 #ifdef KDEBUG
5025  if (TEST_OPT_DEBUG)
5026  {
5027  PrintS("\nto ");
5028  wrp(h->p);
5029  PrintLn();
5030  }
5031 #endif
5032  if (h->IsNull())
5033  {
5034  kDeleteLcm(h);
5035  h->Clear();
5036  return 0;
5037  }
5038  h->SetShortExpVector();
5039 
5040 #if 0
5041  if ((strat->syzComp!=0) && !strat->honey)
5042  {
5043  if ((strat->syzComp>0) &&
5044  (h->Comp() > strat->syzComp))
5045  {
5046  assume(h->MinComp() > strat->syzComp);
5047 #ifdef KDEBUG
5048  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
5049 #endif
5050  if (strat->homog)
5051  h->SetDegStuffReturnLDeg(strat->LDegLast);
5052  return -2;
5053  }
5054  }
5055 #endif
5056  if (!strat->homog)
5057  {
5058  if (!TEST_OPT_OLDSTD && strat->honey)
5059  {
5060  h->SetpFDeg();
5061  if (strat->T[j].ecart <= h->ecart)
5062  h->ecart = d - h->GetpFDeg();
5063  else
5064  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
5065 
5066  d = h->GetpFDeg() + h->ecart;
5067  }
5068  else
5069  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
5070  /*- try to reduce the s-polynomial -*/
5071  pass++;
5072  /*
5073  *test whether the polynomial should go to the lazyset L
5074  *-if the degree jumps
5075  *-if the number of pre-defined reductions jumps
5076  */
5077  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
5078  && ((d >= reddeg) || (pass > strat->LazyPass)))
5079  {
5080  h->SetLmCurrRing();
5081  if (strat->posInLDependsOnLength)
5082  h->SetLength(strat->length_pLength);
5083  at = strat->posInL(strat->L,strat->Ll,h,strat);
5084  if (at <= strat->Ll)
5085  {
5086  //int dummy=strat->sl;
5087  /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
5088  //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
5089  if (kFindDivisibleByInT(strat, h) < 0)
5090  return 1;
5091  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
5092 #ifdef KDEBUG
5093  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
5094 #endif
5095  h->Clear();
5096  return -1;
5097  }
5098  }
5099  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
5100  {
5101  reddeg = d+1;
5102  Print(".%d",d);mflush();
5103  }
5104  }
5105  }
5106 }
KINLINE poly kNoetherTail()
Definition: kInline.h:66
char LDegLast
Definition: kutil.h:385
char length_pLength
Definition: kutil.h:387
#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:189
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_REDTHROUGH
Definition: options.h:123
void wrp(poly p)
Definition: polys.h:310

◆ redHomog()

int redHomog ( LObject h,
kStrategy  strat 
)

Definition at line 1121 of file kstd2.cc.

1122 {
1123  if (strat->tl<0) return 1;
1124  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1125  assume(h->FDeg == h->pFDeg());
1126 
1127  poly h_p;
1128  int i,j,at,pass,cnt,ii;
1129  // long reddeg,d;
1130  int li;
1131  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1132 
1133  pass = j = 0;
1134  cnt = RED_CANONICALIZE;
1135  // d = reddeg = h->GetpFDeg();
1136  h->SetShortExpVector();
1137  h_p = h->GetLmTailRing();
1138  h->PrepareRed(strat->use_buckets);
1139  loop
1140  {
1141  j = kFindDivisibleByInT(strat, h);
1142  if (j < 0) return 1;
1143 
1144  li = strat->T[j].pLength;
1145  ii = j;
1146  /*
1147  * the polynomial to reduce with (up to the moment) is;
1148  * pi with length li
1149  */
1150  i = j;
1151 #if 1
1152  if (test_opt_length)
1153  {
1154  if (li<=0) li=strat->T[j].GetpLength();
1155  if (li>2)
1156  {
1157  unsigned long not_sev = ~ h->sev;
1158  loop
1159  {
1160  /*- search the shortest possible with respect to length -*/
1161  i++;
1162  if (i > strat->tl)
1163  break;
1164  if ((strat->T[i].pLength < li)
1165  &&
1166  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1167  h_p, not_sev, strat->tailRing))
1168  {
1169  /*
1170  * the polynomial to reduce with is now;
1171  */
1172  li = strat->T[i].pLength;
1173  if (li<=0) li=strat->T[i].GetpLength();
1174  ii = i;
1175  if (li<3) break;
1176  }
1177  }
1178  }
1179  }
1180 #endif
1181 
1182  /*
1183  * end of search: have to reduce with pi
1184  */
1185 #ifdef KDEBUG
1186  if (TEST_OPT_DEBUG)
1187  {
1188  PrintS("red:");
1189  h->wrp();
1190  PrintS(" with ");
1191  strat->T[ii].wrp();
1192  }
1193 #endif
1194  assume(strat->fromT == FALSE);
1195 
1196  ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1197 #if SBA_PRINT_REDUCTION_STEPS
1198  sba_interreduction_steps++;
1199 #endif
1200 #if SBA_PRINT_OPERATIONS
1201  sba_interreduction_operations += pLength(strat->T[ii].p);
1202 #endif
1203 
1204 #ifdef KDEBUG
1205  if (TEST_OPT_DEBUG)
1206  {
1207  PrintS("\nto ");
1208  h->wrp();
1209  PrintLn();
1210  }
1211 #endif
1212 
1213  h_p = h->GetLmTailRing();
1214  if (h_p == NULL)
1215  {
1216  kDeleteLcm(h);
1217  return 0;
1218  }
1219  #if 0 // red is redLiftstd if OPT_IDLIFT
1221  {
1222  if (h->p!=NULL)
1223  {
1224  if(p_GetComp(h->p,currRing)>strat->syzComp)
1225  {
1226  h->Delete();
1227  return 0;
1228  }
1229  }
1230  else if (h->t_p!=NULL)
1231  {
1232  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1233  {
1234  h->Delete();
1235  return 0;
1236  }
1237  }
1238  }
1239  #endif
1240  #if 0
1241  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1242  {
1243  if (h->p!=NULL)
1244  {
1245  if(p_GetComp(h->p,currRing)>strat->syzComp)
1246  {
1247  return 1;
1248  }
1249  }
1250  else if (h->t_p!=NULL)
1251  {
1252  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1253  {
1254  return 1;
1255  }
1256  }
1257  }
1258  #endif
1259  h->SetShortExpVector();
1260  /*
1261  * try to reduce the s-polynomial h
1262  *test first whether h should go to the lazyset L
1263  *-if the degree jumps
1264  *-if the number of pre-defined reductions jumps
1265  */
1266  cnt--;
1267  pass++;
1268  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1269  {
1270  h->SetLmCurrRing();
1271  at = strat->posInL(strat->L,strat->Ll,h,strat);
1272  if (at <= strat->Ll)
1273  {
1274 #ifdef HAVE_SHIFTBBA
1275  if (rIsLPRing(currRing))
1276  {
1277  if (kFindDivisibleByInT(strat, h) < 0)
1278  return 1;
1279  }
1280  else
1281 #endif
1282  {
1283  int dummy=strat->sl;
1284  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1285  return 1;
1286  }
1287  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1288 #ifdef KDEBUG
1289  if (TEST_OPT_DEBUG)
1290  Print(" lazy: -> L%d\n",at);
1291 #endif
1292  h->Clear();
1293  return -1;
1294  }
1295  }
1296  else if (UNLIKELY(cnt==0))
1297  {
1298  h->CanonicalizeP();
1299  cnt=RED_CANONICALIZE;
1300  //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1301  }
1302  }
1303 }
#define UNLIKELY(X)
Definition: auxiliary.h:404
char fromT
Definition: kutil.h:379
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:421
#define RED_CANONICALIZE
Definition: kutil.h:36
#define p_GetComp(p, r)
Definition: monomials.h:64
#define TEST_OPT_LENGTH
Definition: options.h:132
#define TEST_OPT_REDTAIL_SYZ
Definition: options.h:118

◆ redHoney()

int redHoney ( LObject h,
kStrategy  strat 
)

Definition at line 2088 of file kstd2.cc.

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

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1881 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2325 of file kstd2.cc.

2326 {
2327  if (h==NULL) return NULL;
2328  int j,j_ring;
2329  int cnt=REDNF_CANONICALIZE;
2330  max_ind=strat->sl;
2331 
2332  if (0 > strat->sl)
2333  {
2334  return h;
2335  }
2336  LObject P(h);
2337  P.SetShortExpVector();
2338  P.t_p=NULL;
2339 #ifdef HAVE_RINGS
2340  BOOLEAN is_ring = rField_is_Ring(currRing);
2341  if(is_ring) nonorm=TRUE;
2342 #endif
2343 #ifdef KDEBUG
2344 // if (TEST_OPT_DEBUG)
2345 // {
2346 // PrintS("redNF: starting S:\n");
2347 // for( j = 0; j <= max_ind; j++ )
2348 // {
2349 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2350 // pWrite(strat->S[j]);
2351 // }
2352 // };
2353 #endif
2354  if (rField_is_Z(currRing))
2355  {
2356  redRing_Z_S(&P,strat);
2357  if (P.bucket!=NULL)
2358  {
2359  P.p=kBucketClear(P.bucket);
2360  kBucketDestroy(&P.bucket);
2361  }
2362  return P.p;
2363  }
2364  else if (rField_is_Ring(currRing))
2365  {
2366  redRing_S(&P,strat);
2367  if (P.bucket!=NULL)
2368  {
2369  P.p=kBucketClear(P.bucket);
2370  kBucketDestroy(&P.bucket);
2371  }
2372  return P.p;
2373  }
2374 
2375  P.bucket = kBucketCreate(currRing);
2376  kBucketInit(P.bucket,P.p,pLength(P.p));
2377  kbTest(P.bucket);
2378  P.p=kBucketGetLm(P.bucket);
2379  loop
2380  {
2381  j_ring=j=kFindDivisibleByInS_noCF(strat,&max_ind,&P);
2382  while ((j>=0)
2383  && (nonorm)
2384  && (!n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[j]),currRing->cf)))
2385  j=kFindNextDivisibleByInS(strat,j+1,max_ind,&P);
2386  if (j>=0)
2387  {
2388  int sl=pSize(strat->S[j]);
2389  int jj=j;
2390  loop
2391  {
2392  int sll;
2393  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2394  if (jj<0) break;
2395  if ((!nonorm)
2396  || (n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[jj]),currRing->cf)))
2397  {
2398  sll=pSize(strat->S[jj]);
2399  if (sll<sl)
2400  {
2401  #ifdef KDEBUG
2402  if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2403  #endif
2404  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2405  j=jj;
2406  sl=sll;
2407  }
2408  }
2409  }
2410  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2411  {
2412  pNorm(strat->S[j]);
2413  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2414  }
2415  nNormalize(pGetCoeff(P.p));
2416 #ifdef KDEBUG
2417  if (TEST_OPT_DEBUG)
2418  {
2419  PrintS("red:");
2420  wrp(P.p);
2421  PrintS(" with ");
2422  wrp(strat->S[j]);
2423  }
2424 #endif
2425 #ifdef HAVE_PLURAL
2426  if (rIsPluralRing(currRing))
2427  {
2428  number coef;
2429  nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
2430  nDelete(&coef);
2431  }
2432  else
2433 #endif
2434  {
2435  kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),
2436  strat->kNoether);
2437  }
2438  cnt--;
2439  if (cnt==0)
2440  {
2441  kBucketCanonicalize(P.bucket);
2442  cnt=REDNF_CANONICALIZE;
2443  }
2444  P.p=kBucketGetLm(P.bucket);
2445  //P.t_p=NULL;
2446 #ifdef KDEBUG
2447  if (TEST_OPT_DEBUG)
2448  {
2449  PrintS("\nto:");
2450  wrp(P.p);
2451  PrintLn();
2452  }
2453 #endif
2454  if (P.p==NULL)
2455  {
2456  kBucketDestroy(&P.bucket);
2457  return NULL;
2458  }
2459  kbTest(P.bucket);
2460  P.SetShortExpVector();
2461  }
2462 #ifdef HAVE_RINGS
2463  else if (is_ring && (j_ring>=0) && (currRing->cf->cfQuotRem!=ndQuotRem))
2464  {
2465  number r;
2466  number n=n_QuotRem(pGetCoeff(P.p),pGetCoeff(strat->S[j_ring]),&r,currRing->cf);
2467  if(!n_IsZero(n,currRing->cf))
2468  {
2469  poly lm=kBucketGetLm(P.bucket);
2470  poly m=p_Head(lm,currRing);
2471  p_ExpVectorSub(m,strat->S[j_ring],currRing);
2472  if (p_GetComp(strat->S[j_ring], currRing) != p_GetComp(lm, currRing))
2473  {
2475  }
2476  p_SetCoeff(m,n,currRing);
2477  p_Setm(m,currRing);
2478 #ifdef KDEBUG
2479  if (TEST_OPT_DEBUG)
2480  {
2481  PrintS("redi (coeff):");
2482  wrp(P.p);
2483  PrintS(" with ");
2484  wrp(strat->S[j]);
2485  }
2486 #endif
2487  int l=-1;
2488  kBucket_Minus_m_Mult_p(P.bucket,m,strat->S[j_ring],&l);
2489  P.p=kBucketGetLm(P.bucket);
2490  p_Delete(&m,currRing);
2491 #ifdef KDEBUG
2492  if (TEST_OPT_DEBUG)
2493  {
2494  PrintS("\nto:");
2495  wrp(P.p);
2496  PrintLn();
2497  }
2498 #endif
2499  }
2500  else
2501  {
2502  n_Delete(&n,currRing->cf);
2503  }
2504  n_Delete(&r,currRing->cf);
2505  P.p=kBucketClear(P.bucket);
2506  kBucketDestroy(&P.bucket);
2507  pNormalize(P.p);
2508  return P.p;
2509  }
2510 #endif
2511  else
2512  {
2513  P.p=kBucketClear(P.bucket);
2514  kBucketDestroy(&P.bucket);
2515  pNormalize(P.p);
2516  return P.p;
2517  }
2518  }
2519 }
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:524
int kFindDivisibleByInS_noCF(const kStrategy strat, int *max_ind, LObject *L)
Definition: kstd2.cc:484
static int redRing_S(LObject *h, kStrategy strat)
Definition: kstd2.cc:1056
static int redRing_Z_S(LObject *h, kStrategy strat)
Definition: kstd2.cc:841
#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:1438
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:410
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition: p_polys.h:858
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 2525 of file kstd2.cc.

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

◆ redRing()

int redRing ( LObject h,
kStrategy  strat 
)

Definition at line 954 of file kstd2.cc.

955 {
956  if (strat->tl<0) return 1;
957  if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
958 
959  int at/*,i*/;
960  long d;
961  int j = 0;
962  int pass = 0;
963  // poly zeroPoly = NULL;
964 
965 // TODO warum SetpFDeg notwendig?
966  h->SetpFDeg();
967  assume(h->pFDeg() == h->FDeg);
968  long reddeg = h->GetpFDeg();
969 
970  h->SetShortExpVector();
971  loop
972  {
973  j = kFindDivisibleByInT(strat, h);
974  if (j < 0)
975  {
976  // over ZZ: cleanup coefficients by complete reduction with monomials
977  postReduceByMon(h, strat);
978  if(h->p == NULL)
979  {
980  kDeleteLcm(h);
981  h->Clear();
982  return 0;
983  }
984  if(nIsZero(pGetCoeff(h->p))) return 2;
985  j = kFindDivisibleByInT(strat, h);
986  if(j < 0)
987  {
988  if(strat->tl >= 0)
989  h->i_r1 = strat->tl;
990  else
991  h->i_r1 = -1;
992  if (h->GetLmTailRing() == NULL)
993  {
994  kDeleteLcm(h);
995  h->Clear();
996  return 0;
997  }
998  return 1;
999  }
1000  }
1001  //printf("\nFound one: ");pWrite(strat->T[j].p);
1002  //enterT(*h, strat);
1003  ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
1004  //printf("\nAfter small red: ");pWrite(h->p);
1005  if (h->GetLmTailRing() == NULL)
1006  {
1007  kDeleteLcm(h);
1008  h->Clear();
1009  return 0;
1010  }
1011  h->SetShortExpVector();
1012  d = h->SetpFDeg();
1013  /*- try to reduce the s-polynomial -*/
1014  pass++;
1015  if (!TEST_OPT_REDTHROUGH &&
1016  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1017  {
1018  h->SetLmCurrRing();
1019  if (strat->posInLDependsOnLength)
1020  h->SetLength(strat->length_pLength);
1021  at = strat->posInL(strat->L,strat->Ll,h,strat);
1022  if (at <= strat->Ll)
1023  {
1024 #ifdef KDEBUG
1025  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1026 #endif
1027  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
1028  h->Clear();
1029  return -1;
1030  }
1031  }
1032  if (d != reddeg)
1033  {
1034  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1035  {
1036  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1037  {
1038  strat->overflow=TRUE;
1039  //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1040  h->GetP();
1041  at = strat->posInL(strat->L,strat->Ll,h,strat);
1042  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1043  h->Clear();
1044  return -1;
1045  }
1046  }
1047  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1048  {
1049  Print(".%ld",d);mflush();
1050  reddeg = d;
1051  }
1052  }
1053  }
1054 }
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:10763

◆ redRing_S()

static int redRing_S ( LObject h,
kStrategy  strat 
)
static

Definition at line 1056 of file kstd2.cc.

1057 {
1058  if (strat->sl<0) return 1;
1059  if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
1060 
1061  int at/*,i*/;
1062  long d;
1063  int j = 0;
1064  int pass = 0;
1065  // poly zeroPoly = NULL;
1066 
1067  h->SetpFDeg();
1068  assume(h->pFDeg() == h->FDeg);
1069  long reddeg = h->GetpFDeg();
1070  int max_ind;
1071 
1072  h->SetShortExpVector();
1073  loop
1074  {
1075  max_ind=strat->sl;
1076  j = kFindDivisibleByInS(strat, &max_ind, h);
1077  if (j < 0)
1078  {
1079  // over ZZ: cleanup coefficients by complete reduction with monomials
1080  postReduceByMon(h, strat);
1081  if(h->p == NULL)
1082  {
1083  h->Clear();
1084  return 0;
1085  }
1086  if(nIsZero(pGetCoeff(h->p))) return 2;
1087  max_ind=strat->sl;
1088  j = kFindDivisibleByInS(strat, &max_ind,h);
1089  if(j < 0)
1090  {
1091  if (h->GetLmTailRing() == NULL)
1092  {
1093  h->Clear();
1094  return 0;
1095  }
1096  return 1;
1097  }
1098  }
1099  //printf("\nFound one: ");pWrite(strat->T[j].p);
1100  //enterT(*h, strat);
1101  TObject tj(strat->S[j]);
1102  ksReducePoly(h, &tj, NULL, NULL, NULL, strat); // with debug output
1103  //printf("\nAfter small red: ");pWrite(h->p);
1104  if (h->GetLmTailRing() == NULL)
1105  {
1106  h->Clear();
1107  return 0;
1108  }
1109  h->SetShortExpVector();
1110  d = h->SetpFDeg();
1111  /*- try to reduce the s-polynomial -*/
1112  pass++;
1113  }
1114 }
class sTObject TObject
Definition: kutil.h:57

◆ redRing_Z()

int redRing_Z ( LObject h,
kStrategy  strat 
)

Definition at line 683 of file kstd2.cc.

684 {
685  if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
686  if (strat->tl<0) return 1;
687 
688  int at;
689  long d;
690  int j = 0;
691  int pass = 0;
692 
693 // TODO warum SetpFDeg notwendig?
694  h->SetpFDeg();
695  assume(h->pFDeg() == h->FDeg);
696  long reddeg = h->GetpFDeg();
697 
698  h->SetShortExpVector();
699  loop
700  {
701  /* check if a reducer of the lead term exists */
702  j = kFindDivisibleByInT(strat, h);
703  if (j < 0)
704  {
705 #if STDZ_EXCHANGE_DURING_REDUCTION
706  /* check if a reducer with the same lead monomial exists */
707  j = kFindSameLMInT_Z(strat, h);
708  if (j < 0)
709  {
710 #endif
711  /* check if a reducer of the lead monomial exists, by the above
712  * check this is a real divisor of the lead monomial */
713  j = kFindDivisibleByInT_Z(strat, h);
714  if (j < 0)
715  {
716  // over ZZ: cleanup coefficients by complete reduction with monomials
718  postReduceByMon(h, strat);
719  if(h->p == NULL)
720  {
721  if (h->lcm!=NULL) pLmDelete(h->lcm);
722  h->Clear();
723  return 0;
724  }
725  if(nIsZero(pGetCoeff(h->p))) return 2;
726  j = kFindDivisibleByInT(strat, h);
727  if(j < 0)
728  {
729  if(strat->tl >= 0)
730  h->i_r1 = strat->tl;
731  else
732  h->i_r1 = -1;
733  if (h->GetLmTailRing() == NULL)
734  {
735  if (h->lcm!=NULL) pLmDelete(h->lcm);
736  h->Clear();
737  return 0;
738  }
739  return 1;
740  }
741  }
742  else
743  {
744  /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
745  * => we try to cut down the lead coefficient at least */
746  /* first copy T[j] in order to multiply it with a coefficient later on */
747  number mult, rest;
748  TObject tj = strat->T[j];
749  tj.Copy();
750  /* tj.max_exp = strat->T[j].max_exp; */
751  /* compute division with remainder of lc(h) and lc(T[j]) */
752  mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
753  &rest, currRing->cf);
754  /* set corresponding new lead coefficient already. we do not
755  * remove the lead term in ksReducePolyLC, but only apply
756  * a lead coefficient reduction */
757  tj.Mult_nn(mult);
758  ksReducePolyLC(h, &tj, NULL, &rest, strat);
759  tj.Delete();
760  tj.Clear();
761  }
762 #if STDZ_EXCHANGE_DURING_REDUCTION
763  }
764  else
765  {
766  /* same lead monomial but lead coefficients do not divide each other:
767  * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
768  LObject h2 = *h;
769  h2.Copy();
770 
771  ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
772  ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
774  {
775  redtailBbaAlsoLC_Z(&h2, j, strat);
776  }
777  /* replace h2 for tj in L (already generated pairs with tj), S and T */
778  replaceInLAndSAndT(h2, j, strat);
779  }
780 #endif
781  }
782  else
783  {
784  ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat);
785  }
786  /* printf("\nAfter small red: ");pWrite(h->p); */
787  if (h->GetLmTailRing() == NULL)
788  {
789  if (h->lcm!=NULL) pLmDelete(h->lcm);
790 #ifdef KDEBUG
791  h->lcm=NULL;
792 #endif
793  h->Clear();
794  return 0;
795  }
796  h->SetShortExpVector();
797  d = h->SetpFDeg();
798  /*- try to reduce the s-polynomial -*/
799  pass++;
800  if (!TEST_OPT_REDTHROUGH &&
801  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
802  {
803  h->SetLmCurrRing();
804  if (strat->posInLDependsOnLength)
805  h->SetLength(strat->length_pLength);
806  at = strat->posInL(strat->L,strat->Ll,h,strat);
807  if (at <= strat->Ll)
808  {
809 #ifdef KDEBUG
810  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
811 #endif
812  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
813  h->Clear();
814  return -1;
815  }
816  }
817  if (d != reddeg)
818  {
819  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
820  {
821  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
822  {
823  strat->overflow=TRUE;
824  //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
825  h->GetP();
826  at = strat->posInL(strat->L,strat->Ll,h,strat);
827  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
828  h->Clear();
829  return -1;
830  }
831  }
832  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
833  {
834  Print(".%ld",d);mflush();
835  reddeg = d;
836  }
837  }
838  }
839 }
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:481
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:9087
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 841 of file kstd2.cc.

842 {
843  if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
844  if (strat->sl<0) return 1;
845 
846  int at;
847  long d;
848  int j = 0;
849  int pass = 0;
850 
851 // TODO warum SetpFDeg notwendig?
852  h->SetpFDeg();
853  assume(h->pFDeg() == h->FDeg);
854  long reddeg = h->GetpFDeg();
855  h->SetShortExpVector();
856  int max_ind=strat->sl;
857 
858  loop
859  {
860  /* check if a reducer of the lead term exists */
861  max_ind=strat->sl;
862  j = kFindDivisibleByInS(strat,&max_ind, h);
863  if (j < 0)
864  {
865 #if STDZ_EXCHANGE_DURING_REDUCTION
866  /* check if a reducer with the same lead monomial exists */
867  j = kFindSameLMInT_Z(strat, h);
868  if (j < 0)
869  {
870 #endif
871  /* check if a reducer of the lead monomial exists, by the above
872  * check this is a real divisor of the lead monomial */
873  j = kFindDivisibleByInS_Z(strat, h);
874  if (j < 0)
875  {
876  // over ZZ: cleanup coefficients by complete reduction with monomials
878  postReduceByMon(h, strat);
879  if(h->p == NULL)
880  {
881  h->Clear();
882  return 0;
883  }
884  if(nIsZero(pGetCoeff(h->p))) return 2;
885  max_ind=strat->sl;
886  j = kFindDivisibleByInS(strat, &max_ind, h);
887  if(j < 0)
888  {
889  if (h->GetLmTailRing() == NULL)
890  {
891  h->Clear();
892  return 0;
893  }
894  return 1;
895  }
896  }
897  else
898  {
899  /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
900  * => we try to cut down the lead coefficient at least */
901  /* first copy T[j] in order to multiply it with a coefficient later on */
902  number mult, rest;
903  TObject tj(pCopy(strat->S[j]));
904  /* compute division with remainder of lc(h) and lc(S[j]) */
905  mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->S[j]),
906  &rest, currRing->cf);
907  /* set corresponding new lead coefficient already. we do not
908  * remove the lead term in ksReducePolyLC, but only apply
909  * a lead coefficient reduction */
910  tj.Mult_nn(mult);
911  ksReducePolyLC(h, &tj, NULL, &rest, strat);
912  tj.Delete();
913  tj.Clear();
914  }
915 #if STDZ_EXCHANGE_DURING_REDUCTION
916  }
917  else
918  {
919  /* same lead monomial but lead coefficients do not divide each other:
920  * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
921  LObject h2 = *h;
922  h2.Copy();
923  TObject tj(strat->S[j]);
924 
925  ksReducePolyZ(h, &tj, NULL, NULL, strat);
926  ksReducePolyGCD(&h2, &tj, NULL, NULL, strat);
928  {
929  redtailBbaAlsoLC_Z_S(&h2, j, strat);
930  }
931  /* replace h2 for tj in L (already generated pairs with tj), S and T */
932  replaceInLAndSAndT(h2, j, strat);
933  }
934 #endif
935  }
936  else
937  {
938  TObject tj(strat->S[j]);
939  ksReducePoly(h, &tj, NULL, NULL, NULL, strat);
940  }
941  /* printf("\nAfter small red: ");pWrite(h->p); */
942  if (h->GetLmCurrRing() == NULL)
943  {
944  h->Clear();
945  return 0;
946  }
947  h->SetShortExpVector();
948  d = h->SetpFDeg();
949  /*- try to reduce the s-polynomial -*/
950  pass++;
951  }
952 }
static int kFindDivisibleByInS_Z(const kStrategy strat, LObject *L)
Definition: kstd2.cc:276

◆ redSig()

int redSig ( LObject h,
kStrategy  strat 
)

Definition at line 1343 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1511 of file kstd2.cc.

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

1762 {
1763  strat->redTailChange=FALSE;
1764  if (strat->noTailReduction) return L->GetLmCurrRing();
1765  poly h, p;
1766  p = h = L->GetLmTailRing();
1767  if ((h==NULL) || (pNext(h)==NULL))
1768  return L->GetLmCurrRing();
1769 
1770  TObject* With;
1771  // placeholder in case strat->tl < 0
1772  TObject With_s(strat->tailRing);
1773 
1774  LObject Ln(pNext(h), strat->tailRing);
1775  Ln.sig = L->sig;
1776  Ln.sevSig = L->sevSig;
1777  Ln.pLength = L->GetpLength() - 1;
1778 
1779  pNext(h) = NULL;
1780  if (L->p != NULL) pNext(L->p) = NULL;
1781  L->pLength = 1;
1782 
1783  Ln.PrepareRed(strat->use_buckets);
1784 
1785  int cnt=REDTAIL_CANONICALIZE;
1786  while(!Ln.IsNull())
1787  {
1788  loop
1789  {
1790  if(rField_is_Ring(currRing) && strat->sigdrop)
1791  break;
1792  Ln.SetShortExpVector();
1793  if (withT)
1794  {
1795  int j;
1796  j = kFindDivisibleByInT(strat, &Ln);
1797  if (j < 0) break;
1798  With = &(strat->T[j]);
1799  }
1800  else
1801  {
1802  With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1803  if (With == NULL) break;
1804  }
1805  cnt--;
1806  if (cnt==0)
1807  {
1809  /*poly tmp=*/Ln.CanonicalizeP();
1811  {
1812  Ln.Normalize();
1813  //pNormalize(tmp);
1814  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1815  }
1816  }
1817  if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
1818  {
1819  With->pNorm();
1820  }
1821  strat->redTailChange=TRUE;
1822  int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1824  L->sig = Ln.sig;
1825  //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1826  // I delete it an then set Ln.sig. Hence L->sig is lost
1827 #if SBA_PRINT_REDUCTION_STEPS
1828  if (ret != 3)
1829  sba_reduction_steps++;
1830 #endif
1831 #if SBA_PRINT_OPERATIONS
1832  if (ret != 3)
1833  sba_operations += pLength(With->p);
1834 #endif
1835  if (ret)
1836  {
1837  // reducing the tail would violate the exp bound
1838  // set a flag and hope for a retry (in bba)
1839  strat->completeReduce_retry=TRUE;
1840  if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1841  do
1842  {
1843  pNext(h) = Ln.LmExtractAndIter();
1844  pIter(h);
1845  L->pLength++;
1846  } while (!Ln.IsNull());
1847  goto all_done;
1848  }
1849  if (Ln.IsNull()) goto all_done;
1850  if (! withT) With_s.Init(currRing);
1851  if(rField_is_Ring(currRing) && strat->sigdrop)
1852  {
1853  //Cannot break the loop here so easily
1854  break;
1855  }
1856  }
1857  pNext(h) = Ln.LmExtractAndIter();
1858  pIter(h);
1859  if(!rField_is_Ring(currRing))
1860  pNormalize(h);
1861  L->pLength++;
1862  }
1863  all_done:
1864  Ln.Delete();
1865  if (L->p != NULL) pNext(L->p) = pNext(p);
1866 
1867  if (strat->redTailChange)
1868  {
1869  L->length = 0;
1870  }
1871  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1872  //L->Normalize(); // HANNES: should have a test
1873  kTest_L(L,strat);
1874  return L->GetLmCurrRing();
1875 }
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition: kstd2.cc:1305
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition: kutil.cc:926
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition: kutil.cc:6740
#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,
ideal  Q 
)

Definition at line 4972 of file kstd2.cc.

4973 {
4975  assume(idIsInV(F));
4976  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4977  idSkipZeroes(RS); // is this even necessary?
4978  assume(idIsInV(RS));
4979  return(RS);
4980 }
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2926
#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 3001 of file kstd2.cc.

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

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.