source: git/kernel/kutil.h @ 8fcfae

fieker-DuValspielwiese
Last change on this file since 8fcfae was a7b37d, checked in by Christian Eder, 10 years ago
1. some more memory leaks fixed 2. preparation for buchber product criterion check
  • Property mode set to 100644
File size: 28.0 KB
Line 
1#ifndef KUTIL_H
2#define KUTIL_H
3/****************************************
4*  Computer Algebra System SINGULAR     *
5****************************************/
6/*
7* ABSTRACT: kernel: utils for kStd
8*/
9
10
11#include <string.h>
12
13#include <omalloc/omalloc.h>
14#include <misc/mylimits.h>
15
16
17#include <kernel/polys.h>
18#include <polys/operations/pShallowCopyDelete.h>
19
20#include <kernel/structs.h>
21
22#if 1
23#define setmax 16
24#define setmaxL ((4096-12)/sizeof(LObject))
25#define setmaxLinc ((4096)/sizeof(LObject))
26
27#define setmaxT 64
28#define setmaxTinc 32
29#else
30#define setmax 16
31#define setmaxL 16
32#define setmaxLinc 16
33#define setmaxT 16
34#define setmaxTinc 16
35#endif
36
37// if you want std computations as in Singular version < 2:
38// This disables RedThrough, tailReductions against T (bba),
39// sets posInT = posInT15 (bba, strat->honey), and enables redFirst with LDeg
40// NOTE: can be achieved with option(oldStd)
41
42#undef NO_KINLINE
43#if !defined(KDEBUG) && !defined(NO_INLINE)
44#define KINLINE inline
45#else
46#define KINLINE
47#define NO_KINLINE 1
48#endif
49
50typedef int* intset;
51typedef int64  wlen_type;
52typedef wlen_type* wlen_set;
53
54typedef class sTObject TObject;
55typedef class sLObject LObject;
56typedef TObject * TSet;
57typedef LObject * LSet;
58
59typedef struct denominator_list_s denominator_list_s;
60typedef denominator_list_s *denominator_list;
61
62struct denominator_list_s{number n; denominator_list next;};
63extern denominator_list DENOMINATOR_LIST;
64
65class sTObject
66{
67public:
68  unsigned long sevSig;
69  poly sig;   // the signature of the element
70  poly p;       // Lm(p) \in currRing Tail(p) \in tailRing
71  poly t_p;     // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
72  poly max;     // p_GetMaxExpP(pNext(p))
73  ring tailRing;
74  long FDeg;    // pFDeg(p)
75  int ecart,
76    length,     // as of pLDeg
77    pLength,    // either == 0, or == pLength(p)
78    i_r;        // index of TObject in R set, or -1 if not in T
79  BOOLEAN is_normalized; // true, if pNorm was called on p, false otherwise
80  // used in incremental sba() with F5C:
81  // we know some of the redundant elements in
82  // strat->T beforehand, so we can just discard
83  // them and do not need to consider them in the
84  // interreduction process
85  BOOLEAN is_redundant;
86  // used in sba's sig-safe reduction:
87  // sometimes we already know that a reducer
88  // is sig-safe, so no need for a real
89  // sig-safeness check
90  BOOLEAN is_sigsafe;
91
92
93#ifdef HAVE_PLURAL
94  BOOLEAN is_special; // true, it is a new special S-poly (e.g. for SCA)
95#endif
96
97  // initialization
98  KINLINE void Init(ring r = currRing);
99  KINLINE sTObject(ring tailRing = currRing);
100  KINLINE sTObject(poly p, ring tailRing = currRing);
101  KINLINE sTObject(poly p, ring c_r, ring tailRing);
102  KINLINE sTObject(sTObject* T, int copy);
103
104  KINLINE void Set(ring r=currRing);
105  KINLINE void Set(poly p_in, ring r=currRing);
106  KINLINE void Set(poly p_in, ring c_r, ring t_r);
107
108  // Frees the polys of T
109  KINLINE void Delete();
110  // Sets polys to NULL
111  KINLINE void Clear();
112  // makes a copy of the poly of T
113  KINLINE void Copy();
114
115  // ring-dependent Lm access: these might result in allocation of monomials
116  KINLINE poly GetLmCurrRing();
117  KINLINE poly GetLmTailRing();
118  KINLINE poly GetLm(ring r);
119  // this returns Lm and ring r (preferably from tailRing), but does not
120  // allocate a new poly
121  KINLINE void GetLm(poly &p, ring &r) const;
122
123#ifdef OLIVER_PRIVAT_LT
124  // routines for calc. with rings
125  KINLINE poly GetLtCurrRing();
126  KINLINE poly GetLtTailRing();
127  KINLINE poly GetLt(ring r);
128  KINLINE void GetLt(poly &p, ring &r) const;
129#endif
130
131  KINLINE BOOLEAN IsNull() const;
132
133  KINLINE int GetpLength();
134
135  // makes sure that T.p exists
136  KINLINE void SetLmCurrRing();
137
138  // Iterations
139  // simply get the next monomial
140  KINLINE poly Next();
141  KINLINE void LmDeleteAndIter();
142
143  // deg stuff
144  // compute pTotalDegree
145  KINLINE long pTotalDeg() const;
146  // computes pFDeg
147  KINLINE long pFDeg() const;
148  // computes and sets FDeg
149  KINLINE long SetpFDeg();
150  // gets stored FDeg
151  KINLINE long GetpFDeg() const;
152
153  // computes pLDeg
154  KINLINE long pLDeg();
155  // sets length, FDeg, returns LDeg
156  KINLINE long SetDegStuffReturnLDeg();
157
158  // arithmetic
159  KINLINE void Mult_nn(number n);
160  KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin,
161                                 pShallowCopyDeleteProc p_shallow_copy_delete,
162                                 BOOLEAN set_max = TRUE);
163  // manipulations
164  KINLINE void pNorm();
165  KINLINE void pCleardenom();
166
167#ifdef KDEBUG
168  void wrp();
169#endif
170};
171
172#ifndef NDEBUG
173extern int strat_nr;
174extern int strat_fac_debug;
175#endif
176
177class sLObject : public sTObject
178{
179
180public:
181  unsigned long sev;
182  unsigned long from; // from which polynomial it comes from
183            // this is important for signature-based
184            // algorithms
185  unsigned long checked; // this is the index of S up to which
186                      // the corresponding LObject was already checked in
187                      // critical pair creation => when entering the
188                      // reduction process it is enough to start a second
189                      // rewritten criterion check from checked+1 onwards
190  BOOLEAN prod_crit;
191                      // NOTE: If prod_crit = TRUE then the corresponding pair is
192                      // detected by Buchberger's Product Criterion and can be
193                      // deleted
194  poly  p1,p2; /*- the pair p comes from,
195                 lm(pi) in currRing, tail(pi) in tailring -*/
196
197  poly  lcm;   /*- the lcm of p1,p2 -*/
198  kBucket_pt bucket;
199  int   i_r1, i_r2;
200
201  // initialization
202  KINLINE void Init(ring tailRing = currRing);
203  KINLINE sLObject(ring tailRing = currRing);
204  KINLINE sLObject(poly p, ring tailRing = currRing);
205  KINLINE sLObject(poly p, ring c_r, ring tailRing);
206
207  // Frees the polys of L
208  KINLINE void Delete();
209  KINLINE void Clear();
210
211  // Iterations
212  KINLINE void LmDeleteAndIter();
213  KINLINE poly LmExtractAndIter();
214
215  // spoly related things
216  // preparation for reduction if not spoly
217  KINLINE void PrepareRed(BOOLEAN use_bucket);
218  KINLINE void SetLmTail(poly lm, poly new_p, int length,
219                         int use_bucket, ring r);
220  KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
221  KINLINE void Tail_Mult_nn(number n);
222  // deletes bucket, makes sure that p and t_p exists
223  KINLINE poly GetP(omBin lmBin = NULL);
224  // similar, except that only t_p exists
225  KINLINE poly GetTP();
226
227  // does not delete bucket, just canonicalizes it
228  // returned poly is such that Lm(p) \in currRing, Tail(p) \in tailRing
229  KINLINE poly CanonicalizeP();
230
231  // makes a copy of the poly of L
232  KINLINE void Copy();
233  // gets the poly and makes a copy of it
234  KINLINE poly CopyGetP();
235
236  KINLINE int GetpLength();
237  KINLINE long pLDeg(BOOLEAN use_last);
238  KINLINE long pLDeg();
239  KINLINE int SetLength(BOOLEAN lengt_pLength = FALSE);
240  KINLINE long SetDegStuffReturnLDeg();
241  KINLINE long SetDegStuffReturnLDeg(BOOLEAN use_last);
242
243  // returns minimal component of p
244  KINLINE long MinComp();
245  // returns component of p
246  KINLINE long Comp();
247
248  KINLINE void ShallowCopyDelete(ring new_tailRing,
249                                 pShallowCopyDeleteProc p_shallow_copy_delete);
250
251  // sets sev
252  KINLINE void SetShortExpVector();
253
254  // enable assignment from TObject
255  KINLINE sLObject& operator=(const sTObject&);
256
257  // get T's corresponding to p1, p2: they might return NULL
258  KINLINE TObject* T_1(const skStrategy* strat);
259  KINLINE TObject* T_2(const skStrategy* strat);
260  KINLINE void     T_1_2(const skStrategy* strat,
261                         TObject* &T_1, TObject* &T_2);
262
263  // simplify coefficients
264  KINLINE void Normalize();
265  KINLINE void HeadNormalize();
266};
267
268
269extern int HCord;
270
271class skStrategy;
272typedef skStrategy * kStrategy;
273class skStrategy
274{
275public:
276  kStrategy next;
277  int (*red)(LObject * L,kStrategy strat);
278  int (*red2)(LObject * L,kStrategy strat);
279  void (*initEcart)(LObject * L);
280  int (*posInT)(const TSet T,const int tl,LObject &h);
281  int (*posInLSba)(const LSet set, const int length,
282                LObject* L,const kStrategy strat);
283  int (*posInL)(const LSet set, const int length,
284                LObject* L,const kStrategy strat);
285  void (*enterS)(LObject h, int pos,kStrategy strat, int atR/* =-1*/ );
286  void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
287  int (*posInLOld)(const LSet Ls,const int Ll,
288                   LObject* Lo,const kStrategy strat);
289  void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
290  void (*chainCrit) (poly p,int ecart,kStrategy strat);
291  BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
292  BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
293  BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
294  pFDegProc pOrigFDeg;
295  pLDegProc pOrigLDeg;
296  pFDegProc pOrigFDeg_TailRing;
297  pLDegProc pOrigLDeg_TailRing;
298
299  LObject P;
300  ideal Shdl;
301  ideal D; /*V(S) is in D(D)*/
302  ideal M; /*set of minimal generators*/
303  polyset S;
304  polyset syz;
305  polyset sig;
306  intset ecartS;
307  intset fromS; // from which S[i] S[j] comes from
308                // this is important for signature-based
309                // algorithms
310  intset syzIdx;// index in the syz array at which the first
311                // syzygy of component i comes up
312                // important for signature-based algorithms
313  unsigned sbaOrder;
314  unsigned long currIdx;
315  int max_lower_index;
316  intset lenS;
317  wlen_set lenSw; /* for tgb.ccc */
318  intset fromQ;
319  unsigned long* sevS;
320  unsigned long* sevSyz;
321  unsigned long* sevSig;
322  unsigned long* sevT;
323  TSet T;
324  LSet L;
325  LSet    B;
326  poly    kHEdge;
327  poly    kNoether;
328  poly    t_kHEdge; // same polys in tailring
329  KINLINE poly    kNoetherTail();
330  poly    t_kNoether;
331  BOOLEAN * NotUsedAxis;
332  BOOLEAN * pairtest;/*used for enterOnePair*/
333  poly tail;
334  intvec * kModW;
335  intvec * kHomW;
336  // procedure for ShalloCopy from tailRing  to currRing
337  pShallowCopyDeleteProc p_shallow_copy_delete;
338  // pointers to Tobjects R[i] is ith Tobject which is generated
339  TObject**  R;
340  // S_2_R[i] yields Tobject which corresponds to S[i]
341  int*      S_2_R;
342  ring tailRing;
343  omBin lmBin;
344  omBin tailBin;
345#ifndef NDEBUG
346  int nr;
347#endif
348  int cp,c3;
349  int cv; // in shift bases: counting V criterion
350  int sl,mu;
351  int syzl,syzmax,syzidxmax;
352  int tl,tmax;
353  int Ll,Lmax;
354  int Bl,Bmax;
355  int ak,LazyDegree,LazyPass;
356  int syzComp;
357  int HCord;
358  int lastAxis;
359  int newIdeal;
360  int minim;
361  #ifdef HAVE_SHIFTBBA
362  int lV;
363  #endif
364  BOOLEAN interpt;
365  BOOLEAN homog;
366#ifdef HAVE_PLURAL
367  BOOLEAN z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
368#endif
369  BOOLEAN kHEdgeFound;
370  BOOLEAN honey,sugarCrit;
371  BOOLEAN Gebauer,noTailReduction;
372  BOOLEAN fromT;
373  BOOLEAN noetherSet;
374  BOOLEAN update;
375  BOOLEAN posInLOldFlag;
376  BOOLEAN use_buckets;
377  BOOLEAN interred_flag;
378  // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
379  BOOLEAN LDegLast;
380  // if set, then L.length == L.pLength
381  BOOLEAN length_pLength;
382  // if set, then posInL does not depend on L.length
383  BOOLEAN posInLDependsOnLength;
384  /*FALSE, if posInL == posInL10*/
385#ifdef HAVE_PLURAL
386  // set this flag to 1 to stop the product criteria
387  // use ALLOW_PROD_CRIT(strat) to test
388  BOOLEAN no_prod_crit;
389#define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
390#else
391#define ALLOW_PROD_CRIT(A) (1)
392#endif
393  char    redTailChange;
394  char    news;
395  char    newt;/*used for messageSets*/
396  char    noClearS;
397  char    completeReduce_retry;
398  char    overflow;
399
400  skStrategy();
401  ~skStrategy();
402
403  // return TObject corresponding to S[i]: assume that it exists
404  // i.e. no error checking is done
405  KINLINE TObject* S_2_T(int i);
406  // like S_2_T, except that NULL is returned if it can not be found
407  KINLINE TObject* s_2_t(int i);
408};
409
410void deleteHC(poly *p, int *e, int *l, kStrategy strat);
411void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
412void deleteInS (int i,kStrategy strat);
413void deleteInSSba (int i,kStrategy strat);
414void cleanT (kStrategy strat);
415static inline LSet initL (int nr=setmaxL)
416{ return (LSet)omAlloc(nr*sizeof(LObject)); }
417void deleteInL(LSet set, int *length, int j,kStrategy strat);
418void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
419void enterSBba (LObject p,int atS,kStrategy strat, int atR = -1);
420void enterSSba (LObject p,int atS,kStrategy strat, int atR = -1);
421void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
422void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
423int posInS (const kStrategy strat, const int length, const poly p,
424            const int ecart_p);
425int posInT0 (const TSet set,const int length,LObject &p);
426int posInT1 (const TSet set,const int length,LObject &p);
427int posInT2 (const TSet set,const int length,LObject &p);
428int posInT11 (const TSet set,const int length,LObject &p);
429int posInTSig (const TSet set,const int length,LObject &p);
430int posInT110 (const TSet set,const int length,LObject &p);
431int posInT13 (const TSet set,const int length,LObject &p);
432int posInT15 (const TSet set,const int length,LObject &p);
433int posInT17 (const TSet set,const int length,LObject &p);
434int posInT19 (const TSet set,const int length,LObject &p);
435int posInT_EcartpLength(const TSet set,const int length,LObject &p);
436
437#ifdef HAVE_MORE_POS_IN_T
438int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
439int posInT_FDegpLength(const TSet set,const int length,LObject &p);
440int posInT_pLength(const TSet set,const int length,LObject &p);
441#endif
442
443
444void reorderS (int* suc,kStrategy strat);
445int posInLF5C (const LSet set, const int length,
446               LObject* L,const kStrategy strat);
447int posInLSig (const LSet set, const int length,
448               LObject* L,const kStrategy strat);
449int posInL0 (const LSet set, const int length,
450             LObject* L,const kStrategy strat);
451int posInL11 (const LSet set, const int length,
452             LObject* L,const kStrategy strat);
453int posInL13 (const LSet set, const int length,
454             LObject* L,const kStrategy strat);
455int posInL15 (const LSet set, const int length,
456             LObject* L,const kStrategy strat);
457int posInL17 (const LSet set, const int length,
458             LObject* L,const kStrategy strat);
459int posInL10 (const LSet set, const int length,
460             LObject* L,const kStrategy strat);
461int posInL110 (const LSet set, const int length,
462             LObject* L,const kStrategy strat);
463KINLINE poly redtailBba (poly p,int pos,kStrategy strat,BOOLEAN normalize=FALSE);
464#ifdef HAVE_RINGS
465KINLINE poly redtailBba_Z (poly p,int pos,kStrategy strat);
466poly redtailBba_Z (LObject* L, int pos, kStrategy strat );
467#endif
468poly redtailBba (LObject *L, int pos,kStrategy strat,
469                 BOOLEAN withT = FALSE,BOOLEAN normalize=FALSE);
470poly redtailSba (LObject *L, int pos,kStrategy strat,
471                 BOOLEAN withT = FALSE,BOOLEAN normalize=FALSE);
472poly redtailBba (TObject *T, int pos,kStrategy strat);
473poly redtail (poly p,int pos,kStrategy strat);
474poly redtail (LObject *L,int pos,kStrategy strat);
475poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
476int redNF0 (LObject *P,kStrategy strat);
477poly redNFTail (poly h,const int sl,kStrategy strat);
478int redHoney (LObject* h, kStrategy strat);
479#ifdef HAVE_RINGS
480int redRing (LObject* h,kStrategy strat);
481int redRiloc (LObject* h,kStrategy strat);
482void enterExtendedSpoly(poly h,kStrategy strat);
483void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
484poly kCreateZeroPoly(long exp[], long cabsind, poly* t_p, ring leadRing, ring tailRing);
485long ind2(long arg);
486
487long ind_fact_2(long arg);
488long twoPow(long arg);
489ideal createG0();
490#endif
491int redLazy (LObject* h,kStrategy strat);
492int redHomog (LObject* h,kStrategy strat);
493int redSig (LObject* h,kStrategy strat);
494//adds hSig to be able to check with F5's criteria when entering pairs!
495void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
496void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
497void entersets (LObject h);
498void pairs ();
499void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
500void messageStat (int hilbcount,kStrategy strat);
501#ifdef KDEBUG
502void messageSets (kStrategy strat);
503#else
504#define messageSets(s)  do {} while (0)
505#endif
506
507void initEcartNormal (LObject* h);
508void initEcartBBA (LObject* h);
509void initS (ideal F, ideal Q,kStrategy strat);
510void initSL (ideal F, ideal Q,kStrategy strat);
511void initSLSba (ideal F, ideal Q,kStrategy strat);
512/*************************************************
513 * when initializing a new bunch of principal
514 * syzygies at the beginning of a new iteration
515 * step in a signature-based algorithm we
516 * compute ONLY the leading elements of those
517 * syzygies, NOT the whole syzygy
518 * NOTE: this needs to be adjusted for a more
519 * general approach on signature-based algorithms
520 ***********************************************/
521void initSyzRules (kStrategy strat);
522void updateS(BOOLEAN toT,kStrategy strat);
523void enterSyz (LObject p,kStrategy strat);
524void enterT (LObject p,kStrategy strat, int atT = -1);
525void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
526void HEckeTest (poly pp,kStrategy strat);
527void initBuchMoraCrit(kStrategy strat);
528void initSbaCrit(kStrategy strat);
529void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
530void initBuchMoraPos(kStrategy strat);
531void initSbaPos(kStrategy strat);
532void initBuchMora (ideal F, ideal Q,kStrategy strat);
533void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
534void exitBuchMora (kStrategy strat);
535void exitSba (kStrategy strat);
536void updateResult(ideal r,ideal Q,kStrategy strat);
537void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
538void kFreeStrat(kStrategy strat);
539void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
540void enterOnePairSig (int i,poly p,poly pSig,int ecart, int isFromQ,kStrategy strat, int atR);
541void chainCritNormal (poly p,int ecart,kStrategy strat);
542void chainCritSig (poly p,int ecart,kStrategy strat);
543BOOLEAN homogTest(polyset F, int Fmax);
544BOOLEAN newHEdge(kStrategy strat);
545BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
546BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
547KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
548BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
549BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
550BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
551// returns index of p in TSet, or -1 if not found
552int kFindInT(poly p, TSet T, int tlength);
553
554// return -1 if no divisor is found
555//        number of first divisor, otherwise
556int kFindDivisibleByInT(const TSet &T, const unsigned long* sevT,
557                        const int tl, const LObject* L, const int start=0);
558// same with S
559int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
560
561int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
562TObject*
563kFindDivisibleByInS(kStrategy strat, int pos, LObject* L, TObject *T,
564                    long ecart = LONG_MAX);
565
566/***************************************************************
567 *
568 * stuff to be inlined
569 *
570 ***************************************************************/
571
572KINLINE TSet initT ();
573KINLINE TObject** initR();
574KINLINE unsigned long* initsevT();
575KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
576KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
577KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
578KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing,  omBin bin);
579
580KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
581KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
582KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
583KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
584
585// if exp bound is not violated, return TRUE and
586//                               get m1 = LCM(LM(p1), LM(p2))/LM(p1)
587//                                   m2 = LCM(LM(p1), LM(p2))/LM(p2)
588// return FALSE and m1 == NULL, m2 == NULL     , otherwise
589KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
590                               poly &m1, poly &m2, const ring m_r);
591#ifdef HAVE_RINGS
592KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
593                               poly &m1, poly &m2, poly &lcm, const ring taiRing);
594#endif
595#ifdef KDEBUG
596// test strat
597BOOLEAN kTest(kStrategy strat);
598// test strat, and test that S is contained in T
599BOOLEAN kTest_TS(kStrategy strat);
600// test LObject
601BOOLEAN kTest_L(LObject* L, ring tailRing = NULL,
602                 BOOLEAN testp = FALSE, int lpos = -1,
603                 TSet T = NULL, int tlength = -1);
604// test TObject
605BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char TN = '?');
606// test set strat->SevS
607BOOLEAN kTest_S(kStrategy strat);
608#else
609#define kTest(A)        (TRUE)
610#define kTest_TS(A)     (TRUE)
611#define kTest_T(T)      (TRUE)
612#define kTest_S(T)      (TRUE)
613#define kTest_L(T)      (TRUE)
614#endif
615
616
617/***************************************************************
618 *
619 * From kstd2.cc
620 *
621 ***************************************************************/
622poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
623ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
624ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
625poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
626ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
627void initBba(ideal F,kStrategy strat);
628void initSba(ideal F,kStrategy strat);
629void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
630          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
631          intvec *w,intvec *hilb );
632
633/***************************************************************
634 *
635 * From kspoly.cc
636 *
637 ***************************************************************/
638// Reduces PR with PW
639// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
640// Changes: PR
641// Const:   PW
642// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
643// If strat != NULL, tailRing is changed if reduction would violate exp bound
644// of tailRing
645// Returns: 0 everything ok, no tailRing change
646//          1 tailRing has successfully changed (strat != NULL)
647//          2 no reduction performed, tailRing needs to be changed first
648//            (strat == NULL)
649//         -1 tailRing change could not be performed due to exceeding exp
650//            bound of currRing
651int ksReducePoly(LObject* PR,
652                 TObject* PW,
653                 poly spNoether = NULL,
654                 number *coef = NULL,
655                 kStrategy strat = NULL);
656
657// Reduces PR with PW
658// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
659// Changes: PR
660// Const:   PW
661// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
662// If strat != NULL, tailRing is changed if reduction would violate exp bound
663// of tailRing
664// Returns: 0 everything ok, no tailRing change
665//          1 tailRing has successfully changed (strat != NULL)
666//          2 no reduction performed, tailRing needs to be changed first
667//            (strat == NULL)
668//          3 no reduction performed, not sig-safe!!!
669//         -1 tailRing change could not be performed due to exceeding exp
670//            bound of currRing
671int ksReducePolySig(LObject* PR,
672                 TObject* PW,
673                 long idx,
674                 poly spNoether = NULL,
675                 number *coef = NULL,
676                 kStrategy strat = NULL);
677
678// Reduces PR at Current->next with PW
679// Assumes PR != NULL, Current contained in PR
680//         Current->next != NULL, LM(PW) devides LM(Current->next)
681// Changes: PR
682// Const:   PW
683// Return: see ksReducePoly
684int ksReducePolyTail(LObject* PR,
685                     TObject* PW,
686                     poly Current,
687                     poly spNoether = NULL);
688
689KINLINE int ksReducePolyTail(LObject* PR, TObject* PW, LObject* Red);
690
691// Creates S-Poly of Pair
692// Const:   Pair->p1, Pair->p2
693// Changes: Pair->p == S-Poly of p1, p2
694// Assume:  Pair->p1 != NULL && Pair->p2
695void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
696                   int use_buckets=0, ring tailRing=currRing,
697                   poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
698
699/*2
700* creates the leading term of the S-polynomial of p1 and p2
701* do not destroy p1 and p2
702* remarks:
703*   1. the coefficient is 0 (nNew)
704*   2. pNext is undefined
705*/
706poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
707
708
709// old stuff
710KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
711KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
712KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
713KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
714
715/***************************************************************
716 *
717 * Routines related for ring changes during std computations
718 *
719 ***************************************************************/
720// return TRUE and set m1, m2 to k_GetLcmTerms,
721//             if spoly creation of strat->P does not violate
722//             exponent bound of strat->tailRing
723//      FALSE, otherwise
724BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
725#ifdef HAVE_RINGS
726// return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
727//             exponent bound of strat->tailRing
728//      FALSE, otherwise
729BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
730#endif
731// change strat->tailRing and adjust all data in strat, L, and T:
732// new tailRing has larger exponent bound
733// do nothing and return FALSE if exponent bound increase would result in
734// larger exponent bound that that of currRing
735BOOLEAN kStratChangeTailRing(kStrategy strat,
736                             LObject* L = NULL, TObject* T = NULL,
737                             // take this as new_expbound: if 0
738                             // new expbound is 2*expbound of tailRing
739                             unsigned long new_expbound = 0);
740// initiate a change of the tailRing of strat -- should be called
741// right before main loop in bba
742void kStratInitChangeTailRing(kStrategy strat);
743
744/// Output some debug info about a given strategy
745void kDebugPrint(kStrategy strat);
746
747// getting sb order for sba computations
748ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
749
750KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
751  kStrategy strat);
752
753#include <kernel/kInline.h>
754
755/* shiftgb stuff */
756#include <kernel/shiftgb.h>
757
758poly pMove2CurrTail(poly p, kStrategy strat);
759
760poly pMoveCurrTail2poly(poly p, kStrategy strat);
761
762poly pCopyL2p(LObject h, kStrategy strat);
763
764void enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV);
765
766void initBuchMoraShift (ideal F,ideal Q,kStrategy strat);
767
768void enterOnePairManyShifts (int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV); // ok
769
770void enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV);
771
772void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS, int uptodeg, int lV); // ok
773
774void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR,int uptodeg, int lV);
775
776void initenterpairsShift (poly h,int k,int ecart,int isFromQ,kStrategy strat, int atR,int uptodeg, int lV);
777
778void updateSShift(kStrategy strat,int uptodeg,int lV);
779
780void initBbaShift(ideal F,kStrategy strat);
781
782poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
783
784int redFirstShift (LObject* h,kStrategy strat); // ok
785
786ideal freegb(ideal I, int uptodeg, int lVblock);
787
788ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV);
789// test syz strategy: // will be removed soon
790extern  int (*test_PosInT)(const TSet T,const int tl,LObject &h);
791extern  int (*test_PosInL)(const LSet set, const int length,
792                LObject* L,const kStrategy strat);
793#endif
Note: See TracBrowser for help on using the repository browser.