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

Go to the source code of this file.

Macros

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

Functions

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

Variables

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

Macro Definition Documentation

◆ DEBUGF50

#define DEBUGF50   0

Definition at line 24 of file kstd2.cc.

◆ DEBUGF51

#define DEBUGF51   0

Definition at line 25 of file kstd2.cc.

◆ F5C

#define F5C   1

Definition at line 32 of file kstd2.cc.

◆ F5CTAILRED

#define F5CTAILRED   1

Definition at line 34 of file kstd2.cc.

◆ GCD_SBA

#define GCD_SBA   1

Definition at line 12 of file kstd2.cc.

◆ PLURAL_INTERNAL_DECLARATIONS

#define PLURAL_INTERNAL_DECLARATIONS   1

Definition at line 18 of file kstd2.cc.

◆ SBA_INTERRED_START

#define SBA_INTERRED_START   0

Definition at line 37 of file kstd2.cc.

◆ SBA_PRINT_OPERATIONS

#define SBA_PRINT_OPERATIONS   0

Definition at line 42 of file kstd2.cc.

◆ SBA_PRINT_PRODUCT_CRITERION

#define SBA_PRINT_PRODUCT_CRITERION   0

Definition at line 45 of file kstd2.cc.

◆ SBA_PRINT_REDUCTION_STEPS

#define SBA_PRINT_REDUCTION_STEPS   0

Definition at line 41 of file kstd2.cc.

◆ SBA_PRINT_SIZE_G

#define SBA_PRINT_SIZE_G   0

Definition at line 43 of file kstd2.cc.

◆ SBA_PRINT_SIZE_SYZ

#define SBA_PRINT_SIZE_SYZ   0

Definition at line 44 of file kstd2.cc.

◆ SBA_PRINT_ZERO_REDUCTIONS

#define SBA_PRINT_ZERO_REDUCTIONS   0

Definition at line 40 of file kstd2.cc.

◆ SBA_PRODUCT_CRITERION

#define SBA_PRODUCT_CRITERION   0

Definition at line 39 of file kstd2.cc.

◆ SBA_TAIL_RED

#define SBA_TAIL_RED   1

Definition at line 38 of file kstd2.cc.

Function Documentation

◆ bba()

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

Definition at line 2374 of file kstd2.cc.

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

◆ bbaShift()

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

Definition at line 4345 of file kstd2.cc.

