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 kFindSameLMInT_Z (const kStrategy strat, const LObject *L, const int start)
 
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)
 
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 kFindNextDivisibleByInS (const kStrategy strat, int start, int max_ind, LObject *L)
 
static long ind2 (long arg)
 
static long ind_fact_2 (long arg)
 
poly kFindZeroPoly (poly input_p, ring leadRing, ring tailRing)
 
int redRing_Z (LObject *h, kStrategy strat)
 
int redRing (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 2390 of file kstd2.cc.

2391 {
2392  int red_result = 1;
2393  int olddeg,reduc;
2394  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2395  BOOLEAN withT = FALSE;
2396  BITSET save;
2397  SI_SAVE_OPT1(save);
2398 
2399  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2401  initBuchMoraPosRing(strat);
2402  else
2403  initBuchMoraPos(strat);
2404  initHilbCrit(F,Q,&hilb,strat);
2405  initBba(strat);
2406  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2407  /*Shdl=*/initBuchMora(F, Q,strat);
2408  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2409  reduc = olddeg = 0;
2410 
2411 #ifndef NO_BUCKETS
2412  if (!TEST_OPT_NOT_BUCKETS)
2413  strat->use_buckets = 1;
2414 #endif
2415  // redtailBBa against T for inhomogenous input
2416  if (!TEST_OPT_OLDSTD)
2417  withT = ! strat->homog;
2418 
2419  // strat->posInT = posInT_pLength;
2420  kTest_TS(strat);
2421 
2422 #ifdef HAVE_TAIL_RING
2423  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2424  kStratInitChangeTailRing(strat);
2425 #endif
2426  if (BVERBOSE(23))
2427  {
2428  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2429  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2430  kDebugPrint(strat);
2431  }
2432 
2433 
2434 #ifdef KDEBUG
2435  //kDebugPrint(strat);
2436 #endif
2437  /* compute------------------------------------------------------- */
2438  while (strat->Ll >= 0)
2439  {
2440  #ifdef KDEBUG
2441  if (TEST_OPT_DEBUG) messageSets(strat);
2442  #endif
2443  if (siCntrlc)
2444  {
2445  while (strat->Ll >= 0)
2446  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2447  strat->noClearS=TRUE;
2448  }
2449  if (TEST_OPT_DEGBOUND
2450  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2451  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2452  {
2453  /*
2454  *stops computation if
2455  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2456  *a predefined number Kstd1_deg
2457  */
2458  while ((strat->Ll >= 0)
2459  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2460  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2461  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2462  )
2463  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2464  if (strat->Ll<0) break;
2465  else strat->noClearS=TRUE;
2466  }
2467  if (strat->Ll== 0) strat->interpt=TRUE;
2468  /* picks the last element from the lazyset L */
2469  strat->P = strat->L[strat->Ll];
2470  strat->Ll--;
2471 
2472  if (pNext(strat->P.p) == strat->tail)
2473  {
2474  // deletes the short spoly
2475  if (rField_is_Ring(currRing))
2476  pLmDelete(strat->P.p);
2477  else
2478  pLmFree(strat->P.p);
2479  strat->P.p = NULL;
2480  poly m1 = NULL, m2 = NULL;
2481 
2482  // check that spoly creation is ok
2483  while (strat->tailRing != currRing &&
2484  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2485  {
2486  assume(m1 == NULL && m2 == NULL);
2487  // if not, change to a ring where exponents are at least
2488  // large enough
2489  if (!kStratChangeTailRing(strat))
2490  {
2491  WerrorS("OVERFLOW...");
2492  break;
2493  }
2494  }
2495  // create the real one
2496  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2497  strat->tailRing, m1, m2, strat->R);
2498  }
2499  else if (strat->P.p1 == NULL)
2500  {
2501  if (strat->minim > 0)
2502  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2503  // for input polys, prepare reduction
2504  strat->P.PrepareRed(strat->use_buckets);
2505  }
2506 
2507  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2508  {
2509  red_result = 0;
2510  }
2511  else
2512  {
2513  if (TEST_OPT_PROT)
2514  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2515  &olddeg,&reduc,strat, red_result);
2516 
2517  /* reduction of the element chosen from L */
2518  red_result = strat->red(&strat->P,strat);
2519  if (errorreported) break;
2520  }
2521 
2522  if (strat->overflow)
2523  {
2524  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2525  }
2526 
2527  // reduction to non-zero new poly
2528  if (red_result == 1)
2529  {
2530  // get the polynomial (canonicalize bucket, make sure P.p is set)
2531  strat->P.GetP(strat->lmBin);
2532  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2533  // but now, for entering S, T, we reset it
2534  // in the inhomogeneous case: FDeg == pFDeg
2535  if (strat->homog) strat->initEcart(&(strat->P));
2536 
2537  /* statistic */
2538  if (TEST_OPT_PROT) PrintS("s");
2539 
2540  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2541 
2542  // reduce the tail and normalize poly
2543  // in the ring case we cannot expect LC(f) = 1,
2544  strat->redTailChange=FALSE;
2545 
2546  /* if we are computing over Z we always want to try and cut down
2547  * the coefficients in the tail terms */
2549  {
2550  redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2551  }
2552 
2554  {
2555  strat->P.pCleardenom();
2557  {
2558  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2559  strat->P.pCleardenom();
2560  if (strat->redTailChange) { strat->P.t_p=NULL; }
2561  }
2562  }
2563  else
2564  {
2565  strat->P.pNorm();
2567  {
2568  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2569  if (strat->redTailChange) { strat->P.t_p=NULL; }
2570  }
2571  }
2572 
2573 #ifdef KDEBUG
2574  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2575 #endif /* KDEBUG */
2576 
2577  // min_std stuff
2578  if ((strat->P.p1==NULL) && (strat->minim>0))
2579  {
2580  if (strat->minim==1)
2581  {
2582  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2583  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2584  }
2585  else
2586  {
2587  strat->M->m[minimcnt]=strat->P.p2;
2588  strat->P.p2=NULL;
2589  }
2590  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2591  pNext(strat->M->m[minimcnt])
2592  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2593  strat->tailRing, currRing,
2594  currRing->PolyBin);
2595  minimcnt++;
2596  }
2597 
2598  // enter into S, L, and T
2599  if (((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2600  && ((!TEST_OPT_IDELIM) || (p_Deg(strat->P.p,currRing) > 0)))
2601  {
2602  strat->P.SetShortExpVector();
2603  enterT(strat->P, strat);
2604  if (rField_is_Ring(currRing))
2605  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2606  else
2607  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2608  // posInS only depends on the leading term
2609  strat->enterS(strat->P, pos, strat, strat->tl);
2610 #if 0
2611  int pl=pLength(strat->P.p);
2612  if (pl==1)
2613  {
2614  //if (TEST_OPT_PROT)
2615  //PrintS("<1>");
2616  }
2617  else if (pl==2)
2618  {
2619  //if (TEST_OPT_PROT)
2620  //PrintS("<2>");
2621  }
2622 #endif
2623  }
2624  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2625 // Print("[%d]",hilbeledeg);
2626  kDeleteLcm(&strat->P);
2627  if (strat->s_poly!=NULL)
2628  {
2629  // the only valid entries are: strat->P.p,
2630  // strat->tailRing (read-only, keep it)
2631  // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2632  if (strat->s_poly(strat))
2633  {
2634  // we are called AFTER enterS, i.e. if we change P
2635  // we have to add it also to S/T
2636  // and add pairs
2637  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2638  enterT(strat->P, strat);
2639  if (rField_is_Ring(currRing))
2640  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2641  else
2642  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2643  strat->enterS(strat->P, pos, strat, strat->tl);
2644  }
2645  }
2646  }
2647  else if (strat->P.p1 == NULL && strat->minim > 0)
2648  {
2649  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2650  }
2651 
2652 #ifdef KDEBUG
2653  memset(&(strat->P), 0, sizeof(strat->P));
2654 #endif /* KDEBUG */
2655  kTest_TS(strat);
2656  }
2657 #ifdef KDEBUG
2658  if (TEST_OPT_DEBUG) messageSets(strat);
2659 #endif /* KDEBUG */
2660 
2661  if (TEST_OPT_SB_1)
2662  {
2663  if(!rField_is_Ring(currRing))
2664  {
2665  int k=1;
2666  int j;
2667  while(k<=strat->sl)
2668  {
2669  j=0;
2670  loop
2671  {
2672  if (j>=k) break;
2673  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2674  j++;
2675  }
2676  k++;
2677  }
2678  }
2679  }
2680  /* complete reduction of the standard basis--------- */
2681  if (TEST_OPT_REDSB)
2682  {
2683  completeReduce(strat);
2684  if (strat->completeReduce_retry)
2685  {
2686  // completeReduce needed larger exponents, retry
2687  // to reduce with S (instead of T)
2688  // and in currRing (instead of strat->tailRing)
2689 #ifdef HAVE_TAIL_RING
2690  if(currRing->bitmask>strat->tailRing->bitmask)
2691  {
2692  strat->completeReduce_retry=FALSE;
2693  cleanT(strat);strat->tailRing=currRing;
2694  int i;
2695  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2696  completeReduce(strat);
2697  }
2698  if (strat->completeReduce_retry)
2699 #endif
2700  Werror("exponent bound is %ld",currRing->bitmask);
2701  }
2702  }
2703  else if (TEST_OPT_PROT) PrintLn();
2704  /* release temp data-------------------------------- */
2705  exitBuchMora(strat);
2706  /* postprocessing for GB over ZZ --------------------*/
2707  if (!errorreported)
2708  {
2709  if(rField_is_Z(currRing))
2710  {
2711  for(int i = 0;i<=strat->sl;i++)
2712  {
2713  if(!nGreaterZero(pGetCoeff(strat->S[i])))
2714  {
2715  strat->S[i] = pNeg(strat->S[i]);
2716  }
2717  }
2718  finalReduceByMon(strat);
2719  for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2720  {
2721  if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2722  {
2723  strat->S[i] = pNeg(strat->Shdl->m[i]);
2724  }
2725  }
2726  }
2727  //else if (rField_is_Ring(currRing))
2728  // finalReduceByMon(strat);
2729  }
2730 // if (TEST_OPT_WEIGHTM)
2731 // {
2732 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2733 // if (ecartWeights)
2734 // {
2735 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2736 // ecartWeights=NULL;
2737 // }
2738 // }
2739  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2740  SI_RESTORE_OPT1(save);
2741  /* postprocessing for GB over Q-rings ------------------*/
2742  if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2743 
2744  idTest(strat->Shdl);
2745 
2746  return (strat->Shdl);
2747 }
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int syzComp
Definition: kutil.h:354
int * S_2_R
Definition: kutil.h:342
ring tailRing
Definition: kutil.h:343
int Ll
Definition: kutil.h:351
omBin lmBin
Definition: kutil.h:344
char honey
Definition: kutil.h:377
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:1223
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition: kInline.h:1248
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:1185
void initBba(kStrategy strat)
Definition: kstd1.cc:1676
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:11833
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:7784
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10073
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9450
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1097
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4587
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7452
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9730
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9900
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11294
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10158
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4763
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10807
void cleanT(kStrategy strat)
Definition: kutil.cc:569
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10401
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4556
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1295
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11387
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9748
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10613
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9986
void messageSets(kStrategy strat)
Definition: kutil.cc:7857
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7825
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11201
static void kDeleteLcm(LObject *P)
Definition: kutil.h:886
#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 void p_Delete(poly *p, const ring r)
Definition: p_polys.h:903
static unsigned pLength(poly a)
Definition: p_polys.h:191
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:848
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:510
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:761
#define rField_is_Ring(R)
Definition: ring.h:486
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 4358 of file kstd2.cc.

4359 {
4360  int red_result = 1;
4361  int olddeg,reduc;
4362  int hilbeledeg=1,hilbcount=0,minimcnt=0;
4363  BOOLEAN withT = TRUE; // currently only T contains the shifts
4364  BITSET save;
4365  SI_SAVE_OPT1(save);
4366 
4367  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4369  initBuchMoraPosRing(strat);
4370  else
4371  initBuchMoraPos(strat);
4372  initHilbCrit(F,Q,&hilb,strat);
4373  initBba(strat);
4374  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4375  /*Shdl=*/initBuchMora(F, Q,strat);
4376  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4377  reduc = olddeg = 0;
4378 
4379 #ifndef NO_BUCKETS
4380  if (!TEST_OPT_NOT_BUCKETS)
4381  strat->use_buckets = 1;
4382 #endif
4383  // redtailBBa against T for inhomogenous input
4384  // if (!TEST_OPT_OLDSTD)
4385  // withT = ! strat->homog;
4386 
4387  // strat->posInT = posInT_pLength;
4388  kTest_TS(strat);
4389 
4390 #ifdef HAVE_TAIL_RING
4391  // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4392  // kStratInitChangeTailRing(strat);
4393  strat->tailRing=currRing;
4394 #endif
4395  if (BVERBOSE(23))
4396  {
4397  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4398  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4399  kDebugPrint(strat);
4400  }
4401 
4402 #ifdef KDEBUG
4403  //kDebugPrint(strat);
4404 #endif
4405  /* compute------------------------------------------------------- */
4406  while (strat->Ll >= 0)
4407  {
4408  #ifdef KDEBUG
4409  if (TEST_OPT_DEBUG) messageSets(strat);
4410  #endif
4411  if (siCntrlc)
4412  {
4413  while (strat->Ll >= 0)
4414  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4415  strat->noClearS=TRUE;
4416  }
4417  if (TEST_OPT_DEGBOUND
4418  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4419  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4420  {
4421  /*
4422  *stops computation if
4423  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4424  *a predefined number Kstd1_deg
4425  */
4426  while ((strat->Ll >= 0)
4427  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4428  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4429  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4430  )
4431  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4432  if (strat->Ll<0) break;
4433  else strat->noClearS=TRUE;
4434  }
4435  if (strat->Ll== 0) strat->interpt=TRUE;
4436  /* picks the last element from the lazyset L */
4437  strat->P = strat->L[strat->Ll];
4438  strat->Ll--;
4439 
4440  if (pNext(strat->P.p) == strat->tail)
4441  {
4442  // deletes the short spoly
4443  if (rField_is_Ring(currRing))
4444  pLmDelete(strat->P.p);
4445  else
4446  pLmFree(strat->P.p);
4447  strat->P.p = NULL;
4448  poly m1 = NULL, m2 = NULL;
4449 
4450  // check that spoly creation is ok
4451  while (strat->tailRing != currRing &&
4452  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4453  {
4454  assume(m1 == NULL && m2 == NULL);
4455  // if not, change to a ring where exponents are at least
4456  // large enough
4457  if (!kStratChangeTailRing(strat))
4458  {
4459  WerrorS("OVERFLOW...");
4460  break;
4461  }
4462  }
4463  // create the real one
4464  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4465  strat->tailRing, m1, m2, strat->R);
4466  }
4467  else if (strat->P.p1 == NULL)
4468  {
4469  if (strat->minim > 0)
4470  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4471  // for input polys, prepare reduction
4472  strat->P.PrepareRed(strat->use_buckets);
4473  }
4474 
4475  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4476  {
4477  red_result = 0;
4478  }
4479  else
4480  {
4481  if (TEST_OPT_PROT)
4482  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4483  &olddeg,&reduc,strat, red_result);
4484 
4485  /* reduction of the element chosen from L */
4486  red_result = strat->red(&strat->P,strat);
4487  if (errorreported) break;
4488  }
4489 
4490  if (strat->overflow)
4491  {
4492  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4493  }
4494 
4495  // reduction to non-zero new poly
4496  if (red_result == 1)
4497  {
4498  // get the polynomial (canonicalize bucket, make sure P.p is set)
4499  strat->P.GetP(strat->lmBin);
4500  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4501  // but now, for entering S, T, we reset it
4502  // in the inhomogeneous case: FDeg == pFDeg
4503  if (strat->homog) strat->initEcart(&(strat->P));
4504 
4505  /* statistic */
4506  if (TEST_OPT_PROT) PrintS("s");
4507 
4508  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4509 
4510  // reduce the tail and normalize poly
4511  // in the ring case we cannot expect LC(f) = 1,
4512  strat->redTailChange=FALSE;
4513 
4514  /* if we are computing over Z we always want to try and cut down
4515  * the coefficients in the tail terms */
4517  {
4518  redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4519  }
4520 
4522  {
4523  strat->P.pCleardenom();
4525  {
4526  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4527  strat->P.pCleardenom();
4528  if (strat->redTailChange)
4529  {
4530  strat->P.t_p=NULL;
4531  strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4532  }
4533  }
4534  }
4535  else
4536  {
4537  strat->P.pNorm();
4539  {
4540  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4541  if (strat->redTailChange)
4542  {
4543  strat->P.t_p=NULL;
4544  strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4545  }
4546  }
4547  }
4548 
4549 #ifdef KDEBUG
4550  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4551 #endif /* KDEBUG */
4552 
4553  // min_std stuff
4554  if ((strat->P.p1==NULL) && (strat->minim>0))
4555  {
4556  if (strat->minim==1)
4557  {
4558  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4559  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4560  }
4561  else
4562  {
4563  strat->M->m[minimcnt]=strat->P.p2;
4564  strat->P.p2=NULL;
4565  }
4566  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4567  pNext(strat->M->m[minimcnt])
4568  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4569  strat->tailRing, currRing,
4570  currRing->PolyBin);
4571  minimcnt++;
4572  }
4573 
4574 
4575  // enter into S, L, and T
4576  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4577  {
4578  enterT(strat->P, strat);
4579  enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4580  // posInS only depends on the leading term
4581  strat->enterS(strat->P, pos, strat, strat->tl);
4582  if (!strat->rightGB)
4583  enterTShift(strat->P, strat);
4584  }
4585 
4586  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4587 // Print("[%d]",hilbeledeg);
4588  kDeleteLcm(&strat->P);
4589  if (strat->s_poly!=NULL)
4590  {
4591  // the only valid entries are: strat->P.p,
4592  // strat->tailRing (read-only, keep it)
4593  // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4594  if (strat->s_poly(strat))
4595  {
4596  // we are called AFTER enterS, i.e. if we change P
4597  // we have to add it also to S/T
4598  // and add pairs
4599  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4600  enterT(strat->P, strat);
4601  enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4602  strat->enterS(strat->P, pos, strat, strat->tl);
4603  if (!strat->rightGB)
4604  enterTShift(strat->P,strat);
4605  }
4606  }
4607  }
4608  else if (strat->P.p1 == NULL && strat->minim > 0)
4609  {
4610  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4611  }
4612 #ifdef KDEBUG
4613  memset(&(strat->P), 0, sizeof(strat->P));
4614 #endif /* KDEBUG */
4615  kTest_TS(strat);
4616  }
4617 #ifdef KDEBUG
4618  if (TEST_OPT_DEBUG) messageSets(strat);
4619 #endif /* KDEBUG */
4620  /* shift case: look for elt's in S such that they are divisible by elt in T */
4621  if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4622  {
4623  if(!rField_is_Ring(currRing))
4624  {
4625  for (int k = 0; k <= strat->sl; ++k)
4626  {
4627  if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4628  for (int j = 0; j<=strat->tl; ++j)
4629  {
4630  if (strat->T[j].p!=NULL)
4631  {
4632  // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4633  assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4634  assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4635  if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4636  {
4637  if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4638  { // check whether LM is different
4639  deleteInS(k, strat);
4640  --k;
4641  break;
4642  }
4643  }
4644  }
4645  }
4646  }
4647  }
4648  }
4649  /* complete reduction of the standard basis--------- */
4650  if (TEST_OPT_REDSB)
4651  {
4652  completeReduce(strat, TRUE); //shift: withT = TRUE
4653  if (strat->completeReduce_retry)
4654  {
4655  // completeReduce needed larger exponents, retry
4656  // to reduce with S (instead of T)
4657  // and in currRing (instead of strat->tailRing)
4658 #ifdef HAVE_TAIL_RING
4659  if(currRing->bitmask>strat->tailRing->bitmask)
4660  {
4661  strat->completeReduce_retry=FALSE;
4662  cleanT(strat);strat->tailRing=currRing;
4663  int i;
4664  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4665  WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4666  completeReduce(strat);
4667  }
4668  if (strat->completeReduce_retry)
4669 #endif
4670  Werror("exponent bound is %ld",currRing->bitmask);
4671  }
4672  }
4673  else if (TEST_OPT_PROT) PrintLn();
4674 
4675  /* release temp data-------------------------------- */
4676  exitBuchMora(strat);
4677  /* postprocessing for GB over ZZ --------------------*/
4678  if (!errorreported)
4679  {
4680  if(rField_is_Z(currRing))
4681  {
4682  for(int i = 0;i<=strat->sl;i++)
4683  {
4684  if(!nGreaterZero(pGetCoeff(strat->S[i])))
4685  {
4686  strat->S[i] = pNeg(strat->S[i]);
4687  }
4688  }
4689  finalReduceByMon(strat);
4690  for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4691  {
4692  if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4693  {
4694  strat->S[i] = pNeg(strat->Shdl->m[i]);
4695  }
4696  }
4697  }
4698  //else if (rField_is_Ring(currRing))
4699  // finalReduceByMon(strat);
4700  }
4701 // if (TEST_OPT_WEIGHTM)
4702 // {
4703 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4704 // if (ecartWeights)
4705 // {
4706 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4707 // ecartWeights=NULL;
4708 // }
4709 // }
4710  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4711  SI_RESTORE_OPT1(save);
4712  /* postprocessing for GB over Q-rings ------------------*/
4713  if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4714 
4715  idTest(strat->Shdl);
4716 
4717  return (strat->Shdl);
4718 }
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:13450
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13420
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1163
#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 4046 of file kstd2.cc.

