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

◆ DEBUGF51

#define DEBUGF51   0

Definition at line 25 of file kstd2.cc.

◆ F5C

#define F5C   1

Definition at line 32 of file kstd2.cc.

◆ F5CTAILRED

#define F5CTAILRED   1

Definition at line 34 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 37 of file kstd2.cc.

◆ SBA_PRINT_OPERATIONS

#define SBA_PRINT_OPERATIONS   0

Definition at line 42 of file kstd2.cc.

◆ SBA_PRINT_PRODUCT_CRITERION

#define SBA_PRINT_PRODUCT_CRITERION   0

Definition at line 45 of file kstd2.cc.

◆ SBA_PRINT_REDUCTION_STEPS

#define SBA_PRINT_REDUCTION_STEPS   0

Definition at line 41 of file kstd2.cc.

◆ SBA_PRINT_SIZE_G

#define SBA_PRINT_SIZE_G   0

Definition at line 43 of file kstd2.cc.

◆ SBA_PRINT_SIZE_SYZ

#define SBA_PRINT_SIZE_SYZ   0

Definition at line 44 of file kstd2.cc.

◆ SBA_PRINT_ZERO_REDUCTIONS

#define SBA_PRINT_ZERO_REDUCTIONS   0

Definition at line 40 of file kstd2.cc.

◆ SBA_PRODUCT_CRITERION

#define SBA_PRODUCT_CRITERION   0

Definition at line 39 of file kstd2.cc.

◆ SBA_TAIL_RED

#define SBA_TAIL_RED   1

Definition at line 38 of file kstd2.cc.

Function Documentation

◆ bba()

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

Definition at line 2374 of file kstd2.cc.

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

◆ bbaShift()

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

Definition at line 4345 of file kstd2.cc.