4346{
4347 int red_result = 1;
4348 int olddeg,reduc;
4349 int hilbeledeg=1,hilbcount=0,minimcnt=0;
4350 BOOLEAN withT = TRUE; // currently only T contains the shifts
4351 BITSET save;
4352 SI_SAVE_OPT1(save);
4353
4354 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4356 initBuchMoraPosRing(strat);
4357 else
4358 initBuchMoraPos(strat);
4359 initHilbCrit(F,Q,&hilb,strat);
4360 initBba(strat);
4361 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4362 /*Shdl=*/initBuchMora(F, Q,strat);
4363 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4364 reduc = olddeg = 0;
4365
4366#ifndef NO_BUCKETS
4368 strat->use_buckets = 1;
4369#endif
4370 // redtailBBa against T for inhomogenous input
4371 // if (!TEST_OPT_OLDSTD)
4372 // withT = ! strat->homog;
4373
4374 // strat->posInT = posInT_pLength;
4375 kTest_TS(strat);
4376
4377#ifdef HAVE_TAIL_RING
4378 // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4379 // kStratInitChangeTailRing(strat);
4380 strat->tailRing=currRing;
4381#endif
4382 if (BVERBOSE(23))
4383 {
4384 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4385 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4386 kDebugPrint(strat);
4387 }
4388
4389#ifdef KDEBUG
4390 //kDebugPrint(strat);
4391#endif
4392 /* compute------------------------------------------------------- */
4393 while (strat->Ll >= 0)
4394 {
4395 #ifdef KDEBUG
4396 if (TEST_OPT_DEBUG) messageSets(strat);
4397 #endif
4398 if (siCntrlc)
4399 {
4400 while (strat->Ll >= 0)
4401 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4402 strat->noClearS=TRUE;
4403 }
4405 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4406 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4407 {
4408 /*
4409 *stops computation if
4410 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4411 *a predefined number Kstd1_deg
4412 */
4413 while ((strat->Ll >= 0)
4414 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4415 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4416 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4417 )
4418 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4419 if (strat->Ll<0) break;
4420 else strat->noClearS=TRUE;
4421 }
4422 if (strat->Ll== 0) strat->interpt=TRUE;
4423 /* picks the last element from the lazyset L */
4424 strat->P = strat->L[strat->Ll];
4425 strat->Ll--;
4426
4427 if (pNext(strat->P.p) == strat->tail)
4428 {
4429 // deletes the short spoly
4431 pLmDelete(strat->P.p);
4432 else
4433 pLmFree(strat->P.p);
4434 strat->P.p = NULL;
4435 poly m1 = NULL, m2 = NULL;
4436
4437 // check that spoly creation is ok
4438 while (strat->tailRing != currRing &&
4439 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4440 {
4441 assume(m1 == NULL && m2 == NULL);
4442 // if not, change to a ring where exponents are at least
4443 // large enough
4444 if (!kStratChangeTailRing(strat))
4445 {
4446 WerrorS("OVERFLOW...");
4447 break;
4448 }
4449 }
4450 // create the real one
4451 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4452 strat->tailRing, m1, m2, strat->R);
4453 }
4454 else if (strat->P.p1 == NULL)
4455 {
4456 if (strat->minim > 0)
4457 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4458 // for input polys, prepare reduction
4459 strat->P.PrepareRed(strat->use_buckets);
4460 }
4461
4462 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4463 {
4464 red_result = 0;
4465 }
4466 else
4467 {
4468 if (TEST_OPT_PROT)
4469 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4470 &olddeg,&reduc,strat, red_result);
4471
4472 /* reduction of the element chosen from L */
4473 red_result = strat->red(&strat->P,strat);
4474 if (errorreported) break;
4475 }
4476
4477 if (strat->overflow)
4478 {
4479 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4480 }
4481
4482 // reduction to non-zero new poly
4483 if (red_result == 1)
4484 {
4485 // get the polynomial (canonicalize bucket, make sure P.p is set)
4486 strat->P.GetP(strat->lmBin);
4487 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4488 // but now, for entering S, T, we reset it
4489 // in the inhomogeneous case: FDeg == pFDeg
4490 if (strat->homog) strat->initEcart(&(strat->P));
4491
4492 /* statistic */
4493 if (TEST_OPT_PROT) PrintS("s");
4494
4495 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4496
4497 // reduce the tail and normalize poly
4498 // in the ring case we cannot expect LC(f) = 1,
4499 // therefore we call pCleardenom instead of pNorm
4500 strat->redTailChange=FALSE;
4501
4502 /* if we are computing over Z we always want to try and cut down
4503 * the coefficients in the tail terms */
4505 {
4506 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4507 strat->P.pCleardenom();
4508 }
4509
4511 {
4512 strat->P.pCleardenom();
4514 {
4515 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4516 strat->P.pCleardenom();
4517 if (strat->redTailChange)
4518 {
4519 strat->P.t_p=NULL;
4520 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4521 }
4522 }
4523 }
4524 else
4525 {
4526 strat->P.pNorm();
4528 {
4529 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4530 if (strat->redTailChange)
4531 {
4532 strat->P.t_p=NULL;
4533 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4534 }
4535 }
4536 }
4537
4538#ifdef KDEBUG
4539 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4540#endif /* KDEBUG */
4541
4542 // min_std stuff
4543 if ((strat->P.p1==NULL) && (strat->minim>0))
4544 {
4545 if (strat->minim==1)
4546 {
4547 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4548 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4549 }
4550 else
4551 {
4552 strat->M->m[minimcnt]=strat->P.p2;
4553 strat->P.p2=NULL;
4554 }
4555 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4556 pNext(strat->M->m[minimcnt])
4557 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4558 strat->tailRing, currRing,
4559 currRing->PolyBin);
4560 minimcnt++;
4561 }
4562
4563
4564 // enter into S, L, and T
4565 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4566 {
4567 enterT(strat->P, strat);
4568 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4569 // posInS only depends on the leading term
4570 strat->enterS(strat->P, pos, strat, strat->tl);
4571 if (!strat->rightGB)
4572 enterTShift(strat->P, strat);
4573 }
4574
4575 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4576// Print("[%d]",hilbeledeg);
4577 kDeleteLcm(&strat->P);
4578 if (strat->s_poly!=NULL)
4579 {
4580 // the only valid entries are: strat->P.p,
4581 // strat->tailRing (read-only, keep it)
4582 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4583 if (strat->s_poly(strat))
4584 {
4585 // we are called AFTER enterS, i.e. if we change P
4586 // we have to add it also to S/T
4587 // and add pairs
4588 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4589 enterT(strat->P, strat);
4590 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4591 strat->enterS(strat->P, pos, strat, strat->tl);
4592 if (!strat->rightGB)
4593 enterTShift(strat->P,strat);
4594 }
4595 }
4596 }
4597 else if (strat->P.p1 == NULL && strat->minim > 0)
4598 {
4599 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4600 }
4601#ifdef KDEBUG
4602 memset(&(strat->P), 0, sizeof(strat->P));
4603#endif /* KDEBUG */
4604 kTest_TS(strat);
4605 }
4606#ifdef KDEBUG
4607 if (TEST_OPT_DEBUG) messageSets(strat);
4608#endif /* KDEBUG */
4609 /* shift case: look for elt's in S such that they are divisible by elt in T */
4610 if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4611 {
4613 {
4614 for (int k = 0; k <= strat->sl; ++k)
4615 {
4616 if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4617 for (int j = 0; j<=strat->tl; ++j)
4618 {
4619 // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4620 assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4621 assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4622 if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4623 {
4624 if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4625 { // check whether LM is different
4626 deleteInS(k, strat);
4627 --k;
4628 break;
4629 }
4630 }
4631 }
4632 }
4633 }
4634 }
4635 /* complete reduction of the standard basis--------- */
4636 if (TEST_OPT_REDSB)
4637 {
4638 completeReduce(strat, TRUE); //shift: withT = TRUE
4639 if (strat->completeReduce_retry)
4640 {
4641 // completeReduce needed larger exponents, retry
4642 // to reduce with S (instead of T)
4643 // and in currRing (instead of strat->tailRing)
4644#ifdef HAVE_TAIL_RING
4645 if(currRing->bitmask>strat->tailRing->bitmask)
4646 {
4648 cleanT(strat);strat->tailRing=currRing;
4649 int i;
4650 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4651 WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4652 completeReduce(strat);
4653 }
4654 if (strat->completeReduce_retry)
4655#endif
4656 Werror("exponent bound is %ld",currRing->bitmask);
4657 }
4658 }
4659 else if (TEST_OPT_PROT) PrintLn();
4660
4661 /* release temp data-------------------------------- */
4662 exitBuchMora(strat);
4663 /* postprocessing for GB over ZZ --------------------*/
4664 if (!errorreported)
4665 {
4667 {
4668 for(int i = 0;i<=strat->sl;i++)
4669 {
4670 if(!nGreaterZero(pGetCoeff(strat->S[i])))
4671 {
4672 strat->S[i] = pNeg(strat->S[i]);
4673 }
4674 }
4675 finalReduceByMon(strat);
4676 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4677 {
4678 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4679 {
4680 strat->S[i] = pNeg(strat->Shdl->m[i]);
4681 }
4682 }
4683 }
4684 //else if (rField_is_Ring(currRing))
4685 // finalReduceByMon(strat);
4686 }
4687// if (TEST_OPT_WEIGHTM)
4688// {
4689// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4690// if (ecartWeights)
4691// {
4692// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4693// ecartWeights=NULL;
4694// }
4695// }
4696 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4697 SI_RESTORE_OPT1(save);
4698 /* postprocessing for GB over Q-rings ------------------*/
4699 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4700
4701 idTest(strat->Shdl);
4702
4703 return (strat->Shdl);
4704}
TSet T
Definition: kutil.h:327
char rightGB
Definition: kutil.h:373
unsigned long * sevT
Definition: kutil.h:326
intset fromQ
Definition: kutil.h:322
#define WarnS
Definition: emacs.cc:78
void enterTShift(LObject p, kStrategy strat, int atT)
Definition: kutil.cc:13339
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13309
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1137
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition: polys.h:146
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105

