My Project
kLiftstd.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT - Kernel: alg. of Buchberger
6 */
7 
8 #include "kernel/mod2.h"
9 
10 // define if no buckets should be used
11 // #define NO_BUCKETS
12 
13 #include "kernel/GBEngine/kutil.h"
14 #include "misc/options.h"
15 #include "kernel/polys.h"
16 #include "kernel/ideals.h"
17 #include "kernel/GBEngine/kstd1.h"
18 #include "kernel/GBEngine/khstd.h"
19 #include "polys/kbuckets.h"
20 #include "polys/prCopy.h"
21 #include "polys/weight.h"
22 #include "misc/intvec.h"
23 #ifdef HAVE_PLURAL
24 #include "polys/nc/nc.h"
25 #endif
26 
27 static poly kSplitAt(int k,TObject* h,kStrategy strat)
28 {
29  poly p;
30  if (h->t_p==NULL)
31  {
32  if (currRing!=strat->tailRing)
33  {
34  h->t_p=k_LmInit_currRing_2_tailRing(h->p, strat->tailRing);
35  p=h->t_p;
36  }
37  else
38  p=h->p;
39  }
40  else
41  p=h->t_p;
42  if (p->next==NULL) return NULL;
43  const ring tailRing=strat->tailRing;
44  while(p_GetComp(p->next,tailRing)<=k)
45  {
46  pIter(p);
47  if ((p==NULL)||(p->next==NULL))
48  {
49  h->pLength=0; // force re-computation
50  return NULL;
51  }
52  }
53  poly t=p->next;
54  p->next=NULL;
55  h->pLength=0; // force re-computation
56  return t;
57 }
58 static poly kSplitAt(int k,LObject* h,kStrategy strat)
59 {
60  poly p,pr,t=NULL;
61  int l;
62  if (h->bucket!=NULL)
63  {
64  kBucketClear(h->bucket,&p,&l);
65  pr=p;
66  }
67  else
68  {
69  if (h->t_p==NULL)
70  {
71  if (currRing!=strat->tailRing)
72  {
73  h->t_p=k_LmInit_currRing_2_tailRing(h->p, strat->tailRing);
74  p=h->t_p;
75  }
76  else
77  p=h->p;
78  }
79  else
80  p=h->t_p;
81  }
82  const ring tailRing=strat->tailRing;
83  if(p==NULL) return NULL;
84  if (p_GetComp(p,tailRing)>k)
85  {
86  return p;
87  }
88  if (p->next==NULL)
89  {
90  goto finish;
91  }
92  while(p_GetComp(p->next,tailRing)<=k)
93  {
94  pIter(p);
95  if (p->next==NULL) break;
96  }
97  t=p->next;
98  p->next=NULL;
99 finish:
100  if (h->bucket!=NULL)
101  {
102  l=pLength(pr);
103  kBucketInit(h->bucket,pr,l);
104  }
105  return t;
106 }
107 static void kAppend(poly t,TObject* h)
108 {
109  poly p;
110  if (h->t_p!=NULL)
111  p=h->t_p;
112  else
113  p=h->p;
114  while(p->next!=NULL) pIter(p);
115  p->next=t;
116  if ((h->p!=NULL)&&(h->t_p!=NULL)) pNext(h->p)=pNext(h->t_p);
117 }
118 static poly lazyComp(number* A, poly* M,poly* T,int index,poly s,int *l,const ring tailR)
119 {
120  if ((TEST_OPT_PROT) && (index>0)) { Print("<%d>",index+1); mflush(); }
121  kBucket_pt b=kBucketCreate(tailR);
122  kBucketInit(b,s,pLength(s));
123  int cnt=RED_CANONICALIZE;
124  for(int i=0;i<index;i++)
125  {
126  kBucket_Mult_n(b,A[i]);
127  n_Delete(&A[i],tailR->cf);
128  poly tt=T[i];
129  if (tt!=NULL)
130  {
131  cnt--;
132  int dummy=pLength(tt);
133  kBucket_Minus_m_Mult_p(b,M[i],tt,&dummy);
134  }
135  p_Delete(&M[i],tailR);
136  if (UNLIKELY(cnt==0))
137  {
138  cnt=RED_CANONICALIZE;
140  }
141  }
142  poly p;
143  kBucketClear(b,&p,l);
144  kBucketDestroy(&b);
145  return p;
146 }
147 /*2
148 * reduction procedure for the sugar-strategy (honey)
149 * reduces h with elements from T choosing first possible
150 * element in T with respect to the given ecart
151 */
153 {
154  if (strat->tl<0) return 1;
155  assume(h->FDeg == h->pFDeg());
157  poly h_p;
158  int i,j,pass,ei, ii, h_d,ci;
159  unsigned long not_sev;
160  long reddeg,d;
161  number A[500];
162  poly C[500];
163  poly T[500];
164  memset(T,0,sizeof(T));
165  memset(C,0,sizeof(T));
166  const ring tailRing=strat->tailRing;
167 
168  pass = j = 0;
169  d = reddeg = h->GetpFDeg() + h->ecart;
170  h->SetShortExpVector();
171  int li;
172  h_p = h->GetLmTailRing();
173  not_sev = ~ h->sev;
174 
175  // split h into mina part (h) and tail (h_tail)
176  poly h_tail=kSplitAt(strat->syzComp,h,strat);
177  // fix h-pLength
178  h->pLength=0;
179  // remove content
180  //number cont;
181  //p_Content_n(h_p,cont,strat->tailRing);
182  //if (!n_IsOne(cont,strat->tailRing))
183  // h_tail=p_Div_nn(h_tail,cont,tailRing);
184 
185  h->PrepareRed(strat->use_buckets);
186  loop
187  {
188  j=kFindDivisibleByInT(strat, h);
189  if (j < 0)
190  {
191  // lazy computation:
192  int l;
193  poly p=lazyComp(A,C,T,pass,h_tail,&l,strat->tailRing);
194  kBucket_Add_q(h->bucket,p,&l);
195  return 1;
196  }
197 
198  ei = strat->T[j].ecart;
199  li = strat->T[j].pLength;
200  ci = nSize(pGetCoeff(strat->T[j].p));
201  ii = j;
202  /*
203  * the polynomial to reduce with (up to the moment) is;
204  * pi with ecart ei (T[ii])
205  */
206  i = j;
207  if (TEST_OPT_LENGTH)
208  {
209  if (li<=0) li=strat->T[j].GetpLength();
210  if (li>1)
211  loop
212  {
213  /*- possible with respect to ecart, minimal nSize -*/
214  i++;
215  if (i > strat->tl)
216  break;
217  //if (ei < h->ecart)
218  // break;
219  if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
220  || ((strat->T[i].ecart <= h->ecart)
221  && (strat->T[i].pLength <= li)
222  && (nSize(pGetCoeff(strat->T[i].p)) <ci)))
223  &&
224  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
225  h_p, not_sev, tailRing))
226  {
227  /*
228  * the polynomial to reduce with is now;
229  */
230  ei = strat->T[i].ecart;
231  li = strat->T[i].pLength;
232  if (li<=0) li=strat->T[i].GetpLength();
233  ii = i;
234  if (li==1) break;
235  }
236  }
237  }
238 
239  /*
240  * end of search: have to reduce with pi
241  */
242 #ifdef KDEBUG
243  if (TEST_OPT_DEBUG)
244  {
245  PrintS("red:");
246  h->wrp();
247  Print("\nwith T[%d]:",ii);
248  strat->T[ii].wrp();
249  }
250 #endif
251  assume(strat->fromT == FALSE);
252 
253  //strat->T[ii].pCleardenom();
254  // split T[ii]:
255  // remember pLength of strat->T[ii]
256  int l_orig=strat->T[ii].pLength;
257  // split strat->T[ii]
258  poly T_tail=kSplitAt(strat->syzComp,&strat->T[ii],strat);
259  h->pLength=0; // force re-computation of length
260  ksReducePoly(h,&(strat->T[ii]),NULL,&A[pass],&C[pass], strat);
261  // restore T[ii]:
262  kAppend(T_tail,&strat->T[ii]);
263  strat->T[ii].pLength=l_orig;
264  // store T_tail
265  T[pass]=T_tail;
266  // delayed computation: A[pass]*tail-M[pass]*T[pass]
267 #ifdef KDEBUG
268  if (TEST_OPT_DEBUG)
269  {
270  PrintS("\nto:");
271  h->wrp();
272  PrintLn();
273  }
274 #endif
275  if(h->IsNull())
276  {
277  // clean up A,C,h_tail:
278  for(int i=0;i<=pass;i++)
279  {
280  n_Delete(&A[i],tailRing->cf);
281  p_Delete(&C[i],tailRing);
282  }
283  p_Delete(&h_tail,tailRing);
284  kDeleteLcm(h);
285  h->Clear();
286  return 0;
287  }
288  h->SetShortExpVector();
289  not_sev = ~ h->sev;
290  h_d = h->SetpFDeg();
291  /* compute the ecart */
292  if (ei <= h->ecart)
293  h->ecart = d-h_d;
294  else
295  h->ecart = d-h_d+ei-h->ecart;
296 
297  /*
298  * try to reduce the s-polynomial h
299  *test first whether h should go to the lazyset L
300  *-if the degree jumps
301  *-if the number of pre-defined reductions jumps
302  */
303  pass++;
304  d = h_d + h->ecart;
305  if (pass%RED_CANONICALIZE==0) kBucketCanonicalize(h->bucket);
306  }
307 }
#define UNLIKELY(X)
Definition: auxiliary.h:404
#define FALSE
Definition: auxiliary.h:96
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
CanonicalForm b
Definition: cfModGcd.cc:4105
int syzComp
Definition: kutil.h:357
ring tailRing
Definition: kutil.h:346
TSet T
Definition: kutil.h:327
int tl
Definition: kutil.h:353
unsigned long * sevT
Definition: kutil.h:326
char use_buckets
Definition: kutil.h:387
char fromT
Definition: kutil.h:383
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
#define Print
Definition: emacs.cc:80
const CanonicalForm int s
Definition: facAbsFact.cc:51
int j
Definition: facHensel.cc:110
STATIC_VAR jList * T
Definition: janet.cc:30
STATIC_VAR Poly * h
Definition: janet.cc:971
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin tailBin)
Definition: kInline.h:927
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:152
static poly lazyComp(number *A, poly *M, poly *T, int index, poly s, int *l, const ring tailR)
Definition: kLiftstd.cc:118
static void kAppend(poly t, TObject *h)
Definition: kLiftstd.cc:107
static poly kSplitAt(int k, TObject *h, kStrategy strat)
Definition: kLiftstd.cc:27
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:722
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:598
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.
Definition: kbuckets.cc:660
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
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
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
#define RED_CANONICALIZE
Definition: kutil.h:36
class sTObject TObject
Definition: kutil.h:57
class sLObject LObject
Definition: kutil.h:58
#define assume(x)
Definition: mod2.h:387
#define p_GetComp(p, r)
Definition: monomials.h:64
#define pIter(p)
Definition: monomials.h:37
#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 nSize(n)
Definition: numbers.h:39
#define NULL
Definition: omList.c:12
#define TEST_OPT_IDLIFT
Definition: options.h:129
#define TEST_OPT_LENGTH
Definition: options.h:131
#define TEST_OPT_PROT
Definition: options.h:103
#define TEST_OPT_DEBUG
Definition: options.h:108
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
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 void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
static unsigned pLength(poly a)
Definition: p_polys.h:191
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatiblity layer for legacy polynomial operations (over currRing)
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
#define mflush()
Definition: reporter.h:58
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
#define loop
Definition: structs.h:80