4049 {
4050  int Ll_old, red_result = 1;
4051  int pos = 0;
4052  hilbeledeg=1;
4053  hilbcount=0;
4054  minimcnt=0;
4055  srmax = 0; // strat->sl is 0 at this point
4056  reduc = olddeg = lrmax = 0;
4057  // we cannot use strat->T anymore
4058  //cleanT(strat);
4059  //strat->tl = -1;
4060  Ll_old = strat->Ll;
4061  while (strat->tl >= 0)
4062  {
4063  if(!strat->T[strat->tl].is_redundant)
4064  {
4065  LObject h;
4066  h.p = strat->T[strat->tl].p;
4067  h.tailRing = strat->T[strat->tl].tailRing;
4068  h.t_p = strat->T[strat->tl].t_p;
4069  if (h.p!=NULL)
4070  {
4071  if (currRing->OrdSgn==-1)
4072  {
4073  cancelunit(&h);
4074  deleteHC(&h, strat);
4075  }
4076  if (h.p!=NULL)
4077  {
4079  {
4080  h.pCleardenom(); // also does remove Content
4081  }
4082  else
4083  {
4084  h.pNorm();
4085  }
4086  strat->initEcart(&h);
4088  pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4089  else
4090  pos = strat->Ll+1;
4091  h.sev = pGetShortExpVector(h.p);
4092  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4093  }
4094  }
4095  }
4096  strat->tl--;
4097  }
4098  strat->sl = -1;
4099 #if 0
4100 //#ifdef HAVE_TAIL_RING
4101  if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4102  kStratInitChangeTailRing(strat);
4103 #endif
4104  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
4105  //strat->sl = -1;
4106  /* picks the last element from the lazyset L */
4107  while (strat->Ll>Ll_old)
4108  {
4109  strat->P = strat->L[strat->Ll];
4110  strat->Ll--;
4111 //#if 1
4112 #ifdef DEBUGF5
4113  PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4114  PrintS("-------------------------------------------------\n");
4115  pWrite(pHead(strat->P.p));
4116  pWrite(pHead(strat->P.p1));
4117  pWrite(pHead(strat->P.p2));
4118  printf("%d\n",strat->tl);
4119  PrintS("-------------------------------------------------\n");
4120 #endif
4121  if (pNext(strat->P.p) == strat->tail)
4122  {
4123  // deletes the short spoly
4124  if (rField_is_Ring(currRing))
4125  pLmDelete(strat->P.p);
4126  else
4127  pLmFree(strat->P.p);
4128 
4129  // TODO: needs some masking
4130  // TODO: masking needs to vanish once the signature
4131  // sutff is completely implemented
4132  strat->P.p = NULL;
4133  poly m1 = NULL, m2 = NULL;
4134 
4135  // check that spoly creation is ok
4136  while (strat->tailRing != currRing &&
4137  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4138  {
4139  assume(m1 == NULL && m2 == NULL);
4140  // if not, change to a ring where exponents are at least
4141  // large enough
4142  if (!kStratChangeTailRing(strat))
4143  {
4144  WerrorS("OVERFLOW...");
4145  break;
4146  }
4147  }
4148  // create the real one
4149  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4150  strat->tailRing, m1, m2, strat->R);
4151  }
4152  else if (strat->P.p1 == NULL)
4153  {
4154  if (strat->minim > 0)
4155  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4156  // for input polys, prepare reduction
4157  if(!rField_is_Ring(currRing))
4158  strat->P.PrepareRed(strat->use_buckets);
4159  }
4160 
4161  if (strat->P.p == NULL && strat->P.t_p == NULL)
4162  {
4163  red_result = 0;
4164  }
4165  else
4166  {
4167  if (TEST_OPT_PROT)
4168  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4169  &olddeg,&reduc,strat, red_result);
4170 
4171 #ifdef DEBUGF5
4172  PrintS("Poly before red: ");
4173  pWrite(strat->P.p);
4174 #endif
4175  /* complete reduction of the element chosen from L */
4176  red_result = strat->red2(&strat->P,strat);
4177  if (errorreported) break;
4178  }
4179 
4180  if (strat->overflow)
4181  {
4182  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4183  }
4184 
4185  // reduction to non-zero new poly
4186  if (red_result == 1)
4187  {
4188  // get the polynomial (canonicalize bucket, make sure P.p is set)
4189  strat->P.GetP(strat->lmBin);
4190  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4191  // but now, for entering S, T, we reset it
4192  // in the inhomogeneous case: FDeg == pFDeg
4193  if (strat->homog) strat->initEcart(&(strat->P));
4194 
4195  /* statistic */
4196  if (TEST_OPT_PROT) PrintS("s");
4197  int pos;
4198  #if 1
4199  if(!rField_is_Ring(currRing))
4200  pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4201  else
4202  pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4203  #else
4204  pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4205  #endif
4206  // reduce the tail and normalize poly
4207  // in the ring case we cannot expect LC(f) = 1,
4208 #if F5CTAILRED
4209  BOOLEAN withT = TRUE;
4211  {
4212  strat->P.pCleardenom();
4214  {
4215  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4216  strat->P.pCleardenom();
4217  }
4218  }
4219  else
4220  {
4221  strat->P.pNorm();
4223  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4224  }
4225 #endif
4226 #ifdef KDEBUG
4227  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4228 #endif /* KDEBUG */
4229 
4230  // min_std stuff
4231  if ((strat->P.p1==NULL) && (strat->minim>0))
4232  {
4233  if (strat->minim==1)
4234  {
4235  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4236  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4237  }
4238  else
4239  {
4240  strat->M->m[minimcnt]=strat->P.p2;
4241  strat->P.p2=NULL;
4242  }
4243  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4244  pNext(strat->M->m[minimcnt])
4245  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4246  strat->tailRing, currRing,
4247  currRing->PolyBin);
4248  minimcnt++;
4249  }
4250 
4251  // enter into S, L, and T
4252  // here we need to recompute new signatures, but those are trivial ones
4253  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4254  {
4255  enterT(strat->P, strat);
4256  // posInS only depends on the leading term
4257  strat->enterS(strat->P, pos, strat, strat->tl);
4258 //#if 1
4259 #ifdef DEBUGF5
4260  PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4261  pWrite(pHead(strat->S[strat->sl]));
4262  pWrite(strat->sig[strat->sl]);
4263 #endif
4264  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4265  }
4266  // Print("[%d]",hilbeledeg);
4267  kDeleteLcm(&strat->P);
4268  if (strat->sl>srmax) srmax = strat->sl;
4269  }
4270  else
4271  {
4272  // adds signature of the zero reduction to
4273  // strat->syz. This is the leading term of
4274  // syzygy and can be used in syzCriterion()
4275  // the signature is added if and only if the
4276  // pair was not detected by the rewritten criterion in strat->red = redSig
4277  if (strat->P.p1 == NULL && strat->minim > 0)
4278  {
4279  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4280  }
4281  }
4282 
4283 #ifdef KDEBUG
4284  memset(&(strat->P), 0, sizeof(strat->P));
4285 #endif /* KDEBUG */
4286  }
4287  int cc = 0;
4288  while (cc<strat->tl+1)
4289  {
4290  strat->T[cc].sig = pOne();
4291  p_SetComp(strat->T[cc].sig,cc+1,currRing);
4292  strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4293  strat->sig[cc] = strat->T[cc].sig;
4294  strat->sevSig[cc] = strat->T[cc].sevSig;
4295  strat->T[cc].is_sigsafe = TRUE;
4296  cc++;
4297  }
4298  strat->max_lower_index = strat->tl;
4299  // set current signature index of upcoming iteration step
4300  // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4301  // the corresponding syzygy rules correctly
4302  strat->currIdx = cc+1;
4303  for (int cd=strat->Ll; cd>=0; cd--)
4304  {
4305  p_SetComp(strat->L[cd].sig,cc+1,currRing);
4306  cc++;
4307  }
4308  for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4309  strat->Shdl->m[cc] = NULL;
4310  #if 0
4311  printf("\nAfter f5c sorting\n");
4312  for(int i=0;i<=strat->sl;i++)
4313  pWrite(pHead(strat->S[i]));
4314  getchar();
4315  #endif
4316 //#if 1
4317 #if DEBUGF5
4318  PrintS("------------------- STRAT S ---------------------\n");
4319  cc = 0;
4320  while (cc<strat->tl+1)
4321  {
4322  pWrite(pHead(strat->S[cc]));
4323  pWrite(strat->sig[cc]);
4324  printf("- - - - - -\n");
4325  cc++;
4326  }
4327  PrintS("-------------------------------------------------\n");
4328  PrintS("------------------- STRAT T ---------------------\n");
4329  cc = 0;
4330  while (cc<strat->tl+1)
4331  {
4332  pWrite(pHead(strat->T[cc].p));
4333  pWrite(strat->T[cc].sig);
4334  printf("- - - - - -\n");
4335  cc++;
4336  }
4337  PrintS("-------------------------------------------------\n");
4338  PrintS("------------------- STRAT L ---------------------\n");
4339  cc = 0;
4340  while (cc<strat->Ll+1)
4341  {
4342  pWrite(pHead(strat->L[cc].p));
4343  pWrite(pHead(strat->L[cc].p1));
4344  pWrite(pHead(strat->L[cc].p2));
4345  pWrite(strat->L[cc].sig);
4346  printf("- - - - - -\n");
4347  cc++;
4348  }
4349  PrintS("-------------------------------------------------\n");
4350  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4351 #endif
4352 
4353 }
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:1360
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition: kutil.cc:4864
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:6136
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:249
#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

◆ ind2()

static long ind2 ( long  arg)
static

Definition at line 532 of file kstd2.cc.

533 {
534  if (arg <= 0) return 0;
535  long ind = 0;
536  while (arg%2 == 0)
537  {
538  arg = arg / 2;
539  ind++;
540  }
541  return ind;
542 }

◆ ind_fact_2()

static long ind_fact_2 ( long  arg)
static

Definition at line 544 of file kstd2.cc.

545 {
546  if (arg <= 0) return 0;
547  long ind = 0;
548  if (arg%2 == 1) { arg--; }
549  while (arg > 0)
550  {
551  ind += ind2(arg);
552  arg = arg - 2;
553  }
554  return ind;
555 }
static long ind2(long arg)
Definition: kstd2.cc:532

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11833 of file kutil.cc.

