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

Go to the source code of this file.

Macros

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

Functions

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

Variables

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

Macro Definition Documentation

◆ DEBUGF50

#define DEBUGF50   0

Definition at line 26 of file kstd2.cc.

◆ DEBUGF51

#define DEBUGF51   0

Definition at line 27 of file kstd2.cc.

◆ F5C

#define F5C   1

Definition at line 34 of file kstd2.cc.

◆ F5CTAILRED

#define F5CTAILRED   1

Definition at line 36 of file kstd2.cc.

◆ GCD_SBA

#define GCD_SBA   1

Definition at line 12 of file kstd2.cc.

◆ PLURAL_INTERNAL_DECLARATIONS

#define PLURAL_INTERNAL_DECLARATIONS   1

Definition at line 18 of file kstd2.cc.

◆ SBA_INTERRED_START

#define SBA_INTERRED_START   0

Definition at line 39 of file kstd2.cc.

◆ SBA_PRINT_OPERATIONS

#define SBA_PRINT_OPERATIONS   0

Definition at line 44 of file kstd2.cc.

◆ SBA_PRINT_PRODUCT_CRITERION

#define SBA_PRINT_PRODUCT_CRITERION   0

Definition at line 47 of file kstd2.cc.

◆ SBA_PRINT_REDUCTION_STEPS

#define SBA_PRINT_REDUCTION_STEPS   0

Definition at line 43 of file kstd2.cc.

◆ SBA_PRINT_SIZE_G

#define SBA_PRINT_SIZE_G   0

Definition at line 45 of file kstd2.cc.

◆ SBA_PRINT_SIZE_SYZ

#define SBA_PRINT_SIZE_SYZ   0

Definition at line 46 of file kstd2.cc.

◆ SBA_PRINT_ZERO_REDUCTIONS

#define SBA_PRINT_ZERO_REDUCTIONS   0

Definition at line 42 of file kstd2.cc.

◆ SBA_PRODUCT_CRITERION

#define SBA_PRODUCT_CRITERION   0

Definition at line 41 of file kstd2.cc.

◆ SBA_TAIL_RED

#define SBA_TAIL_RED   1

Definition at line 40 of file kstd2.cc.

◆ STDZ_EXHANGE_DURING_REDUCTION

#define STDZ_EXHANGE_DURING_REDUCTION   0

Definition at line 21 of file kstd2.cc.

Function Documentation

◆ bba()

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

Definition at line 2642 of file kstd2.cc.

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

◆ bbaShift()

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

Definition at line 4608 of file kstd2.cc.

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

◆ f5c()

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

Definition at line 4296 of file kstd2.cc.

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

◆ ind_fact_2()

static long ind_fact_2 ( long  arg)
static

Definition at line 554 of file kstd2.cc.

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

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11560 of file kutil.cc.

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

◆ kFindDivisibleByInS()

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

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

Definition at line 421 of file kstd2.cc.

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

◆ kFindDivisibleByInS_noCF()

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

Definition at line 484 of file kstd2.cc.

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

◆ kFindDivisibleByInS_Z()

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

Definition at line 276 of file kstd2.cc.

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

◆ kFindDivisibleByInT()

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

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

Definition at line 321 of file kstd2.cc.

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

◆ kFindDivisibleByInT_Z()

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

Definition at line 213 of file kstd2.cc.

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

◆ kFindNextDivisibleByInS()

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

Definition at line 524 of file kstd2.cc.

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

◆ kFindZeroPoly()

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

Definition at line 569 of file kstd2.cc.

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

◆ kNF2() [1/2]

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

Definition at line 4123 of file kstd2.cc.

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

◆ kNF2() [2/2]

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

Definition at line 3967 of file kstd2.cc.

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

◆ kNF2Bound() [1/2]

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

Definition at line 4208 of file kstd2.cc.

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

◆ kNF2Bound() [2/2]

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

Definition at line 4049 of file kstd2.cc.

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

◆ ksReducePolyTailSig()

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

Definition at line 1305 of file kstd2.cc.

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

◆ kTestDivisibleByT0_Z()

int kTestDivisibleByT0_Z ( const kStrategy  strat,
const LObject L 
)

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

Definition at line 146 of file kstd2.cc.

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

◆ redFirstShift()

int redFirstShift ( LObject h,
kStrategy  strat 
)

Definition at line 4988 of file kstd2.cc.

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

◆ redHomog()

int redHomog ( LObject h,
kStrategy  strat 
)

Definition at line 1121 of file kstd2.cc.

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

◆ redHoney()

int redHoney ( LObject h,
kStrategy  strat 
)

Definition at line 2088 of file kstd2.cc.

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

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1881 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2325 of file kstd2.cc.

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

◆ redNFBound()

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

Definition at line 2525 of file kstd2.cc.

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

◆ redRing()

int redRing ( LObject h,
kStrategy  strat 
)

Definition at line 954 of file kstd2.cc.

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

◆ redRing_S()

static int redRing_S ( LObject h,
kStrategy  strat 
)
static

Definition at line 1056 of file kstd2.cc.

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

◆ redRing_Z()

int redRing_Z ( LObject h,
kStrategy  strat 
)

Definition at line 683 of file kstd2.cc.

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

◆ redRing_Z_S()

static int redRing_Z_S ( LObject h,
kStrategy  strat 
)
static

Definition at line 841 of file kstd2.cc.

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

◆ redSig()

int redSig ( LObject h,
kStrategy  strat 
)

Definition at line 1343 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1511 of file kstd2.cc.

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

◆ redtailSba()

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

Definition at line 1761 of file kstd2.cc.

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

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4972 of file kstd2.cc.

4973{
4975 assume(idIsInV(F));
4976 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4977 idSkipZeroes(RS); // is this even necessary?
4978 assume(idIsInV(RS));
4979 return(RS);
4980}
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2926
#define idIsInV(I)
Definition: shiftop.h:49
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
@ testHomog
Definition: structs.h:38

◆ sba()

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

Definition at line 3001 of file kstd2.cc.

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

Variable Documentation

◆ test_PosInL

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

Definition at line 83 of file kstd2.cc.

◆ test_PosInT

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

Definition at line 82 of file kstd2.cc.