My Project
Loading...
Searching...
No Matches
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 kFindDivisibleByInT_ecart (const kStrategy strat, const LObject *L, const int ecart)
 
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, bigintmat *hilb, kStrategy strat)
 
ideal sba (ideal F0, ideal Q, intvec *w, bigintmat *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, bigintmat *hilb)
 
ideal bbaShift (ideal F, ideal Q, intvec *w, bigintmat *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,
bigintmat * hilb,
kStrategy strat )

Definition at line 2622 of file kstd2.cc.

2623{
2624 int red_result = 1;
2625 int olddeg,reduc;
2626 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2627 BOOLEAN withT = FALSE;
2628 BITSET save;
2629 SI_SAVE_OPT1(save);
2630
2631 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2633 initBuchMoraPosRing(strat);
2634 else
2635 initBuchMoraPos(strat);
2636 initHilbCrit(F,Q,&hilb,strat);
2637 initBba(strat);
2638 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2639 /*Shdl=*/initBuchMora(F, Q,strat);
2640 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2641 reduc = olddeg = 0;
2642
2643#ifndef NO_BUCKETS
2645 strat->use_buckets = 1;
2646#endif
2647 // redtailBBa against T for inhomogeneous input
2648 if (!TEST_OPT_OLDSTD)
2649 withT = ! strat->homog;
2650
2651 // strat->posInT = posInT_pLength;
2652 #ifdef KDEBUG
2653 kTest_TS(strat);
2654 #endif
2655
2656#ifdef HAVE_TAIL_RING
2657 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2659#endif
2660 if (BVERBOSE(23))
2661 {
2662 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2663 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2664 kDebugPrint(strat);
2665 }
2666
2667
2668#ifdef KDEBUG
2669 //kDebugPrint(strat);
2670#endif
2671 /* compute------------------------------------------------------- */
2672 while (strat->Ll >= 0)
2673 {
2674 #ifdef KDEBUG
2675 if (TEST_OPT_DEBUG) messageSets(strat);
2676 #endif
2677 if (siCntrlc)
2678 {
2679 while (strat->Ll >= 0)
2680 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2681 strat->noClearS=TRUE;
2682 }
2684 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2685 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2686 {
2687 /*
2688 *stops computation if
2689 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2690 *a predefined number Kstd1_deg
2691 */
2692 while ((strat->Ll >= 0)
2693 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2694 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2695 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2696 )
2697 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2698 if (strat->Ll<0) break;
2699 else strat->noClearS=TRUE;
2700 }
2701 if (strat->Ll== 0) strat->interpt=TRUE;
2702 /* picks the last element from the lazyset L */
2703 strat->P = strat->L[strat->Ll];
2704 strat->Ll--;
2705
2706 if (pNext(strat->P.p) == strat->tail)
2707 {
2708 // deletes the short spoly
2710 pLmDelete(strat->P.p);
2711 else
2712 pLmFree(strat->P.p);
2713 strat->P.p = NULL;
2714 poly m1 = NULL, m2 = NULL;
2715
2716 // check that spoly creation is ok
2717 while (strat->tailRing != currRing &&
2718 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2719 {
2720 assume(m1 == NULL && m2 == NULL);
2721 // if not, change to a ring where exponents are at least
2722 // large enough
2723 if (!kStratChangeTailRing(strat))
2724 {
2725 WerrorS("OVERFLOW...");
2726 break;
2727 }
2728 }
2729 // create the real one
2730 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2731 strat->tailRing, m1, m2, strat->R);
2732 }
2733 else if (strat->P.p1 == NULL)
2734 {
2735 if (strat->minim > 0)
2736 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2737 // for input polys, prepare reduction
2738 strat->P.PrepareRed(strat->use_buckets);
2739 }
2740
2741 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2742 {
2743 red_result = 0;
2744 }
2745 else
2746 {
2747 if (TEST_OPT_PROT)
2748 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2749 &olddeg,&reduc,strat, red_result);
2750
2751 /* reduction of the element chosen from L */
2752 red_result = strat->red(&strat->P,strat);
2753 if (errorreported) break;
2754 }
2755
2756 if (strat->overflow)
2757 {
2758 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2759 }
2760
2761 // reduction to non-zero new poly
2762 if (red_result == 1)
2763 {
2764 // get the polynomial (canonicalize bucket, make sure P.p is set)
2765 strat->P.GetP(strat->lmBin);
2766 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2767 // but now, for entering S, T, we reset it
2768 // in the inhomogeneous case: FDeg == pFDeg
2769 if (strat->homog) strat->initEcart(&(strat->P));
2770
2771 /* statistic */
2772 if (TEST_OPT_PROT) PrintS("s");
2773
2774 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2775
2776 // reduce the tail and normalize poly
2777 // in the ring case we cannot expect LC(f) = 1,
2778 strat->redTailChange=FALSE;
2779
2780 /* if we are computing over Z we always want to try and cut down
2781 * the coefficients in the tail terms */
2783 {
2784 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2785 }
2786
2788 {
2789 strat->P.pCleardenom();
2791 {
2792 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2793 strat->P.pCleardenom();
2794 if (strat->redTailChange) { strat->P.t_p=NULL; }
2795 }
2796 }
2797 else
2798 {
2799 strat->P.pNorm();
2801 {
2802 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2803 if (strat->redTailChange) { strat->P.t_p=NULL; }
2804 }
2805 }
2806
2807#ifdef KDEBUG
2808 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2809#endif /* KDEBUG */
2810
2811 // min_std stuff
2812 if ((strat->P.p1==NULL) && (strat->minim>0))
2813 {
2814 if (strat->minim==1)
2815 {
2816 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2817 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2818 }
2819 else
2820 {
2821 strat->M->m[minimcnt]=strat->P.p2;
2822 strat->P.p2=NULL;
2823 }
2824 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2825 pNext(strat->M->m[minimcnt])
2826 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2827 strat->tailRing, currRing,
2828 currRing->PolyBin);
2829 minimcnt++;
2830 }
2831
2832 // enter into S, L, and T
2833 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2834 {
2835 strat->P.SetShortExpVector();
2836 enterT(strat->P, strat);
2838 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2839 else
2840 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2841 // posInS only depends on the leading term
2842 strat->enterS(strat->P, pos, strat, strat->tl);
2843#if 0
2844 int pl=pLength(strat->P.p);
2845 if (pl==1)
2846 {
2847 //if (TEST_OPT_PROT)
2848 //PrintS("<1>");
2849 }
2850 else if (pl==2)
2851 {
2852 //if (TEST_OPT_PROT)
2853 //PrintS("<2>");
2854 }
2855#endif
2856 }
2857 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2858// Print("[%d]",hilbeledeg);
2859 kDeleteLcm(&strat->P);
2860 if (strat->s_poly!=NULL)
2861 {
2862 // the only valid entries are: strat->P.p,
2863 // strat->tailRing (read-only, keep it)
2864 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2865 if (strat->s_poly(strat))
2866 {
2867 // we are called AFTER enterS, i.e. if we change P
2868 // we have to add it also to S/T
2869 // and add pairs
2870 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2871 enterT(strat->P, strat);
2873 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2874 else
2875 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2876 strat->enterS(strat->P, pos, strat, strat->tl);
2877 }
2878 }
2879 }
2880 else if (strat->P.p1 == NULL && strat->minim > 0)
2881 {
2882 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2883 }
2884
2885#ifdef KDEBUG
2886 strat->P.Init();
2887 kTest_TS(strat);
2888#endif /* KDEBUG */
2889 }
2890#ifdef KDEBUG
2891 if (TEST_OPT_DEBUG) messageSets(strat);
2892#endif /* KDEBUG */
2893
2894 if (TEST_OPT_SB_1)
2895 {
2897 {
2898 int k=1;
2899 int j;
2900 while(k<=strat->sl)
2901 {
2902 j=0;
2903 loop
2904 {
2905 if (j>=k) break;
2906 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2907 j++;
2908 }
2909 k++;
2910 }
2911 }
2912 }
2913 /* complete reduction of the standard basis--------- */
2914 if (TEST_OPT_REDSB)
2915 {
2916 completeReduce(strat);
2917 if (strat->completeReduce_retry)
2918 {
2919 // completeReduce needed larger exponents, retry
2920 // to reduce with S (instead of T)
2921 // and in currRing (instead of strat->tailRing)
2922#ifdef HAVE_TAIL_RING
2923 if(currRing->bitmask>strat->tailRing->bitmask)
2924 {
2926 cleanT(strat);strat->tailRing=currRing;
2927 int i;
2928 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2929 completeReduce(strat);
2930 }
2931 if (strat->completeReduce_retry)
2932#endif
2933 Werror("exponent bound is %ld",currRing->bitmask);
2934 }
2935 }
2936 else if (TEST_OPT_PROT) PrintLn();
2937 /* release temp data-------------------------------- */
2938 exitBuchMora(strat);
2939 /* postprocessing for GB over ZZ --------------------*/
2940 if (!errorreported)
2941 {
2943 {
2944 for(int i = 0;i<=strat->sl;i++)
2945 {
2946 if(!nGreaterZero(pGetCoeff(strat->S[i])))
2947 {
2948 strat->S[i] = pNeg(strat->S[i]);
2949 }
2950 }
2951 finalReduceByMon(strat);
2952 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2953 {
2954 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2955 {
2956 strat->S[i] = pNeg(strat->Shdl->m[i]);
2957 }
2958 }
2959 }
2960 //else if (rField_is_Ring(currRing))
2961 // finalReduceByMon(strat);
2962 }
2963// if (TEST_OPT_WEIGHTM)
2964// {
2965// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2966// if (ecartWeights)
2967// {
2968// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2969// ecartWeights=NULL;
2970// }
2971// }
2972 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2973 SI_RESTORE_OPT1(save);
2974 /* postprocessing for GB over Q-rings ------------------*/
2975 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2976
2977 idTest(strat->Shdl);
2978
2979 return (strat->Shdl);
2980}
#define BITSET
Definition auxiliary.h:85
int BOOLEAN
Definition auxiliary.h:88
#define TRUE
Definition auxiliary.h:101
#define FALSE
Definition auxiliary.h:97
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
int syzComp
Definition kutil.h:355
int * S_2_R
Definition kutil.h:343
ring tailRing
Definition kutil.h:344
int Ll
Definition kutil.h:352
omBin lmBin
Definition kutil.h:345
char honey
Definition kutil.h:376
polyset S
Definition kutil.h:307
int minim
Definition kutil.h:358
TObject ** R
Definition kutil.h:341
ideal M
Definition kutil.h:306
int tl
Definition kutil.h:351
poly tail
Definition kutil.h:335
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:285
ideal Shdl
Definition kutil.h:304
pShallowCopyDeleteProc p_shallow_copy_delete
Definition kutil.h:339
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:287
char use_buckets
Definition kutil.h:382
char interpt
Definition kutil.h:370
char redTailChange
Definition kutil.h:398
char completeReduce_retry
Definition kutil.h:402
void(* initEcart)(TObject *L)
Definition kutil.h:281
LObject P
Definition kutil.h:303
char noClearS
Definition kutil.h:401
char overflow
Definition kutil.h:403
LSet L
Definition kutil.h:328
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:282
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:279
int sl
Definition kutil.h:349
unsigned long * sevS
Definition kutil.h:323
char homog
Definition kutil.h:371
s_poly_proc_t s_poly
Definition kutil.h:301
const CanonicalForm & w
Definition facAbsFact.cc:51
int j
Definition facHensel.cc:110
VAR short errorreported
Definition feFopen.cc:23
void WerrorS(const char *s)
Definition feFopen.cc:24
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
#define idTest(id)
Definition ideals.h:47
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition kInline.h:1209
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition kInline.h:1232
void khCheck(ideal Q, intvec *w, bigintmat *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:1203
void initBba(kStrategy strat)
Definition kstd1.cc:1681
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:70
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:11505
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:7467
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9751
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9143
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1074
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4494
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:7144
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9580
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10961
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9838
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4670
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10481
void cleanT(kStrategy strat)
Definition kutil.cc:557
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10081
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4464
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1215
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11058
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9435
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10287
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9665
void messageSets(kStrategy strat)
Definition kutil.cc:7540
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7508
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition kutil.cc:10869
void initHilbCrit(ideal, ideal, bigintmat **hilb, kStrategy strat)
Definition kutil.cc:9417
static void kDeleteLcm(LObject *P)
Definition kutil.h:870
#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:131
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
#define BVERBOSE(a)
Definition options.h:35
#define TEST_OPT_REDTAIL
Definition options.h:118
#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:125
#define TEST_OPT_REDSB
Definition options.h:106
#define TEST_OPT_DEGBOUND
Definition options.h:115
#define TEST_OPT_SB_1
Definition options.h:121
#define TEST_OPT_PROT
Definition options.h:105
#define TEST_OPT_DEBUG
Definition options.h:110
#define TEST_OPT_CONTENTSB
Definition options.h:129
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
static int pLength(poly a)
Definition p_polys.h:190
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:848
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:199
#define pGetComp(p)
Component.
Definition polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:77
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:71
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:515
static BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:769
#define rField_is_Ring(R)
Definition ring.h:491
ideal idInit(int idsize, int rank)
initialise an ideal / module
#define IDELEMS(i)
#define Q
Definition sirandom.c:26
#define loop
Definition structs.h:71

◆ bbaShift()

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

Definition at line 4594 of file kstd2.cc.

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

◆ f5c()

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

Definition at line 4282 of file kstd2.cc.

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

◆ ind_fact_2()

static long ind_fact_2 ( long arg)
static

Definition at line 600 of file kstd2.cc.

601{
602 if (arg <= 0) return 0;
603 long ind = 0;
604 if (arg%2 == 1) { arg--; }
605 while (arg > 0)
606 {
607 ind += SI_LOG2_LONG(arg);
608 arg = arg - 2;
609 }
610 return ind;
611}
static int SI_LOG2_LONG(long v)
Definition si_log2.h:22

◆ kDebugPrint()

void kDebugPrint ( kStrategy strat)

Definition at line 11505 of file kutil.cc.

11506{
11507 printf("red: ");
11508 if (strat->red==redFirst) printf("redFirst\n");
11509 else if (strat->red==redHoney) printf("redHoney\n");
11510 else if (strat->red==redEcart) printf("redEcart\n");
11511 else if (strat->red==redHomog) printf("redHomog\n");
11512 else if (strat->red==redLazy) printf("redLazy\n");
11513 else if (strat->red==redLiftstd) printf("redLiftstd\n");
11514 else printf("%p\n",(void*)strat->red);
11515 printf("posInT: ");
11516 if (strat->posInT==posInT0) printf("posInT0\n");
11517 else if (strat->posInT==posInT1) printf("posInT1\n");
11518 else if (strat->posInT==posInT11) printf("posInT11\n");
11519 else if (strat->posInT==posInT110) printf("posInT110\n");
11520 else if (strat->posInT==posInT13) printf("posInT13\n");
11521 else if (strat->posInT==posInT15) printf("posInT15\n");
11522 else if (strat->posInT==posInT17) printf("posInT17\n");
11523 else if (strat->posInT==posInT17_c) printf("posInT17_c\n");
11524 else if (strat->posInT==posInT19) printf("posInT19\n");
11525 else if (strat->posInT==posInT2) printf("posInT2\n");
11526 else if (strat->posInT==posInT11Ring) printf("posInT11Ring\n");
11527 else if (strat->posInT==posInT110Ring) printf("posInT110Ring\n");
11528 else if (strat->posInT==posInT15Ring) printf("posInT15Ring\n");
11529 else if (strat->posInT==posInT17Ring) printf("posInT17Ring\n");
11530 else if (strat->posInT==posInT17_cRing) printf("posInT17_cRing\n");
11531#ifdef HAVE_MORE_POS_IN_T
11532 else if (strat->posInT==posInT_EcartFDegpLength) printf("posInT_EcartFDegpLength\n");
11533 else if (strat->posInT==posInT_FDegpLength) printf("posInT_FDegpLength\n");
11534 else if (strat->posInT==posInT_pLength) printf("posInT_pLength\n");
11535#endif
11536 else if (strat->posInT==posInT_EcartpLength) printf("posInT_EcartpLength\n");
11537 else printf("%p\n",(void*)strat->posInT);
11538 printf("posInL: ");
11539 if (strat->posInL==posInL0) printf("posInL0\n");
11540 else if (strat->posInL==posInL10) printf("posInL10\n");
11541 else if (strat->posInL==posInL11) printf("posInL11\n");
11542 else if (strat->posInL==posInL110) printf("posInL110\n");
11543 else if (strat->posInL==posInL13) printf("posInL13\n");
11544 else if (strat->posInL==posInL15) printf("posInL15\n");
11545 else if (strat->posInL==posInL17) printf("posInL17\n");
11546 else if (strat->posInL==posInL17_c) printf("posInL17_c\n");
11547 else if (strat->posInL==posInL0) printf("posInL0Ring\n");
11548 else if (strat->posInL==posInL11Ring) printf("posInL11Ring\n");
11549 else if (strat->posInL==posInL11Ringls) printf("posInL11Ringls\n");
11550 else if (strat->posInL==posInL110Ring) printf("posInL110Ring\n");
11551 else if (strat->posInL==posInL15Ring) printf("posInL15Ring\n");
11552 else if (strat->posInL==posInL17Ring) printf("posInL17Ring\n");
11553 else if (strat->posInL==posInL17_cRing) printf("posInL17_cRing\n");
11554 else if (strat->posInL==posInLSpecial) printf("posInLSpecial\n");
11555 else printf("%p\n",(void*)strat->posInL);
11556 printf("enterS: ");
11557 if (strat->enterS==enterSBba) printf("enterSBba\n");
11558 else if (strat->enterS==enterSMora) printf("enterSMora\n");
11559 else if (strat->enterS==enterSMoraNF) printf("enterSMoraNF\n");
11560 else printf("%p\n",(void*)strat->enterS);
11561 printf("initEcart: ");
11562 if (strat->initEcart==initEcartBBA) printf("initEcartBBA\n");
11563 else if (strat->initEcart==initEcartNormal) printf("initEcartNormal\n");
11564 else printf("%p\n",(void*)strat->initEcart);
11565 printf("initEcartPair: ");
11566 if (strat->initEcartPair==initEcartPairBba) printf("initEcartPairBba\n");
11567 else if (strat->initEcartPair==initEcartPairMora) printf("initEcartPairMora\n");
11568 else printf("%p\n",(void*)strat->initEcartPair);
11569 printf("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11570 strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11571 printf("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11572 strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11573 printf("chainCrit: ");
11574 if (strat->chainCrit==chainCritNormal) printf("chainCritNormal\n");
11575 else if (strat->chainCrit==chainCritOpt_1) printf("chainCritOpt_1\n");
11576 else printf("%p\n",(void*)strat->chainCrit);
11577 printf("posInLDependsOnLength=%d\n",
11578 strat->posInLDependsOnLength);
11579 printf("%s\n",showOption());
11580 printf("LDeg: ");
11581 if (currRing->pLDeg==pLDeg0) printf("pLDeg0");
11582 else if (currRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11583 else if (currRing->pLDeg==pLDegb) printf("pLDegb");
11584 else if (currRing->pLDeg==pLDeg1) printf("pLDeg1");
11585 else if (currRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11586 else if (currRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11587 else if (currRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11588 else if (currRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11589 else if (currRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11590 else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11591 else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11592 else if (currRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11593 else printf("? (%lx)", (long)currRing->pLDeg);
11594 printf(" / ");
11595 if (strat->tailRing->pLDeg==pLDeg0) printf("pLDeg0");
11596 else if (strat->tailRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11597 else if (strat->tailRing->pLDeg==pLDegb) printf("pLDegb");
11598 else if (strat->tailRing->pLDeg==pLDeg1) printf("pLDeg1");
11599 else if (strat->tailRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11600 else if (strat->tailRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11601 else if (strat->tailRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11602 else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11603 else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11604 else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11605 else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11606 else if (strat->tailRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11607 else printf("? (%lx)", (long)strat->tailRing->pLDeg);
11608 printf("\n");
11609 printf("currRing->pFDeg: ");
11610 if (currRing->pFDeg==p_Totaldegree) printf("p_Totaldegree");
11611 else if (currRing->pFDeg==p_WFirstTotalDegree) printf("pWFirstTotalDegree");
11612 else if (currRing->pFDeg==p_Deg) printf("p_Deg");
11613 else if (currRing->pFDeg==kHomModDeg) printf("kHomModDeg");
11614 else if (currRing->pFDeg==totaldegreeWecart) printf("totaldegreeWecart");
11615 else if (currRing->pFDeg==p_WTotaldegree) printf("p_WTotaldegree");
11616 else printf("? (%lx)", (long)currRing->pFDeg);
11617 printf("\n");
11618 printf(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11620 printf(" degBound: %d\n", Kstd1_deg);
11621
11622 if( ecartWeights != NULL )
11623 {
11624 printf("ecartWeights: ");
11625 for (int i = rVar(currRing); i > 0; i--)
11626 printf("%hd ", ecartWeights[i]);
11627 printf("\n");
11629 }
11630
11631#ifndef SING_NDEBUG
11633#endif
11634}
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:292
char noTailReduction
Definition kutil.h:377
int ak
Definition kutil.h:354
char sugarCrit
Definition kutil.h:376
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:288
char Gebauer
Definition kutil.h:377
int LazyPass
Definition kutil.h:354
int LazyDegree
Definition kutil.h:354
char posInLDependsOnLength
Definition kutil.h:388
int redLiftstd(LObject *h, kStrategy strat)
Definition kLiftstd.cc:167
long kHomModDeg(poly p, const ring r)
Definition kstd1.cc:2417
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:794
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:168
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1673
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition kstd1.cc:1360
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1620
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2114
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1154
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1909
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6303
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6416
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6062
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5285
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5848
int posInT11(const TSet set, const int length, LObject &p)
Definition kutil.cc:4960
int posInT1(const TSet set, const int length, LObject &p)
Definition kutil.cc:4903
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5078
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:5153
int posInT0(const TSet, const int length, LObject &)
Definition kutil.cc:4892
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4932
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6149
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6103
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11471
int posInT13(const TSet set, const int length, LObject &p)
Definition kutil.cc:5124
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1322
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5618
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3452
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:4996
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6184
int posInT17_c(const TSet set, const int length, LObject &p)
Definition kutil.cc:5391
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11380
int posInT15(const TSet set, const int length, LObject &p)
Definition kutil.cc:5191
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5574
void initEcartNormal(TObject *h)
Definition kutil.cc:1300
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5916
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6259
int posInT110(const TSet set, const int length, LObject &p)
Definition kutil.cc:5036
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6219
int posInT19(const TSet set, const int length, LObject &p)
Definition kutil.cc:5517
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5245
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5346
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition kutil.cc:5452
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6352
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11434
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3211
void initEcartBBA(TObject *h)
Definition kutil.cc:1308
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5806
char * showOption()
Definition misc_ip.cc:711
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1315
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8794
#define TEST_OPT_WEIGHTM
Definition options.h:123
long pLDegb(poly p, int *l, const ring r)
Definition p_polys.cc:812
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition p_polys.cc:976
long p_WFirstTotalDegree(poly p, const ring r)
Definition p_polys.cc:595
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition p_polys.cc:1039
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition p_polys.cc:1069
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition p_polys.cc:942
long pLDeg1(poly p, int *l, const ring r)
Definition p_polys.cc:842
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition p_polys.cc:911
long p_WTotaldegree(poly p, const ring r)
Definition p_polys.cc:612
long pLDeg1c(poly p, int *l, const ring r)
Definition p_polys.cc:878
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition p_polys.cc:1006
long pLDeg0c(poly p, int *l, const ring r)
Definition p_polys.cc:771
long pLDeg0(poly p, int *l, const ring r)
Definition p_polys.cc:740
long p_Deg(poly a, const ring r)
Definition p_polys.cc:586
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1523
void rDebugPrint(const ring r)
Definition ring.cc:4214
static int rGetCurrSyzLimit(const ring r)
Definition ring.h:729
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition ring.h:726
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:598
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 468 of file kstd2.cc.

469{
470 unsigned long not_sev = ~L->sev;
471 poly p = L->GetLmCurrRing();
472 int j = 0;
473
474 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
475
477#if 1
478 int ende;
479 if (is_Ring
480 || (strat->ak>0)
481 || currRing->pLexOrder)
482 ende=strat->sl;
483 else
484 {
485 ende=posInS(strat,*max_ind,p,0)+1;
486 if (ende>(*max_ind)) ende=(*max_ind);
487 }
488#else
489 int ende=strat->sl;
490#endif
491 if(is_Ring)
492 {
493 loop
494 {
495 if (j > ende) return -1;
496#if defined(PDEBUG) || defined(PDIV_DEBUG)
497 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
498 p, not_sev, currRing))
499#else
500 if ( !(strat->sevS[j] & not_sev) &&
501 p_LmDivisibleBy(strat->S[j], p, currRing))
502#endif
503 {
504 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
505 return j;
506 }
507 j++;
508 }
509 }
510 else
511 {
512 loop
513 {
514 if (j > ende) return -1;
515#if defined(PDEBUG) || defined(PDIV_DEBUG)
516 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
517 p, not_sev, currRing))
518#else
519 if ( !(strat->sevS[j] & not_sev) &&
520 p_LmDivisibleBy(strat->S[j], p, currRing))
521#endif
522 {
523 return j;
524 }
525 j++;
526 }
527 }
528}
int p
Definition cfModGcd.cc:4086
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:748
#define pAssume(cond)
Definition monomials.h:90
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition p_polys.cc:4889
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition p_polys.h:1926
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1907

◆ kFindDivisibleByInS_noCF()

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

Definition at line 531 of file kstd2.cc.

532{
533 unsigned long not_sev = ~L->sev;
534 poly p = L->GetLmCurrRing();
535 int j = 0;
536
537 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
538
540#if 1
541 int ende;
542 if (is_Ring
543 || (strat->ak>0)
544 || currRing->pLexOrder)
545 ende=strat->sl;
546 else
547 {
548 ende=posInS(strat,*max_ind,p,0)+1;
549 if (ende>(*max_ind)) ende=(*max_ind);
550 }
551#else
552 int ende=strat->sl;
553#endif
554 loop
555 {
556 if (j > ende) return -1;
557#if defined(PDEBUG) || defined(PDIV_DEBUG)
558 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
559 p, not_sev, currRing))
560#else
561 if ( !(strat->sevS[j] & not_sev) &&
562 p_LmDivisibleBy(strat->S[j], p, currRing))
563#endif
564 {
565 return j;
566 }
567 j++;
568 }
569}

◆ kFindDivisibleByInS_Z()

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

Definition at line 276 of file kstd2.cc.

277{
278 unsigned long not_sev = ~L->sev;
279 int j = 0;
280 int o = -1;
281
282 const polyset S=strat->S;
283 const unsigned long* sevS=strat->sevS;
284 number rest, orest, mult;
285 L->GetP();
286 if (L->p!=NULL)
287 {
288 const ring r=currRing;
289 const poly p=L->p;
290 orest = pGetCoeff(p);
291
292 pAssume(~not_sev == p_GetShortExpVector(p, r));
293
294 loop
295 {
296 if (j > strat->sl) return o;
297#if defined(PDEBUG) || defined(PDIV_DEBUG)
298 if (p_LmShortDivisibleBy(S[j], sevS[j],p, not_sev, r))
299#else
300 if (!(sevS[j] & not_sev) && p_LmDivisibleBy(S[j], p, r))
301#endif
302 {
303 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(S[j]), &rest, r->cf);
304 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
305 {
306 o = j;
307 orest = rest;
308 }
309 }
310 j++;
311 }
312 }
313 else
314 {
315 return -1;
316 }
317}
static FORCE_INLINE number n_EucNorm(number a, const coeffs r)
Definition coeffs.h:676
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition coeffs.h:682
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:515
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:468
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:260

◆ kFindDivisibleByInT()

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

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

Definition at line 321 of file kstd2.cc.

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

◆ kFindDivisibleByInT_ecart()

int kFindDivisibleByInT_ecart ( const kStrategy strat,
const LObject * L,
const int ecart )

Definition at line 420 of file kstd2.cc.

421{
422 if (TEST_OPT_LENGTH)
423 {
424 int r=-1; // found, but bad ecart
425 int j=-2; // found, good ecart
426 int jj=-1; // current search
427 loop
428 {
429 jj=kFindDivisibleByInT(strat,L,jj+1);
430 if (jj== -1)
431 {
432 if (j<0) return r; // nothing with good ecart
433 else return j; // end of search, return best found
434 }
435 else if (r<0) r=jj; // save bad ecart found
436 if (strat->T[jj].ecart<=ecart) // good enough
437 {
438 if (strat->T[jj].pLength<=0)
439 strat->T[jj].pLength=strat->T[jj].GetpLength();
440 if (j== -2) j=jj; // first found
441 else if (strat->T[j].pLength > strat->T[jj].pLength) // jj better then j
442 j=jj;
443 if (strat->T[j].pLength<=2) return j; // length already minimal
444 }
445 }
446 }
447 else
448 {
449 int r=-1;
450 int jj=-1;
451 loop
452 {
453 jj=kFindDivisibleByInT(strat,L,jj+1);
454 if (jj== -1)
455 {
456 return r; // nothing found
457 }
458 else if (r== -1) r=jj;
459 if (strat->T[jj].ecart<=ecart) // good enough
460 {
461 return jj;
462 }
463 }
464 }
465}
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_LENGTH
Definition options.h:132

◆ kFindDivisibleByInT_Z()

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

Definition at line 213 of file kstd2.cc.

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

◆ kFindNextDivisibleByInS()

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

Definition at line 571 of file kstd2.cc.

572{
573 unsigned long not_sev = ~L->sev;
574 poly p = L->GetLmCurrRing();
575 int j = start;
576
577 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
578#if 1
579 int ende=max_ind;
580#else
581 int ende=strat->sl;
582#endif
583 loop
584 {
585 if (j > ende) return -1;
586#if defined(PDEBUG) || defined(PDIV_DEBUG)
587 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
588 p, not_sev, currRing))
589#else
590 if ( !(strat->sevS[j] & not_sev) &&
591 p_LmDivisibleBy(strat->S[j], p, currRing))
592#endif
593 {
594 return j;
595 }
596 j++;
597 }
598}

◆ kFindZeroPoly()

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

Definition at line 613 of file kstd2.cc.

614{
615 // m = currRing->ch
616
617 if (input_p == NULL) return NULL;
618
619 poly p = input_p;
620 poly zeroPoly = NULL;
621 unsigned long a = (unsigned long) pGetCoeff(p);
622
623 int k_ind2 = 0;
624 int a_ind2 = SI_LOG2_LONG(a);
625
626 // unsigned long k = 1;
627 // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
628 for (int i = 1; i <= leadRing->N; i++)
629 {
630 k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
631 }
632
633 a = (unsigned long) pGetCoeff(p);
634
635 number tmp1;
636 poly tmp2, tmp3;
637 poly lead_mult = p_ISet(1, tailRing);
638 if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
639 {
640 int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
641 int s_exp;
642 zeroPoly = p_ISet(a, tailRing);
643 for (int i = 1; i <= leadRing->N; i++)
644 {
645 s_exp = p_GetExp(p, i,leadRing);
646 if (s_exp % 2 != 0)
647 {
648 s_exp = s_exp - 1;
649 }
650 while ( (0 < SI_LOG2_LONG(s_exp)) && (SI_LOG2_LONG(s_exp) <= too_much) )
651 {
652 too_much = too_much - SI_LOG2_LONG(s_exp);
653 s_exp = s_exp - 2;
654 }
655 p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
656 for (int j = 1; j <= s_exp; j++)
657 {
658 tmp1 = nInit(j);
659 tmp2 = p_ISet(1, tailRing);
660 p_SetExp(tmp2, i, 1, tailRing);
661 p_Setm(tmp2, tailRing);
662 if (nIsZero(tmp1))
663 { // should nowbe obsolet, test ! TODO OLIVER
664 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
665 }
666 else
667 {
668 tmp3 = p_NSet(nCopy(tmp1), tailRing);
669 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
670 }
671 }
672 }
673 p_Setm(lead_mult, tailRing);
674 zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
675 tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
676 for (int i = 1; i <= leadRing->N; i++)
677 {
678 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
679 }
680 p_Setm(tmp2, leadRing);
681 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
682 pNext(tmp2) = zeroPoly;
683 return tmp2;
684 }
685/* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
686 if (1 == 0 && alpha_k <= a)
687 { // Temporarily disabled, reducing coefficients not compatible with std TODO Oliver
688 zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
689 for (int i = 1; i <= leadRing->N; i++)
690 {
691 for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
692 {
693 tmp1 = nInit(j);
694 tmp2 = p_ISet(1, tailRing);
695 p_SetExp(tmp2, i, 1, tailRing);
696 p_Setm(tmp2, tailRing);
697 if (nIsZero(tmp1))
698 {
699 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
700 }
701 else
702 {
703 tmp3 = p_ISet((unsigned long) tmp1, tailRing);
704 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
705 }
706 }
707 }
708 tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
709 for (int i = 1; i <= leadRing->N; i++)
710 {
711 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
712 }
713 p_Setm(tmp2, leadRing);
714 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
715 pNext(tmp2) = zeroPoly;
716 return tmp2;
717 } */
718 return NULL;
719}
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition coeffs.h:448
CFList tmp1
Definition facFqBivar.cc:75
CFList tmp2
Definition facFqBivar.cc:75
static long ind_fact_2(long arg)
Definition kstd2.cc:600
#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:1298
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition p_polys.cc:1474
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
static poly p_Mult_q(poly p, poly q, const ring r)
Definition p_polys.h:1120
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:490
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
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:471
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1053
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition p_polys.h:757
#define pSetExp(p, i, v)
Definition polys.h:43

◆ kNF2() [1/2]

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

Definition at line 4107 of file kstd2.cc.

4108{
4109 assume(!idIs0(q));
4110 assume(!(idIs0(F)&&(Q==NULL)));
4111// lazy_reduce flags: can be combined by |
4112//#define KSTD_NF_LAZY 1
4113 // do only a reduction of the leading term
4114//#define KSTD_NF_NONORM 4
4115 // only global: avoid normalization, return a multiply of NF
4116 poly p;
4117 int i;
4118 ideal res;
4119 int max_ind;
4120
4121 //if (idIs0(q))
4122 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4123 //if ((idIs0(F))&&(Q==NULL))
4124 // return idCopy(q); /*F=0*/
4125 //strat->ak = idRankFreeModule(F);
4126 /*- creating temp data structures------------------- -*/
4127 BITSET save1;
4128 SI_SAVE_OPT1(save1);
4130 initBuchMoraCrit(strat);
4131 strat->initEcart = initEcartBBA;
4132#ifdef HAVE_SHIFTBBA
4133 if (rIsLPRing(currRing))
4134 {
4135 strat->enterS = enterSBbaShift;
4136 }
4137 else
4138#endif
4139 {
4140 strat->enterS = enterSBba;
4141 }
4142 /*- set S -*/
4143 strat->sl = -1;
4144#ifndef NO_BUCKETS
4146#endif
4147 /*- init local data struct.---------------------------------------- -*/
4148 /*Shdl=*/initS(F,Q,strat);
4149 /*- compute------------------------------------------------------- -*/
4150 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4151 for (i=IDELEMS(q)-1; i>=0; i--)
4152 {
4153 if (q->m[i]!=NULL)
4154 {
4155 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4156 p = redNF(pCopy(q->m[i]),max_ind,
4157 (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4158 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4159 {
4160 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4162 {
4163 p = redtailBba_NF(p,strat);
4164 }
4165 else
4166 {
4168 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4169 }
4170 }
4171 res->m[i]=p;
4172 }
4173 //else
4174 // res->m[i]=NULL;
4175 }
4176 /*- release temp data------------------------------- -*/
4177 assume(strat->L==NULL); /* strat->L unused */
4178 assume(strat->B==NULL); /* strat->B unused */
4179 omFree(strat->sevS);
4180 omFree(strat->ecartS);
4181 assume(strat->T==NULL);//omfree(strat->T);
4182 assume(strat->sevT==NULL);//omfree(strat->sevT);
4183 assume(strat->R==NULL);//omfree(strat->R);
4184 omfree(strat->S_2_R);
4185 omfree(strat->fromQ);
4186 strat->fromQ=NULL;
4187 idDelete(&strat->Shdl);
4188 SI_RESTORE_OPT1(save1);
4189 if (TEST_OPT_PROT) PrintLn();
4190 return res;
4191}
static int si_max(const int a, const int b)
Definition auxiliary.h:125
intset ecartS
Definition kutil.h:310
LSet B
Definition kutil.h:329
CanonicalForm res
Definition facAbsFact.cc:60
#define idDelete(H)
delete an ideal
Definition ideals.h:29
#define KSTD_NF_LAZY
Definition kstd1.h:18
#define KSTD_NF_NONORM
Definition kstd1.h:22
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition kstd2.cc:2315
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7590
poly redtailBba_NF(poly p, kStrategy strat)
Definition kutil.cc:7354
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8894
#define omfree(addr)
#define omFree(addr)
VAR unsigned si_opt_1
Definition options.c:5
#define OPT_INTSTRATEGY
Definition options.h:93
#define OPT_REDTAIL
Definition options.h:92
#define Sy_bit(x)
Definition options.h:31
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
#define mflush()
Definition reporter.h:58
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:417

◆ kNF2() [2/2]

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

Definition at line 3944 of file kstd2.cc.

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

◆ kNF2Bound() [1/2]

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

Definition at line 4193 of file kstd2.cc.

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

◆ 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;
4049 SI_SAVE_OPT1(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;
4071 p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
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 {
4086 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
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 strat->fromQ=NULL;
4101 idDelete(&strat->Shdl);
4102 SI_RESTORE_OPT1(save1);
4103 if (TEST_OPT_PROT) PrintLn();
4104 return p;
4105}

◆ ksReducePolyTailSig()

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

Definition at line 1335 of file kstd2.cc.

1336{
1337 BOOLEAN ret;
1338 number coef;
1339 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1341 Red->HeadNormalize();
1342 /*
1343 printf("------------------------\n");
1344 pWrite(Red->GetLmCurrRing());
1345 */
1347 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1348 else
1349 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1350 if (!ret)
1351 {
1352 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1353 {
1354 PR->Mult_nn(coef);
1355 // HANNES: mark for Normalize
1356 }
1357 n_Delete(&coef, currRing->cf);
1358 }
1359 return ret;
1360}
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:459
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:472
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:737
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:943

◆ kTestDivisibleByT0_Z()

int kTestDivisibleByT0_Z ( const kStrategy strat,
const LObject * L )

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

Definition at line 146 of file kstd2.cc.

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

◆ redFirstShift()

int redFirstShift ( LObject * h,
kStrategy strat )

Definition at line 4974 of file kstd2.cc.

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

◆ redHomog()

int redHomog ( LObject * h,
kStrategy strat )

Definition at line 1154 of file kstd2.cc.

1155{
1156 if (strat->tl<0) return 1;
1157 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1158 assume(h->FDeg == h->pFDeg());
1159
1160 poly h_p;
1161 int i,j,at,pass,cnt,ii;
1162 // long reddeg,d;
1163 int li;
1164 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1165
1166 pass = j = 0;
1167 cnt = RED_CANONICALIZE;
1168 h->SetShortExpVector();
1169 h_p = h->GetLmTailRing();
1170 h->PrepareRed(strat->use_buckets);
1171 loop
1172 {
1173 j = kFindDivisibleByInT(strat, h);
1174 if (j < 0) return 1;
1175
1176 li = strat->T[j].pLength;
1177 ii = j;
1178 /*
1179 * the polynomial to reduce with (up to the moment) is;
1180 * pi with length li
1181 */
1182 i = j;
1183#if 1
1184 if (test_opt_length)
1185 {
1186 if (li<=0) li=strat->T[j].GetpLength();
1187 if (li>2)
1188 {
1189 unsigned long not_sev = ~ h->sev;
1190 loop
1191 {
1192 /*- search the shortest possible with respect to length -*/
1193 i++;
1194 if (i > strat->tl)
1195 break;
1196 if ((strat->T[i].pLength < li)
1197 &&
1198 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1199 h_p, not_sev, strat->tailRing))
1200 {
1201 /*
1202 * the polynomial to reduce with is now;
1203 */
1204 li = strat->T[i].pLength;
1205 if (li<=0) li=strat->T[i].GetpLength();
1206 ii = i;
1207 if (li<3) break;
1208 }
1209 }
1210 }
1211 }
1212#endif
1213
1214 /*
1215 * end of search: have to reduce with pi
1216 */
1217#ifdef KDEBUG
1218 if (TEST_OPT_DEBUG)
1219 {
1220 PrintS("red:");
1221 h->wrp();
1222 PrintS(" with ");
1223 strat->T[ii].wrp();
1224 }
1225#endif
1226 assume(strat->fromT == FALSE);
1227
1228 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1229#if SBA_PRINT_REDUCTION_STEPS
1230 sba_interreduction_steps++;
1231#endif
1232#if SBA_PRINT_OPERATIONS
1233 sba_interreduction_operations += pLength(strat->T[ii].p);
1234#endif
1235
1236#ifdef KDEBUG
1237 if (TEST_OPT_DEBUG)
1238 {
1239 PrintS("\nto ");
1240 h->wrp();
1241 PrintLn();
1242 }
1243#endif
1244
1245 h_p = h->GetLmTailRing();
1246 if (h_p == NULL)
1247 {
1248 kDeleteLcm(h);
1249 return 0;
1250 }
1252 {
1253 if (h->p!=NULL)
1254 {
1255 if(p_GetComp(h->p,currRing)>strat->syzComp)
1256 {
1257 h->Delete();
1258 return 0;
1259 }
1260 }
1261 else if (h->t_p!=NULL)
1262 {
1263 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1264 {
1265 h->Delete();
1266 return 0;
1267 }
1268 }
1269 }
1270 #if 0
1271 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1272 {
1273 if (h->p!=NULL)
1274 {
1275 if(p_GetComp(h->p,currRing)>strat->syzComp)
1276 {
1277 return 1;
1278 }
1279 }
1280 else if (h->t_p!=NULL)
1281 {
1282 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1283 {
1284 return 1;
1285 }
1286 }
1287 }
1288 #endif
1289 h->SetShortExpVector();
1290 /*
1291 * try to reduce the s-polynomial h
1292 *test first whether h should go to the lazyset L
1293 *-if the degree jumps
1294 *-if the number of pre-defined reductions jumps
1295 */
1296 cnt--;
1297 pass++;
1298 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1299 {
1300 h->SetLmCurrRing();
1301 at = strat->posInL(strat->L,strat->Ll,h,strat);
1302 if (at <= strat->Ll)
1303 {
1304#ifdef HAVE_SHIFTBBA
1305 if (rIsLPRing(currRing))
1306 {
1307 if (kFindDivisibleByInT(strat, h) < 0)
1308 return 1;
1309 }
1310 else
1311#endif
1312 {
1313 int dummy=strat->sl;
1314 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1315 return 1;
1316 }
1317 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1318#ifdef KDEBUG
1319 if (TEST_OPT_DEBUG)
1320 Print(" lazy: -> L%d\n",at);
1321#endif
1322 h->Clear();
1323 return -1;
1324 }
1325 }
1326 else if (UNLIKELY(cnt==0))
1327 {
1328 h->CanonicalizeP();
1329 cnt=RED_CANONICALIZE;
1330 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1331 }
1332 }
1333}
#define UNLIKELY(X)
Definition auxiliary.h:405
char fromT
Definition kutil.h:378
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:468
#define RED_CANONICALIZE
Definition kutil.h:37
#define p_GetComp(p, r)
Definition monomials.h:64
#define TEST_OPT_REDTAIL_SYZ
Definition options.h:119

◆ redHoney()

int redHoney ( LObject * h,
kStrategy strat )

Definition at line 2114 of file kstd2.cc.

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

◆ redLazy()

int redLazy ( LObject * h,
kStrategy strat )

TEST_OPT_REDTHROUGH &&

Definition at line 1909 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2315 of file kstd2.cc.

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

◆ redNFBound()

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

Definition at line 2511 of file kstd2.cc.

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

◆ redRing()

int redRing ( LObject * h,
kStrategy strat )

Definition at line 992 of file kstd2.cc.

993{
994 if (strat->tl<0) return 1;
995 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
996
997 int at/*,i*/;
998 long d;
999 int j = 0;
1000 int pass = 0;
1001 // poly zeroPoly = NULL;
1002
1003// TODO warum SetpFDeg notwendig?
1004 h->SetpFDeg();
1005 assume(h->pFDeg() == h->FDeg);
1006 long reddeg = h->GetpFDeg();
1007
1008 h->SetShortExpVector();
1009 loop
1010 {
1011 j = kFindDivisibleByInT(strat, h);
1012 if (j < 0)
1013 {
1014 // over ZZ: cleanup coefficients by complete reduction with monomials
1015 postReduceByMon(h, strat);
1016 if(h->p == NULL)
1017 {
1018 kDeleteLcm(h);
1019 h->Clear();
1020 return 0;
1021 }
1022 if(nIsZero(pGetCoeff(h->p))) return 2;
1023 j = kFindDivisibleByInT(strat, h);
1024 if(j < 0)
1025 {
1026 if(strat->tl >= 0)
1027 h->i_r1 = strat->tl;
1028 else
1029 h->i_r1 = -1;
1030 if (h->GetLmTailRing() == NULL)
1031 {
1032 kDeleteLcm(h);
1033 h->Clear();
1034 return 0;
1035 }
1036 return 1;
1037 }
1038 }
1039 //printf("\nFound one: ");pWrite(strat->T[j].p);
1040 //enterT(*h, strat);
1041 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
1042 //printf("\nAfter small red: ");pWrite(h->p);
1043 if (h->GetLmTailRing() == NULL)
1044 {
1045 kDeleteLcm(h);
1046 h->Clear();
1047 return 0;
1048 }
1049 h->SetShortExpVector();
1050 d = h->SetpFDeg();
1051 /*- try to reduce the s-polynomial -*/
1052 pass++;
1053 if (!TEST_OPT_REDTHROUGH &&
1054 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1055 {
1056 h->SetLmCurrRing();
1057 if (strat->posInLDependsOnLength)
1058 h->SetLength(strat->length_pLength);
1059 at = strat->posInL(strat->L,strat->Ll,h,strat);
1060 if (at <= strat->Ll)
1061 {
1062#ifdef KDEBUG
1063 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1064#endif
1065 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
1066 h->Clear();
1067 return -1;
1068 }
1069 }
1070 if (d != reddeg)
1071 {
1072 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1073 {
1074 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1075 {
1076 strat->overflow=TRUE;
1077 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1078 h->GetP();
1079 at = strat->posInL(strat->L,strat->Ll,h,strat);
1080 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1081 h->Clear();
1082 return -1;
1083 }
1084 }
1085 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1086 {
1087 Print(".%ld",d);mflush();
1088 reddeg = d;
1089 }
1090 }
1091 }
1092}
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition kutil.cc:10704

◆ redRing_S()

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

Definition at line 1094 of file kstd2.cc.

1095{
1096 if (strat->sl<0) return 1;
1097 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
1098
1099 int j = 0;
1100 int pass = 0;
1101 // poly zeroPoly = NULL;
1102
1103 h->SetpFDeg();
1104 assume(h->pFDeg() == h->FDeg);
1105 int max_ind;
1106
1107 h->SetShortExpVector();
1108 loop
1109 {
1110 max_ind=strat->sl;
1111 j = kFindDivisibleByInS(strat, &max_ind, h);
1112 if (j < 0)
1113 {
1114 // over ZZ: cleanup coefficients by complete reduction with monomials
1115 postReduceByMon(h, strat);
1116 if(h->p == NULL)
1117 {
1118 h->Clear();
1119 return 0;
1120 }
1121 if(nIsZero(pGetCoeff(h->p))) return 2;
1122 max_ind=strat->sl;
1123 j = kFindDivisibleByInS(strat, &max_ind,h);
1124 if(j < 0)
1125 {
1126 if (h->GetLmTailRing() == NULL)
1127 {
1128 h->Clear();
1129 return 0;
1130 }
1131 return 1;
1132 }
1133 }
1134 //printf("\nFound one: ");pWrite(strat->T[j].p);
1135 //enterT(*h, strat);
1136 TObject tj(strat->S[j]);
1137 ksReducePoly(h, &tj, NULL, NULL, NULL, strat); // with debug output
1138 //printf("\nAfter small red: ");pWrite(h->p);
1139 if (h->GetLmTailRing() == NULL)
1140 {
1141 h->Clear();
1142 return 0;
1143 }
1144 h->SetShortExpVector();
1145 /*- try to reduce the s-polynomial -*/
1146 pass++;
1147 }
1148}
class sTObject TObject
Definition kutil.h:58

◆ redRing_Z()

int redRing_Z ( LObject * h,
kStrategy strat )

Definition at line 724 of file kstd2.cc.

725{
726 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
727 if (strat->tl<0) return 1;
728
729 int at;
730 long d;
731 int j = 0;
732 int pass = 0;
733
734// TODO warum SetpFDeg notwendig?
735 h->SetpFDeg();
736 assume(h->pFDeg() == h->FDeg);
737 long reddeg = h->GetpFDeg();
738
739 h->SetShortExpVector();
740 loop
741 {
742 /* check if a reducer of the lead term exists */
743 j = kFindDivisibleByInT(strat, h);
744 if (j < 0)
745 {
746#if STDZ_EXCHANGE_DURING_REDUCTION
747 /* check if a reducer with the same lead monomial exists */
748 j = kFindSameLMInT_Z(strat, h);
749 if (j < 0)
750 {
751#endif
752 /* check if a reducer of the lead monomial exists, by the above
753 * check this is a real divisor of the lead monomial */
754 j = kFindDivisibleByInT_Z(strat, h);
755 if (j < 0)
756 {
757 // over ZZ: cleanup coefficients by complete reduction with monomials
759 postReduceByMon(h, strat);
760 if(h->p == NULL)
761 {
762 if (h->lcm!=NULL) pLmDelete(h->lcm);
763 h->Clear();
764 return 0;
765 }
766 if(nIsZero(pGetCoeff(h->p))) return 2;
767 j = kFindDivisibleByInT(strat, h);
768 if(j < 0)
769 {
770 if(strat->tl >= 0)
771 h->i_r1 = strat->tl;
772 else
773 h->i_r1 = -1;
774 if (h->GetLmTailRing() == NULL)
775 {
776 if (h->lcm!=NULL) pLmDelete(h->lcm);
777 h->Clear();
778 return 0;
779 }
780 return 1;
781 }
782 }
783 else
784 {
785 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
786 * => we try to cut down the lead coefficient at least */
787 /* first copy T[j] in order to multiply it with a coefficient later on */
788 number mult, rest;
789 TObject tj = strat->T[j];
790 tj.Copy();
791 /* tj.max_exp = strat->T[j].max_exp; */
792 /* compute division with remainder of lc(h) and lc(T[j]) */
793 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
794 &rest, currRing->cf);
795 /* set corresponding new lead coefficient already. we do not
796 * remove the lead term in ksReducePolyLC, but only apply
797 * a lead coefficient reduction */
798 tj.Mult_nn(mult);
799 ksReducePolyLC(h, &tj, NULL, &rest, strat);
800 tj.Delete();
801 tj.Clear();
802 }
803#if STDZ_EXCHANGE_DURING_REDUCTION
804 }
805 else
806 {
807 /* same lead monomial but lead coefficients do not divide each other:
808 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
809 LObject h2 = *h;
810 h2.Copy();
811
812 ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
813 ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
815 {
816 redtailBbaAlsoLC_Z(&h2, j, strat);
817 }
818 /* replace h2 for tj in L (already generated pairs with tj), S and T */
819 replaceInLAndSAndT(h2, j, strat);
820 }
821#endif
822 }
823 else
824 {
825 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat);
826 }
827 /* printf("\nAfter small red: ");pWrite(h->p); */
828 if (h->GetLmTailRing() == NULL)
829 {
830 if (h->lcm!=NULL) pLmDelete(h->lcm);
831#ifdef KDEBUG
832 h->lcm=NULL;
833#endif
834 h->Clear();
835 return 0;
836 }
837 h->SetShortExpVector();
838 d = h->SetpFDeg();
839 /*- try to reduce the s-polynomial -*/
840 pass++;
841 if (!TEST_OPT_REDTHROUGH &&
842 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
843 {
844 h->SetLmCurrRing();
845 if (strat->posInLDependsOnLength)
846 h->SetLength(strat->length_pLength);
847 at = strat->posInL(strat->L,strat->Ll,h,strat);
848 if (at <= strat->Ll)
849 {
850#ifdef KDEBUG
851 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
852#endif
853 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
854 h->Clear();
855 return -1;
856 }
857 }
858 if (d != reddeg)
859 {
860 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
861 {
862 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
863 {
864 strat->overflow=TRUE;
865 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
866 h->GetP();
867 at = strat->posInL(strat->L,strat->Ll,h,strat);
868 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
869 h->Clear();
870 return -1;
871 }
872 }
873 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
874 {
875 Print(".%ld",d);mflush();
876 reddeg = d;
877 }
878 }
879 }
880}
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
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:9052
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 882 of file kstd2.cc.

883{
884 if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
885 if (strat->sl<0) return 1;
886
887 int j = 0;
888 int pass = 0;
889
890// TODO warum SetpFDeg notwendig?
891 h->SetpFDeg();
892 assume(h->pFDeg() == h->FDeg);
893 h->SetShortExpVector();
894 int max_ind=strat->sl;
895
896 loop
897 {
898 /* check if a reducer of the lead term exists */
899 max_ind=strat->sl;
900 j = kFindDivisibleByInS(strat,&max_ind, h);
901 if (j < 0)
902 {
903#if STDZ_EXCHANGE_DURING_REDUCTION
904 /* check if a reducer with the same lead monomial exists */
905 j = kFindSameLMInT_Z(strat, h);
906 if (j < 0)
907 {
908#endif
909 /* check if a reducer of the lead monomial exists, by the above
910 * check this is a real divisor of the lead monomial */
911 j = kFindDivisibleByInS_Z(strat, h);
912 if (j < 0)
913 {
914 // over ZZ: cleanup coefficients by complete reduction with monomials
916 postReduceByMon(h, strat);
917 if(h->p == NULL)
918 {
919 h->Clear();
920 return 0;
921 }
922 if(nIsZero(pGetCoeff(h->p))) return 2;
923 max_ind=strat->sl;
924 j = kFindDivisibleByInS(strat, &max_ind, h);
925 if(j < 0)
926 {
927 if (h->GetLmTailRing() == NULL)
928 {
929 h->Clear();
930 return 0;
931 }
932 return 1;
933 }
934 }
935 else
936 {
937 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
938 * => we try to cut down the lead coefficient at least */
939 /* first copy T[j] in order to multiply it with a coefficient later on */
940 number mult, rest;
941 TObject tj(pCopy(strat->S[j]));
942 /* compute division with remainder of lc(h) and lc(S[j]) */
943 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->S[j]),
944 &rest, currRing->cf);
945 /* set corresponding new lead coefficient already. we do not
946 * remove the lead term in ksReducePolyLC, but only apply
947 * a lead coefficient reduction */
948 tj.Mult_nn(mult);
949 ksReducePolyLC(h, &tj, NULL, &rest, strat);
950 tj.Delete();
951 tj.Clear();
952 }
953#if STDZ_EXCHANGE_DURING_REDUCTION
954 }
955 else
956 {
957 /* same lead monomial but lead coefficients do not divide each other:
958 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
959 LObject h2 = *h;
960 h2.Copy();
961 TObject tj(strat->S[j]);
962
963 ksReducePolyZ(h, &tj, NULL, NULL, strat);
964 ksReducePolyGCD(&h2, &tj, NULL, NULL, strat);
966 {
967 redtailBbaAlsoLC_Z_S(&h2, j, strat);
968 }
969 /* replace h2 for tj in L (already generated pairs with tj), S and T */
970 replaceInLAndSAndT(h2, j, strat);
971 }
972#endif
973 }
974 else
975 {
976 TObject tj(strat->S[j]);
977 ksReducePoly(h, &tj, NULL, NULL, NULL, strat);
978 }
979 /* printf("\nAfter small red: ");pWrite(h->p); */
980 if (h->GetLmCurrRing() == NULL)
981 {
982 h->Clear();
983 return 0;
984 }
985 h->SetShortExpVector();
986 h->SetpFDeg();
987 /*- try to reduce the s-polynomial -*/
988 pass++;
989 }
990}
static int kFindDivisibleByInS_Z(const kStrategy strat, LObject *L)
Definition kstd2.cc:276

◆ redSig()

int redSig ( LObject * h,
kStrategy strat )

Definition at line 1373 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject * h,
kStrategy strat )

Definition at line 1540 of file kstd2.cc.

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

◆ redtailSba()

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

Definition at line 1789 of file kstd2.cc.

1790{
1791 strat->redTailChange=FALSE;
1792 if (strat->noTailReduction) return L->GetLmCurrRing();
1793 poly h, p;
1794 p = h = L->GetLmTailRing();
1795 if ((h==NULL) || (pNext(h)==NULL))
1796 return L->GetLmCurrRing();
1797
1798 TObject* With;
1799 // placeholder in case strat->tl < 0
1800 TObject With_s(strat->tailRing);
1801
1802 LObject Ln(pNext(h), strat->tailRing);
1803 Ln.sig = L->sig;
1804 Ln.sevSig = L->sevSig;
1805 Ln.pLength = L->GetpLength() - 1;
1806
1807 pNext(h) = NULL;
1808 if (L->p != NULL) pNext(L->p) = NULL;
1809 L->pLength = 1;
1810
1811 Ln.PrepareRed(strat->use_buckets);
1812
1813 int cnt=REDTAIL_CANONICALIZE;
1814 while(!Ln.IsNull())
1815 {
1816 loop
1817 {
1818 if(rField_is_Ring(currRing) && strat->sigdrop)
1819 break;
1820 Ln.SetShortExpVector();
1821 if (withT)
1822 {
1823 int j;
1824 j = kFindDivisibleByInT(strat, &Ln);
1825 if (j < 0) break;
1826 With = &(strat->T[j]);
1827 }
1828 else
1829 {
1830 With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1831 if (With == NULL) break;
1832 }
1833 cnt--;
1834 if (cnt==0)
1835 {
1837 /*poly tmp=*/Ln.CanonicalizeP();
1839 {
1840 Ln.Normalize();
1841 //pNormalize(tmp);
1842 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1843 }
1844 }
1846 {
1847 With->pNorm();
1848 }
1849 strat->redTailChange=TRUE;
1850 int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1852 L->sig = Ln.sig;
1853 //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1854 // I delete it an then set Ln.sig. Hence L->sig is lost
1855#if SBA_PRINT_REDUCTION_STEPS
1856 if (ret != 3)
1857 sba_reduction_steps++;
1858#endif
1859#if SBA_PRINT_OPERATIONS
1860 if (ret != 3)
1861 sba_operations += pLength(With->p);
1862#endif
1863 if (ret)
1864 {
1865 // reducing the tail would violate the exp bound
1866 // set a flag and hope for a retry (in bba)
1868 if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1869 do
1870 {
1871 pNext(h) = Ln.LmExtractAndIter();
1872 pIter(h);
1873 L->pLength++;
1874 } while (!Ln.IsNull());
1875 goto all_done;
1876 }
1877 if (Ln.IsNull()) goto all_done;
1878 if (! withT) With_s.Init(currRing);
1879 if(rField_is_Ring(currRing) && strat->sigdrop)
1880 {
1881 //Cannot break the loop here so easily
1882 break;
1883 }
1884 }
1885 pNext(h) = Ln.LmExtractAndIter();
1886 pIter(h);
1888 pNormalize(h);
1889 L->pLength++;
1890 }
1891 all_done:
1892 Ln.Delete();
1893 if (L->p != NULL) pNext(L->p) = pNext(p);
1894
1895 if (strat->redTailChange)
1896 {
1897 L->length = 0;
1898 }
1899 //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1900 //L->Normalize(); // HANNES: should have a test
1901 kTest_L(L,strat);
1902 return L->GetLmCurrRing();
1903}
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition kstd2.cc:1335
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition kutil.cc:6701
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:923
#define REDTAIL_CANONICALIZE
Definition kutil.h:39
#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 4958 of file kstd2.cc.

4959{
4961 assume(idIsInV(F));
4962 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4963 idSkipZeroes(RS); // is this even necessary?
4964 assume(idIsInV(RS));
4965 return(RS);
4966}
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition kstd1.cc:2959
#define idIsInV(I)
Definition shiftop.h:49
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
@ testHomog
Definition structs.h:34

◆ sba()

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

Definition at line 2982 of file kstd2.cc.

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

Variable Documentation

◆ test_PosInL

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

Definition at line 83 of file kstd2.cc.

◆ test_PosInT

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

Definition at line 82 of file kstd2.cc.