11834 {
11835  PrintS("red: ");
11836  if (strat->red==redFirst) PrintS("redFirst\n");
11837  else if (strat->red==redHoney) PrintS("redHoney\n");
11838  else if (strat->red==redEcart) PrintS("redEcart\n");
11839  else if (strat->red==redHomog) PrintS("redHomog\n");
11840  else if (strat->red==redLazy) PrintS("redLazy\n");
11841  else if (strat->red==redLiftstd) PrintS("redLiftstd\n");
11842  else Print("%p\n",(void*)strat->red);
11843  PrintS("posInT: ");
11844  if (strat->posInT==posInT0) PrintS("posInT0\n");
11845  else if (strat->posInT==posInT1) PrintS("posInT1\n");
11846  else if (strat->posInT==posInT11) PrintS("posInT11\n");
11847  else if (strat->posInT==posInT110) PrintS("posInT110\n");
11848  else if (strat->posInT==posInT13) PrintS("posInT13\n");
11849  else if (strat->posInT==posInT15) PrintS("posInT15\n");
11850  else if (strat->posInT==posInT17) PrintS("posInT17\n");
11851  else if (strat->posInT==posInT17_c) PrintS("posInT17_c\n");
11852  else if (strat->posInT==posInT19) PrintS("posInT19\n");
11853  else if (strat->posInT==posInT2) PrintS("posInT2\n");
11854  #ifdef HAVE_RINGS
11855  else if (strat->posInT==posInT11Ring) PrintS("posInT11Ring\n");
11856  else if (strat->posInT==posInT110Ring) PrintS("posInT110Ring\n");
11857  else if (strat->posInT==posInT15Ring) PrintS("posInT15Ring\n");
11858  else if (strat->posInT==posInT17Ring) PrintS("posInT17Ring\n");
11859  else if (strat->posInT==posInT17_cRing) PrintS("posInT17_cRing\n");
11860  #endif
11861 #ifdef HAVE_MORE_POS_IN_T
11862  else if (strat->posInT==posInT_EcartFDegpLength) PrintS("posInT_EcartFDegpLength\n");
11863  else if (strat->posInT==posInT_FDegpLength) PrintS("posInT_FDegpLength\n");
11864  else if (strat->posInT==posInT_pLength) PrintS("posInT_pLength\n");
11865 #endif
11866  else if (strat->posInT==posInT_EcartpLength) PrintS("posInT_EcartpLength\n");
11867  else if (strat->posInT==posInTrg0) PrintS("posInTrg0\n");
11868  else Print("%p\n",(void*)strat->posInT);
11869  PrintS("posInL: ");
11870  if (strat->posInL==posInL0) PrintS("posInL0\n");
11871  else if (strat->posInL==posInL10) PrintS("posInL10\n");
11872  else if (strat->posInL==posInL11) PrintS("posInL11\n");
11873  else if (strat->posInL==posInL110) PrintS("posInL110\n");
11874  else if (strat->posInL==posInL13) PrintS("posInL13\n");
11875  else if (strat->posInL==posInL15) PrintS("posInL15\n");
11876  else if (strat->posInL==posInL17) PrintS("posInL17\n");
11877  else if (strat->posInL==posInL17_c) PrintS("posInL17_c\n");
11878  #ifdef HAVE_RINGS
11879  else if (strat->posInL==posInL0) PrintS("posInL0Ring\n");
11880  else if (strat->posInL==posInL11Ring) PrintS("posInL11Ring\n");
11881  else if (strat->posInL==posInL11Ringls) PrintS("posInL11Ringls\n");
11882  else if (strat->posInL==posInL110Ring) PrintS("posInL110Ring\n");
11883  else if (strat->posInL==posInL15Ring) PrintS("posInL15Ring\n");
11884  else if (strat->posInL==posInL17Ring) PrintS("posInL17Ring\n");
11885  else if (strat->posInL==posInL17_cRing) PrintS("posInL17_cRing\n");
11886  #endif
11887  else if (strat->posInL==posInLSpecial) PrintS("posInLSpecial\n");
11888  else if (strat->posInL==posInLrg0) PrintS("posInLrg0\n");
11889  else Print("%p\n",(void*)strat->posInL);
11890  PrintS("enterS: ");
11891  if (strat->enterS==enterSBba) PrintS("enterSBba\n");
11892  else if (strat->enterS==enterSMora) PrintS("enterSMora\n");
11893  else if (strat->enterS==enterSMoraNF) PrintS("enterSMoraNF\n");
11894  else Print("%p\n",(void*)strat->enterS);
11895  PrintS("initEcart: ");
11896  if (strat->initEcart==initEcartBBA) PrintS("initEcartBBA\n");
11897  else if (strat->initEcart==initEcartNormal) PrintS("initEcartNormal\n");
11898  else Print("%p\n",(void*)strat->initEcart);
11899  PrintS("initEcartPair: ");
11900  if (strat->initEcartPair==initEcartPairBba) PrintS("initEcartPairBba\n");
11901  else if (strat->initEcartPair==initEcartPairMora) PrintS("initEcartPairMora\n");
11902  else Print("%p\n",(void*)strat->initEcartPair);
11903  Print("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11904  strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11905  Print("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11906  strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11907  PrintS("chainCrit: ");
11908  if (strat->chainCrit==chainCritNormal) PrintS("chainCritNormal\n");
11909  else if (strat->chainCrit==chainCritOpt_1) PrintS("chainCritOpt_1\n");
11910  else Print("%p\n",(void*)strat->chainCrit);
11911  Print("posInLDependsOnLength=%d\n",
11912  strat->posInLDependsOnLength);
11913  PrintS(showOption());PrintLn();
11914  PrintS("LDeg: ");
11915  if (currRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11916  else if (currRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11917  else if (currRing->pLDeg==pLDegb) PrintS("pLDegb");
11918  else if (currRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11919  else if (currRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11920  else if (currRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11921  else if (currRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11922  else if (currRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11923  else if (currRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11924  else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11925  else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11926  else if (currRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11927  else Print("? (%lx)", (long)currRing->pLDeg);
11928  PrintS(" / ");
11929  if (strat->tailRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11930  else if (strat->tailRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11931  else if (strat->tailRing->pLDeg==pLDegb) PrintS("pLDegb");
11932  else if (strat->tailRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11933  else if (strat->tailRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11934  else if (strat->tailRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11935  else if (strat->tailRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11936  else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11937  else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11938  else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11939  else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11940  else if (strat->tailRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11941  else Print("? (%lx)", (long)strat->tailRing->pLDeg);
11942  PrintLn();
11943  PrintS("currRing->pFDeg: ");
11944  if (currRing->pFDeg==p_Totaldegree) PrintS("p_Totaldegree");
11945  else if (currRing->pFDeg==p_WFirstTotalDegree) PrintS("pWFirstTotalDegree");
11946  else if (currRing->pFDeg==p_Deg) PrintS("p_Deg");
11947  else if (currRing->pFDeg==kHomModDeg) PrintS("kHomModDeg");
11948  else if (currRing->pFDeg==totaldegreeWecart) PrintS("totaldegreeWecart");
11949  else if (currRing->pFDeg==p_WTotaldegree) PrintS("p_WTotaldegree");
11950  else Print("? (%lx)", (long)currRing->pFDeg);
11951  PrintLn();
11952  Print(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11953  if(TEST_OPT_DEGBOUND)
11954  Print(" degBound: %d\n", Kstd1_deg);
11955 
11956  if( ecartWeights != NULL )
11957  {
11958  PrintS("ecartWeights: ");
11959  for (int i = rVar(currRing); i > 0; i--)
11960  Print("%hd ", ecartWeights[i]);
11961  PrintLn();
11963  }
11964 
11965 #ifndef SING_NDEBUG
11967 #endif
11968 }
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
#define Print
Definition: emacs.cc:80
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:1352
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2420
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1905
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:938
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1698
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6604
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6719
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6358
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5460
int posInTrg0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5131
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:6102
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5053
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4996
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5250
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1668
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5326
int posInT0(const TSet, const int length, LObject &)
Definition: kutil.cc:4985
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5025
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6447
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6400
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11799
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5297
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1406
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5797
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3538
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5090
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6482
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5568
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11708
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5364
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5753
VAR int Kstd1_deg
Definition: kutil.cc:247
void initEcartNormal(TObject *h)
Definition: kutil.cc:1384
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6172
char * showOption()
Definition: misc_ip.cc:709
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6559
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5207
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6518
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5696
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5419
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5522
int posInLrg0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6274
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1615
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5630
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6654
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11762
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3297
void initEcartBBA(TObject *h)
Definition: kutil.cc:1392
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6059
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1399
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9101
#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:1509
void rDebugPrint(const ring r)
Definition: ring.cc:4164
static int rGetCurrSyzLimit(const ring r)
Definition: ring.h:724
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition: ring.h:721
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:593
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 404 of file kstd2.cc.

405 {
406  unsigned long not_sev = ~L->sev;
407  poly p = L->GetLmCurrRing();
408  int j = 0;
409 
410  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
411 
413 #if 1
414  int ende;
415  if (is_Ring
416  || (strat->ak>0)
417  || currRing->pLexOrder)
418  ende=strat->sl;
419  else
420  {
421  ende=posInS(strat,*max_ind,p,0)+1;
422  if (ende>(*max_ind)) ende=(*max_ind);
423  }
424 #else
425  int ende=strat->sl;
426 #endif
427  if(is_Ring)
428  {
429  loop
430  {
431  if (j > ende) return -1;
432 #if defined(PDEBUG) || defined(PDIV_DEBUG)
433  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
434  p, not_sev, currRing))
435  {
436  if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
437  return j;
438  }
439 #else
440  if ( !(strat->sevS[j] & not_sev) &&
441  p_LmDivisibleBy(strat->S[j], p, currRing))
442  {
443  if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
444  return j;
445  }
446 #endif
447  j++;
448  }
449  }
450  else
451  {
452  loop
453  {
454  if (j > ende) return -1;
455 #if defined(PDEBUG) || defined(PDIV_DEBUG)
456  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
457  p, not_sev, currRing))
458  {
459  return j;
460  }
461 #else
462  if ( !(strat->sevS[j] & not_sev) &&
463  p_LmDivisibleBy(strat->S[j], p, currRing))
464  {
465  return j;
466  }
467 #endif
468  j++;
469  }
470  }
471 }
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:753
#define pAssume(cond)
Definition: monomials.h:90
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4897
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1931
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1897

◆ 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 290 of file kstd2.cc.

291 {
292  unsigned long not_sev = ~L->sev;
293  int j = start;
294 
295  const TSet T=strat->T;
296  const unsigned long* sevT=strat->sevT;
297  const ring r=currRing;
298  const BOOLEAN is_Ring=rField_is_Ring(r);
299  if (L->p!=NULL)
300  {
301  const poly p=L->p;
302 
303  pAssume(~not_sev == p_GetShortExpVector(p, r));
304 
305  if(is_Ring)
306  {
307  loop
308  {
309  if (j > strat->tl) return -1;
310 #if defined(PDEBUG) || defined(PDIV_DEBUG)
311  if ((T[j].p!=NULL)
312  && p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
313  {
314  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
315  return j;
316  }
317 #else
318  if (!(sevT[j] & not_sev)
319  && (T[j].p!=NULL)
320  && p_LmDivisibleBy(T[j].p, p, r))
321  {
322  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
323  return j;
324  }
325 #endif
326  j++;
327  }
328  }
329  else
330  {
331  loop
332  {
333  if (j > strat->tl) return -1;
334 #if defined(PDEBUG) || defined(PDIV_DEBUG)
335  if ((T[j].p!=NULL)
336  && p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
337  {
338  return j;
339  }
340 #else
341  if (!(sevT[j] & not_sev)
342  && (T[j].p!=NULL)
343  && p_LmDivisibleBy(T[j].p, p, r))
344  {
345  return j;
346  }
347 #endif
348  j++;
349  }
350  }
351  }
352  else
353  {
354  const poly p=L->t_p;
355  const ring r=strat->tailRing;
356  if(is_Ring)
357  {
358  loop
359  {
360  if (j > strat->tl) return -1;
361 #if defined(PDEBUG) || defined(PDIV_DEBUG)
362  if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
363  p, not_sev, r))
364  {
365  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
366  return j;
367  }
368 #else
369  if (!(sevT[j] & not_sev) &&
370  p_LmDivisibleBy(T[j].t_p, p, r))
371  {
372  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
373  return j;
374  }
375 #endif
376  j++;
377  }
378  }
379  else
380  {
381  loop
382  {
383  if (j > strat->tl) return -1;
384 #if defined(PDEBUG) || defined(PDIV_DEBUG)
385  if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
386  p, not_sev, r))
387  {
388  return j;
389  }
390 #else
391  if (!(sevT[j] & not_sev) &&
392  p_LmDivisibleBy(T[j].t_p, p, r))
393  {
394  return j;
395  }
396 #endif
397  j++;
398  }
399  }
400  }
401 }
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 209 of file kstd2.cc.

210 {
211  unsigned long not_sev = ~L->sev;
212  int j = start;
213  int o = -1;
214 
215  const TSet T=strat->T;
216  const unsigned long* sevT=strat->sevT;
217  number rest, orest, mult;
218  if (L->p!=NULL)
219  {
220  const ring r=currRing;
221  const poly p=L->p;
222  orest = pGetCoeff(p);
223 
224  pAssume(~not_sev == p_GetShortExpVector(p, r));
225 
226  loop
227  {
228  if (j > strat->tl) return o;
229 #if defined(PDEBUG) || defined(PDIV_DEBUG)
230  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
231  {
232  mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
233  if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
234  {
235  o = j;
236  orest = rest;
237  }
238  }
239 #else
240  if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
241  {
242  mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
243  if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
244  {
245  o = j;
246  orest = rest;
247  }
248  }
249 #endif
250  j++;
251  }
252  }
253  else
254  {
255  const ring r=strat->tailRing;
256  const poly p=L->t_p;
257  orest = pGetCoeff(p);
258  loop
259  {
260  if (j > strat->tl) return o;
261 #if defined(PDEBUG) || defined(PDIV_DEBUG)
262  if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
263  p, not_sev, r))
264  {
265  mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
266  if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
267  {
268  o = j;
269  orest = rest;
270  }
271  }
272 #else
273  if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
274  {
275  mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
276  if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
277  {
278  o = j;
279  orest = rest;
280  }
281  }
282 #endif
283  j++;
284  }
285  }
286 }
static FORCE_INLINE number n_EucNorm(number a, const coeffs r)
Definition: coeffs.h:675
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition: coeffs.h:681
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:511
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647

◆ kFindNextDivisibleByInS()

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

Definition at line 473 of file kstd2.cc.

474 {
475  unsigned long not_sev = ~L->sev;
476  poly p = L->GetLmCurrRing();
477  int j = start;
478 
479  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
480 #if 1
481  int ende=max_ind;
482 #else
483  int ende=strat->sl;
484 #endif
486  {
487  loop
488  {
489  if (j > ende) return -1;
490 #if defined(PDEBUG) || defined(PDIV_DEBUG)
491  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
492  p, not_sev, currRing))
493  {
494  if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
495  return j;
496  }
497 #else
498  if ( !(strat->sevS[j] & not_sev) &&
499  p_LmDivisibleBy(strat->S[j], p, currRing))
500  {
501  if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
502  return j;
503  }
504 #endif
505  j++;
506  }
507  }
508  else
509  {
510  loop
511  {
512  if (j > ende) return -1;
513 #if defined(PDEBUG) || defined(PDIV_DEBUG)
514  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
515  p, not_sev, currRing))
516  {
517  return j;
518  }
519 #else
520  if ( !(strat->sevS[j] & not_sev) &&
521  p_LmDivisibleBy(strat->S[j], p, currRing))
522  {
523  return j;
524  }
525 #endif
526  j++;
527  }
528  }
529 }

◆ kFindSameLMInT_Z()

int kFindSameLMInT_Z ( const kStrategy  strat,
const LObject L,
const int  start 
)

Definition at line 86 of file kstd2.cc.

87 {
88  unsigned long not_sev = ~L->sev;
89  int j = start;
90  int o = -1;
91 
92  const TSet T=strat->T;
93  const unsigned long* sevT=strat->sevT;
94  number gcd, ogcd;
95  if (L->p!=NULL)
96  {
97  const ring r=currRing;
98  const poly p=L->p;
99  ogcd = pGetCoeff(p);
100 
101  pAssume(~not_sev == p_GetShortExpVector(p, r));
102 
103  loop
104  {
105  if (j > strat->tl) return o;
106  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
107  {
108  gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
109  if (o == -1
110  || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
111  {
112  ogcd = gcd;
113  o = j;
114  }
115  }
116  j++;
117  }
118  }
119  else
120  {
121  const ring r=strat->tailRing;
122  const poly p=L->t_p;
123  ogcd = pGetCoeff(p);
124  loop
125  {
126  if (j > strat->tl) return o;
127  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
128  {
129  gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
130  if (o == -1
131  || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
132  {
133  ogcd = gcd;
134  o = j;
135  }
136  }
137  j++;
138  }
139  }
140 }
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
Definition: coeffs.h:664
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1725
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ kFindZeroPoly()

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

Definition at line 559 of file kstd2.cc.

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

3872 {
3873  assume(!idIs0(q));
3874  assume(!(idIs0(F)&&(Q==NULL)));
3875 // lazy_reduce flags: can be combined by |
3876 //#define KSTD_NF_LAZY 1
3877  // do only a reduction of the leading term
3878 //#define KSTD_NF_NONORM 4
3879  // only global: avoid normalization, return a multiply of NF
3880  poly p;
3881  int i;
3882  ideal res;
3883  int max_ind;
3884 
3885  //if (idIs0(q))
3886  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3887  //if ((idIs0(F))&&(Q==NULL))
3888  // return idCopy(q); /*F=0*/
3889  //strat->ak = idRankFreeModule(F);
3890  /*- creating temp data structures------------------- -*/
3891  BITSET save1;
3892  SI_SAVE_OPT1(save1);
3894  initBuchMoraCrit(strat);
3895  strat->initEcart = initEcartBBA;
3896 #ifdef HAVE_SHIFTBBA
3897  if (rIsLPRing(currRing))
3898  {
3899  strat->enterS = enterSBbaShift;
3900  }
3901  else
3902 #endif
3903  {
3904  strat->enterS = enterSBba;
3905  }
3906  /*- set S -*/
3907  strat->sl = -1;
3908 #ifndef NO_BUCKETS
3910 #endif
3911  /*- init local data struct.---------------------------------------- -*/
3912  /*Shdl=*/initS(F,Q,strat);
3913  /*- compute------------------------------------------------------- -*/
3914  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3915  for (i=IDELEMS(q)-1; i>=0; i--)
3916  {
3917  if (q->m[i]!=NULL)
3918  {
3919  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3920  p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3921  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3922  {
3923  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3925  {
3926  p = redtailBba_Z(p,max_ind,strat);
3927  }
3928  else if (rField_is_Ring(currRing))
3929  {
3930  p = redtailBba_Ring(p,max_ind,strat);
3931  }
3932  else
3933  {
3935  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3936  }
3937  }
3938  res->m[i]=p;
3939  }
3940  //else
3941  // res->m[i]=NULL;
3942  }
3943  /*- release temp data------------------------------- -*/
3944  assume(strat->L==NULL); /* strat->L unused */
3945  assume(strat->B==NULL); /* strat->B unused */
3946  omFree(strat->sevS);
3947  omFree(strat->ecartS);
3948  assume(strat->T==NULL);//omfree(strat->T);
3949  assume(strat->sevT==NULL);//omfree(strat->sevT);
3950  assume(strat->R==NULL);//omfree(strat->R);
3951  omfree(strat->S_2_R);
3952  omfree(strat->fromQ);
3953  idDelete(&strat->Shdl);
3954  SI_RESTORE_OPT1(save1);
3955  if (TEST_OPT_PROT) PrintLn();
3956  return res;
3957 }
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
KINLINE poly redtailBba_Ring(poly p, int pos, kStrategy strat)
Definition: kInline.h:1236
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
Definition: kInline.h:1241
#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:2142
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7907
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9201
#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 rField_is_Zn(const ring r)
Definition: ring.h:513
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 3715 of file kstd2.cc.

3716 {
3717  assume(q!=NULL);
3718  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3719 
3720 // lazy_reduce flags: can be combined by |
3721 //#define KSTD_NF_LAZY 1
3722  // do only a reduction of the leading term
3723 //#define KSTD_NF_NONORM 4
3724  // only global: avoid normalization, return a multiply of NF
3725  poly p;
3726 
3727  //if ((idIs0(F))&&(Q==NULL))
3728  // return pCopy(q); /*F=0*/
3729  //strat->ak = idRankFreeModule(F);
3730  /*- creating temp data structures------------------- -*/
3731  BITSET save1;
3732  SI_SAVE_OPT1(save1);
3734  initBuchMoraCrit(strat);
3735  strat->initEcart = initEcartBBA;
3736 #ifdef HAVE_SHIFTBBA
3737  if (rIsLPRing(currRing))
3738  {
3739  strat->enterS = enterSBbaShift;
3740  }
3741  else
3742 #endif
3743  {
3744  strat->enterS = enterSBba;
3745  }
3746 #ifndef NO_BUCKETS
3748 #endif
3749  /*- set S -*/
3750  strat->sl = -1;
3751  /*- init local data struct.---------------------------------------- -*/
3752  /*Shdl=*/initS(F,Q,strat);
3753  /*- compute------------------------------------------------------- -*/
3754  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3755  //{
3756  // for (i=strat->sl;i>=0;i--)
3757  // pNorm(strat->S[i]);
3758  //}
3759  kTest(strat);
3760  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3761  if (BVERBOSE(23)) kDebugPrint(strat);
3762  int max_ind;
3763  p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3764  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3765  {
3766  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3768  {
3769  p = redtailBba_Z(p,max_ind,strat);
3770  }
3771  else if (rField_is_Ring(currRing))
3772  {
3773  p = redtailBba_Ring(p,max_ind,strat);
3774  }
3775  else
3776  {
3778  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3779  }
3780  }
3781  /*- release temp data------------------------------- -*/
3782  assume(strat->L==NULL); /* strat->L unused */
3783  assume(strat->B==NULL); /* strat->B unused */
3784  omFree(strat->sevS);
3785  omFree(strat->ecartS);
3786  assume(strat->T==NULL);//omfree(strat->T);
3787  assume(strat->sevT==NULL);//omfree(strat->sevT);
3788  assume(strat->R==NULL);//omfree(strat->R);
3789  omfree(strat->S_2_R);
3790  omfree(strat->fromQ);
3791  idDelete(&strat->Shdl);
3792  SI_RESTORE_OPT1(save1);
3793  if (TEST_OPT_PROT) PrintLn();
3794  return p;
3795 }
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1036

◆ kNF2Bound() [1/2]

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

Definition at line 3959 of file kstd2.cc.

3960 {
3961  assume(!idIs0(q));
3962  assume(!(idIs0(F)&&(Q==NULL)));
3963 // lazy_reduce flags: can be combined by |
3964 //#define KSTD_NF_LAZY 1
3965  // do only a reduction of the leading term
3966 //#define KSTD_NF_NONORM 4
3967  // only global: avoid normalization, return a multiply of NF
3968  poly p;
3969  int i;
3970  ideal res;
3971  int max_ind;
3972 
3973  //if (idIs0(q))
3974  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3975  //if ((idIs0(F))&&(Q==NULL))
3976  // return idCopy(q); /*F=0*/
3977  //strat->ak = idRankFreeModule(F);
3978  /*- creating temp data structures------------------- -*/
3979  BITSET save1;
3980  SI_SAVE_OPT1(save1);
3982  initBuchMoraCrit(strat);
3983  strat->initEcart = initEcartBBA;
3984  strat->enterS = enterSBba;
3985  /*- set S -*/
3986  strat->sl = -1;
3987 #ifndef NO_BUCKETS
3989 #endif
3990  /*- init local data struct.---------------------------------------- -*/
3991  /*Shdl=*/initS(F,Q,strat);
3992  /*- compute------------------------------------------------------- -*/
3993  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3994  for (i=IDELEMS(q)-1; i>=0; i--)
3995  {
3996  if (q->m[i]!=NULL)
3997  {
3998  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3999  p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
4000  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4001  {
4002  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4004  {
4005  p = redtailBba_Z(p,max_ind,strat);
4006  }
4007  else if (rField_is_Ring(currRing))
4008  {
4009  p = redtailBba_Ring(p,max_ind,strat);
4010  }
4011  else
4012  {
4014  p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4015  }
4016  }
4017  res->m[i]=p;
4018  }
4019  //else
4020  // res->m[i]=NULL;
4021  }
4022  /*- release temp data------------------------------- -*/
4023  assume(strat->L==NULL); /* strat->L unused */
4024  assume(strat->B==NULL); /* strat->B unused */
4025  omFree(strat->sevS);
4026  omFree(strat->ecartS);
4027  assume(strat->T==NULL);//omfree(strat->T);
4028  assume(strat->sevT==NULL);//omfree(strat->sevT);
4029  assume(strat->R==NULL);//omfree(strat->R);
4030  omfree(strat->S_2_R);
4031  omfree(strat->fromQ);
4032  idDelete(&strat->Shdl);
4033  SI_RESTORE_OPT1(save1);
4034  if (TEST_OPT_PROT) PrintLn();
4035  return res;
4036 }
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:1229
poly redNFBound(poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
Definition: kstd2.cc:2271

◆ kNF2Bound() [2/2]

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

Definition at line 3797 of file kstd2.cc.

3798 {
3799  assume(q!=NULL);
3800  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3801 
3802 // lazy_reduce flags: can be combined by |
3803 //#define KSTD_NF_LAZY 1
3804  // do only a reduction of the leading term
3805 //#define KSTD_NF_NONORM 4
3806  // only global: avoid normalization, return a multiply of NF
3807  poly p;
3808 
3809  //if ((idIs0(F))&&(Q==NULL))
3810  // return pCopy(q); /*F=0*/
3811  //strat->ak = idRankFreeModule(F);
3812  /*- creating temp data structures------------------- -*/
3813  BITSET save1;
3814  SI_SAVE_OPT1(save1);
3816  initBuchMoraCrit(strat);
3817  strat->initEcart = initEcartBBA;
3818  strat->enterS = enterSBba;
3819 #ifndef NO_BUCKETS
3821 #endif
3822  /*- set S -*/
3823  strat->sl = -1;
3824  /*- init local data struct.---------------------------------------- -*/
3825  /*Shdl=*/initS(F,Q,strat);
3826  /*- compute------------------------------------------------------- -*/
3827  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3828  //{
3829  // for (i=strat->sl;i>=0;i--)
3830  // pNorm(strat->S[i]);
3831  //}
3832  kTest(strat);
3833  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3834  if (BVERBOSE(23)) kDebugPrint(strat);
3835  int max_ind;
3836  p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3837  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3838  {
3839  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3841  {
3842  p = redtailBba_Z(p,max_ind,strat);
3843  }
3844  else if (rField_is_Ring(currRing))
3845  {
3846  p = redtailBba_Ring(p,max_ind,strat);
3847  }
3848  else
3849  {
3851  p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3852  //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3853  }
3854  }
3855  /*- release temp data------------------------------- -*/
3856  assume(strat->L==NULL); /* strat->L unused */
3857  assume(strat->B==NULL); /* strat->B unused */
3858  omFree(strat->sevS);
3859  omFree(strat->ecartS);
3860  assume(strat->T==NULL);//omfree(strat->T);
3861  assume(strat->sevT==NULL);//omfree(strat->sevT);
3862  assume(strat->R==NULL);//omfree(strat->R);
3863  omfree(strat->S_2_R);
3864  omfree(strat->fromQ);
3865  idDelete(&strat->Shdl);
3866  SI_RESTORE_OPT1(save1);
3867  if (TEST_OPT_PROT) PrintLn();
3868  return p;
3869 }

◆ ksReducePolyTailSig()

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

Definition at line 1122 of file kstd2.cc.

1123 {
1124  BOOLEAN ret;
1125  number coef;
1126  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1127  if(!rField_is_Ring(currRing))
1128  Red->HeadNormalize();
1129  /*
1130  printf("------------------------\n");
1131  pWrite(Red->GetLmCurrRing());
1132  */
1134  ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1135  else
1136  ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1137  if (!ret)
1138  {
1139  if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1140  {
1141  PR->Mult_nn(coef);
1142  // HANNES: mark for Normalize
1143  }
1144  n_Delete(&coef, currRing->cf);
1145  }
1146  return ret;
1147 }
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:719
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:925

◆ 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 142 of file kstd2.cc.

143 {
144  if (strat->tl < 1)
145  return -1;
146 
147  unsigned long not_sev = ~L->sev;
148  const unsigned long sevT0 = strat->sevT[0];
149  number rest, orest, mult;
150  if (L->p!=NULL)
151  {
152  const poly T0p = strat->T[0].p;
153  const ring r = currRing;
154  const poly p = L->p;
155  orest = pGetCoeff(p);
156 
157  pAssume(~not_sev == p_GetShortExpVector(p, r));
158 
159 #if defined(PDEBUG) || defined(PDIV_DEBUG)
160  if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
161  {
162  mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
163  if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
164  {
165  return 0;
166  }
167  }
168 #else
169  if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
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  return 0;
175  }
176  }
177 #endif
178  }
179  else
180  {
181  const poly T0p = strat->T[0].t_p;
182  const ring r = strat->tailRing;
183  const poly p = L->t_p;
184  orest = pGetCoeff(p);
185 #if defined(PDEBUG) || defined(PDIV_DEBUG)
186  if (p_LmShortDivisibleBy(T0p, sevT0,
187  p, not_sev, r))
188  {
189  mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
190  if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
191  {
192  return 0;
193  }
194  }
195 #else
196  if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
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  return 0;
202  }
203  }
204 #endif
205  }
206  return -1;
207 }

◆ redFirstShift()

int redFirstShift ( LObject h,
kStrategy  strat 
)

Definition at line 4738 of file kstd2.cc.

4739 {
4740  if (h->IsNull()) return 0;
4741 
4742  int at, reddeg,d;
4743  int pass = 0;
4744  int j = 0;
4745 
4746  if (! strat->homog)
4747  {
4748  d = h->GetpFDeg() + h->ecart;
4749  reddeg = strat->LazyDegree+d;
4750  }
4751  h->SetShortExpVector();
4752  loop
4753  {
4754  j = kFindDivisibleByInT(strat, h);
4755  if (j < 0)
4756  {
4757  h->SetDegStuffReturnLDeg(strat->LDegLast);
4758  return 1;
4759  }
4760 
4761  if (!TEST_OPT_INTSTRATEGY)
4762  strat->T[j].pNorm();
4763 #ifdef KDEBUG
4764  if (TEST_OPT_DEBUG)
4765  {
4766  PrintS("reduce ");
4767  h->wrp();
4768  PrintS(" with ");
4769  strat->T[j].wrp();
4770  }
4771 #endif
4772  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
4773 
4774 #ifdef KDEBUG
4775  if (TEST_OPT_DEBUG)
4776  {
4777  PrintS("\nto ");
4778  wrp(h->p);
4779  PrintLn();
4780  }
4781 #endif
4782  if (h->IsNull())
4783  {
4784  kDeleteLcm(h);
4785  h->Clear();
4786  return 0;
4787  }
4788  h->SetShortExpVector();
4789 
4790 #if 0
4791  if ((strat->syzComp!=0) && !strat->honey)
4792  {
4793  if ((strat->syzComp>0) &&
4794  (h->Comp() > strat->syzComp))
4795  {
4796  assume(h->MinComp() > strat->syzComp);
4797 #ifdef KDEBUG
4798  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4799 #endif
4800  if (strat->homog)
4801  h->SetDegStuffReturnLDeg(strat->LDegLast);
4802  return -2;
4803  }
4804  }
4805 #endif
4806  if (!strat->homog)
4807  {
4808  if (!TEST_OPT_OLDSTD && strat->honey)
4809  {
4810  h->SetpFDeg();
4811  if (strat->T[j].ecart <= h->ecart)
4812  h->ecart = d - h->GetpFDeg();
4813  else
4814  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4815 
4816  d = h->GetpFDeg() + h->ecart;
4817  }
4818  else
4819  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4820  /*- try to reduce the s-polynomial -*/
4821  pass++;
4822  /*
4823  *test whether the polynomial should go to the lazyset L
4824  *-if the degree jumps
4825  *-if the number of pre-defined reductions jumps
4826  */
4827  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4828  && ((d >= reddeg) || (pass > strat->LazyPass)))
4829  {
4830  h->SetLmCurrRing();
4831  if (strat->posInLDependsOnLength)
4832  h->SetLength(strat->length_pLength);
4833  at = strat->posInL(strat->L,strat->Ll,h,strat);
4834  if (at <= strat->Ll)
4835  {
4836  //int dummy=strat->sl;
4837  /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4838  //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4839  if (kFindDivisibleByInT(strat, h) < 0)
4840  return 1;
4841  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4842 #ifdef KDEBUG
4843  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4844 #endif
4845  h->Clear();
4846  return -1;
4847  }
4848  }
4849  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4850  {
4851  reddeg = d+1;
4852  Print(".%d",d);mflush();
4853  }
4854  }
4855  }
4856 }
KINLINE poly kNoetherTail()
Definition: kInline.h:66
char LDegLast
Definition: kutil.h:385
char length_pLength
Definition: kutil.h:387
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat)
Definition: kspoly.cc:187
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:290
#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 938 of file kstd2.cc.

939 {
940  if (strat->tl<0) return 1;
941  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
942  assume(h->FDeg == h->pFDeg());
943 
944  poly h_p;
945  int i,j,at,pass,cnt,ii;
946  // long reddeg,d;
947  int li;
948  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
949 
950  pass = j = 0;
951  cnt = RED_CANONICALIZE;
952  // d = reddeg = h->GetpFDeg();
953  h->SetShortExpVector();
954  h_p = h->GetLmTailRing();
955  h->PrepareRed(strat->use_buckets);
956  loop
957  {
958  j = kFindDivisibleByInT(strat, h);
959  if (j < 0) return 1;
960 
961  li = strat->T[j].pLength;
962  ii = j;
963  /*
964  * the polynomial to reduce with (up to the moment) is;
965  * pi with length li
966  */
967  i = j;
968 #if 1
969  if (test_opt_length)
970  {
971  if (li<=0) li=strat->T[j].GetpLength();
972  if (li>2)
973  {
974  unsigned long not_sev = ~ h->sev;
975  loop
976  {
977  /*- search the shortest possible with respect to length -*/
978  i++;
979  if (i > strat->tl)
980  break;
981  if ((strat->T[i].pLength < li)
982  &&
983  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
984  h_p, not_sev, strat->tailRing))
985  {
986  /*
987  * the polynomial to reduce with is now;
988  */
989  li = strat->T[i].pLength;
990  if (li<=0) li=strat->T[i].GetpLength();
991  ii = i;
992  if (li<3) break;
993  }
994  }
995  }
996  }
997 #endif
998 
999  /*
1000  * end of search: have to reduce with pi
1001  */
1002 #ifdef KDEBUG
1003  if (TEST_OPT_DEBUG)
1004  {
1005  PrintS("red:");
1006  h->wrp();
1007  PrintS(" with ");
1008  strat->T[ii].wrp();
1009  }
1010 #endif
1011  assume(strat->fromT == FALSE);
1012 
1013  ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1014 #if SBA_PRINT_REDUCTION_STEPS
1015  sba_interreduction_steps++;
1016 #endif
1017 #if SBA_PRINT_OPERATIONS
1018  sba_interreduction_operations += pLength(strat->T[ii].p);
1019 #endif
1020 
1021 #ifdef KDEBUG
1022  if (TEST_OPT_DEBUG)
1023  {
1024  PrintS("\nto ");
1025  h->wrp();
1026  PrintLn();
1027  }
1028 #endif
1029 
1030  h_p = h->GetLmTailRing();
1031  if (h_p == NULL)
1032  {
1033  kDeleteLcm(h);
1034  return 0;
1035  }
1036  #if 0 // red is redLiftstd if OPT_IDLIFT
1038  {
1039  if (h->p!=NULL)
1040  {
1041  if(p_GetComp(h->p,currRing)>strat->syzComp)
1042  {
1043  h->Delete();
1044  return 0;
1045  }
1046  }
1047  else if (h->t_p!=NULL)
1048  {
1049  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1050  {
1051  h->Delete();
1052  return 0;
1053  }
1054  }
1055  }
1056  #endif
1057  #if 0
1058  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1059  {
1060  if (h->p!=NULL)
1061  {
1062  if(p_GetComp(h->p,currRing)>strat->syzComp)
1063  {
1064  return 1;
1065  }
1066  }
1067  else if (h->t_p!=NULL)
1068  {
1069  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1070  {
1071  return 1;
1072  }
1073  }
1074  }
1075  #endif
1076  h->SetShortExpVector();
1077  /*
1078  * try to reduce the s-polynomial h
1079  *test first whether h should go to the lazyset L
1080  *-if the degree jumps
1081  *-if the number of pre-defined reductions jumps
1082  */
1083  cnt--;
1084  pass++;
1085  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1086  {
1087  h->SetLmCurrRing();
1088  at = strat->posInL(strat->L,strat->Ll,h,strat);
1089  if (at <= strat->Ll)
1090  {
1091 #ifdef HAVE_SHIFTBBA
1092  if (rIsLPRing(currRing))
1093  {
1094  if (kFindDivisibleByInT(strat, h) < 0)
1095  return 1;
1096  }
1097  else
1098 #endif
1099  {
1100  int dummy=strat->sl;
1101  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1102  return 1;
1103  }
1104  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1105 #ifdef KDEBUG
1106  if (TEST_OPT_DEBUG)
1107  Print(" lazy: -> L%d\n",at);
1108 #endif
1109  h->Clear();
1110  return -1;
1111  }
1112  }
1113  else if (UNLIKELY(cnt==0))
1114  {
1115  h->CanonicalizeP();
1116  cnt=RED_CANONICALIZE;
1117  //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1118  }
1119  }
1120 }
#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:404
#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 1905 of file kstd2.cc.

1906 {
1907  if (strat->tl<0) return 1;
1908  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1909  assume(h->FDeg == h->pFDeg());
1910  poly h_p;
1911  int i,j,at,pass,ei, ii, h_d;
1912  long reddeg,d;
1913  int li;
1914  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1915 
1916  pass = j = 0;
1917  d = reddeg = h->GetpFDeg() + h->ecart;
1918  h->SetShortExpVector();
1919  h_p = h->GetLmTailRing();
1920 
1921  h->PrepareRed(strat->use_buckets);
1922  loop
1923  {
1924  j=kFindDivisibleByInT(strat, h);
1925  if (j < 0) return 1;
1926 
1927  ei = strat->T[j].ecart;
1928  li = strat->T[j].pLength;
1929  ii = j;
1930  /*
1931  * the polynomial to reduce with (up to the moment) is;
1932  * pi with ecart ei (T[ii])
1933  */
1934  i = j;
1935  if (test_opt_length)
1936  {
1937  if (li<=0) li=strat->T[j].GetpLength();
1938  if (li>2)
1939  {
1940  unsigned long not_sev = ~ h->sev;
1941  loop
1942  {
1943  /*- takes the first possible with respect to ecart -*/
1944  i++;
1945  if (i > strat->tl) break;
1946  if (ei <= h->ecart) break;
1947  if(p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1948  h_p, not_sev, strat->tailRing))
1949  {
1950  strat->T[i].GetpLength();
1951  if (((strat->T[i].ecart < ei) && (ei> h->ecart))
1952  || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1953  {
1954  /*
1955  * the polynomial to reduce with is now;
1956  */
1957  ei = strat->T[i].ecart;
1958  li = strat->T[i].pLength;
1959  ii = i;
1960  if (li==1) break;
1961  if (ei<=h->ecart) break;
1962  }
1963  }
1964  }
1965  }
1966  }
1967 
1968  /*
1969  * end of search: have to reduce with pi
1970  */
1971  if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
1972  {
1973  h->GetTP(); // clears bucket
1974  h->SetLmCurrRing();
1975  /*
1976  * It is not possible to reduce h with smaller ecart;
1977  * if possible h goes to the lazy-set L,i.e
1978  * if its position in L would be not the last one
1979  */
1980  if (strat->Ll >= 0) /* L is not empty */
1981  {
1982  at = strat->posInL(strat->L,strat->Ll,h,strat);
1983  if(at <= strat->Ll)
1984  /*- h will not become the next element to reduce -*/
1985  {
1986  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1987 #ifdef KDEBUG
1988  if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1989 #endif
1990  h->Clear();
1991  return -1;
1992  }
1993  }
1994  }
1995 #ifdef KDEBUG
1996  if (TEST_OPT_DEBUG)
1997  {
1998  PrintS("red:");
1999  h->wrp();
2000  Print("\nwith T[%d]:",ii);
2001  strat->T[ii].wrp();
2002  }
2003 #endif
2004  assume(strat->fromT == FALSE);
2005 
2006  ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
2007 #if SBA_PRINT_REDUCTION_STEPS
2008  sba_interreduction_steps++;
2009 #endif
2010 #if SBA_PRINT_OPERATIONS
2011  sba_interreduction_operations += strat->T[ii].pLength;
2012 #endif
2013 #ifdef KDEBUG
2014  if (TEST_OPT_DEBUG)
2015  {
2016  PrintS("\nto:");
2017  h->wrp();
2018  PrintLn();
2019  }
2020 #endif
2021  if(h->IsNull())
2022  {
2023  kDeleteLcm(h);
2024  h->Clear();
2025  return 0;
2026  }
2027  #if 0 // red is redLiftstd if OPT_IDLIFT
2029  {
2030  if (h->p!=NULL)
2031  {
2032  if(p_GetComp(h->p,currRing)>strat->syzComp)
2033  {
2034  h->Delete();
2035  return 0;
2036  }
2037  }
2038  else if (h->t_p!=NULL)
2039  {
2040  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2041  {
2042  h->Delete();
2043  return 0;
2044  }
2045  }
2046  }
2047  else
2048  #endif
2049  if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
2050  {
2051  if (h->p!=NULL)
2052  {
2053  if(p_GetComp(h->p,currRing)>strat->syzComp)
2054  {
2055  return 1;
2056  }
2057  }
2058  else if (h->t_p!=NULL)
2059  {
2060  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2061  {
2062  return 1;
2063  }
2064  }
2065  }
2066  h->SetShortExpVector();
2067  h_d = h->SetpFDeg();
2068  /* compute the ecart */
2069  if (ei <= h->ecart)
2070  h->ecart = d-h_d;
2071  else
2072  h->ecart = d-h_d+ei-h->ecart;
2073 
2074  /*
2075  * try to reduce the s-polynomial h
2076  *test first whether h should go to the lazyset L
2077  *-if the degree jumps
2078  *-if the number of pre-defined reductions jumps
2079  */
2080  pass++;
2081  d = h_d + h->ecart;
2083  && (strat->Ll >= 0)
2084  && ((d > reddeg) || (pass > strat->LazyPass))))
2085  {
2086  h->GetTP(); // clear bucket
2087  h->SetLmCurrRing();
2088  at = strat->posInL(strat->L,strat->Ll,h,strat);
2089  if (at <= strat->Ll)
2090  {
2091 #ifdef HAVE_SHIFTBBA
2092  if (rIsLPRing(currRing))
2093  {
2094  if (kFindDivisibleByInT(strat, h) < 0)
2095  return 1;
2096  }
2097  else
2098 #endif
2099  {
2100  int dummy=strat->sl;
2101  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2102  return 1;
2103  }
2104  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2105 #ifdef KDEBUG
2106  if (TEST_OPT_DEBUG)
2107  Print(" degree jumped: -> L%d\n",at);
2108 #endif
2109  h->Clear();
2110  return -1;
2111  }
2112  }
2113  else if (d > reddeg)
2114  {
2115  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2116  {
2117  if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2118  {
2119  strat->overflow=TRUE;
2120  //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2121  h->GetP();
2122  at = strat->posInL(strat->L,strat->Ll,h,strat);
2123  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2124  h->Clear();
2125  return -1;
2126  }
2127  }
2128  else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
2129  {
2130  //h->wrp(); Print("<%d>\n",h->GetpLength());
2131  reddeg = d;
2132  Print(".%ld",d); mflush();
2133  }
2134  }
2135  }
2136 }

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1698 of file kstd2.cc.

1699 {
1700  if (strat->tl<0) return 1;
1701  int at,i,ii,li;
1702  int j = 0;
1703  int pass = 0;
1704  int cnt = RED_CANONICALIZE;
1705  assume(h->pFDeg() == h->FDeg);
1706  long reddeg = h->GetpFDeg();
1707  long d;
1708  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1709 
1710  h->SetShortExpVector();
1711  poly h_p = h->GetLmTailRing();
1712  h->PrepareRed(strat->use_buckets);
1713  loop
1714  {
1715  j = kFindDivisibleByInT(strat, h);
1716  if (j < 0) return 1;
1717 
1718  li = strat->T[j].pLength;
1719  ii = j;
1720  /*
1721  * the polynomial to reduce with (up to the moment) is;
1722  * pi with length li
1723  */
1724 
1725  i = j;
1726 #if 1
1727  if (test_opt_length)
1728  {
1729  if (li<=0) li=strat->T[j].GetpLength();
1730  if(li>2)
1731  {
1732  unsigned long not_sev = ~ h->sev;
1733  loop
1734  {
1735  /*- search the shortest possible with respect to length -*/
1736  i++;
1737  if (i > strat->tl)
1738  break;
1739  if ((strat->T[i].pLength < li)
1740  &&
1741  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1742  h_p, not_sev, strat->tailRing))
1743  {
1744  /*
1745  * the polynomial to reduce with is now;
1746  */
1747  li = strat->T[i].pLength;
1748  if (li<=0) li=strat->T[i].GetpLength();
1749  ii = i;
1750  if (li<3) break;
1751  }
1752  }
1753  }
1754  }
1755 #endif
1756 
1757  /*
1758  * end of search: have to reduce with pi
1759  */
1760 
1761 
1762 #ifdef KDEBUG
1763  if (TEST_OPT_DEBUG)
1764  {
1765  PrintS("red:");
1766  h->wrp();
1767  PrintS(" with ");
1768  strat->T[ii].wrp();
1769  }
1770 #endif
1771 
1772  ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1773 #if SBA_PRINT_REDUCTION_STEPS
1774  sba_interreduction_steps++;
1775 #endif
1776 #if SBA_PRINT_OPERATIONS
1777  sba_interreduction_operations += pLength(strat->T[ii].p);
1778 #endif
1779 
1780 #ifdef KDEBUG
1781  if (TEST_OPT_DEBUG)
1782  {
1783  PrintS("\nto ");
1784  h->wrp();
1785  PrintLn();
1786  }
1787 #endif
1788 
1789  h_p=h->GetLmTailRing();
1790 
1791  if (h_p == NULL)
1792  {
1793  kDeleteLcm(h);
1794  return 0;
1795  }
1796  #if 0 // red id redLiftstd if OPT_IDLIFT
1798  {
1799  if (h->p!=NULL)
1800  {
1801  if(p_GetComp(h->p,currRing)>strat->syzComp)
1802  {
1803  h->Delete();
1804  return 0;
1805  }
1806  }
1807  else if (h->t_p!=NULL)
1808  {
1809  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1810  {
1811  h->Delete();
1812  return 0;
1813  }
1814  }
1815  }
1816  #endif
1817  #if 0
1818  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1819  {
1820  if (h->p!=NULL)
1821  {
1822  if(p_GetComp(h->p,currRing)>strat->syzComp)
1823  {
1824  return 1;
1825  }
1826  }
1827  else if (h->t_p!=NULL)
1828  {
1829  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1830  {
1831  return 1;
1832  }
1833  }
1834  }
1835  #endif
1836  h->SetShortExpVector();
1837  d = h->SetpFDeg();
1838  /*- try to reduce the s-polynomial -*/
1839  cnt--;
1840  pass++;
1841  if (//!TEST_OPT_REDTHROUGH &&
1842  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1843  {
1844  h->SetLmCurrRing();
1845  at = strat->posInL(strat->L,strat->Ll,h,strat);
1846  if (at <= strat->Ll)
1847  {
1848 #if 1
1849 #ifdef HAVE_SHIFTBBA
1850  if (rIsLPRing(currRing))
1851  {
1852  if (kFindDivisibleByInT(strat, h) < 0)
1853  return 1;
1854  }
1855  else
1856 #endif
1857  {
1858  int dummy=strat->sl;
1859  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1860  return 1;
1861  }
1862 #endif
1863 #ifdef KDEBUG
1864  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1865 #endif
1866  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1867  h->Clear();
1868  return -1;
1869  }
1870  }
1871  else if (d != reddeg)
1872  {
1873  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1874  {
1875  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1876  {
1877  strat->overflow=TRUE;
1878  //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1879  h->GetP();
1880  at = strat->posInL(strat->L,strat->Ll,h,strat);
1881  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1882  h->Clear();
1883  return -1;
1884  }
1885  }
1886  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1887  {
1888  Print(".%ld",d);mflush();
1889  reddeg = d;
1890  }
1891  }
1892  else if (UNLIKELY(cnt==0))
1893  {
1894  h->CanonicalizeP();
1895  cnt=RED_CANONICALIZE;
1896  //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1897  }
1898  }
1899 }

◆ redNF()

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

Definition at line 2142 of file kstd2.cc.

2143 {
2144  if (h==NULL) return NULL;
2145  int j;
2146  int cnt=REDNF_CANONICALIZE;
2147  max_ind=strat->sl;
2148 
2149  if (0 > strat->sl)
2150  {
2151  return h;
2152  }
2153  LObject P(h);
2154  P.SetShortExpVector();
2155  P.bucket = kBucketCreate(currRing);
2156  kBucketInit(P.bucket,P.p,pLength(P.p));
2157  kbTest(P.bucket);
2158 #ifdef HAVE_RINGS
2159  BOOLEAN is_ring = rField_is_Ring(currRing);
2160 #endif
2161 #ifdef KDEBUG
2162 // if (TEST_OPT_DEBUG)
2163 // {
2164 // PrintS("redNF: starting S:\n");
2165 // for( j = 0; j <= max_ind; j++ )
2166 // {
2167 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2168 // pWrite(strat->S[j]);
2169 // }
2170 // };
2171 #endif
2172 
2173  loop
2174  {
2175  j=kFindDivisibleByInS(strat,&max_ind,&P);
2176  if (j>=0)
2177  {
2178 #ifdef HAVE_RINGS
2179  if (!is_ring)
2180  {
2181 #endif
2182  int sl=pSize(strat->S[j]);
2183  int jj=j;
2184  loop
2185  {
2186  int sll;
2187  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2188  if (jj<0) break;
2189  sll=pSize(strat->S[jj]);
2190  if (sll<sl)
2191  {
2192  #ifdef KDEBUG
2193  if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2194  #endif
2195  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2196  j=jj;
2197  sl=sll;
2198  }
2199  }
2200  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2201  {
2202  pNorm(strat->S[j]);
2203  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2204  }
2205 #ifdef HAVE_RINGS
2206  }
2207 #endif
2208  nNormalize(pGetCoeff(P.p));
2209 #ifdef KDEBUG
2210  if (TEST_OPT_DEBUG)
2211  {
2212  PrintS("red:");
2213  wrp(h);
2214  PrintS(" with ");
2215  wrp(strat->S[j]);
2216  }
2217 #endif
2218 #ifdef HAVE_PLURAL
2219  if (rIsPluralRing(currRing))
2220  {
2221  number coef;
2222  nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2223  nDelete(&coef);
2224  }
2225  else
2226 #endif
2227  {
2228  number coef;
2229  coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2230  nDelete(&coef);
2231  }
2232  cnt--;
2233  if (cnt==0)
2234  {
2235  kBucketCanonicalize(P.bucket);
2236  cnt=REDNF_CANONICALIZE;
2237  }
2238  h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2239  if (h==NULL)
2240  {
2241  kBucketDestroy(&P.bucket);
2242  return NULL;
2243  }
2244  kbTest(P.bucket);
2245  P.p=h;
2246  P.t_p=NULL;
2247  P.SetShortExpVector();
2248 #ifdef KDEBUG
2249  if (TEST_OPT_DEBUG)
2250  {
2251  PrintS("\nto:");
2252  wrp(h);
2253  PrintLn();
2254  }
2255 #endif
2256  }
2257  else
2258  {
2259  P.p=kBucketClear(P.bucket);
2260  kBucketDestroy(&P.bucket);
2261  pNormalize(P.p);
2262  return P.p;
2263  }
2264  }
2265 }
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 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
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1085
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:473
#define REDNF_CANONICALIZE
Definition: kutil.h:37
static void nc_kBucketPolyRed_NF(kBucket_pt b, poly p, number *c)
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
void pNorm(poly p)
Definition: polys.h:363
#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 2271 of file kstd2.cc.

2272 {
2273  h = pJet(h,bound);
2274  if (h==NULL) return NULL;
2275  int j;
2276  max_ind=strat->sl;
2277 
2278  if (0 > strat->sl)
2279  {
2280  return h;
2281  }
2282  LObject P(h);
2283  P.SetShortExpVector();
2284  P.bucket = kBucketCreate(currRing);
2285  kBucketInit(P.bucket,P.p,pLength(P.p));
2286  kbTest(P.bucket);
2287 #ifdef HAVE_RINGS
2288  BOOLEAN is_ring = rField_is_Ring(currRing);
2289 #endif
2290 
2291  loop
2292  {
2293  j=kFindDivisibleByInS(strat,&max_ind,&P);
2294  if (j>=0)
2295  {
2296 #ifdef HAVE_RINGS
2297  if (!is_ring)
2298  {
2299 #endif
2300  int sl=pSize(strat->S[j]);
2301  int jj=j;
2302  loop
2303  {
2304  int sll;
2305  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2306  if (jj<0) break;
2307  sll=pSize(strat->S[jj]);
2308  if (sll<sl)
2309  {
2310  #ifdef KDEBUG
2311  if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2312  #endif
2313  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2314  j=jj;
2315  sl=sll;
2316  }
2317  }
2318  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2319  {
2320  pNorm(strat->S[j]);
2321  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2322  }
2323 #ifdef HAVE_RINGS
2324  }
2325 #endif
2326  nNormalize(pGetCoeff(P.p));
2327 #ifdef KDEBUG
2328  if (TEST_OPT_DEBUG)
2329  {
2330  PrintS("red:");
2331  wrp(h);
2332  PrintS(" with ");
2333  wrp(strat->S[j]);
2334  }
2335 #endif
2336 #ifdef HAVE_PLURAL
2337  if (rIsPluralRing(currRing))
2338  {
2339  number coef;
2340  nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2341  nDelete(&coef);
2342  }
2343  else
2344 #endif
2345  {
2346  number coef;
2347  coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2348  P.p = kBucketClear(P.bucket);
2349  P.p = pJet(P.p,bound);
2350  if(!P.IsNull())
2351  {
2352  kBucketDestroy(&P.bucket);
2353  P.SetShortExpVector();
2354  P.bucket = kBucketCreate(currRing);
2355  kBucketInit(P.bucket,P.p,pLength(P.p));
2356  }
2357  nDelete(&coef);
2358  }
2359  h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2360  if (h==NULL)
2361  {
2362  kBucketDestroy(&P.bucket);
2363  return NULL;
2364  }
2365  kbTest(P.bucket);
2366  P.p=h;
2367  P.t_p=NULL;
2368  P.SetShortExpVector();
2369 #ifdef KDEBUG
2370  if (TEST_OPT_DEBUG)
2371  {
2372  PrintS("\nto:");
2373  wrp(h);
2374  PrintLn();
2375  }
2376 #endif
2377  }
2378  else
2379  {
2380  P.p=kBucketClear(P.bucket);
2381  kBucketDestroy(&P.bucket);
2382  pNormalize(P.p);
2383  return P.p;
2384  }
2385  }
2386 }
#define pJet(p, m)
Definition: polys.h:368

◆ redRing()

int redRing ( LObject h,
kStrategy  strat 
)

Definition at line 831 of file kstd2.cc.

832 {
833  if (strat->tl<0) return 1;
834  if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
835 
836  int at/*,i*/;
837  long d;
838  int j = 0;
839  int pass = 0;
840  // poly zeroPoly = NULL;
841 
842 // TODO warum SetpFDeg notwendig?
843  h->SetpFDeg();
844  assume(h->pFDeg() == h->FDeg);
845  long reddeg = h->GetpFDeg();
846 
847  h->SetShortExpVector();
848  loop
849  {
850  j = kFindDivisibleByInT(strat, h);
851  if (j < 0)
852  {
853  // over ZZ: cleanup coefficients by complete reduction with monomials
854  postReduceByMon(h, strat);
855  if(h->p == NULL)
856  {
857  kDeleteLcm(h);
858  h->Clear();
859  return 0;
860  }
861  if(nIsZero(pGetCoeff(h->p))) return 2;
862  j = kFindDivisibleByInT(strat, h);
863  if(j < 0)
864  {
865  if(strat->tl >= 0)
866  h->i_r1 = strat->tl;
867  else
868  h->i_r1 = -1;
869  if (h->GetLmTailRing() == NULL)
870  {
871  kDeleteLcm(h);
872  h->Clear();
873  return 0;
874  }
875  return 1;
876  }
877  }
878  //printf("\nFound one: ");pWrite(strat->T[j].p);
879  //enterT(*h, strat);
880  ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
881  //printf("\nAfter small red: ");pWrite(h->p);
882  if (h->GetLmTailRing() == NULL)
883  {
884  kDeleteLcm(h);
885  h->Clear();
886  return 0;
887  }
888  h->SetShortExpVector();
889  d = h->SetpFDeg();
890  /*- try to reduce the s-polynomial -*/
891  pass++;
892  if (!TEST_OPT_REDTHROUGH &&
893  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
894  {
895  h->SetLmCurrRing();
896  if (strat->posInLDependsOnLength)
897  h->SetLength(strat->length_pLength);
898  at = strat->posInL(strat->L,strat->Ll,h,strat);
899  if (at <= strat->Ll)
900  {
901 #ifdef KDEBUG
902  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
903 #endif
904  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
905  h->Clear();
906  return -1;
907  }
908  }
909  if (d != reddeg)
910  {
911  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
912  {
913  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
914  {
915  strat->overflow=TRUE;
916  //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
917  h->GetP();
918  at = strat->posInL(strat->L,strat->Ll,h,strat);
919  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
920  h->Clear();
921  return -1;
922  }
923  }
924  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
925  {
926  Print(".%ld",d);mflush();
927  reddeg = d;
928  }
929  }
930  }
931 }
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:11036

◆ redRing_Z()

int redRing_Z ( LObject h,
kStrategy  strat 
)

Definition at line 673 of file kstd2.cc.

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

◆ redSig()

int redSig ( LObject h,
kStrategy  strat 
)

Definition at line 1160 of file kstd2.cc.

1161 {
1162  if (strat->tl<0) return 1;
1163  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1164  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1165  assume(h->FDeg == h->pFDeg());
1166 //#if 1
1167 #ifdef DEBUGF5
1168  PrintS("------- IN REDSIG -------\n");
1169  Print("p: ");
1170  pWrite(pHead(h->p));
1171  PrintS("p1: ");
1172  pWrite(pHead(h->p1));
1173  PrintS("p2: ");
1174  pWrite(pHead(h->p2));
1175  PrintS("---------------------------\n");
1176 #endif
1177  poly h_p;
1178  int i,j,at,pass, ii;
1179  int start=0;
1180  int sigSafe;
1181  unsigned long not_sev;
1182  // long reddeg,d;
1183  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1184  int li;
1185 
1186  pass = j = 0;
1187  // d = reddeg = h->GetpFDeg();
1188  h->SetShortExpVector();
1189  h_p = h->GetLmTailRing();
1190  not_sev = ~ h->sev;
1191  loop
1192  {
1193  j = kFindDivisibleByInT(strat, h, start);
1194  if (j < 0)
1195  {
1196  return 1;
1197  }
1198 
1199  li = strat->T[j].pLength;
1200  if (li<=0) li=strat->T[j].GetpLength();
1201  ii = j;
1202  /*
1203  * the polynomial to reduce with (up to the moment) is;
1204  * pi with length li
1205  */
1206  i = j;
1207 #if 1
1208  if (test_opt_length)
1209  loop
1210  {
1211  /*- search the shortest possible with respect to length -*/
1212  i++;
1213  if (i > strat->tl)
1214  break;
1215  if (li==1)
1216  break;
1217  if ((strat->T[i].pLength < li)
1218  &&
1219  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1220  h_p, not_sev, strat->tailRing))
1221  {
1222  /*
1223  * the polynomial to reduce with is now;
1224  */
1225  li = strat->T[i].pLength;
1226  if (li<=0) li=strat->T[i].GetpLength();
1227  ii = i;
1228  }
1229  }
1230  start = ii+1;
1231 #endif
1232 
1233  /*
1234  * end of search: have to reduce with pi
1235  */
1236 #ifdef KDEBUG
1237  if (TEST_OPT_DEBUG)
1238  {
1239  PrintS("red:");
1240  h->wrp();
1241  PrintS(" with ");
1242  strat->T[ii].wrp();
1243  }
1244 #endif
1245  assume(strat->fromT == FALSE);
1246 //#if 1
1247 #ifdef DEBUGF5
1248  Print("BEFORE REDUCTION WITH %d:\n",ii);
1249  PrintS("--------------------------------\n");
1250  pWrite(h->sig);
1251  pWrite(strat->T[ii].sig);
1252  pWrite(h->GetLmCurrRing());
1253  pWrite(pHead(h->p1));
1254  pWrite(pHead(h->p2));
1255  pWrite(pHead(strat->T[ii].p));
1256  PrintS("--------------------------------\n");
1257  printf("INDEX OF REDUCER T: %d\n",ii);
1258 #endif
1259  sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1260 #if SBA_PRINT_REDUCTION_STEPS
1261  if (sigSafe != 3)
1262  sba_reduction_steps++;
1263 #endif
1264 #if SBA_PRINT_OPERATIONS
1265  if (sigSafe != 3)
1266  sba_operations += pLength(strat->T[ii].p);
1267 #endif
1268  // if reduction has taken place, i.e. the reduction was sig-safe
1269  // otherwise start is already at the next position and the loop
1270  // searching reducers in T goes on from index start
1271 //#if 1
1272 #ifdef DEBUGF5
1273  Print("SigSAFE: %d\n",sigSafe);
1274 #endif
1275  if (sigSafe != 3)
1276  {
1277  // start the next search for reducers in T from the beginning
1278  start = 0;
1279 #ifdef KDEBUG
1280  if (TEST_OPT_DEBUG)
1281  {
1282  PrintS("\nto ");
1283  h->wrp();
1284  PrintLn();
1285  }
1286 #endif
1287 
1288  h_p = h->GetLmTailRing();
1289  if (h_p == NULL)
1290  {
1291  kDeleteLcm(h);
1292  return 0;
1293  }
1294  h->SetShortExpVector();
1295  not_sev = ~ h->sev;
1296  /*
1297  * try to reduce the s-polynomial h
1298  *test first whether h should go to the lazyset L
1299  *-if the degree jumps
1300  *-if the number of pre-defined reductions jumps
1301  */
1302  pass++;
1303  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1304  {
1305  h->SetLmCurrRing();
1306  at = strat->posInL(strat->L,strat->Ll,h,strat);
1307  if (at <= strat->Ll)
1308  {
1309  int dummy=strat->sl;
1310  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1311  {
1312  return 1;
1313  }
1314  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1315 #ifdef KDEBUG
1316  if (TEST_OPT_DEBUG)
1317  Print(" lazy: -> L%d\n",at);
1318 #endif
1319  h->Clear();
1320  return -1;
1321  }
1322  }
1323  }
1324  }
1325 }

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1328 of file kstd2.cc.

1329 {
1330  //Since reduce is really bad for SBA we use the following idea:
1331  // We first check if we can build a gcd pair between h and S
1332  //where the sig remains the same and replace h by this gcd poly
1334  #if GCD_SBA
1335  while(sbaCheckGcdPair(h,strat))
1336  {
1337  h->sev = pGetShortExpVector(h->p);
1338  }
1339  #endif
1340  poly beforeredsig;
1341  beforeredsig = pCopy(h->sig);
1342 
1343  if (strat->tl<0) return 1;
1344  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1345  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1346  assume(h->FDeg == h->pFDeg());
1347 //#if 1
1348 #ifdef DEBUGF5
1349  Print("------- IN REDSIG -------\n");
1350  Print("p: ");
1351  pWrite(pHead(h->p));
1352  Print("p1: ");
1353  pWrite(pHead(h->p1));
1354  Print("p2: ");
1355  pWrite(pHead(h->p2));
1356  Print("---------------------------\n");
1357 #endif
1358  poly h_p;
1359  int i,j,at,pass, ii;
1360  int start=0;
1361  int sigSafe;
1362  unsigned long not_sev;
1363  // long reddeg,d;
1364  int li;
1365  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1366 
1367  pass = j = 0;
1368  // d = reddeg = h->GetpFDeg();
1369  h->SetShortExpVector();
1370  h_p = h->GetLmTailRing();
1371  not_sev = ~ h->sev;
1372  loop
1373  {
1374  j = kFindDivisibleByInT(strat, h, start);
1375  if (j < 0)
1376  {
1377  #if GCD_SBA
1378  while(sbaCheckGcdPair(h,strat))
1379  {
1380  h->sev = pGetShortExpVector(h->p);
1381  h->is_redundant = FALSE;
1382  start = 0;
1383  }
1384  #endif
1385  // over ZZ: cleanup coefficients by complete reduction with monomials
1386  postReduceByMonSig(h, strat);
1387  if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
1388  j = kFindDivisibleByInT(strat, h,start);
1389  if(j < 0)
1390  {
1391  if(strat->tl >= 0)
1392  h->i_r1 = strat->tl;
1393  else
1394  h->i_r1 = -1;
1395  if (h->GetLmTailRing() == NULL)
1396  {
1397  kDeleteLcm(h);
1398  h->Clear();
1399  return 0;
1400  }
1401  //Check for sigdrop after reduction
1402  if(pLtCmp(beforeredsig,h->sig) == 1)
1403  {
1404  strat->sigdrop = TRUE;
1405  //Reduce it as much as you can
1406  int red_result = redRing(h,strat);
1407  if(red_result == 0)
1408  {
1409  //It reduced to 0, cancel the sigdrop
1410  strat->sigdrop = FALSE;
1411  p_Delete(&h->sig,currRing);h->sig = NULL;
1412  return 0;
1413  }
1414  else
1415  {
1416  //strat->enterS(*h, strat->sl+1, strat, strat->tl);
1417  return 0;
1418  }
1419  }
1420  p_Delete(&beforeredsig,currRing);
1421  return 1;
1422  }
1423  }
1424 
1425  li = strat->T[j].pLength;
1426  if (li<=0) li=strat->T[j].GetpLength();
1427  ii = j;
1428  /*
1429  * the polynomial to reduce with (up to the moment) is;
1430  * pi with length li
1431  */
1432  i = j;
1433  if (test_opt_length)
1434  loop
1435  {
1436  /*- search the shortest possible with respect to length -*/
1437  i++;
1438  if (i > strat->tl)
1439  break;
1440  if (li==1)
1441  break;
1442  if ((strat->T[i].pLength < li)
1443  && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1444  && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1445  h_p, not_sev, strat->tailRing))
1446  {
1447  /*
1448  * the polynomial to reduce with is now;
1449  */
1450  li = strat->T[i].pLength;
1451  if (li<=0) li=strat->T[i].GetpLength();
1452  ii = i;
1453  }
1454  }
1455 
1456  start = ii+1;
1457 
1458  /*
1459  * end of search: have to reduce with pi
1460  */
1461 #ifdef KDEBUG
1462  if (TEST_OPT_DEBUG)
1463  {
1464  PrintS("red:");
1465  h->wrp();
1466  PrintS(" with ");
1467  strat->T[ii].wrp();
1468  }
1469 #endif
1470  assume(strat->fromT == FALSE);
1471 //#if 1
1472 #ifdef DEBUGF5
1473  Print("BEFORE REDUCTION WITH %d:\n",ii);
1474  Print("--------------------------------\n");
1475  pWrite(h->sig);
1476  pWrite(strat->T[ii].sig);
1477  pWrite(h->GetLmCurrRing());
1478  pWrite(pHead(h->p1));
1479  pWrite(pHead(h->p2));
1480  pWrite(pHead(strat->T[ii].p));
1481  Print("--------------------------------\n");
1482  printf("INDEX OF REDUCER T: %d\n",ii);
1483 #endif
1484  sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1485  if(h->p == NULL && h->sig == NULL)
1486  {
1487  //Trivial case catch
1488  strat->sigdrop = FALSE;
1489  }
1490  #if 0
1491  //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1492  //In some cases this proves to be very bad
1493  if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1494  {
1495  int red_result = redRing(h,strat);
1496  if(red_result == 0)
1497  {
1498  pDelete(&h->sig);h->sig = NULL;
1499  return 0;
1500  }
1501  else
1502  {
1503  strat->sigdrop = TRUE;
1504  return 1;
1505  }
1506  }
1507  #endif
1508  if(strat->sigdrop)
1509  return 1;
1510 #if SBA_PRINT_REDUCTION_STEPS
1511  if (sigSafe != 3)
1512  sba_reduction_steps++;
1513 #endif
1514 #if SBA_PRINT_OPERATIONS
1515  if (sigSafe != 3)
1516  sba_operations += pLength(strat->T[ii].p);
1517 #endif
1518  // if reduction has taken place, i.e. the reduction was sig-safe
1519  // otherwise start is already at the next position and the loop
1520  // searching reducers in T goes on from index start
1521 //#if 1
1522 #ifdef DEBUGF5
1523  Print("SigSAFE: %d\n",sigSafe);
1524 #endif
1525  if (sigSafe != 3)
1526  {
1527  // start the next search for reducers in T from the beginning
1528  start = 0;
1529 #ifdef KDEBUG
1530  if (TEST_OPT_DEBUG)
1531  {
1532  PrintS("\nto ");
1533  h->wrp();
1534  PrintLn();
1535  }
1536 #endif
1537 
1538  h_p = h->GetLmTailRing();
1539  if (h_p == NULL)
1540  {
1541  kDeleteLcm(h);
1542  return 0;
1543  }
1544  h->SetShortExpVector();
1545  not_sev = ~ h->sev;
1546  /*
1547  * try to reduce the s-polynomial h
1548  *test first whether h should go to the lazyset L
1549  *-if the degree jumps
1550  *-if the number of pre-defined reductions jumps
1551  */
1552  pass++;
1553  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1554  {
1555  h->SetLmCurrRing();
1556  at = strat->posInL(strat->L,strat->Ll,h,strat);
1557  if (at <= strat->Ll)
1558  {
1559  int dummy=strat->sl;
1560  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1561  {
1562  return 1;
1563  }
1564  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1565 #ifdef KDEBUG
1566  if (TEST_OPT_DEBUG)
1567  Print(" lazy: -> L%d\n",at);
1568 #endif
1569  h->Clear();
1570  return -1;
1571  }
1572  }
1573  }
1574  }
1575 }
bool sigdrop
Definition: kutil.h:359
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:831
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:11112
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition: kutil.cc:1780
#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 1578 of file kstd2.cc.

1579 {
1580  strat->redTailChange=FALSE;
1581  if (strat->noTailReduction) return L->GetLmCurrRing();
1582  poly h, p;
1583  p = h = L->GetLmTailRing();
1584  if ((h==NULL) || (pNext(h)==NULL))
1585  return L->GetLmCurrRing();
1586 
1587  TObject* With;
1588  // placeholder in case strat->tl < 0
1589  TObject With_s(strat->tailRing);
1590 
1591  LObject Ln(pNext(h), strat->tailRing);
1592  Ln.sig = L->sig;
1593  Ln.sevSig = L->sevSig;
1594  Ln.pLength = L->GetpLength() - 1;
1595 
1596  pNext(h) = NULL;
1597  if (L->p != NULL) pNext(L->p) = NULL;
1598  L->pLength = 1;
1599 
1600  Ln.PrepareRed(strat->use_buckets);
1601 
1602  int cnt=REDTAIL_CANONICALIZE;
1603  while(!Ln.IsNull())
1604  {
1605  loop
1606  {
1607  if(rField_is_Ring(currRing) && strat->sigdrop)
1608  break;
1609  Ln.SetShortExpVector();
1610  if (withT)
1611  {
1612  int j;
1613  j = kFindDivisibleByInT(strat, &Ln);
1614  if (j < 0) break;
1615  With = &(strat->T[j]);
1616  }
1617  else
1618  {
1619  With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1620  if (With == NULL) break;
1621  }
1622  cnt--;
1623  if (cnt==0)
1624  {
1626  /*poly tmp=*/Ln.CanonicalizeP();
1628  {
1629  Ln.Normalize();
1630  //pNormalize(tmp);
1631  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1632  }
1633  }
1634  if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
1635  {
1636  With->pNorm();
1637  }
1638  strat->redTailChange=TRUE;
1639  int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1641  L->sig = Ln.sig;
1642  //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1643  // I delete it an then set Ln.sig. Hence L->sig is lost
1644 #if SBA_PRINT_REDUCTION_STEPS
1645  if (ret != 3)
1646  sba_reduction_steps++;
1647 #endif
1648 #if SBA_PRINT_OPERATIONS
1649  if (ret != 3)
1650  sba_operations += pLength(With->p);
1651 #endif
1652  if (ret)
1653  {
1654  // reducing the tail would violate the exp bound
1655  // set a flag and hope for a retry (in bba)
1656  strat->completeReduce_retry=TRUE;
1657  if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1658  do
1659  {
1660  pNext(h) = Ln.LmExtractAndIter();
1661  pIter(h);
1662  L->pLength++;
1663  } while (!Ln.IsNull());
1664  goto all_done;
1665  }
1666  if (Ln.IsNull()) goto all_done;
1667  if (! withT) With_s.Init(currRing);
1668  if(rField_is_Ring(currRing) && strat->sigdrop)
1669  {
1670  //Cannot break the loop here so easily
1671  break;
1672  }
1673  }
1674  pNext(h) = Ln.LmExtractAndIter();
1675  pIter(h);
1676  if(!rField_is_Ring(currRing))
1677  pNormalize(h);
1678  L->pLength++;
1679  }
1680  all_done:
1681  Ln.Delete();
1682  if (L->p != NULL) pNext(L->p) = pNext(p);
1683 
1684  if (strat->redTailChange)
1685  {
1686  L->length = 0;
1687  }
1688  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1689  //L->Normalize(); // HANNES: should have a test
1690  kTest_L(L,strat);
1691  return L->GetLmCurrRing();
1692 }
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition: kstd2.cc:1122
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition: kutil.cc:950
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition: kutil.cc:7005
#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:1026

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4722 of file kstd2.cc.

4723 {
4725  assume(idIsInV(F));
4726  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4727  idSkipZeroes(RS); // is this even necessary?
4728  assume(idIsInV(RS));
4729  return(RS);
4730 }
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2911
#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 2749 of file kstd2.cc.

2750 {
2751  // ring order stuff:
2752  // in sba we have (until now) two possibilities:
2753  // 1. an incremental computation w.r.t. (C,monomial order)
2754  // 2. a (possibly non-incremental) computation w.r.t. the
2755  // induced Schreyer order.
2756  // The corresponding orders are computed in sbaRing(), depending
2757  // on the flag strat->sbaOrder
2758 #if SBA_PRINT_ZERO_REDUCTIONS
2759  long zeroreductions = 0;
2760 #endif
2761 #if SBA_PRINT_PRODUCT_CRITERION
2762  long product_criterion = 0;
2763 #endif
2764 #if SBA_PRINT_SIZE_G
2765  int size_g = 0;
2766  int size_g_non_red = 0;
2767 #endif
2768 #if SBA_PRINT_SIZE_SYZ
2769  long size_syz = 0;
2770 #endif
2771  // global variable
2772 #if SBA_PRINT_REDUCTION_STEPS
2773  sba_reduction_steps = 0;
2774  sba_interreduction_steps = 0;
2775 #endif
2776 #if SBA_PRINT_OPERATIONS
2777  sba_operations = 0;
2778  sba_interreduction_operations = 0;
2779 #endif
2780 
2781  ideal F1 = F0;
2782  ring sRing, currRingOld;
2783  currRingOld = currRing;
2784  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
2785  {
2786  sRing = sbaRing(strat);
2787  if (sRing!=currRingOld)
2788  {
2789  rChangeCurrRing (sRing);
2790  F1 = idrMoveR (F0, currRingOld, currRing);
2791  }
2792  }
2793  ideal F;
2794  // sort ideal F
2795  //Put the SigDrop element on the correct position (think of sbaEnterS)
2796  //We also sort them
2797  if(rField_is_Ring(currRing) && strat->sigdrop)
2798  {
2799  #if 1
2800  F = idInit(IDELEMS(F1),F1->rank);
2801  for (int i=0; i<IDELEMS(F1);++i)
2802  F->m[i] = F1->m[i];
2803  if(strat->sbaEnterS >= 0)
2804  {
2805  poly dummy;
2806  dummy = pCopy(F->m[0]); //the sigdrop element
2807  for(int i = 0;i<strat->sbaEnterS;i++)
2808  F->m[i] = F->m[i+1];
2809  F->m[strat->sbaEnterS] = dummy;
2810  }
2811  #else
2812  F = idInit(1,F1->rank);
2813  //printf("\nBefore the initial block sorting:\n");idPrint(F1);
2814  F->m[0] = F1->m[0];
2815  int pos;
2816  if(strat->sbaEnterS >= 0)
2817  {
2818  for(int i=1;i<=strat->sbaEnterS;i++)
2819  {
2820  pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2821  idInsertPolyOnPos(F,F1->m[i],pos);
2822  }
2823  for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2824  {
2825  pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2826  idInsertPolyOnPos(F,F1->m[i],pos);
2827  }
2828  poly dummy;
2829  dummy = pCopy(F->m[0]); //the sigdrop element
2830  for(int i = 0;i<strat->sbaEnterS;i++)
2831  F->m[i] = F->m[i+1];
2832  F->m[strat->sbaEnterS] = dummy;
2833  }
2834  else
2835  {
2836  for(int i=1;i<IDELEMS(F1);i++)
2837  {
2838  pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2839  idInsertPolyOnPos(F,F1->m[i],pos);
2840  }
2841  }
2842  #endif
2843  //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2844  }
2845  else
2846  {
2847  F = idInit(IDELEMS(F1),F1->rank);
2848  intvec *sort = idSort(F1);
2849  for (int i=0; i<sort->length();++i)
2850  F->m[i] = F1->m[(*sort)[i]-1];
2852  {
2853  // put the monomials after the sbaEnterS polynomials
2854  //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2855  int nrmon = 0;
2856  for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2857  {
2858  //pWrite(F->m[i]);
2859  if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2860  {
2861  poly mon = F->m[i];
2862  for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2863  {
2864  F->m[j] = F->m[j-1];
2865  }
2866  F->m[j] = mon;
2867  nrmon++;
2868  }
2869  //idPrint(F);
2870  }
2871  }
2872  }
2873  //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2875  strat->sigdrop = FALSE;
2876  strat->nrsyzcrit = 0;
2877  strat->nrrewcrit = 0;
2878 #if SBA_INTERRED_START
2879  F = kInterRed(F,NULL);
2880 #endif
2881 #if F5DEBUG
2882  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2883  rWrite (currRing);
2884  printf("ordSgn = %d\n",currRing->OrdSgn);
2885  printf("\n");
2886 #endif
2887  int srmax,lrmax, red_result = 1;
2888  int olddeg,reduc;
2889  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2890  LObject L;
2891  BOOLEAN withT = TRUE;
2892  strat->max_lower_index = 0;
2893  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2894  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
2895  initSbaPos(strat);
2896  initHilbCrit(F,Q,&hilb,strat);
2897  initSba(F,strat);
2898  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2899  /*Shdl=*/initSbaBuchMora(F, Q,strat);
2900  idTest(strat->Shdl);
2901  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2902  srmax = strat->sl;
2903  reduc = olddeg = lrmax = 0;
2904 #ifndef NO_BUCKETS
2905  if (!TEST_OPT_NOT_BUCKETS)
2906  strat->use_buckets = 1;
2907 #endif
2908 
2909  // redtailBBa against T for inhomogenous input
2910  // if (!TEST_OPT_OLDSTD)
2911  // withT = ! strat->homog;
2912 
2913  // strat->posInT = posInT_pLength;
2914  kTest_TS(strat);
2915 
2916 #ifdef HAVE_TAIL_RING
2917  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2918  kStratInitChangeTailRing(strat);
2919 #endif
2920  if (BVERBOSE(23))
2921  {
2922  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2923  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2924  kDebugPrint(strat);
2925  }
2926  // We add the elements directly in S from the previous loop
2927  if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2928  {
2929  for(int i = 0;i<strat->sbaEnterS;i++)
2930  {
2931  //Update: now the element is at the corect place
2932  //i+1 because on the 0 position is the sigdrop element
2933  enterT(strat->L[strat->Ll-(i)],strat);
2934  strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2935  }
2936  strat->Ll = strat->Ll - strat->sbaEnterS;
2937  strat->sbaEnterS = -1;
2938  }
2939  kTest_TS(strat);
2940 #ifdef KDEBUG
2941  //kDebugPrint(strat);
2942 #endif
2943  /* compute------------------------------------------------------- */
2944  while (strat->Ll >= 0)
2945  {
2946  if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2947  #ifdef KDEBUG
2948  if (TEST_OPT_DEBUG) messageSets(strat);
2949  #endif
2950  if (strat->Ll== 0) strat->interpt=TRUE;
2951  /*
2952  if (TEST_OPT_DEGBOUND
2953  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2954  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2955  {
2956 
2957  //stops computation if
2958  // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2959  //a predefined number Kstd1_deg
2960  while ((strat->Ll >= 0)
2961  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2962  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2963  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2964  )
2965  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2966  if (strat->Ll<0) break;
2967  else strat->noClearS=TRUE;
2968  }
2969  */
2970  if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2971  {
2972  strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2973 #if F5C
2974  // 1. interreduction of the current standard basis
2975  // 2. generation of new principal syzygy rules for syzCriterion
2976  f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2977  lrmax, reduc, Q, w, hilb );
2978 #endif
2979  // initialize new syzygy rules for the next iteration step
2980  initSyzRules(strat);
2981  }
2982  /*********************************************************************
2983  * interrreduction step is done, we can go on with the next iteration
2984  * step of the signature-based algorithm
2985  ********************************************************************/
2986  /* picks the last element from the lazyset L */
2987  strat->P = strat->L[strat->Ll];
2988  strat->Ll--;
2989 
2991  strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2992  /* reduction of the element chosen from L */
2993  if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2994  {
2995  //#if 1
2996 #ifdef DEBUGF5
2997  PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2998  PrintS("-------------------------------------------------\n");
2999  pWrite(strat->P.sig);
3000  pWrite(pHead(strat->P.p));
3001  pWrite(pHead(strat->P.p1));
3002  pWrite(pHead(strat->P.p2));
3003  PrintS("-------------------------------------------------\n");
3004 #endif
3005  if (pNext(strat->P.p) == strat->tail)
3006  {
3007  // deletes the short spoly
3008  /*
3009  if (rField_is_Ring(currRing))
3010  pLmDelete(strat->P.p);
3011  else
3012  pLmFree(strat->P.p);
3013 */
3014  // TODO: needs some masking
3015  // TODO: masking needs to vanish once the signature
3016  // sutff is completely implemented
3017  strat->P.p = NULL;
3018  poly m1 = NULL, m2 = NULL;
3019 
3020  // check that spoly creation is ok
3021  while (strat->tailRing != currRing &&
3022  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3023  {
3024  assume(m1 == NULL && m2 == NULL);
3025  // if not, change to a ring where exponents are at least
3026  // large enough
3027  if (!kStratChangeTailRing(strat))
3028  {
3029  WerrorS("OVERFLOW...");
3030  break;
3031  }
3032  }
3033  // create the real one
3034  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3035  strat->tailRing, m1, m2, strat->R);
3036 
3037  }
3038  else if (strat->P.p1 == NULL)
3039  {
3040  if (strat->minim > 0)
3041  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3042  // for input polys, prepare reduction
3043  if(!rField_is_Ring(currRing))
3044  strat->P.PrepareRed(strat->use_buckets);
3045  }
3046  if (strat->P.p == NULL && strat->P.t_p == NULL)
3047  {
3048  red_result = 0;
3049  }
3050  else
3051  {
3052  //#if 1
3053 #ifdef DEBUGF5
3054  PrintS("Poly before red: ");
3055  pWrite(pHead(strat->P.p));
3056  pWrite(strat->P.sig);
3057 #endif
3058 #if SBA_PRODUCT_CRITERION
3059  if (strat->P.prod_crit)
3060  {
3061 #if SBA_PRINT_PRODUCT_CRITERION
3062  product_criterion++;
3063 #endif
3064  int pos = posInSyz(strat, strat->P.sig);
3065  enterSyz(strat->P, strat, pos);
3066  kDeleteLcm(&strat->P);
3067  red_result = 2;
3068  }
3069  else
3070  {
3071  red_result = strat->red(&strat->P,strat);
3072  }
3073 #else
3074  red_result = strat->red(&strat->P,strat);
3075 #endif
3076  }
3077  }
3078  else
3079  {
3080  /*
3081  if (strat->P.lcm != NULL)
3082  pLmFree(strat->P.lcm);
3083  */
3084  red_result = 2;
3085  }
3087  {
3088  if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3089  {
3090  strat->P.p = pNeg(strat->P.p);
3091  strat->P.sig = pNeg(strat->P.sig);
3092  }
3093  strat->P.pLength = pLength(strat->P.p);
3094  if(strat->P.sig != NULL)
3095  strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3096  if(strat->P.p != NULL)
3097  strat->P.sev = pGetShortExpVector(strat->P.p);
3098  }
3099  //sigdrop case
3100  if(rField_is_Ring(currRing) && strat->sigdrop)
3101  {
3102  //First reduce it as much as one can
3103  red_result = redRing(&strat->P,strat);
3104  if(red_result == 0)
3105  {
3106  strat->sigdrop = FALSE;
3107  pDelete(&strat->P.sig);
3108  strat->P.sig = NULL;
3109  }
3110  else
3111  {
3112  strat->enterS(strat->P, 0, strat, strat->tl);
3113  if (TEST_OPT_PROT)
3114  PrintS("-");
3115  break;
3116  }
3117  }
3118  if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3119  {
3120  strat->sigdrop = TRUE;
3121  break;
3122  }
3123 
3124  if (errorreported) break;
3125 
3126 //#if 1
3127 #ifdef DEBUGF5
3128  if (red_result != 0)
3129  {
3130  PrintS("Poly after red: ");
3131  pWrite(pHead(strat->P.p));
3132  pWrite(strat->P.GetLmCurrRing());
3133  pWrite(strat->P.sig);
3134  printf("%d\n",red_result);
3135  }
3136 #endif
3137  if (TEST_OPT_PROT)
3138  {
3139  if(strat->P.p != NULL)
3140  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3141  &olddeg,&reduc,strat, red_result);
3142  else
3143  message((strat->honey ? strat->P.ecart : 0),
3144  &olddeg,&reduc,strat, red_result);
3145  }
3146 
3147  if (strat->overflow)
3148  {
3149  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3150  }
3151  // reduction to non-zero new poly
3152  if (red_result == 1)
3153  {
3154  // get the polynomial (canonicalize bucket, make sure P.p is set)
3155  strat->P.GetP(strat->lmBin);
3156 
3157  // sig-safe computations may lead to wrong FDeg computation, thus we need
3158  // to recompute it to make sure everything is alright
3159  (strat->P).FDeg = (strat->P).pFDeg();
3160  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3161  // but now, for entering S, T, we reset it
3162  // in the inhomogeneous case: FDeg == pFDeg
3163  if (strat->homog) strat->initEcart(&(strat->P));
3164 
3165  /* statistic */
3166  if (TEST_OPT_PROT) PrintS("s");
3167 
3168  //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3169  // in F5E we know that the last reduced element is already the
3170  // the one with highest signature
3171  int pos = strat->sl+1;
3172 
3173  // reduce the tail and normalize poly
3174  // in the ring case we cannot expect LC(f) = 1,
3175  #ifdef HAVE_RINGS
3176  poly beforetailred;
3178  beforetailred = pCopy(strat->P.sig);
3179  #endif
3180 #if SBA_TAIL_RED
3182  {
3184  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3185  }
3186  else
3187  {
3188  if (strat->sbaOrder != 2)
3189  {
3191  {
3192  strat->P.pCleardenom();
3194  {
3195  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3196  strat->P.pCleardenom();
3197  }
3198  }
3199  else
3200  {
3201  strat->P.pNorm();
3203  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3204  }
3205  }
3206  }
3207  // It may happen that we have lost the sig in redtailsba
3208  // It cannot reduce to 0 since here we are doing just tail reduction.
3209  // Best case scenerio: remains the leading term
3210  if(rField_is_Ring(currRing) && strat->sigdrop)
3211  {
3212  strat->enterS(strat->P, 0, strat, strat->tl);
3213  break;
3214  }
3215 #endif
3217  {
3218  if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
3219  {
3220  strat->sigdrop = TRUE;
3221  //Reduce it as much as you can
3222  red_result = redRing(&strat->P,strat);
3223  if(red_result == 0)
3224  {
3225  //It reduced to 0, cancel the sigdrop
3226  strat->sigdrop = FALSE;
3227  p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3228  }
3229  else
3230  {
3231  strat->enterS(strat->P, 0, strat, strat->tl);
3232  break;
3233  }
3234  }
3235  p_Delete(&beforetailred,currRing);
3236  // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3237  if(strat->P.p == NULL)
3238  goto case_when_red_result_changed;
3239  }
3240  // remove sigsafe label since it is no longer valid for the next element to
3241  // be reduced
3242  if (strat->sbaOrder == 1)
3243  {
3244  for (int jj = 0; jj<strat->tl+1; jj++)
3245  {
3246  if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3247  {
3248  strat->T[jj].is_sigsafe = FALSE;
3249  }
3250  }
3251  }
3252  else
3253  {
3254  for (int jj = 0; jj<strat->tl+1; jj++)
3255  {
3256  strat->T[jj].is_sigsafe = FALSE;
3257  }
3258  }
3259 #ifdef KDEBUG
3260  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3261 #endif /* KDEBUG */
3262 
3263  // min_std stuff
3264  if ((strat->P.p1==NULL) && (strat->minim>0))
3265  {
3266  if (strat->minim==1)
3267  {
3268  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3269  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3270  }
3271  else
3272  {
3273  strat->M->m[minimcnt]=strat->P.p2;
3274  strat->P.p2=NULL;
3275  }
3276  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3277  pNext(strat->M->m[minimcnt])
3278  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3279  strat->tailRing, currRing,
3280  currRing->PolyBin);
3281  minimcnt++;
3282  }
3283 
3284  // enter into S, L, and T
3285  //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3286  enterT(strat->P, strat);
3287  strat->T[strat->tl].is_sigsafe = FALSE;
3288  /*
3289  printf("hier\n");
3290  pWrite(strat->P.GetLmCurrRing());
3291  pWrite(strat->P.sig);
3292  */
3293  if (rField_is_Ring(currRing))
3294  superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3295  else
3296  enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3297  if(rField_is_Ring(currRing) && strat->sigdrop)
3298  break;
3300  strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3301  strat->enterS(strat->P, pos, strat, strat->tl);
3302  if(strat->sbaOrder != 1)
3303  {
3304  BOOLEAN overwrite = FALSE;
3305  for (int tk=0; tk<strat->sl+1; tk++)
3306  {
3307  if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3308  {
3309  //printf("TK %d / %d\n",tk,strat->sl);
3310  overwrite = FALSE;
3311  break;
3312  }
3313  }
3314  //printf("OVERWRITE %d\n",overwrite);
3315  if (overwrite)
3316  {
3317  int cmp = pGetComp(strat->P.sig);
3318  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3319  p_GetExpV (strat->P.p,vv,currRing);
3320  p_SetExpV (strat->P.sig, vv,currRing);
3321  p_SetComp (strat->P.sig,cmp,currRing);
3322 
3323  strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3324  int i;
3325  LObject Q;
3326  for(int ps=0;ps<strat->sl+1;ps++)
3327  {
3328 
3329  strat->newt = TRUE;
3330  if (strat->syzl == strat->syzmax)
3331  {
3332  pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3333  strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3334  (strat->syzmax)*sizeof(unsigned long),
3335  ((strat->syzmax)+setmaxTinc)
3336  *sizeof(unsigned long));
3337  strat->syzmax += setmaxTinc;
3338  }
3339  Q.sig = pCopy(strat->P.sig);
3340  // add LM(F->m[i]) to the signature to get a Schreyer order
3341  // without changing the underlying polynomial ring at all
3342  if (strat->sbaOrder == 0)
3343  p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3344  // since p_Add_q() destroys all input
3345  // data we need to recreate help
3346  // each time
3347  // ----------------------------------------------------------
3348  // in the Schreyer order we always know that the multiplied
3349  // module monomial strat->P.sig gives the leading monomial of
3350  // the corresponding principal syzygy
3351  // => we do not need to compute the "real" syzygy completely
3352  poly help = p_Copy(strat->sig[ps],currRing);
3353  p_ExpVectorAdd (help,strat->P.p,currRing);
3354  Q.sig = p_Add_q(Q.sig,help,currRing);
3355  //printf("%d. SYZ ",i+1);
3356  //pWrite(strat->syz[i]);
3357  Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3358  i = posInSyz(strat, Q.sig);
3359  enterSyz(Q, strat, i);
3360  }
3361  }
3362  }
3363  // deg - idx - lp/rp
3364  // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3365  if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3366  {
3367  int cmp = pGetComp(strat->P.sig);
3368  unsigned max_cmp = IDELEMS(F);
3369  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3370  p_GetExpV (strat->P.p,vv,currRing);
3371  LObject Q;
3372  int pos;
3373  int idx = __p_GetComp(strat->P.sig,currRing);
3374  //printf("++ -- adding syzygies -- ++\n");
3375  // if new element is the first one in this index
3376  if (strat->currIdx < idx)
3377  {
3378  for (int i=0; i<strat->sl; ++i)
3379  {
3380  Q.sig = p_Copy(strat->P.sig,currRing);
3381  p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3382  poly help = p_Copy(strat->sig[i],currRing);
3383  p_ExpVectorAdd(help,strat->P.p,currRing);
3384  Q.sig = p_Add_q(Q.sig,help,currRing);
3385  //pWrite(Q.sig);
3386  pos = posInSyz(strat, Q.sig);
3387  enterSyz(Q, strat, pos);
3388  }
3389  strat->currIdx = idx;
3390  }
3391  else
3392  {
3393  // if the element is not the first one in the given index we build all
3394  // possible syzygies with elements of higher index
3395  for (unsigned i=cmp+1; i<=max_cmp; ++i)
3396  {
3397  pos = -1;
3398  for (int j=0; j<strat->sl; ++j)
3399  {
3400  if (__p_GetComp(strat->sig[j],currRing) == i)
3401  {
3402  pos = j;
3403  break;
3404  }
3405  }
3406  if (pos != -1)
3407  {
3408  Q.sig = p_One(currRing);
3409  p_SetExpV(Q.sig, vv, currRing);
3410  // F->m[i-1] corresponds to index i
3411  p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3412  p_SetComp(Q.sig, i, currRing);
3413  poly help = p_Copy(strat->P.sig,currRing);
3414  p_ExpVectorAdd(help,strat->S[pos],currRing);
3415  Q.sig = p_Add_q(Q.sig,help,currRing);
3416  if (strat->sbaOrder == 0)
3417  {
3418  if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3419  {
3420  pos = posInSyz(strat, Q.sig);
3421  enterSyz(Q, strat, pos);
3422  }
3423  }
3424  else
3425  {
3426  pos = posInSyz(strat, Q.sig);
3427  enterSyz(Q, strat, pos);
3428  }
3429  }
3430  }
3431  //printf("++ -- done adding syzygies -- ++\n");
3432  }
3433  }
3434 //#if 1
3435 #if DEBUGF50
3436  printf("---------------------------\n");
3437  Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3438  PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3439  PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3440 #endif
3441  /*
3442  if (newrules)
3443  {
3444  newrules = FALSE;
3445  }
3446  */
3447 #if 0
3448  int pl=pLength(strat->P.p);
3449  if (pl==1)
3450  {
3451  //if (TEST_OPT_PROT)
3452  //PrintS("<1>");
3453  }
3454  else if (pl==2)
3455  {
3456  //if (TEST_OPT_PROT)
3457  //PrintS("<2>");
3458  }
3459 #endif
3460  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3461 // Print("[%d]",hilbeledeg);
3462  kDeleteLcm(&strat->P);
3463  if (strat->sl>srmax) srmax = strat->sl;
3464  }
3465  else
3466  {
3467  case_when_red_result_changed:
3468  // adds signature of the zero reduction to
3469  // strat->syz. This is the leading term of
3470  // syzygy and can be used in syzCriterion()
3471  // the signature is added if and only if the
3472  // pair was not detected by the rewritten criterion in strat->red = redSig
3473  if (red_result!=2)
3474  {
3475 #if SBA_PRINT_ZERO_REDUCTIONS
3476  zeroreductions++;
3477 #endif
3478  if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3479  {
3480  //Catch the case when p = 0, sig = 0
3481  }
3482  else
3483  {
3484  int pos = posInSyz(strat, strat->P.sig);
3485  enterSyz(strat->P, strat, pos);
3486  //#if 1
3487  #ifdef DEBUGF5
3488  Print("ADDING STUFF TO SYZ : ");
3489  //pWrite(strat->P.p);
3490  pWrite(strat->P.sig);
3491  #endif
3492  }
3493  }
3494  if (strat->P.p1 == NULL && strat->minim > 0)
3495  {
3496  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3497  }
3498  }
3499 
3500 #ifdef KDEBUG
3501  memset(&(strat->P), 0, sizeof(strat->P));
3502 #endif /* KDEBUG */
3503  kTest_TS(strat);
3504  }
3505  #if 0
3506  if(strat->sigdrop)
3507  printf("\nSigDrop!\n");
3508  else
3509  printf("\nEnded with no SigDrop\n");
3510  #endif
3511 // Clean strat->P for the next sba call
3512  if(rField_is_Ring(currRing) && strat->sigdrop)
3513  {
3514  //This is used to know how many elements can we directly add to S in the next run
3515  if(strat->P.sig != NULL)
3516  strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3517  //else we already set it at the beggining of the loop
3518  #ifdef KDEBUG
3519  memset(&(strat->P), 0, sizeof(strat->P));
3520  #endif /* KDEBUG */
3521  }
3522 #ifdef KDEBUG
3523  if (TEST_OPT_DEBUG) messageSets(strat);
3524 #endif /* KDEBUG */
3525 
3526  if (TEST_OPT_SB_1)
3527  {
3528  if(!rField_is_Ring(currRing))
3529  {
3530  int k=1;
3531  int j;
3532  while(k<=strat->sl)
3533  {
3534  j=0;
3535  loop
3536  {
3537  if (j>=k) break;
3538  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3539  j++;
3540  }
3541  k++;
3542  }
3543  }
3544  }
3545  /* complete reduction of the standard basis--------- */
3546  if (TEST_OPT_REDSB)
3547  {
3548  completeReduce(strat);
3549  if (strat->completeReduce_retry)
3550  {
3551  // completeReduce needed larger exponents, retry
3552  // to reduce with S (instead of T)
3553  // and in currRing (instead of strat->tailRing)
3554 #ifdef HAVE_TAIL_RING
3555  if(currRing->bitmask>strat->tailRing->bitmask)
3556  {
3557  strat->completeReduce_retry=FALSE;
3558  cleanT(strat);strat->tailRing=currRing;
3559  int i;
3560  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3561  completeReduce(strat);
3562  }
3563  if (strat->completeReduce_retry)
3564 #endif
3565  Werror("exponent bound is %ld",currRing->bitmask);
3566  }
3567  }
3568  else if (TEST_OPT_PROT) PrintLn();
3569 
3570 #if SBA_PRINT_SIZE_SYZ
3571  // that is correct, syzl is counting one too far
3572  size_syz = strat->syzl;
3573 #endif
3574 // if (TEST_OPT_WEIGHTM)
3575 // {
3576 // pRestoreDegProcs(pFDegOld, pLDegOld);
3577 // if (ecartWeights)
3578 // {
3579 // omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3580 // ecartWeights=NULL;
3581 // }
3582 // }
3583  if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3584  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3585 #if SBA_PRINT_SIZE_G
3586  size_g_non_red = IDELEMS(strat->Shdl);
3587 #endif
3588  if(!rField_is_Ring(currRing))
3589  exitSba(strat);
3590  // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3591  #ifdef HAVE_RINGS
3592  int k;
3594  {
3595  //for(k = strat->sl;k>=0;k--)
3596  // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3597  k = strat->Ll;
3598  #if 1
3599  // 1 - adds just the unused ones, 0 - adds everthing
3600  for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3601  {
3602  //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);
3603  deleteInL(strat->L,&strat->Ll,k,strat);
3604  }
3605  #endif
3606  //for(int kk = strat->sl;kk>=0;kk--)
3607  // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3608  //idPrint(strat->Shdl);
3609  //printf("\nk = %i\n",k);
3610  for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3611  {
3612  //printf("\nAdded k = %i\n",k);
3613  strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3614  //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3615  }
3616  }
3617  // 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
3618  #if 0
3619  if(strat->sigdrop && rField_is_Ring(currRing))
3620  {
3621  for(k=strat->sl;k>=0;k--)
3622  {
3623  printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3624  if(strat->sig[k] == NULL)
3625  strat->sig[k] = pCopy(strat->sig[k-1]);
3626  }
3627  }
3628  #endif
3629  #endif
3630  //Never do this - you will damage S
3631  //idSkipZeroes(strat->Shdl);
3632  //idPrint(strat->Shdl);
3633 
3634  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3635  {
3636  rChangeCurrRing (currRingOld);
3637  F0 = idrMoveR (F1, sRing, currRing);
3638  strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3639  rChangeCurrRing (sRing);
3641  exitSba(strat);
3642  rChangeCurrRing (currRingOld);
3643  if(strat->tailRing == sRing)
3644  strat->tailRing = currRing;
3645  rDelete (sRing);
3646  }
3647  if(rField_is_Ring(currRing) && !strat->sigdrop)
3648  id_DelDiv(strat->Shdl, currRing);
3649  if(!rField_is_Ring(currRing))
3650  id_DelDiv(strat->Shdl, currRing);
3651  idSkipZeroes(strat->Shdl);
3652  idTest(strat->Shdl);
3653 
3654 #if SBA_PRINT_SIZE_G
3655  size_g = IDELEMS(strat->Shdl);
3656 #endif
3657 #ifdef DEBUGF5
3658  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3659  int oo = 0;
3660  while (oo<IDELEMS(strat->Shdl))
3661  {
3662  printf(" %d. ",oo+1);
3663  pWrite(pHead(strat->Shdl->m[oo]));
3664  oo++;
3665  }
3666 #endif
3667 #if SBA_PRINT_ZERO_REDUCTIONS
3668  printf("----------------------------------------------------------\n");
3669  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3670  zeroreductions = 0;
3671 #endif
3672 #if SBA_PRINT_REDUCTION_STEPS
3673  printf("----------------------------------------------------------\n");
3674  printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3675 #endif
3676 #if SBA_PRINT_OPERATIONS
3677  printf("OPERATIONS: %ld\n",sba_operations);
3678 #endif
3679 #if SBA_PRINT_REDUCTION_STEPS
3680  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3681  printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3682 #endif
3683 #if SBA_PRINT_OPERATIONS
3684  printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3685 #endif
3686 #if SBA_PRINT_REDUCTION_STEPS
3687  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3688  printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3689  sba_interreduction_steps = 0;
3690  sba_reduction_steps = 0;
3691 #endif
3692 #if SBA_PRINT_OPERATIONS
3693  printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3694  sba_interreduction_operations = 0;
3695  sba_operations = 0;
3696 #endif
3697 #if SBA_PRINT_SIZE_G
3698  printf("----------------------------------------------------------\n");
3699  printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3700  size_g = 0;
3701  size_g_non_red = 0;
3702 #endif
3703 #if SBA_PRINT_SIZE_SYZ
3704  printf("SIZE OF SYZ: %ld\n",size_syz);
3705  printf("----------------------------------------------------------\n");
3706  size_syz = 0;
3707 #endif
3708 #if SBA_PRINT_PRODUCT_CRITERION
3709  printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3710  product_criterion = 0;
3711 #endif
3712  return (strat->Shdl);
3713 }
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:3743
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1734
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kstd2.cc:1578
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:4046
void initSbaPos(kStrategy strat)
Definition: kutil.cc:10184
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9652
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4613
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4569
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
Definition: kutil.cc:11415
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:7838
void initSyzRules(kStrategy strat)
Definition: kutil.cc:8248
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10286
int posInSyz(const kStrategy strat, poly sig)
Definition: kutil.cc:6018
void exitSba(kStrategy strat)
Definition: kutil.cc:10361
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
Definition: kutil.cc:4941
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9813
#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:3812
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1413
static void p_SetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1546
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1582
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1522
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.