◆ f5c()

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

Definition at line 4032 of file kstd2.cc.

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

◆ ind2()

static long ind2 ( long  arg)
static

Definition at line 526 of file kstd2.cc.

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

◆ ind_fact_2()

static long ind_fact_2 ( long  arg)
static

Definition at line 538 of file kstd2.cc.

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

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11753 of file kutil.cc.

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

◆ kFindDivisibleByInS()

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

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

Definition at line 398 of file kstd2.cc.

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

◆ kFindDivisibleByInT()

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

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

Definition at line 288 of file kstd2.cc.

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

◆ kFindDivisibleByInT_Z()

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

Definition at line 207 of file kstd2.cc.

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

◆ kFindNextDivisibleByInS()

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

Definition at line 467 of file kstd2.cc.

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

◆ kFindSameLMInT_Z()

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

Definition at line 84 of file kstd2.cc.

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

◆ kFindZeroPoly()

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

Definition at line 553 of file kstd2.cc.

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

◆ kNF2() [1/2]

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

Definition at line 3857 of file kstd2.cc.

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

◆ kNF2() [2/2]

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

Definition at line 3701 of file kstd2.cc.

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

◆ kNF2Bound() [1/2]

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

Definition at line 3945 of file kstd2.cc.

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

◆ kNF2Bound() [2/2]

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

