source: git/Singular/kutil.h @ 0f98876

fieker-DuValspielwiese
Last change on this file since 0f98876 was 0f98876, checked in by Olaf Bachmann <obachman@…>, 24 years ago
towards strat->tailRing git-svn-id: file:///usr/local/Singular/svn/trunk@4672 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 12.1 KB
Line 
1#ifndef KUTIL_H
2#define KUTIL_H
3/****************************************
4*  Computer Algebra System SINGULAR     *
5****************************************/
6/* $Id: kutil.h,v 1.37 2000-10-26 06:39:29 obachman Exp $ */
7/*
8* ABSTRACT: kernel: utils for kStd
9*/
10
11
12#include <string.h>
13#include "mod2.h"
14
15#include "structs.h"
16#include "omalloc.h"
17#include "ring.h"
18#include "pShallowCopyDelete.h"
19
20#define setmax 16
21
22#undef NO_KINLINE
23#if !defined(KDEBUG) && !defined(NO_INLINE)
24#define KINLINE inline
25#else
26#define KINLINE
27#define NO_KINLINE 1
28#endif
29
30typedef int* intset;
31
32class sTObject 
33{
34public:
35  poly p;       // Lm(p) \in currRing Tail(p) \in tailRing
36  poly t_p;     // t_p \in tailRing
37  ring tailRing;
38  int ecart, length, pLength;
39  poly max; // p_MaxExp(pNext(p))
40  unsigned long sev;
41 
42
43  // initialization
44  KINLINE void Init(ring r = currRing);
45  KINLINE sTObject(ring tailRing = currRing);
46  KINLINE sTObject(poly p, ring tailRing = currRing);
47  KINLINE sTObject(poly p, ring c_r, ring tailRing);
48  KINLINE sTObject(sTObject* T, int copy);
49
50  KINLINE void Set(ring r=currRing);
51  KINLINE void Set(poly p_in, ring r=currRing);
52  KINLINE void Set(poly p_in, ring c_r, ring t_r);
53
54  KINLINE void sTObject::Delete();
55 
56  // ring-dependent Lm access
57  KINLINE poly GetLm(); // equivalent to GetLmCurrRing
58  KINLINE poly GetLmCurrRing();
59  KINLINE poly GetLmTailRing();
60  KINLINE poly GetLm(ring r);
61
62  // makes sure that T.p exists
63  KINLINE void SetLmCurrRing();
64
65  // Iterations
66  KINLINE void LmDeleteAndIter();
67 
68  KINLINE int pFDeg();
69
70  // arithmetic
71  KINLINE void Mult_nn(number n);
72  KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin,
73                                 pShallowCopyDeleteProc p_shallow_copy_delete);
74};
75
76class sLObject : public sTObject
77{
78public:
79  poly  p1,p2; /*- the pair p comes from -*/
80 
81  poly  lcm;   /*- the lcm of p1,p2 -*/
82  kBucket_pt bucket;
83
84  // initialization
85  KINLINE void Init(ring tailRing = currRing);
86  KINLINE sLObject(ring tailRing = currRing);
87  KINLINE sLObject(poly p, ring tailRing = currRing);
88  KINLINE sLObject(poly p, ring c_r, ring tailRing);
89
90  // Iterations
91  KINLINE void LmDeleteAndIter();
92
93  // spoly related things
94  KINLINE void SetLmTail(poly lm, poly new_p, int use_bucket, ring r);
95  KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
96  KINLINE void Tail_Mult_nn(number n);
97  KINLINE poly GetP(omBin lmBin = NULL);
98  KINLINE void CanonicalizeP();
99
100  KINLINE void ShallowCopyDelete(ring new_tailRing, 
101                                 pShallowCopyDeleteProc p_shallow_copy_delete);
102};
103
104typedef class sTObject TObject;
105typedef class sLObject LObject;
106typedef TObject * TSet;
107typedef LObject * LSet;
108
109extern int HCord;
110
111class skStrategy;
112typedef skStrategy * kStrategy;
113class skStrategy
114{
115public:
116  kStrategy next;
117  int (*red)(LObject * L,kStrategy strat);
118  void (*initEcart)(LObject * L);
119  int (*posInT)(const TSet T,const int tl,const LObject &h);
120  int (*posInL)(const LSet set, const int length,
121                const LObject &L,const kStrategy strat);
122  void (*enterS)(LObject h, int pos,kStrategy strat);
123  void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
124  int (*posInLOld)(const LSet Ls,const int Ll,
125                   const LObject &Lo,const kStrategy strat);
126  pFDegProc pOldFDeg;
127  ideal Shdl;
128  ideal D; /*V(S) is in D(D)*/
129  ideal M; /*set of minimal generators*/
130  polyset S;
131  intset ecartS;
132  intset fromQ;
133  unsigned long* sevS;
134  TSet T;
135  LSet L;
136  LSet    B;
137  poly    kHEdge;
138  poly    kNoether;
139  BOOLEAN * NotUsedAxis;
140  LObject P;
141  poly tail;
142  leftv kIdeal;
143  intvec * kModW;
144  intvec * kHomW;
145  BOOLEAN *pairtest;/*used for enterOnePair*/
146  int cp,c3;
147  int sl,mu;
148  int tl,tmax;
149  int Ll,Lmax;
150  int Bl,Bmax;
151  int ak,LazyDegree,LazyPass;
152  int syzComp;
153  int HCord;
154  int lastAxis;
155  int newIdeal;
156  int minim;
157  BOOLEAN interpt;
158  BOOLEAN homog;
159  BOOLEAN kHEdgeFound;
160  BOOLEAN honey,sugarCrit;
161  BOOLEAN Gebauer,noTailReduction;
162  BOOLEAN fromT;
163  BOOLEAN noetherSet;
164  BOOLEAN update;
165  BOOLEAN posInLOldFlag;
166  BOOLEAN use_buckets;
167  ring tailRing;
168  omBin lmBin;
169  omBin tailBin;
170  /*FALSE, if posInL == posInL10*/
171  char    redTailChange;
172  char    news;
173  char    newt;/*used for messageSets*/
174
175  KINLINE skStrategy();
176  KINLINE ~skStrategy();
177};
178
179void deleteHC(poly *p, int *e, int *l, kStrategy strat);
180void deleteInS (int i,kStrategy strat);
181void cleanT (kStrategy strat);
182LSet initL ();
183void deleteInL(LSet set, int *length, int j,kStrategy strat);
184void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
185void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
186void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
187int posInS (polyset set,int length,poly p);
188int posInT0 (const TSet set,const int length,const LObject &p);
189int posInT1 (const TSet set,const int length,const LObject &p);
190int posInT2 (const TSet set,const int length,const LObject &p);
191int posInT11 (const TSet set,const int length,const LObject &p);
192int posInT13 (const TSet set,const int length,const LObject &p);
193int posInT15 (const TSet set,const int length,const LObject &p);
194int posInT17 (const TSet set,const int length,const LObject &p);
195int posInT19 (const TSet set,const int length,const LObject &p);
196void reorderS (int* suc,kStrategy strat);
197int posInL0 (const LSet set, const int length,
198             const LObject &L,const kStrategy strat);
199int posInL11 (const LSet set, const int length,
200             const LObject &L,const kStrategy strat);
201int posInL13 (const LSet set, const int length,
202             const LObject &L,const kStrategy strat);
203int posInL15 (const LSet set, const int length,
204             const LObject &L,const kStrategy strat);
205int posInL17 (const LSet set, const int length,
206             const LObject &L,const kStrategy strat);
207KINLINE poly redtailBba (poly p,int pos,kStrategy strat);
208poly redtailBba (LObject *L, int pos,kStrategy strat);
209poly redtailSyz (poly p,int pos,kStrategy strat);
210poly redtail (poly p,int pos,kStrategy strat);
211void enterpairs (poly h, int k, int ec, int pos,kStrategy strat);
212void entersets (LObject h);
213void pairs ();
214void message (int i,int* reduc,int* olddeg,kStrategy strat);
215void messageStat (int srmax,int lrmax,int hilbcount,kStrategy strat);
216void messageSets (kStrategy strat);
217void initEcartNormal (LObject* h);
218void initEcartBBA (LObject* h);
219void initS (ideal F, ideal Q,kStrategy strat);
220void initSL (ideal F, ideal Q,kStrategy strat);
221void updateS(BOOLEAN toT,kStrategy strat);
222void enterSBba (LObject p, int pos,kStrategy strat);
223void enterT (LObject p,kStrategy strat);
224void enterTBba (LObject p, int pos,kStrategy strat);
225void cancelunit (LObject* p);
226void HEckeTest (poly pp,kStrategy strat);
227void redtailS (poly* h,int maxIndex);
228void redtailMora (poly* h,int maxIndex);
229void initBuchMoraCrit(kStrategy strat);
230void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
231void initBuchMoraPos(kStrategy strat);
232void initBuchMora (ideal F, ideal Q,kStrategy strat);
233void exitBuchMora (kStrategy strat);
234void updateResult(ideal r,ideal Q,kStrategy strat);
235void completeReduce (kStrategy strat);
236void kFreeStrat(kStrategy strat);
237BOOLEAN homogTest(polyset F, int Fmax);
238BOOLEAN newHEdge(polyset S, int ak,kStrategy strat);
239
240/***************************************************************
241 *
242 * stuff to be inlined
243 *
244 ***************************************************************/
245
246KINLINE TSet initT ();
247KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
248KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
249KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
250KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing,  omBin bin);
251
252KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
253KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
254KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
255KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
256
257// if exp bound is not violated, return TRUE and
258//                               get m1 = LCM(LM(p1), LM(p2))/LM(p1)
259//                                   m2 = LCM(LM(p1), LM(p2))/LM(p2)
260// return FALSE and m1 == NULL, m2 == NULL     , otherwise
261KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, 
262                               poly &m1, poly &m2, const ring m_r);
263#ifdef KDEBUG
264// test strat
265BOOLEAN kTest(kStrategy strat);
266// test strat, and test that S is contained in T
267BOOLEAN kTest_TS(kStrategy strat);
268// test LObject
269BOOLEAN kTest_L(LObject* L, ring tailRing = NULL,
270                 BOOLEAN testp = FALSE, int lpos = -1,
271                 TSet T = NULL, int tlength = -1);
272// test TObject
273BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char T = '?');
274// test set strat->SevS
275BOOLEAN kTest_S(kStrategy strat);
276#else
277#define kTest(A)        ((void)0)
278#define kTest_TS(A)     ((void)0)
279#define kTest_T(T)      ((void)0)
280#define kTest_S(T)      ((void)0)
281#define kTest_L(T)      ((void)0)
282#endif
283
284
285/***************************************************************
286 *
287 * From kstd2.cc
288 *
289 ***************************************************************/
290ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
291poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
292ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
293void initBba(ideal F,kStrategy strat);
294
295/***************************************************************
296 *
297 * From kSpolys.cc
298 *
299 ***************************************************************/
300// Reduces PR with PW
301// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
302// Changes: PR
303// Const:   PW
304// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
305BOOLEAN ksReducePoly(LObject* PR,
306                     TObject* PW,
307                     poly spNoether = NULL,
308                     number *coef = NULL, 
309                     kStrategy strat = NULL);
310
311// Reduces PR at Current->next with PW
312// Assumes PR != NULL, Current contained in PR
313//         Current->next != NULL, LM(PW) devides LM(Current->next)
314// Changes: PR
315// Const:   PW
316BOOLEAN ksReducePolyTail(LObject* PR,
317                         TObject* PW,
318                         poly Current,
319                         poly spNoether = NULL);
320
321// Creates S-Poly of Pair
322// Const:   Pair->p1, Pair->p2
323// Changes: Pair->p == S-Poly of p1, p2
324// Assume:  Pair->p1 != NULL && Pair->p2
325void ksCreateSpoly(LObject* Pair, poly spNoether = NULL, 
326                   int use_buckets=0, ring tailRing=currRing, 
327                   poly m1 = NULL, poly m2 = NULL);
328
329
330/*2
331* creates the leading term of the S-polynomial of p1 and p2
332* do not destroy p1 and p2
333* remarks:
334*   1. the coefficient is 0 (nNew)
335*   2. pNext is undefined
336*/
337poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
338
339
340/*
341* input - output: a, b
342* returns:
343*   a := a/gcd(a,b), b := b/gcd(a,b)
344*   and return value
345*       0  ->  a != 1,  b != 1
346*       1  ->  a == 1,  b != 1
347*       2  ->  a != 1,  b == 1
348*       3  ->  a == 1,  b == 1
349*   this value is used to control the spolys
350*/
351int ksCheckCoeff(number *a, number *b);
352
353// old stuff
354KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
355KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
356KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
357KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
358
359/***************************************************************
360 *
361 * Routines related for ring changes during std computations
362 *
363 ***************************************************************/
364// return TRUE and set m1, m2 to k_GetLcmTerms,
365//             if spoly creation of strat->P does not violate
366//             exponent bound of strat->tailRing
367//      FALSE, otherwise
368BOOLEAN kCheckSpolyCreation(kStrategy strat, poly &m1, poly &m2);
369// change the strat such that strat strat->tailRing == new_tailRing
370void kStratChangeTailRing(kStrategy strat, ring new_tailRing);
371// initiate a change of the tailRing of strat -- should be called
372// right before main loop in bba
373void kStratInitChangeTailRing(kStrategy strat);
374
375#include "kInline.cc"
376
377
378#endif
Note: See TracBrowser for help on using the repository browser.