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
kSplitAt(int k,TObject * h,kStrategy strat)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 }
kSplitAt(int k,LObject * h,kStrategy strat)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 }
kAppend(poly t,TObject * h)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 }
lazyComp(number * A,poly * M,poly * T,int index,poly s,int * l,const ring tailR)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;
139 kBucketCanonicalize(b);
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 */
redLiftstd(LObject * h,kStrategy strat)152 int redLiftstd (LObject* h, kStrategy strat)
153 {
154 if (strat->tl<0) return 1;
155 assume(h->FDeg == h->pFDeg());
156 assume(TEST_OPT_IDLIFT);
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 }
308