Definition at line 3783 of file kstd2.cc.

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

◆ ksReducePolyTailSig()

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

Definition at line 1111 of file kstd2.cc.

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

◆ kTestDivisibleByT0_Z()

int kTestDivisibleByT0_Z ( const kStrategy  strat,
const LObject L 
)

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

Definition at line 140 of file kstd2.cc.

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

◆ redFirstShift()

int redFirstShift ( LObject h,
kStrategy  strat 
)

Definition at line 4724 of file kstd2.cc.

4725{
4726 if (h->IsNull()) return 0;
4727
4728 int at, reddeg,d;
4729 int pass = 0;
4730 int j = 0;
4731
4732 if (! strat->homog)
4733 {
4734 d = h->GetpFDeg() + h->ecart;
4735 reddeg = strat->LazyDegree+d;
4736 }
4737 h->SetShortExpVector();
4738 loop
4739 {
4740 j = kFindDivisibleByInT(strat, h);
4741 if (j < 0)
4742 {
4743 h->SetDegStuffReturnLDeg(strat->LDegLast);
4744 return 1;
4745 }
4746
4748 strat->T[j].pNorm();
4749#ifdef KDEBUG
4750 if (TEST_OPT_DEBUG)
4751 {
4752 PrintS("reduce ");
4753 h->wrp();
4754 PrintS(" with ");
4755 strat->T[j].wrp();
4756 }
4757#endif
4758 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
4759
4760#ifdef KDEBUG
4761 if (TEST_OPT_DEBUG)
4762 {
4763 PrintS("\nto ");
4764 wrp(h->p);
4765 PrintLn();
4766 }
4767#endif
4768 if (h->IsNull())
4769 {
4770 kDeleteLcm(h);
4771 h->Clear();
4772 return 0;
4773 }
4774 h->SetShortExpVector();
4775
4776#if 0
4777 if ((strat->syzComp!=0) && !strat->honey)
4778 {
4779 if ((strat->syzComp>0) &&
4780 (h->Comp() > strat->syzComp))
4781 {
4782 assume(h->MinComp() > strat->syzComp);
4783#ifdef KDEBUG
4784 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4785#endif
4786 if (strat->homog)
4787 h->SetDegStuffReturnLDeg(strat->LDegLast);
4788 return -2;
4789 }
4790 }
4791#endif
4792 if (!strat->homog)
4793 {
4794 if (!TEST_OPT_OLDSTD && strat->honey)
4795 {
4796 h->SetpFDeg();
4797 if (strat->T[j].ecart <= h->ecart)
4798 h->ecart = d - h->GetpFDeg();
4799 else
4800 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4801
4802 d = h->GetpFDeg() + h->ecart;
4803 }
4804 else
4805 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4806 /*- try to reduce the s-polynomial -*/
4807 pass++;
4808 /*
4809 *test whether the polynomial should go to the lazyset L
4810 *-if the degree jumps
4811 *-if the number of pre-defined reductions jumps
4812 */
4813 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4814 && ((d >= reddeg) || (pass > strat->LazyPass)))
4815 {
4816 h->SetLmCurrRing();
4817 if (strat->posInLDependsOnLength)
4818 h->SetLength(strat->length_pLength);
4819 at = strat->posInL(strat->L,strat->Ll,h,strat);
4820 if (at <= strat->Ll)
4821 {
4822 //int dummy=strat->sl;
4823 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4824 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4825 if (kFindDivisibleByInT(strat, h) < 0)
4826 return 1;
4827 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4828#ifdef KDEBUG
4829 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4830#endif
4831 h->Clear();
4832 return -1;
4833 }
4834 }
4835 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4836 {
4837 reddeg = d+1;
4838 Print(".%d",d);mflush();
4839 }
4840 }
4841 }
4842}
KINLINE poly kNoetherTail()
Definition: kInline.h:66
char LDegLast
Definition: kutil.h:389
char length_pLength
Definition: kutil.h:391
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat)
Definition: kspoly.cc:185
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:288
#define TEST_OPT_REDTHROUGH
Definition: options.h:122
void wrp(poly p)
Definition: polys.h:310

