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

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

◆ bbaShift()

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

Definition at line 4347 of file kstd2.cc.

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

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

◆ ind2()

static long ind2 ( long  arg)
static

Definition at line 528 of file kstd2.cc.

529 {
530  if (arg <= 0) return 0;
531  long ind = 0;
532  while (arg%2 == 0)
533  {
534  arg = arg / 2;
535  ind++;
536  }
537  return ind;
538 }

◆ ind_fact_2()

static long ind_fact_2 ( long  arg)
static

Definition at line 540 of file kstd2.cc.

541 {
542  if (arg <= 0) return 0;
543  long ind = 0;
544  if (arg%2 == 1) { arg--; }
545  while (arg > 0)
546  {
547  ind += ind2(arg);
548  arg = arg - 2;
549  }
550  return ind;
551 }
static long ind2(long arg)
Definition: kstd2.cc:528

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11779 of file kutil.cc.

11780 {
11781  PrintS("red: ");
11782  if (strat->red==redFirst) PrintS("redFirst\n");
11783  else if (strat->red==redHoney) PrintS("redHoney\n");
11784  else if (strat->red==redEcart) PrintS("redEcart\n");
11785  else if (strat->red==redHomog) PrintS("redHomog\n");
11786  else if (strat->red==redLazy) PrintS("redLazy\n");
11787  else if (strat->red==redLiftstd) PrintS("redLiftstd\n");
11788  else Print("%p\n",(void*)strat->red);
11789  PrintS("posInT: ");
11790  if (strat->posInT==posInT0) PrintS("posInT0\n");
11791  else if (strat->posInT==posInT1) PrintS("posInT1\n");
11792  else if (strat->posInT==posInT11) PrintS("posInT11\n");
11793  else if (strat->posInT==posInT110) PrintS("posInT110\n");
11794  else if (strat->posInT==posInT13) PrintS("posInT13\n");
11795  else if (strat->posInT==posInT15) PrintS("posInT15\n");
11796  else if (strat->posInT==posInT17) PrintS("posInT17\n");
11797  else if (strat->posInT==posInT17_c) PrintS("posInT17_c\n");
11798  else if (strat->posInT==posInT19) PrintS("posInT19\n");
11799  else if (strat->posInT==posInT2) PrintS("posInT2\n");
11800  #ifdef HAVE_RINGS
11801  else if (strat->posInT==posInT11Ring) PrintS("posInT11Ring\n");
11802  else if (strat->posInT==posInT110Ring) PrintS("posInT110Ring\n");
11803  else if (strat->posInT==posInT15Ring) PrintS("posInT15Ring\n");
11804  else if (strat->posInT==posInT17Ring) PrintS("posInT17Ring\n");
11805  else if (strat->posInT==posInT17_cRing) PrintS("posInT17_cRing\n");
11806  #endif
11807 #ifdef HAVE_MORE_POS_IN_T
11808  else if (strat->posInT==posInT_EcartFDegpLength) PrintS("posInT_EcartFDegpLength\n");
11809  else if (strat->posInT==posInT_FDegpLength) PrintS("posInT_FDegpLength\n");
11810  else if (strat->posInT==posInT_pLength) PrintS("posInT_pLength\n");
11811 #endif
11812  else if (strat->posInT==posInT_EcartpLength) PrintS("posInT_EcartpLength\n");
11813  else if (strat->posInT==posInTrg0) PrintS("posInTrg0\n");
11814  else Print("%p\n",(void*)strat->posInT);
11815  PrintS("posInL: ");
11816  if (strat->posInL==posInL0) PrintS("posInL0\n");
11817  else if (strat->posInL==posInL10) PrintS("posInL10\n");
11818  else if (strat->posInL==posInL11) PrintS("posInL11\n");
11819  else if (strat->posInL==posInL110) PrintS("posInL110\n");
11820  else if (strat->posInL==posInL13) PrintS("posInL13\n");
11821  else if (strat->posInL==posInL15) PrintS("posInL15\n");
11822  else if (strat->posInL==posInL17) PrintS("posInL17\n");
11823  else if (strat->posInL==posInL17_c) PrintS("posInL17_c\n");
11824  #ifdef HAVE_RINGS
11825  else if (strat->posInL==posInL0) PrintS("posInL0Ring\n");
11826  else if (strat->posInL==posInL11Ring) PrintS("posInL11Ring\n");
11827  else if (strat->posInL==posInL11Ringls) PrintS("posInL11Ringls\n");
11828  else if (strat->posInL==posInL110Ring) PrintS("posInL110Ring\n");
11829  else if (strat->posInL==posInL15Ring) PrintS("posInL15Ring\n");
11830  else if (strat->posInL==posInL17Ring) PrintS("posInL17Ring\n");
11831  else if (strat->posInL==posInL17_cRing) PrintS("posInL17_cRing\n");
11832  #endif
11833  else if (strat->posInL==posInLSpecial) PrintS("posInLSpecial\n");
11834  else if (strat->posInL==posInLrg0) PrintS("posInLrg0\n");
11835  else Print("%p\n",(void*)strat->posInL);
11836  PrintS("enterS: ");
11837  if (strat->enterS==enterSBba) PrintS("enterSBba\n");
11838  else if (strat->enterS==enterSMora) PrintS("enterSMora\n");
11839  else if (strat->enterS==enterSMoraNF) PrintS("enterSMoraNF\n");
11840  else Print("%p\n",(void*)strat->enterS);
11841  PrintS("initEcart: ");
11842  if (strat->initEcart==initEcartBBA) PrintS("initEcartBBA\n");
11843  else if (strat->initEcart==initEcartNormal) PrintS("initEcartNormal\n");
11844  else Print("%p\n",(void*)strat->initEcart);
11845  PrintS("initEcartPair: ");
11846  if (strat->initEcartPair==initEcartPairBba) PrintS("initEcartPairBba\n");
11847  else if (strat->initEcartPair==initEcartPairMora) PrintS("initEcartPairMora\n");
11848  else Print("%p\n",(void*)strat->initEcartPair);
11849  Print("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11850  strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11851  Print("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11852  strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11853  PrintS("chainCrit: ");
11854  if (strat->chainCrit==chainCritNormal) PrintS("chainCritNormal\n");
11855  else if (strat->chainCrit==chainCritOpt_1) PrintS("chainCritOpt_1\n");
11856  else Print("%p\n",(void*)strat->chainCrit);
11857  Print("posInLDependsOnLength=%d\n",
11858  strat->posInLDependsOnLength);
11859  PrintS(showOption());PrintLn();
11860  PrintS("LDeg: ");
11861  if (currRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11862  else if (currRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11863  else if (currRing->pLDeg==pLDegb) PrintS("pLDegb");
11864  else if (currRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11865  else if (currRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11866  else if (currRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11867  else if (currRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11868  else if (currRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11869  else if (currRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11870  else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11871  else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11872  else if (currRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11873  else Print("? (%lx)", (long)currRing->pLDeg);
11874  PrintS(" / ");
11875  if (strat->tailRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11876  else if (strat->tailRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11877  else if (strat->tailRing->pLDeg==pLDegb) PrintS("pLDegb");
11878  else if (strat->tailRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11879  else if (strat->tailRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11880  else if (strat->tailRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11881  else if (strat->tailRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11882  else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11883  else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11884  else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11885  else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11886  else if (strat->tailRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11887  else Print("? (%lx)", (long)strat->tailRing->pLDeg);
11888  PrintLn();
11889  PrintS("currRing->pFDeg: ");
11890  if (currRing->pFDeg==p_Totaldegree) PrintS("p_Totaldegree");
11891  else if (currRing->pFDeg==p_WFirstTotalDegree) PrintS("pWFirstTotalDegree");
11892  else if (currRing->pFDeg==p_Deg) PrintS("p_Deg");
11893  else if (currRing->pFDeg==kHomModDeg) PrintS("kHomModDeg");
11894  else if (currRing->pFDeg==totaldegreeWecart) PrintS("totaldegreeWecart");
11895  else if (currRing->pFDeg==p_WTotaldegree) PrintS("p_WTotaldegree");
11896  else Print("? (%lx)", (long)currRing->pFDeg);
11897  PrintLn();
11898  Print(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11899  if(TEST_OPT_DEGBOUND)
11900  Print(" degBound: %d\n", Kstd1_deg);
11901 
11902  if( ecartWeights != NULL )
11903  {
11904  PrintS("ecartWeights: ");
11905  for (int i = rVar(currRing); i > 0; i--)
11906  Print("%hd ", ecartWeights[i]);
11907  PrintLn();
11909  }
11910 
11911 #ifndef SING_NDEBUG
11913 #endif
11914 }
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:1897
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:934
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1692
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6551
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6665
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6308
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5418
int posInTrg0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5091
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:6052
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5014
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4958
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5209
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:5285
int posInT0(const TSet, const int length, LObject &)
Definition: kutil.cc:4947
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4986
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6396
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6349
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11745
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5256
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1373
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5752
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3500
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5050
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6431
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5525
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11654
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5323
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5709
VAR int Kstd1_deg
Definition: kutil.cc:247
void initEcartNormal(TObject *h)
Definition: kutil.cc:1351
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6122
char * showOption()
Definition: misc_ip.cc:713
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6507
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5167
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6466
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5652
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5377
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5479
int posInLrg0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6224
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:5586
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6601
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11708
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3264
void initEcartBBA(TObject *h)
Definition: kutil.cc:1359
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6010
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1366
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9047
#define TEST_OPT_WEIGHTM
Definition: options.h:121
long pLDegb(poly p, int *l, const ring r)
Definition: p_polys.cc:807
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:971
long p_WFirstTotalDegree(poly p, const ring r)
Definition: p_polys.cc:592
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1034
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1064
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:937
long pLDeg1(poly p, int *l, const ring r)
Definition: p_polys.cc:837
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:906
long p_WTotaldegree(poly p, const ring r)
Definition: p_polys.cc:609
long pLDeg1c(poly p, int *l, const ring r)
Definition: p_polys.cc:873
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1001
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:766
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:735
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1479
void rDebugPrint(const ring r)
Definition: ring.cc:4067
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 400 of file kstd2.cc.

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

◆ 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 (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
312  {
313  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
314  return j;
315  }
316 #else
317  if (!(sevT[j] & not_sev) &&
318  p_LmDivisibleBy(T[j].p, p, r))
319  {
320  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
321  return j;
322  }
323 #endif
324  j++;
325  }
326  }
327  else
328  {
329  loop
330  {
331  if (j > strat->tl) return -1;
332 #if defined(PDEBUG) || defined(PDIV_DEBUG)
333  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
334  {
335  return j;
336  }
337 #else
338  if (!(sevT[j] & not_sev) &&
339  p_LmDivisibleBy(T[j].p, p, r))
340  {
341  return j;
342  }
343 #endif
344  j++;
345  }
346  }
347  }
348  else
349  {
350  const poly p=L->t_p;
351  const ring r=strat->tailRing;
352  if(is_Ring)
353  {
354  loop
355  {
356  if (j > strat->tl) return -1;
357 #if defined(PDEBUG) || defined(PDIV_DEBUG)
358  if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
359  p, not_sev, r))
360  {
361  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
362  return j;
363  }
364 #else
365  if (!(sevT[j] & not_sev) &&
366  p_LmDivisibleBy(T[j].t_p, p, r))
367  {
368  if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
369  return j;
370  }
371 #endif
372  j++;
373  }
374  }
375  else
376  {
377  loop
378  {
379  if (j > strat->tl) return -1;
380 #if defined(PDEBUG) || defined(PDIV_DEBUG)
381  if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
382  p, not_sev, r))
383  {
384  return j;
385  }
386 #else
387  if (!(sevT[j] & not_sev) &&
388  p_LmDivisibleBy(T[j].t_p, p, r))
389  {
390  return j;
391  }
392 #endif
393  j++;
394  }
395  }
396  }
397 }
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 469 of file kstd2.cc.

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

◆ 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:1703
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ kFindZeroPoly()

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

Definition at line 555 of file kstd2.cc.

556 {
557  // m = currRing->ch
558 
559  if (input_p == NULL) return NULL;
560 
561  poly p = input_p;
562  poly zeroPoly = NULL;
563  unsigned long a = (unsigned long) pGetCoeff(p);
564 
565  int k_ind2 = 0;
566  int a_ind2 = ind2(a);
567 
568  // unsigned long k = 1;
569  // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
570  for (int i = 1; i <= leadRing->N; i++)
571  {
572  k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
573  }
574 
575  a = (unsigned long) pGetCoeff(p);
576 
577  number tmp1;
578  poly tmp2, tmp3;
579  poly lead_mult = p_ISet(1, tailRing);
580  if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
581  {
582  int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
583  int s_exp;
584  zeroPoly = p_ISet(a, tailRing);
585  for (int i = 1; i <= leadRing->N; i++)
586  {
587  s_exp = p_GetExp(p, i,leadRing);
588  if (s_exp % 2 != 0)
589  {
590  s_exp = s_exp - 1;
591  }
592  while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
593  {
594  too_much = too_much - ind2(s_exp);
595  s_exp = s_exp - 2;
596  }
597  p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
598  for (int j = 1; j <= s_exp; j++)
599  {
600  tmp1 = nInit(j);
601  tmp2 = p_ISet(1, tailRing);
602  p_SetExp(tmp2, i, 1, tailRing);
603  p_Setm(tmp2, tailRing);
604  if (nIsZero(tmp1))
605  { // should nowbe obsolet, test ! TODO OLIVER
606  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
607  }
608  else
609  {
610  tmp3 = p_NSet(nCopy(tmp1), tailRing);
611  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
612  }
613  }
614  }
615  p_Setm(lead_mult, tailRing);
616  zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
617  tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
618  for (int i = 1; i <= leadRing->N; i++)
619  {
620  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
621  }
622  p_Setm(tmp2, leadRing);
623  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
624  pNext(tmp2) = zeroPoly;
625  return tmp2;
626  }
627 /* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
628  if (1 == 0 && alpha_k <= a)
629  { // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
630  zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
631  for (int i = 1; i <= leadRing->N; i++)
632  {
633  for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
634  {
635  tmp1 = nInit(j);
636  tmp2 = p_ISet(1, tailRing);
637  p_SetExp(tmp2, i, 1, tailRing);
638  p_Setm(tmp2, tailRing);
639  if (nIsZero(tmp1))
640  {
641  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
642  }
643  else
644  {
645  tmp3 = p_ISet((unsigned long) tmp1, tailRing);
646  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
647  }
648  }
649  }
650  tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
651  for (int i = 1; i <= leadRing->N; i++)
652  {
653  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
654  }
655  p_Setm(tmp2, leadRing);
656  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
657  pNext(tmp2) = zeroPoly;
658  return tmp2;
659  } */
660  return NULL;
661 }
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:540
#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:1293
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1465
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:908
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1086
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:488
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:233
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:469
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1023
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:731
#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 3860 of file kstd2.cc.

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

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

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

◆ kNF2Bound() [2/2]

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

Definition at line 3786 of file kstd2.cc.

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

◆ ksReducePolyTailSig()

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

Definition at line 1116 of file kstd2.cc.

1117 {
1118  BOOLEAN ret;
1119  number coef;
1120  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1121  if(!rField_is_Ring(currRing))
1122  Red->HeadNormalize();
1123  /*
1124  printf("------------------------\n");
1125  pWrite(Red->GetLmCurrRing());
1126  */
1128  ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1129  else
1130  ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1131  if (!ret)
1132  {
1133  if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1134  {
1135  PR->Mult_nn(coef);
1136  // HANNES: mark for Normalize
1137  }
1138  n_Delete(&coef, currRing->cf);
1139  }
1140  return ret;
1141 }
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 4724 of file kstd2.cc.

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

◆ redHomog()

int redHomog ( LObject h,
kStrategy  strat 
)

Definition at line 934 of file kstd2.cc.

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

◆ redHoney()

int redHoney ( LObject h,
kStrategy  strat 
)

Definition at line 1897 of file kstd2.cc.

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

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1692 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2131 of file kstd2.cc.

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

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

◆ redRing()

int redRing ( LObject h,
kStrategy  strat 
)

Definition at line 827 of file kstd2.cc.

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

◆ redRing_Z()

int redRing_Z ( LObject h,
kStrategy  strat 
)

Definition at line 669 of file kstd2.cc.

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

◆ redSig()

int redSig ( LObject h,
kStrategy  strat 
)

Definition at line 1154 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1322 of file kstd2.cc.

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

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

4709 {
4711  assume(idIsInV(F));
4712  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4713  idSkipZeroes(RS); // is this even necessary?
4714  assume(idIsInV(RS));
4715  return(RS);
4716 }
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:42

◆ sba()

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

Definition at line 2738 of file kstd2.cc.

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