4346 {
4347  int red_result = 1;
4348  int olddeg,reduc;
4349  int hilbeledeg=1,hilbcount=0,minimcnt=0;
4350  BOOLEAN withT = TRUE; // currently only T contains the shifts
4351  BITSET save;
4352  SI_SAVE_OPT1(save);
4353 
4354  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4356  initBuchMoraPosRing(strat);
4357  else
4358  initBuchMoraPos(strat);
4359  initHilbCrit(F,Q,&hilb,strat);
4360  initBba(strat);
4361  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4362  /*Shdl=*/initBuchMora(F, Q,strat);
4363  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4364  reduc = olddeg = 0;
4365 
4366 #ifndef NO_BUCKETS
4367  if (!TEST_OPT_NOT_BUCKETS)
4368  strat->use_buckets = 1;
4369 #endif
4370  // redtailBBa against T for inhomogenous input
4371  // if (!TEST_OPT_OLDSTD)
4372  // withT = ! strat->homog;
4373 
4374  // strat->posInT = posInT_pLength;
4375  kTest_TS(strat);
4376 
4377 #ifdef HAVE_TAIL_RING
4378  // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4379  // kStratInitChangeTailRing(strat);
4380  strat->tailRing=currRing;
4381 #endif
4382  if (BVERBOSE(23))
4383  {
4384  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4385  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4386  kDebugPrint(strat);
4387  }
4388 
4389 #ifdef KDEBUG
4390  //kDebugPrint(strat);
4391 #endif
4392  /* compute------------------------------------------------------- */
4393  while (strat->Ll >= 0)
4394  {
4395  #ifdef KDEBUG
4396  if (TEST_OPT_DEBUG) messageSets(strat);
4397  #endif
4398  if (siCntrlc)
4399  {
4400  while (strat->Ll >= 0)
4401  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4402  strat->noClearS=TRUE;
4403  }
4404  if (TEST_OPT_DEGBOUND
4405  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4406  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4407  {
4408  /*
4409  *stops computation if
4410  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4411  *a predefined number Kstd1_deg
4412  */
4413  while ((strat->Ll >= 0)
4414  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4415  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4416  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4417  )
4418  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4419  if (strat->Ll<0) break;
4420  else strat->noClearS=TRUE;
4421  }
4422  if (strat->Ll== 0) strat->interpt=TRUE;
4423  /* picks the last element from the lazyset L */
4424  strat->P = strat->L[strat->Ll];
4425  strat->Ll--;
4426 
4427  if (pNext(strat->P.p) == strat->tail)
4428  {
4429  // deletes the short spoly
4430  if (rField_is_Ring(currRing))
4431  pLmDelete(strat->P.p);
4432  else
4433  pLmFree(strat->P.p);
4434  strat->P.p = NULL;
4435  poly m1 = NULL, m2 = NULL;
4436 
4437  // check that spoly creation is ok
4438  while (strat->tailRing != currRing &&
4439  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4440  {
4441  assume(m1 == NULL && m2 == NULL);
4442  // if not, change to a ring where exponents are at least
4443  // large enough
4444  if (!kStratChangeTailRing(strat))
4445  {
4446  WerrorS("OVERFLOW...");
4447  break;
4448  }
4449  }
4450  // create the real one
4451  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4452  strat->tailRing, m1, m2, strat->R);
4453  }
4454  else if (strat->P.p1 == NULL)
4455  {
4456  if (strat->minim > 0)
4457  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4458  // for input polys, prepare reduction
4459  strat->P.PrepareRed(strat->use_buckets);
4460  }
4461 
4462  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4463  {
4464  red_result = 0;
4465  }
4466  else
4467  {
4468  if (TEST_OPT_PROT)
4469  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4470  &olddeg,&reduc,strat, red_result);
4471 
4472  /* reduction of the element chosen from L */
4473  red_result = strat->red(&strat->P,strat);
4474  if (errorreported) break;
4475  }
4476 
4477  if (strat->overflow)
4478  {
4479  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4480  }
4481 
4482  // reduction to non-zero new poly
4483  if (red_result == 1)
4484  {
4485  // get the polynomial (canonicalize bucket, make sure P.p is set)
4486  strat->P.GetP(strat->lmBin);
4487  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4488  // but now, for entering S, T, we reset it
4489  // in the inhomogeneous case: FDeg == pFDeg
4490  if (strat->homog) strat->initEcart(&(strat->P));
4491 
4492  /* statistic */
4493  if (TEST_OPT_PROT) PrintS("s");
4494 
4495  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4496 
4497  // reduce the tail and normalize poly
4498  // in the ring case we cannot expect LC(f) = 1,
4499  // therefore we call pCleardenom instead of pNorm
4500  strat->redTailChange=FALSE;
4501 
4502  /* if we are computing over Z we always want to try and cut down
4503  * the coefficients in the tail terms */
4505  {
4506  redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4507  strat->P.pCleardenom();
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:327
char rightGB
Definition: kutil.h:373
unsigned long * sevT
Definition: kutil.h:326
intset fromQ
Definition: kutil.h:322
#define WarnS
Definition: emacs.cc:78
void enterTShift(LObject p, kStrategy strat, int atT)
Definition: kutil.cc:13339
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13309
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1137
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition: polys.h:146
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105

◆ f5c()

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

Definition at line 4032 of file kstd2.cc.

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

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

◆ ind_fact_2()

static long ind_fact_2 ( long  arg)
static

Definition at line 538 of file kstd2.cc.

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

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11753 of file kutil.cc.

11754 {
11755  PrintS("red: ");
11756  if (strat->red==redFirst) PrintS("redFirst\n");
11757  else if (strat->red==redHoney) PrintS("redHoney\n");
11758  else if (strat->red==redEcart) PrintS("redEcart\n");
11759  else if (strat->red==redHomog) PrintS("redHomog\n");
11760  else if (strat->red==redLazy) PrintS("redLazy\n");
11761  else if (strat->red==redLiftstd) PrintS("redLiftstd\n");
11762  else Print("%p\n",(void*)strat->red);
11763  PrintS("posInT: ");
11764  if (strat->posInT==posInT0) PrintS("posInT0\n");
11765  else if (strat->posInT==posInT1) PrintS("posInT1\n");
11766  else if (strat->posInT==posInT11) PrintS("posInT11\n");
11767  else if (strat->posInT==posInT110) PrintS("posInT110\n");
11768  else if (strat->posInT==posInT13) PrintS("posInT13\n");
11769  else if (strat->posInT==posInT15) PrintS("posInT15\n");
11770  else if (strat->posInT==posInT17) PrintS("posInT17\n");
11771  else if (strat->posInT==posInT17_c) PrintS("posInT17_c\n");
11772  else if (strat->posInT==posInT19) PrintS("posInT19\n");
11773  else if (strat->posInT==posInT2) PrintS("posInT2\n");
11774  #ifdef HAVE_RINGS
11775  else if (strat->posInT==posInT11Ring) PrintS("posInT11Ring\n");
11776  else if (strat->posInT==posInT110Ring) PrintS("posInT110Ring\n");
11777  else if (strat->posInT==posInT15Ring) PrintS("posInT15Ring\n");
11778  else if (strat->posInT==posInT17Ring) PrintS("posInT17Ring\n");
11779  else if (strat->posInT==posInT17_cRing) PrintS("posInT17_cRing\n");
11780  #endif
11781 #ifdef HAVE_MORE_POS_IN_T
11782  else if (strat->posInT==posInT_EcartFDegpLength) PrintS("posInT_EcartFDegpLength\n");
11783  else if (strat->posInT==posInT_FDegpLength) PrintS("posInT_FDegpLength\n");
11784  else if (strat->posInT==posInT_pLength) PrintS("posInT_pLength\n");
11785 #endif
11786  else if (strat->posInT==posInT_EcartpLength) PrintS("posInT_EcartpLength\n");
11787  else if (strat->posInT==posInTrg0) PrintS("posInTrg0\n");
11788  else Print("%p\n",(void*)strat->posInT);
11789  PrintS("posInL: ");
11790  if (strat->posInL==posInL0) PrintS("posInL0\n");
11791  else if (strat->posInL==posInL10) PrintS("posInL10\n");
11792  else if (strat->posInL==posInL11) PrintS("posInL11\n");
11793  else if (strat->posInL==posInL110) PrintS("posInL110\n");
11794  else if (strat->posInL==posInL13) PrintS("posInL13\n");
11795  else if (strat->posInL==posInL15) PrintS("posInL15\n");
11796  else if (strat->posInL==posInL17) PrintS("posInL17\n");
11797  else if (strat->posInL==posInL17_c) PrintS("posInL17_c\n");
11798  #ifdef HAVE_RINGS
11799  else if (strat->posInL==posInL0) PrintS("posInL0Ring\n");
11800  else if (strat->posInL==posInL11Ring) PrintS("posInL11Ring\n");
11801  else if (strat->posInL==posInL11Ringls) PrintS("posInL11Ringls\n");
11802  else if (strat->posInL==posInL110Ring) PrintS("posInL110Ring\n");
11803  else if (strat->posInL==posInL15Ring) PrintS("posInL15Ring\n");
11804  else if (strat->posInL==posInL17Ring) PrintS("posInL17Ring\n");
11805  else if (strat->posInL==posInL17_cRing) PrintS("posInL17_cRing\n");
11806  #endif
11807  else if (strat->posInL==posInLSpecial) PrintS("posInLSpecial\n");
11808  else if (strat->posInL==posInLrg0) PrintS("posInLrg0\n");
11809  else Print("%p\n",(void*)strat->posInL);
11810  PrintS("enterS: ");
11811  if (strat->enterS==enterSBba) PrintS("enterSBba\n");
11812  else if (strat->enterS==enterSMora) PrintS("enterSMora\n");
11813  else if (strat->enterS==enterSMoraNF) PrintS("enterSMoraNF\n");
11814  else Print("%p\n",(void*)strat->enterS);
11815  PrintS("initEcart: ");
11816  if (strat->initEcart==initEcartBBA) PrintS("initEcartBBA\n");
11817  else if (strat->initEcart==initEcartNormal) PrintS("initEcartNormal\n");
11818  else Print("%p\n",(void*)strat->initEcart);
11819  PrintS("initEcartPair: ");
11820  if (strat->initEcartPair==initEcartPairBba) PrintS("initEcartPairBba\n");
11821  else if (strat->initEcartPair==initEcartPairMora) PrintS("initEcartPairMora\n");
11822  else Print("%p\n",(void*)strat->initEcartPair);
11823  Print("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11824  strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11825  Print("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11826  strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11827  PrintS("chainCrit: ");
11828  if (strat->chainCrit==chainCritNormal) PrintS("chainCritNormal\n");
11829  else if (strat->chainCrit==chainCritOpt_1) PrintS("chainCritOpt_1\n");
11830  else Print("%p\n",(void*)strat->chainCrit);
11831  Print("posInLDependsOnLength=%d\n",
11832  strat->posInLDependsOnLength);
11833  PrintS(showOption());PrintLn();
11834  PrintS("LDeg: ");
11835  if (currRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11836  else if (currRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11837  else if (currRing->pLDeg==pLDegb) PrintS("pLDegb");
11838  else if (currRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11839  else if (currRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11840  else if (currRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11841  else if (currRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11842  else if (currRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11843  else if (currRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11844  else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11845  else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11846  else if (currRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11847  else Print("? (%lx)", (long)currRing->pLDeg);
11848  PrintS(" / ");
11849  if (strat->tailRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11850  else if (strat->tailRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11851  else if (strat->tailRing->pLDeg==pLDegb) PrintS("pLDegb");
11852  else if (strat->tailRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11853  else if (strat->tailRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11854  else if (strat->tailRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11855  else if (strat->tailRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11856  else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11857  else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11858  else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11859  else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11860  else if (strat->tailRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11861  else Print("? (%lx)", (long)strat->tailRing->pLDeg);
11862  PrintLn();
11863  PrintS("currRing->pFDeg: ");
11864  if (currRing->pFDeg==p_Totaldegree) PrintS("p_Totaldegree");
11865  else if (currRing->pFDeg==p_WFirstTotalDegree) PrintS("pWFirstTotalDegree");
11866  else if (currRing->pFDeg==p_Deg) PrintS("p_Deg");
11867  else if (currRing->pFDeg==kHomModDeg) PrintS("kHomModDeg");
11868  else if (currRing->pFDeg==totaldegreeWecart) PrintS("totaldegreeWecart");
11869  else if (currRing->pFDeg==p_WTotaldegree) PrintS("p_WTotaldegree");
11870  else Print("? (%lx)", (long)currRing->pFDeg);
11871  PrintLn();
11872  Print(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11873  if(TEST_OPT_DEGBOUND)
11874  Print(" degBound: %d\n", Kstd1_deg);
11875 
11876  if( ecartWeights != NULL )
11877  {
11878  PrintS("ecartWeights: ");
11879  for (int i = rVar(currRing); i > 0; i--)
11880  Print("%hd ", ecartWeights[i]);
11881  PrintLn();
11883  }
11884 
11885 #ifndef SING_NDEBUG
11887 #endif
11888 }
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:292
char noTailReduction
Definition: kutil.h:382
int ak
Definition: kutil.h:356
char sugarCrit
Definition: kutil.h:381
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:288
char Gebauer
Definition: kutil.h:382
int LazyPass
Definition: kutil.h:356
int LazyDegree
Definition: kutil.h:356
char posInLDependsOnLength
Definition: kutil.h:393
#define Print
Definition: emacs.cc:80
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:152
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1342
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2417
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1892
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:929
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1687
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6527
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6641
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6284
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5394
int posInTrg0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5067
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:786
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6028
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4990
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4934
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5185
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1660
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5261
int posInT0(const TSet, const int length, LObject &)
Definition: kutil.cc:4923
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4962
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6372
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6325
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11719
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5232
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1347
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5728
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3476
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5026
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6407
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5501
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11628
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5299
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5685
VAR int Kstd1_deg
Definition: kutil.cc:247
void initEcartNormal(TObject *h)
Definition: kutil.cc:1325
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6098
char * showOption()
Definition: misc_ip.cc:717
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6483
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5143
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6442
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5628
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5353
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5455
int posInLrg0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6200
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1606
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5562
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6577
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11682
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3240
void initEcartBBA(TObject *h)
Definition: kutil.cc:1333
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5986
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1340
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9023
#define TEST_OPT_WEIGHTM
Definition: options.h:121
long pLDegb(poly p, int *l, const ring r)
Definition: p_polys.cc:806
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:970
long p_WFirstTotalDegree(poly p, const ring r)
Definition: p_polys.cc:591
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1033
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1063
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:936
long pLDeg1(poly p, int *l, const ring r)
Definition: p_polys.cc:836
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:905
long p_WTotaldegree(poly p, const ring r)
Definition: p_polys.cc:608
long pLDeg1c(poly p, int *l, const ring r)
Definition: p_polys.cc:872
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1000
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:765
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:734
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1467
void rDebugPrint(const ring r)
Definition: ring.cc:4072
static int rGetCurrSyzLimit(const ring r)
Definition: ring.h:725
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition: ring.h:722
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:594
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 398 of file kstd2.cc.

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

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

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

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

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

◆ kFindSameLMInT_Z()

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

Definition at line 84 of file kstd2.cc.

85 {
86  unsigned long not_sev = ~L->sev;
87  int j = start;
88  int o = -1;
89 
90  const TSet T=strat->T;
91  const unsigned long* sevT=strat->sevT;
92  number gcd, ogcd;
93  if (L->p!=NULL)
94  {
95  const ring r=currRing;
96  const poly p=L->p;
97  ogcd = pGetCoeff(p);
98 
99  pAssume(~not_sev == p_GetShortExpVector(p, r));
100 
101  loop
102  {
103  if (j > strat->tl) return o;
104  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
105  {
106  gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
107  if (o == -1
108  || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
109  {
110  ogcd = gcd;
111  o = j;
112  }
113  }
114  j++;
115  }
116  }
117  else
118  {
119  const ring r=strat->tailRing;
120  const poly p=L->t_p;
121  ogcd = pGetCoeff(p);
122  loop
123  {
124  if (j > strat->tl) return o;
125  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
126  {
127  gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
128  if (o == -1
129  || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
130  {
131  ogcd = gcd;
132  o = j;
133  }
134  }
135  j++;
136  }
137  }
138 }
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:687
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1691
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ kFindZeroPoly()

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

Definition at line 553 of file kstd2.cc.

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

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

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

◆ kNF2Bound() [1/2]

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

Definition at line 3945 of file kstd2.cc.

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

◆ kNF2Bound() [2/2]

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

Definition at line 3783 of file kstd2.cc.

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

◆ ksReducePolyTailSig()

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

Definition at line 1111 of file kstd2.cc.

1112 {
1113  BOOLEAN ret;
1114  number coef;
1115  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1116  if(!rField_is_Ring(currRing))
1117  Red->HeadNormalize();
1118  /*
1119  printf("------------------------\n");
1120  pWrite(Red->GetLmCurrRing());
1121  */
1123  ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1124  else
1125  ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1126  if (!ret)
1127  {
1128  if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1129  {
1130  PR->Mult_nn(coef);
1131  // HANNES: mark for Normalize
1132  }
1133  n_Delete(&coef, currRing->cf);
1134  }
1135  return ret;
1136 }
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:707
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:910

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

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

◆ 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:389
char length_pLength
Definition: kutil.h:391
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat)
Definition: kspoly.cc:185
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:288
#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 929 of file kstd2.cc.

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

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

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1687 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2126 of file kstd2.cc.

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

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

◆ redRing()

int redRing ( LObject h,
kStrategy  strat 
)

Definition at line 822 of file kstd2.cc.

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

◆ redRing_Z()

int redRing_Z ( LObject h,
kStrategy  strat 
)

Definition at line 667 of file kstd2.cc.

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

◆ redSig()

int redSig ( LObject h,
kStrategy  strat 
)

Definition at line 1149 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1317 of file kstd2.cc.

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

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

◆ sba()

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

Definition at line 2734 of file kstd2.cc.

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