◆ redHomog()

int redHomog ( LObject h,
kStrategy  strat 
)

Definition at line 929 of file kstd2.cc.

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

◆ redHoney()

int redHoney ( LObject h,
kStrategy  strat 
)

Definition at line 1892 of file kstd2.cc.

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

◆ redLazy()

int redLazy ( LObject h,
kStrategy  strat 
)

TEST_OPT_REDTHROUGH &&

Definition at line 1687 of file kstd2.cc.

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

◆ redNF()

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

Definition at line 2126 of file kstd2.cc.

2127{
2128 if (h==NULL) return NULL;
2129 int j;
2130 int cnt=REDNF_CANONICALIZE;
2131 max_ind=strat->sl;
2132
2133 if (0 > strat->sl)
2134 {
2135 return h;
2136 }
2137 LObject P(h);
2138 P.SetShortExpVector();
2139 P.bucket = kBucketCreate(currRing);
2140 kBucketInit(P.bucket,P.p,pLength(P.p));
2141 kbTest(P.bucket);
2142#ifdef HAVE_RINGS
2143 BOOLEAN is_ring = rField_is_Ring(currRing);
2144#endif
2145#ifdef KDEBUG
2146// if (TEST_OPT_DEBUG)
2147// {
2148// PrintS("redNF: starting S:\n");
2149// for( j = 0; j <= max_ind; j++ )
2150// {
2151// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2152// pWrite(strat->S[j]);
2153// }
2154// };
2155#endif
2156
2157 loop
2158 {
2159 j=kFindDivisibleByInS(strat,&max_ind,&P);
2160 if (j>=0)
2161 {
2162#ifdef HAVE_RINGS
2163 if (!is_ring)
2164 {
2165#endif
2166 int sl=pSize(strat->S[j]);
2167 int jj=j;
2168 loop
2169 {
2170 int sll;
2171 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2172 if (jj<0) break;
2173 sll=pSize(strat->S[jj]);
2174 if (sll<sl)
2175 {
2176 #ifdef KDEBUG
2177 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2178 #endif
2179 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2180 j=jj;
2181 sl=sll;
2182 }
2183 }
2184 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2185 {
2186 pNorm(strat->S[j]);
2187 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2188 }
2189#ifdef HAVE_RINGS
2190 }
2191#endif
2192 nNormalize(pGetCoeff(P.p));
2193#ifdef KDEBUG
2194 if (TEST_OPT_DEBUG)
2195 {
2196 PrintS("red:");
2197 wrp(h);
2198 PrintS(" with ");
2199 wrp(strat->S[j]);
2200 }
2201#endif
2202#ifdef HAVE_PLURAL
2204 {
2205 number coef;
2206 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2207 nDelete(&coef);
2208 }
2209 else
2210#endif
2211 {
2212 number coef;
2213 coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2214 nDelete(&coef);
2215 }
2216 cnt--;
2217 if (cnt==0)
2218 {
2219 kBucketCanonicalize(P.bucket);
2221 }
2222 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2223 if (h==NULL)
2224 {
2225 kBucketDestroy(&P.bucket);
2226 return NULL;
2227 }
2228 kbTest(P.bucket);
2229 P.p=h;
2230 P.t_p=NULL;
2231 P.SetShortExpVector();
2232#ifdef KDEBUG
2233 if (TEST_OPT_DEBUG)
2234 {
2235 PrintS("\nto:");
2236 wrp(h);
2237 PrintLn();
2238 }
2239#endif
2240 }
2241 else
2242 {
2243 P.p=kBucketClear(P.bucket);
2244 kBucketDestroy(&P.bucket);
2245 pNormalize(P.p);
2246 return P.p;
2247 }
2248 }
2249}
poly kNoether
Definition: kutil.h:331
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:197
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1085
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:506
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:467
#define REDNF_CANONICALIZE
Definition: kutil.h:37
static void nc_kBucketPolyRed_NF(kBucket_pt b, poly p, number *c)
Definition: nc.h:275
#define nDelete(n)
Definition: numbers.h:16
#define nIsOne(n)
Definition: numbers.h:25
#define nNormalize(n)
Definition: numbers.h:30
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:363
#define pNormalize(p)
Definition: polys.h:317
#define pSize(p)
Definition: polys.h:318

