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

Go to the source code of this file.

Macros

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

Functions

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

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

◆ bbaShift()

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

Definition at line 4601 of file kstd2.cc.

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

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

◆ 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
long kHomModDeg(poly p, const ring r)
Definition: kstd1.cc:2436
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1365
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:2084
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:1121
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1879
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:121
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
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1507
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:1910
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1891

◆ 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:74
CFList tmp2
Definition: facFqBivar.cc:74
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:936
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1114
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:488
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:233
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:469
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1051
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:755
#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 4116 of file kstd2.cc.

4117{
4118 assume(!idIs0(q));
4119 assume(!(idIs0(F)&&(Q==NULL)));
4120// lazy_reduce flags: can be combined by |
4121//#define KSTD_NF_LAZY 1
4122 // do only a reduction of the leading term
4123//#define KSTD_NF_NONORM 4
4124 // only global: avoid normalization, return a multiply of NF
4125 poly p;
4126 int i;
4127 ideal res;
4128 int max_ind;
4129
4130 //if (idIs0(q))
4131 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4132 //if ((idIs0(F))&&(Q==NULL))
4133 // return idCopy(q); /*F=0*/
4134 //strat->ak = idRankFreeModule(F);
4135 /*- creating temp data structures------------------- -*/
4136 BITSET save1;
4137 SI_SAVE_OPT1(save1);
4139 initBuchMoraCrit(strat);
4140 strat->initEcart = initEcartBBA;
4141#ifdef HAVE_SHIFTBBA
4142 if (rIsLPRing(currRing))
4143 {
4144 strat->enterS = enterSBbaShift;
4145 }
4146 else
4147#endif
4148 {
4149 strat->enterS = enterSBba;
4150 }
4151 /*- set S -*/
4152 strat->sl = -1;
4153#ifndef NO_BUCKETS
4155#endif
4156 /*- init local data struct.---------------------------------------- -*/
4157 /*Shdl=*/initS(F,Q,strat);
4158 /*- compute------------------------------------------------------- -*/
4159 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4160 for (i=IDELEMS(q)-1; i>=0; i--)
4161 {
4162 if (q->m[i]!=NULL)
4163 {
4164 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4165 p = redNF(pCopy(q->m[i]),max_ind,
4166 (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4167 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4168 {
4169 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4171 {
4172 p = redtailBba_NF(p,strat);
4173 }
4174 else
4175 {
4176 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4177 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4178 }
4179 }
4180 res->m[i]=p;
4181 }
4182 //else
4183 // res->m[i]=NULL;
4184 }
4185 /*- release temp data------------------------------- -*/
4186 assume(strat->L==NULL); /* strat->L unused */
4187 assume(strat->B==NULL); /* strat->B unused */
4188 omFree(strat->sevS);
4189 omFree(strat->ecartS);
4190 assume(strat->T==NULL);//omfree(strat->T);
4191 assume(strat->sevT==NULL);//omfree(strat->sevT);
4192 assume(strat->R==NULL);//omfree(strat->R);
4193 omfree(strat->S_2_R);
4194 omfree(strat->fromQ);
4195 idDelete(&strat->Shdl);
4196 SI_RESTORE_OPT1(save1);
4197 if (TEST_OPT_PROT) PrintLn();
4198 return res;
4199}
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:2319
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:92
#define OPT_REDTAIL
Definition: options.h:91
#define Sy_bit(x)
Definition: options.h:31
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define mflush()
Definition: reporter.h:58
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static BOOLEAN 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 3960 of file kstd2.cc.

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

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

◆ kNF2Bound() [2/2]

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

Definition at line 4042 of file kstd2.cc.

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

◆ ksReducePolyTailSig()

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

Definition at line 1303 of file kstd2.cc.

1304{
1305 BOOLEAN ret;
1306 number coef;
1307 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1309 Red->HeadNormalize();
1310 /*
1311 printf("------------------------\n");
1312 pWrite(Red->GetLmCurrRing());
1313 */
1315 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1316 else
1317 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1318 if (!ret)
1319 {
1320 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1321 {
1322 PR->Mult_nn(coef);
1323 // HANNES: mark for Normalize
1324 }
1325 n_Delete(&coef, currRing->cf);
1326 }
1327 return ret;
1328}
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:358

◆ redFirstShift()

int redFirstShift ( LObject h,
kStrategy  strat 
)

Definition at line 4981 of file kstd2.cc.

4982{
4983 if (h->IsNull()) return 0;
4984
4985 int at, reddeg,d;
4986 int pass = 0;
4987 int j = 0;
4988
4989 if (! strat->homog)
4990 {
4991 d = h->GetpFDeg() + h->ecart;
4992 reddeg = strat->LazyDegree+d;
4993 }
4994 h->SetShortExpVector();
4995 loop
4996 {
4997 j = kFindDivisibleByInT(strat, h);
4998 if (j < 0)
4999 {
5000 h->SetDegStuffReturnLDeg(strat->LDegLast);
5001 return 1;
5002 }
5003
5005 strat->T[j].pNorm();
5006#ifdef KDEBUG
5007 if (TEST_OPT_DEBUG)
5008 {
5009 PrintS("reduce ");
5010 h->wrp();
5011 PrintS(" with ");
5012 strat->T[j].wrp();
5013 }
5014#endif
5015 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
5016
5017#ifdef KDEBUG
5018 if (TEST_OPT_DEBUG)
5019 {
5020 PrintS("\nto ");
5021 wrp(h->p);
5022 PrintLn();
5023 }
5024#endif
5025 if (h->IsNull())
5026 {
5027 kDeleteLcm(h);
5028 h->Clear();
5029 return 0;
5030 }
5031 h->SetShortExpVector();
5032
5033#if 0
5034 if ((strat->syzComp!=0) && !strat->honey)
5035 {
5036 if ((strat->syzComp>0) &&
5037 (h->Comp() > strat->syzComp))
5038 {
5039 assume(h->MinComp() > strat->syzComp);
5040#ifdef KDEBUG
5041 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
5042#endif
5043 if (strat->homog)
5044 h->SetDegStuffReturnLDeg(strat->LDegLast);
5045 return -2;
5046 }
5047 }
5048#endif
5049 if (!strat->homog)
5050 {
5051 if (!TEST_OPT_OLDSTD && strat->honey)
5052 {
5053 h->SetpFDeg();
5054 if (strat->T[j].ecart <= h->ecart)
5055 h->ecart = d - h->GetpFDeg();
5056 else
5057 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
5058
5059 d = h->GetpFDeg() + h->ecart;
5060 }
5061 else
5062 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
5063 /*- try to reduce the s-polynomial -*/
5064 pass++;
5065 /*
5066 *test whether the polynomial should go to the lazyset L
5067 *-if the degree jumps
5068 *-if the number of pre-defined reductions jumps
5069 */
5070 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
5071 && ((d >= reddeg) || (pass > strat->LazyPass)))
5072 {
5073 h->SetLmCurrRing();
5074 if (strat->posInLDependsOnLength)
5075 h->SetLength(strat->length_pLength);
5076 at = strat->posInL(strat->L,strat->Ll,h,strat);
5077 if (at <= strat->Ll)
5078 {
5079 //int dummy=strat->sl;
5080 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
5081 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
5082 if (kFindDivisibleByInT(strat, h) < 0)
5083 return 1;
5084 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
5085#ifdef KDEBUG
5086 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
5087#endif
5088 h->Clear();
5089 return -1;
5090 }
5091 }
5092 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
5093 {
5094 reddeg = d+1;
5095 Print(".%d",d);mflush();
5096 }
5097 }
5098 }
5099}
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:122
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 }
1220 {
1221 if (h->p!=NULL)
1222 {
1223 if(p_GetComp(h->p,currRing)>strat->syzComp)
1224 {
1225 h->Delete();
1226 return 0;
1227 }
1228 }
1229 else if (h->t_p!=NULL)
1230 {
1231 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1232 {
1233 h->Delete();
1234 return 0;
1235 }
1236 }
1237 }
1238 #if 0
1239 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1240 {
1241 if (h->p!=NULL)
1242 {
1243 if(p_GetComp(h->p,currRing)>strat->syzComp)
1244 {
1245 return 1;
1246 }
1247 }
1248 else if (h->t_p!=NULL)
1249 {
1250 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1251 {
1252 return 1;
1253 }
1254 }
1255 }
1256 #endif
1257 h->SetShortExpVector();
1258 /*
1259 * try to reduce the s-polynomial h
1260 *test first whether h should go to the lazyset L
1261 *-if the degree jumps
1262 *-if the number of pre-defined reductions jumps
1263 */
1264 cnt--;
1265 pass++;
1266 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1267 {
1268 h->SetLmCurrRing();
1269 at = strat->posInL(strat->L,strat->Ll,h,strat);
1270 if (at <= strat->Ll)
1271 {
1272#ifdef HAVE_SHIFTBBA
1273 if (rIsLPRing(currRing))
1274 {
1275 if (kFindDivisibleByInT(strat, h) < 0)
1276 return 1;
1277 }
1278 else
1279#endif
1280 {
1281 int dummy=strat->sl;
1282 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1283 return 1;
1284 }
1285 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1286#ifdef KDEBUG
1287 if (TEST_OPT_DEBUG)
1288 Print(" lazy: -> L%d\n",at);
1289#endif
1290 h->Clear();
1291 return -1;
1292 }
1293 }
1294 else if (UNLIKELY(cnt==0))
1295 {
1296 h->CanonicalizeP();
1297 cnt=RED_CANONICALIZE;
1298 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1299 }
1300 }
1301}
#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:130
#define TEST_OPT_REDTAIL_SYZ
Definition: options.h:117

◆ redHoney()

int redHoney ( LObject h,
kStrategy  strat 
)

Definition at line 2084 of file kstd2.cc.

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

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1879 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2319 of file kstd2.cc.

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

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

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

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1509 of file kstd2.cc.

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

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

Definition at line 4965 of file kstd2.cc.

4966{
4968 assume(idIsInV(F));
4969 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4970 idSkipZeroes(RS); // is this even necessary?
4971 assume(idIsInV(RS));
4972 return(RS);
4973}
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2928
#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 2994 of file kstd2.cc.

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

Variable Documentation

◆ test_PosInL

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

Definition at line 83 of file kstd2.cc.

◆ test_PosInT

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

Definition at line 82 of file kstd2.cc.