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

Go to the source code of this file.

Macros

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

Functions

int kTestDivisibleByT0_Z (const kStrategy strat, const LObject *L)
 tests if T[0] divides the leading monomial of L, returns -1 if not
 
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
 
int kFindDivisibleByInS (const kStrategy strat, int *max_ind, LObject *L)
 return -1 if no divisor is found number of first divisor in S, otherwise
 
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 2626 of file kstd2.cc.

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

◆ bbaShift()

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

Definition at line 4591 of file kstd2.cc.

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

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

11560{
11561 printf("red: ");
11562 if (strat->red==redFirst) printf("redFirst\n");
11563 else if (strat->red==redHoney) printf("redHoney\n");
11564 else if (strat->red==redEcart) printf("redEcart\n");
11565 else if (strat->red==redHomog) printf("redHomog\n");
11566 else if (strat->red==redLazy) printf("redLazy\n");
11567 else if (strat->red==redLiftstd) printf("redLiftstd\n");
11568 else printf("%p\n",(void*)strat->red);
11569 printf("posInT: ");
11570 if (strat->posInT==posInT0) printf("posInT0\n");
11571 else if (strat->posInT==posInT1) printf("posInT1\n");
11572 else if (strat->posInT==posInT11) printf("posInT11\n");
11573 else if (strat->posInT==posInT110) printf("posInT110\n");
11574 else if (strat->posInT==posInT13) printf("posInT13\n");
11575 else if (strat->posInT==posInT15) printf("posInT15\n");
11576 else if (strat->posInT==posInT17) printf("posInT17\n");
11577 else if (strat->posInT==posInT17_c) printf("posInT17_c\n");
11578 else if (strat->posInT==posInT19) printf("posInT19\n");
11579 else if (strat->posInT==posInT2) printf("posInT2\n");
11580 #ifdef HAVE_RINGS
11581 else if (strat->posInT==posInT11Ring) printf("posInT11Ring\n");
11582 else if (strat->posInT==posInT110Ring) printf("posInT110Ring\n");
11583 else if (strat->posInT==posInT15Ring) printf("posInT15Ring\n");
11584 else if (strat->posInT==posInT17Ring) printf("posInT17Ring\n");
11585 else if (strat->posInT==posInT17_cRing) printf("posInT17_cRing\n");
11586 #endif
11587#ifdef HAVE_MORE_POS_IN_T
11588 else if (strat->posInT==posInT_EcartFDegpLength) printf("posInT_EcartFDegpLength\n");
11589 else if (strat->posInT==posInT_FDegpLength) printf("posInT_FDegpLength\n");
11590 else if (strat->posInT==posInT_pLength) printf("posInT_pLength\n");
11591#endif
11592 else if (strat->posInT==posInT_EcartpLength) printf("posInT_EcartpLength\n");
11593 else printf("%p\n",(void*)strat->posInT);
11594 printf("posInL: ");
11595 if (strat->posInL==posInL0) printf("posInL0\n");
11596 else if (strat->posInL==posInL10) printf("posInL10\n");
11597 else if (strat->posInL==posInL11) printf("posInL11\n");
11598 else if (strat->posInL==posInL110) printf("posInL110\n");
11599 else if (strat->posInL==posInL13) printf("posInL13\n");
11600 else if (strat->posInL==posInL15) printf("posInL15\n");
11601 else if (strat->posInL==posInL17) printf("posInL17\n");
11602 else if (strat->posInL==posInL17_c) printf("posInL17_c\n");
11603 #ifdef HAVE_RINGS
11604 else if (strat->posInL==posInL0) printf("posInL0Ring\n");
11605 else if (strat->posInL==posInL11Ring) printf("posInL11Ring\n");
11606 else if (strat->posInL==posInL11Ringls) printf("posInL11Ringls\n");
11607 else if (strat->posInL==posInL110Ring) printf("posInL110Ring\n");
11608 else if (strat->posInL==posInL15Ring) printf("posInL15Ring\n");
11609 else if (strat->posInL==posInL17Ring) printf("posInL17Ring\n");
11610 else if (strat->posInL==posInL17_cRing) printf("posInL17_cRing\n");
11611 #endif
11612 else if (strat->posInL==posInLSpecial) printf("posInLSpecial\n");
11613 else printf("%p\n",(void*)strat->posInL);
11614 printf("enterS: ");
11615 if (strat->enterS==enterSBba) printf("enterSBba\n");
11616 else if (strat->enterS==enterSMora) printf("enterSMora\n");
11617 else if (strat->enterS==enterSMoraNF) printf("enterSMoraNF\n");
11618 else printf("%p\n",(void*)strat->enterS);
11619 printf("initEcart: ");
11620 if (strat->initEcart==initEcartBBA) printf("initEcartBBA\n");
11621 else if (strat->initEcart==initEcartNormal) printf("initEcartNormal\n");
11622 else printf("%p\n",(void*)strat->initEcart);
11623 printf("initEcartPair: ");
11624 if (strat->initEcartPair==initEcartPairBba) printf("initEcartPairBba\n");
11625 else if (strat->initEcartPair==initEcartPairMora) printf("initEcartPairMora\n");
11626 else printf("%p\n",(void*)strat->initEcartPair);
11627 printf("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11628 strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11629 printf("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11630 strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11631 printf("chainCrit: ");
11632 if (strat->chainCrit==chainCritNormal) printf("chainCritNormal\n");
11633 else if (strat->chainCrit==chainCritOpt_1) printf("chainCritOpt_1\n");
11634 else printf("%p\n",(void*)strat->chainCrit);
11635 printf("posInLDependsOnLength=%d\n",
11636 strat->posInLDependsOnLength);
11637 printf("%s\n",showOption());
11638 printf("LDeg: ");
11639 if (currRing->pLDeg==pLDeg0) printf("pLDeg0");
11640 else if (currRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11641 else if (currRing->pLDeg==pLDegb) printf("pLDegb");
11642 else if (currRing->pLDeg==pLDeg1) printf("pLDeg1");
11643 else if (currRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11644 else if (currRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11645 else if (currRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11646 else if (currRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11647 else if (currRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11648 else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11649 else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11650 else if (currRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11651 else printf("? (%lx)", (long)currRing->pLDeg);
11652 printf(" / ");
11653 if (strat->tailRing->pLDeg==pLDeg0) printf("pLDeg0");
11654 else if (strat->tailRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11655 else if (strat->tailRing->pLDeg==pLDegb) printf("pLDegb");
11656 else if (strat->tailRing->pLDeg==pLDeg1) printf("pLDeg1");
11657 else if (strat->tailRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11658 else if (strat->tailRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11659 else if (strat->tailRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11660 else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11661 else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11662 else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11663 else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11664 else if (strat->tailRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11665 else printf("? (%lx)", (long)strat->tailRing->pLDeg);
11666 printf("\n");
11667 printf("currRing->pFDeg: ");
11668 if (currRing->pFDeg==p_Totaldegree) printf("p_Totaldegree");
11669 else if (currRing->pFDeg==p_WFirstTotalDegree) printf("pWFirstTotalDegree");
11670 else if (currRing->pFDeg==p_Deg) printf("p_Deg");
11671 else if (currRing->pFDeg==kHomModDeg) printf("kHomModDeg");
11672 else if (currRing->pFDeg==totaldegreeWecart) printf("totaldegreeWecart");
11673 else if (currRing->pFDeg==p_WTotaldegree) printf("p_WTotaldegree");
11674 else printf("? (%lx)", (long)currRing->pFDeg);
11675 printf("\n");
11676 printf(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11678 printf(" degBound: %d\n", Kstd1_deg);
11679
11680 if( ecartWeights != NULL )
11681 {
11682 printf("ecartWeights: ");
11683 for (int i = rVar(currRing); i > 0; i--)
11684 printf("%hd ", ecartWeights[i]);
11685 printf("\n");
11687 }
11688
11689#ifndef SING_NDEBUG
11691#endif
11692}
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:2074
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1114
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1869
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6338
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6453
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6092
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5305
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:5875
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition kutil.cc:4974
int posInT1(const TSet set, const int length, LObject &p)
Definition kutil.cc:4917
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5095
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:5171
int posInT0(const TSet, const int length, LObject &)
Definition kutil.cc:4906
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4946
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6181
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6134
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11525
int posInT13(const TSet set, const int length, LObject &p)
Definition kutil.cc:5142
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1325
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5642
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3457
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5011
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6216
int posInT17_c(const TSet set, const int length, LObject &p)
Definition kutil.cc:5413
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11434
int posInT15(const TSet set, const int length, LObject &p)
Definition kutil.cc:5209
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5598
VAR int Kstd1_deg
Definition kutil.cc:247
void initEcartNormal(TObject *h)
Definition kutil.cc:1303
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5945
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6293
int posInT110(const TSet set, const int length, LObject &p)
Definition kutil.cc:5052
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6252
int posInT19(const TSet set, const int length, LObject &p)
Definition kutil.cc:5541
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5264
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5367
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:5475
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6388
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11488
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3216
void initEcartBBA(TObject *h)
Definition kutil.cc:1311
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5832
char * showOption()
Definition misc_ip.cc:709
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1318
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8828
#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:4131
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
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:4077
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
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;
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
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;
330 if (L->p!=NULL)
331 {
332 const poly p=L->p;
333
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;
222 if (L->p!=NULL)
223 {
224 const ring r=currRing;
225 const poly p=L->p;
226 orest = pGetCoeff(p);
227
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
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 {
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 {
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 {
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);
632 for (int i = 1; i <= leadRing->N; i++)
633 {
634 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
635 }
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 4106 of file kstd2.cc.

4107{
4108 assume(!idIs0(q));
4109 assume(!(idIs0(F)&&(Q==NULL)));
4110// lazy_reduce flags: can be combined by |
4111//#define KSTD_NF_LAZY 1
4112 // do only a reduction of the leading term
4113//#define KSTD_NF_NONORM 4
4114 // only global: avoid normalization, return a multiply of NF
4115 poly p;
4116 int i;
4117 ideal res;
4118 int max_ind;
4119
4120 //if (idIs0(q))
4121 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4122 //if ((idIs0(F))&&(Q==NULL))
4123 // return idCopy(q); /*F=0*/
4124 //strat->ak = idRankFreeModule(F);
4125 /*- creating temp data structures------------------- -*/
4126 BITSET save1;
4129 initBuchMoraCrit(strat);
4130 strat->initEcart = initEcartBBA;
4131#ifdef HAVE_SHIFTBBA
4132 if (rIsLPRing(currRing))
4133 {
4134 strat->enterS = enterSBbaShift;
4135 }
4136 else
4137#endif
4138 {
4139 strat->enterS = enterSBba;
4140 }
4141 /*- set S -*/
4142 strat->sl = -1;
4143#ifndef NO_BUCKETS
4145#endif
4146 /*- init local data struct.---------------------------------------- -*/
4147 /*Shdl=*/initS(F,Q,strat);
4148 /*- compute------------------------------------------------------- -*/
4149 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4150 for (i=IDELEMS(q)-1; i>=0; i--)
4151 {
4152 if (q->m[i]!=NULL)
4153 {
4154 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4155 p = redNF(pCopy(q->m[i]),max_ind,
4157 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4158 {
4159 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4161 {
4162 p = redtailBba_NF(p,strat);
4163 }
4164 else
4165 {
4166 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4168 }
4169 }
4170 res->m[i]=p;
4171 }
4172 //else
4173 // res->m[i]=NULL;
4174 }
4175 /*- release temp data------------------------------- -*/
4176 assume(strat->L==NULL); /* strat->L unused */
4177 assume(strat->B==NULL); /* strat->B unused */
4178 omFree(strat->sevS);
4179 omFree(strat->ecartS);
4180 assume(strat->T==NULL);//omfree(strat->T);
4181 assume(strat->sevT==NULL);//omfree(strat->sevT);
4182 assume(strat->R==NULL);//omfree(strat->R);
4183 omfree(strat->S_2_R);
4184 omfree(strat->fromQ);
4185 idDelete(&strat->Shdl);
4187 if (TEST_OPT_PROT) PrintLn();
4188 return res;
4189}
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:2309
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7634
poly redtailBba_NF(poly p, kStrategy strat)
Definition kutil.cc:7397
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8928
#define omfree(addr)
#define omFree(addr)
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 3950 of file kstd2.cc.

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

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

◆ kNF2Bound() [2/2]

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

Definition at line 4032 of file kstd2.cc.

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

◆ ksReducePolyTailSig()

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

Definition at line 1295 of file kstd2.cc.

1296{
1297 BOOLEAN ret;
1298 number coef;
1299 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1301 Red->HeadNormalize();
1302 /*
1303 printf("------------------------\n");
1304 pWrite(Red->GetLmCurrRing());
1305 */
1307 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1308 else
1309 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1310 if (!ret)
1311 {
1312 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1313 {
1314 PR->Mult_nn(coef);
1315 // HANNES: mark for Normalize
1316 }
1317 n_Delete(&coef, currRing->cf);
1318 }
1319 return ret;
1320}
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];
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
162
163#if defined(PDEBUG) || defined(PDIV_DEBUG)
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)
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 4971 of file kstd2.cc.

4972{
4973 if (h->IsNull()) return 0;
4974
4975 int at, reddeg,d;
4976 int pass = 0;
4977 int j = 0;
4978
4979 if (! strat->homog)
4980 {
4981 d = h->GetpFDeg() + h->ecart;
4982 reddeg = strat->LazyDegree+d;
4983 }
4984 h->SetShortExpVector();
4985 loop
4986 {
4987 j = kFindDivisibleByInT(strat, h);
4988 if (j < 0)
4989 {
4990 h->SetDegStuffReturnLDeg(strat->LDegLast);
4991 return 1;
4992 }
4993
4995 strat->T[j].pNorm();
4996#ifdef KDEBUG
4997 if (TEST_OPT_DEBUG)
4998 {
4999 PrintS("reduce ");
5000 h->wrp();
5001 PrintS(" with ");
5002 strat->T[j].wrp();
5003 }
5004#endif
5005 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
5006
5007#ifdef KDEBUG
5008 if (TEST_OPT_DEBUG)
5009 {
5010 PrintS("\nto ");
5011 wrp(h->p);
5012 PrintLn();
5013 }
5014#endif
5015 if (h->IsNull())
5016 {
5017 kDeleteLcm(h);
5018 h->Clear();
5019 return 0;
5020 }
5021 h->SetShortExpVector();
5022
5023#if 0
5024 if ((strat->syzComp!=0) && !strat->honey)
5025 {
5026 if ((strat->syzComp>0) &&
5027 (h->Comp() > strat->syzComp))
5028 {
5029 assume(h->MinComp() > strat->syzComp);
5030#ifdef KDEBUG
5031 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
5032#endif
5033 if (strat->homog)
5034 h->SetDegStuffReturnLDeg(strat->LDegLast);
5035 return -2;
5036 }
5037 }
5038#endif
5039 if (!strat->homog)
5040 {
5041 if (!TEST_OPT_OLDSTD && strat->honey)
5042 {
5043 h->SetpFDeg();
5044 if (strat->T[j].ecart <= h->ecart)
5045 h->ecart = d - h->GetpFDeg();
5046 else
5047 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
5048
5049 d = h->GetpFDeg() + h->ecart;
5050 }
5051 else
5052 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
5053 /*- try to reduce the s-polynomial -*/
5054 pass++;
5055 /*
5056 *test whether the polynomial should go to the lazyset L
5057 *-if the degree jumps
5058 *-if the number of pre-defined reductions jumps
5059 */
5060 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
5061 && ((d >= reddeg) || (pass > strat->LazyPass)))
5062 {
5063 h->SetLmCurrRing();
5064 if (strat->posInLDependsOnLength)
5065 h->SetLength(strat->length_pLength);
5066 at = strat->posInL(strat->L,strat->Ll,h,strat);
5067 if (at <= strat->Ll)
5068 {
5069 //int dummy=strat->sl;
5070 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
5071 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
5072 if (kFindDivisibleByInT(strat, h) < 0)
5073 return 1;
5074 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
5075#ifdef KDEBUG
5076 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
5077#endif
5078 h->Clear();
5079 return -1;
5080 }
5081 }
5082 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
5083 {
5084 reddeg = d+1;
5085 Print(".%d",d);mflush();
5086 }
5087 }
5088 }
5089}
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 1114 of file kstd2.cc.

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

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

◆ redLazy()

int redLazy ( LObject * h,
kStrategy strat )

TEST_OPT_REDTHROUGH &&

Definition at line 1869 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2309 of file kstd2.cc.

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

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

◆ redRing()

int redRing ( LObject * h,
kStrategy strat )

Definition at line 951 of file kstd2.cc.

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

◆ redRing_S()

static int redRing_S ( LObject * h,
kStrategy strat )
static

Definition at line 1053 of file kstd2.cc.

1054{
1055 if (strat->sl<0) return 1;
1056 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
1057
1058 int j = 0;
1059 int pass = 0;
1060 // poly zeroPoly = NULL;
1061
1062 h->SetpFDeg();
1063 assume(h->pFDeg() == h->FDeg);
1064 int max_ind;
1065
1066 h->SetShortExpVector();
1067 loop
1068 {
1069 max_ind=strat->sl;
1070 j = kFindDivisibleByInS(strat, &max_ind, h);
1071 if (j < 0)
1072 {
1073 // over ZZ: cleanup coefficients by complete reduction with monomials
1074 postReduceByMon(h, strat);
1075 if(h->p == NULL)
1076 {
1077 h->Clear();
1078 return 0;
1079 }
1080 if(nIsZero(pGetCoeff(h->p))) return 2;
1081 max_ind=strat->sl;
1082 j = kFindDivisibleByInS(strat, &max_ind,h);
1083 if(j < 0)
1084 {
1085 if (h->GetLmTailRing() == NULL)
1086 {
1087 h->Clear();
1088 return 0;
1089 }
1090 return 1;
1091 }
1092 }
1093 //printf("\nFound one: ");pWrite(strat->T[j].p);
1094 //enterT(*h, strat);
1095 TObject tj(strat->S[j]);
1096 ksReducePoly(h, &tj, NULL, NULL, NULL, strat); // with debug output
1097 //printf("\nAfter small red: ");pWrite(h->p);
1098 if (h->GetLmTailRing() == NULL)
1099 {
1100 h->Clear();
1101 return 0;
1102 }
1103 h->SetShortExpVector();
1104 /*- try to reduce the s-polynomial -*/
1105 pass++;
1106 }
1107}
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 */
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:9086
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 j = 0;
847 int pass = 0;
848
849// TODO warum SetpFDeg notwendig?
850 h->SetpFDeg();
851 assume(h->pFDeg() == h->FDeg);
852 h->SetShortExpVector();
853 int max_ind=strat->sl;
854
855 loop
856 {
857 /* check if a reducer of the lead term exists */
858 max_ind=strat->sl;
859 j = kFindDivisibleByInS(strat,&max_ind, h);
860 if (j < 0)
861 {
862#if STDZ_EXCHANGE_DURING_REDUCTION
863 /* check if a reducer with the same lead monomial exists */
864 j = kFindSameLMInT_Z(strat, h);
865 if (j < 0)
866 {
867#endif
868 /* check if a reducer of the lead monomial exists, by the above
869 * check this is a real divisor of the lead monomial */
870 j = kFindDivisibleByInS_Z(strat, h);
871 if (j < 0)
872 {
873 // over ZZ: cleanup coefficients by complete reduction with monomials
875 postReduceByMon(h, strat);
876 if(h->p == NULL)
877 {
878 h->Clear();
879 return 0;
880 }
881 if(nIsZero(pGetCoeff(h->p))) return 2;
882 max_ind=strat->sl;
883 j = kFindDivisibleByInS(strat, &max_ind, h);
884 if(j < 0)
885 {
886 if (h->GetLmTailRing() == NULL)
887 {
888 h->Clear();
889 return 0;
890 }
891 return 1;
892 }
893 }
894 else
895 {
896 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
897 * => we try to cut down the lead coefficient at least */
898 /* first copy T[j] in order to multiply it with a coefficient later on */
900 TObject tj(pCopy(strat->S[j]));
901 /* compute division with remainder of lc(h) and lc(S[j]) */
902 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->S[j]),
903 &rest, currRing->cf);
904 /* set corresponding new lead coefficient already. we do not
905 * remove the lead term in ksReducePolyLC, but only apply
906 * a lead coefficient reduction */
907 tj.Mult_nn(mult);
908 ksReducePolyLC(h, &tj, NULL, &rest, strat);
909 tj.Delete();
910 tj.Clear();
911 }
912#if STDZ_EXCHANGE_DURING_REDUCTION
913 }
914 else
915 {
916 /* same lead monomial but lead coefficients do not divide each other:
917 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
918 LObject h2 = *h;
919 h2.Copy();
920 TObject tj(strat->S[j]);
921
922 ksReducePolyZ(h, &tj, NULL, NULL, strat);
923 ksReducePolyGCD(&h2, &tj, NULL, NULL, strat);
925 {
926 redtailBbaAlsoLC_Z_S(&h2, j, strat);
927 }
928 /* replace h2 for tj in L (already generated pairs with tj), S and T */
929 replaceInLAndSAndT(h2, j, strat);
930 }
931#endif
932 }
933 else
934 {
935 TObject tj(strat->S[j]);
936 ksReducePoly(h, &tj, NULL, NULL, NULL, strat);
937 }
938 /* printf("\nAfter small red: ");pWrite(h->p); */
939 if (h->GetLmCurrRing() == NULL)
940 {
941 h->Clear();
942 return 0;
943 }
944 h->SetShortExpVector();
945 h->SetpFDeg();
946 /*- try to reduce the s-polynomial -*/
947 pass++;
948 }
949}
static int kFindDivisibleByInS_Z(const kStrategy strat, LObject *L)
Definition kstd2.cc:276

◆ redSig()

int redSig ( LObject * h,
kStrategy strat )

Definition at line 1333 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject * h,
kStrategy strat )

Definition at line 1500 of file kstd2.cc.

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

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

4956{
4958 assume(idIsInV(F));
4959 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4960 idSkipZeroes(RS); // is this even necessary?
4961 assume(idIsInV(RS));
4962 return(RS);
4963}
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 2984 of file kstd2.cc.

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