◆ redNFBound()

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

Definition at line 2255 of file kstd2.cc.

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

◆ redRing()

int redRing ( LObject h,
kStrategy  strat 
)

Definition at line 822 of file kstd2.cc.

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

◆ redRing_Z()

int redRing_Z ( LObject h,
kStrategy  strat 
)

Definition at line 667 of file kstd2.cc.

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

◆ redSig()

int redSig ( LObject h,
kStrategy  strat 
)

Definition at line 1149 of file kstd2.cc.

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

◆ redSigRing()

int redSigRing ( LObject h,
kStrategy  strat 
)

Definition at line 1317 of file kstd2.cc.

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

◆ redtailSba()

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

Definition at line 1567 of file kstd2.cc.

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

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4708 of file kstd2.cc.

4709{
4711 assume(idIsInV(F));
4712 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4713 idSkipZeroes(RS); // is this even necessary?
4714 assume(idIsInV(RS));
4715 return(RS);
4716}
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2911
#define idIsInV(I)
Definition: shiftop.h:49
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
@ testHomog
Definition: structs.h:43

◆ sba()

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

Definition at line 2734 of file kstd2.cc.

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

Variable Documentation

◆ test_PosInL

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

Definition at line 81 of file kstd2.cc.

◆ test_PosInT

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

Definition at line 80 of file kstd2.cc.