kstdfac.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT - Kernel: factorizing alg. of Buchberger
6 */
7 
8 
9 
10 
11 #include <kernel/mod2.h>
12 #include <omalloc/omalloc.h>
13 #include <misc/options.h>
14 #include <kernel/polys.h>
15 #include <kernel/ideals.h>
16 #include <kernel/GBEngine/kutil.h>
17 #include <kernel/GBEngine/kstd1.h>
18 #include <kernel/GBEngine/khstd.h>
19 //#include "cntrlc.h"
20 #include <polys/weight.h>
21 //#include "ipshell.h"
22 #include <misc/intvec.h>
23 #include <polys/clapsing.h>
24 #include <kernel/ideals.h>
26 
27 int strat_nr=0;
28 /*3
29 * copy o->T to n->T, assumes that n->S is already copied
30 */
31 static void copyT (kStrategy o,kStrategy n)
32 {
33  int i,j;
34  poly p;
35  TSet t=(TSet)omAlloc0(o->tmax*sizeof(TObject));
36  TObject** r = (TObject**)omAlloc0(o->tmax*sizeof(TObject*));
37 
38  for (j=0; j<=o->tl; j++)
39  {
40  t[j] = o->T[j];
41  r[t[j].i_r] = &t[j];
42  p = o->T[j].p;
43  i = -1;
44  loop
45  {
46  i++;
47  if (i>o->sl)
48  {
49  t[j].p=pCopy(p);
50  break;
51  }
52  if (p == o->S[i])
53  {
54  t[j].p=n->S[i];
55  break;
56  }
57  }
58  t[j].t_p = NULL; // ?? or t[j].p ??
59  t[j].max_exp = NULL; // ?? or p_GetMaxExpP(t[j].t_p,o->tailRing); ??
60  t[j].pLength = pLength(p);
61  }
62  n->T=t;
63  n->R=r;
64 }
65 
66 /*3
67 * copy o->L to n->L, assumes that n->T,n->tail is already copied
68 */
69 static void copyL (kStrategy o,kStrategy n)
70 {
71  int i,j;
72  poly p;
73  LSet l=(LSet)omAlloc(o->Lmax*sizeof(LObject));
74 
75  for (j=0; j<=o->Ll; j++)
76  {
77  l[j] = o->L[j];
78  // copy .p ----------------------------------------------
79  if (pNext(o->L[j].p)!=o->tail)
80  l[j].p=pCopy(o->L[j].p);
81  else
82  {
83  l[j].p=pHead(o->L[j].p);
84  pNext(l[j].p)=n->tail;
85  }
86  // copy .lcm ----------------------------------------------
87  if (o->L[j].lcm!=NULL)
88  l[j].lcm=pLmInit(o->L[j].lcm);
89  else
90  l[j].lcm=NULL;
91  l[j].p1=NULL;
92  l[j].p2=NULL;
93  l[j].t_p = NULL;
94 
95  // copy .p1 , i_r1----------------------------------------------
96  p = o->L[j].p1;
97  i = -1;
98  loop
99  {
100  if(p==NULL) break;
101  i++;
102  if(i>o->tl)
103  {
104  Warn("poly p1 not found in T:");wrp(p);PrintLn();
105  l[j].p1=pCopy(p);
106  l[j].i_r1=-1;
107  break;
108  }
109  if (p == o->T[i].p)
110  {
111  l[j].p1=n->T[i].p;
112  l[j].i_r1=n->T[i].i_r;
113  break;
114  }
115  }
116 
117  // copy .p2 , i_r2----------------------------------------------
118  p = o->L[j].p2;
119  i = -1;
120  loop
121  {
122  if(p==NULL) break;
123  i++;
124  if(i>o->tl)
125  {
126  Warn("poly p2 not found in T:");wrp(p);PrintLn();
127  l[j].p2=pCopy(p);
128  l[j].i_r2=-1;
129  break;
130  }
131  if (p == o->T[i].p)
132  {
133  l[j].p2=n->T[i].p;
134  l[j].i_r2=n->T[i].i_r;
135  break;
136  }
137  }
138 
139  // copy .ecart ---------------------------------------------
140  l[j].ecart=o->L[j].ecart;
141  // copy .length --------------------------------------------
142  l[j].length=o->L[j].length;
143  // copy .pLength -------------------------------------------
144  l[j].pLength=o->L[j].pLength;
145  // copy .sev -----------------------------------------------
146  l[j].sev=o->L[j].sev;
147  l[j].i_r = o->L[j].i_r;
148  //l[j].i_r1 = o->L[j].i_r1;
149  //l[j].i_r2 = o->L[j].i_r2;
150  }
151  n->L=l;
152 }
153 
155 {
156  // int i;
157  kTest_TS(o);
158  kStrategy s=new skStrategy;
159  s->next=NULL;
160  s->red=o->red;
161  s->initEcart=o->initEcart;
162  s->posInT=o->posInT;
163  s->posInL=o->posInL;
164  s->enterS=o->enterS;
166  s->posInLOld=o->posInLOld;
168  s->chainCrit=o->chainCrit;
169  s->Shdl=idCopy(o->Shdl);
170  s->S=s->Shdl->m;
171  s->tailRing = o->tailRing;
172  if (o->D!=NULL) s->D=idCopy(o->D);
173  else s->D=NULL;
174  s->ecartS=(int *)omAlloc(IDELEMS(o->Shdl)*sizeof(int));
175  memcpy(s->ecartS,o->ecartS,IDELEMS(o->Shdl)*sizeof(int));
176  s->sevS=(unsigned long *)omAlloc(IDELEMS(o->Shdl)*sizeof(unsigned long));
177  memcpy(s->sevS,o->sevS,IDELEMS(o->Shdl)*sizeof(unsigned long));
178  s->S_2_R=(int*)omAlloc(IDELEMS(o->Shdl)*sizeof(int));
179  memcpy(s->S_2_R,o->S_2_R,IDELEMS(o->Shdl)*sizeof(int));
180  s->sevT=(unsigned long *)omAlloc(o->tmax*sizeof(unsigned long));
181  memcpy(s->sevT,o->sevT,o->tmax*sizeof(unsigned long));
182  if(o->fromQ!=NULL)
183  {
184  s->fromQ=(int *)omAlloc(IDELEMS(o->Shdl)*sizeof(int));
185  memcpy(s->fromQ,o->fromQ,IDELEMS(o->Shdl)*sizeof(int));
186  }
187  else
188  s->fromQ=NULL;
189  copyT(o,s);//s->T=...
190  s->tail = pInit();
191  copyL(o,s);//s->L=...
192  s->B=initL();
193  s->kHEdge=pCopy(o->kHEdge);
194  s->kNoether=pCopy(o->kNoether);
195  if (o->NotUsedAxis!=NULL)
196  {
197  s->NotUsedAxis=(BOOLEAN *)omAlloc(currRing->N*sizeof(BOOLEAN));
198  memcpy(s->NotUsedAxis,o->NotUsedAxis,currRing->N*sizeof(BOOLEAN));
199  }
200  //s->P=s->L[s->Ll+1];
201  s->P.Init(o->tailRing);
202  s->update=o->update;
204  s->kModW = o->kModW;
205 // if (o->kModW!=NULL)
206 // s->kModW=ivCopy(o->kModW);
207 // else
208 // s->kModW=NULL;
209  s->pairtest=NULL;
210  s->sl=o->sl;
211  s->mu=o->mu;
212  s->tl=o->tl;
213  s->tmax=o->tmax;
214  s->Ll=o->Ll;
215  s->Lmax=o->Lmax;
216  s->Bl=-1;
217  s->Bmax=setmaxL;
218  s->ak=o->ak;
219  s->syzComp=o->syzComp;
220  s->LazyPass=o->LazyPass;
221  s->LazyDegree=o->LazyDegree;
222  s->HCord=o->HCord;
223  s->lastAxis=o->lastAxis;
224  s->interpt=o->interpt;
225  s->homog=o->homog;
226  s->news=o->news;
227  s->newt=o->newt;
228  s->kHEdgeFound=o->kHEdgeFound;
229  s->honey=o->honey;
230  s->sugarCrit=o->sugarCrit;
231  s->Gebauer=o->Gebauer;
233  s->fromT=o->fromT;
234  s->noetherSet=o->noetherSet;
235 #ifdef HAVE_SHIFTBBA
236  s->lV=o->lV;
237 #endif
238 #ifdef HAVE_PLURAL
240 #endif
241  kTest_TS(s);
242  return s;
243 }
244 
245 BOOLEAN k_factorize(poly p,ideal &rfac, ideal &fac_copy)
246 {
247  int facdeg=currRing->pFDeg(p,currRing);
248  ideal fac=singclap_factorize(pCopy(p),NULL,1,currRing);
249  int fac_elems;
250  fac_elems=IDELEMS(fac);
251  rfac=fac;
252  fac_copy=idInit(fac_elems,1);
253 
254  if ((fac_elems!=1)||(facdeg!=currRing->pFDeg(fac->m[0],currRing)))
255  {
256  if (TEST_OPT_DEBUG)
257  {
258  Print("%d factors:\n",fac_elems);
259  pWrite(p); PrintS(" ->\n");
260  int ii=fac_elems;
261  while(ii>0) { ii--;pWrite(fac->m[ii]); }
262  }
263  else if (TEST_OPT_PROT)
264  {
265  int ii=fac_elems;
266  if (ii>1)
267  {
268  while(ii>0) { PrintS("F"); ii--; }
269  }
270  }
271  return TRUE;
272  }
273  else
274  {
275  pDelete(&(fac->m[0]));
276  fac->m[0]=pCopy(p);
277  }
278  return FALSE;
279 }
280 
281 static void completeReduceFac (kStrategy strat, ideal_list FL)
282 {
283  int si;
284 
285  strat->noTailReduction = FALSE;
286  if (TEST_OPT_PROT)
287  {
288  PrintLn();
289 // if (timerv) writeTime("standard base computed:");
290  }
291  if (TEST_OPT_PROT)
292  {
293  Print("(S:%d)",strat->sl);mflush();
294  }
295  for (si=strat->sl; si>0; si--)
296  {
297  strat->S[si] = redtailBba(strat->S[si],si-1,strat);
299  {
300  strat->S[si]=p_Cleardenom(strat->S[si], currRing);
301  }
302  if (TEST_OPT_PROT)
303  {
304  PrintS("-");mflush();
305  }
306  int i;
307  if (strat->redTailChange)
308  {
309  for(i=strat->tl;i>=0;i--)
310  {
311  strat->initEcart(&strat->T[i]);
312  }
313  }
314  ideal fac;
315  ideal fac_copy;
316 
317  if (!k_factorize(strat->S[si],fac,fac_copy))
318  {
319  idDelete(&fac);
320  idDelete(&fac_copy);
321  continue;
322  }
323 
324  deleteInS(si,strat);
325 
326  for(i=IDELEMS(fac)-1;i>=0;i--)
327  {
328  kStrategy n=strat;
329  if (i>=1)
330  {
331  n=kStratCopy(strat); // includes: memset(&n->P,0,sizeof(n->P));
332  n->next=strat->next;
333  strat->next=n;
334  }
335  else
336  {
337  n->P.Init(strat->tailRing);
338  }
339 
340  n->P.p=fac->m[i];
341  n->P.pLength=0;
342  n->initEcart(&n->P);
343  /* enter P.p into s and L */
344  int pos;
345  if (n->sl==-1) pos=0;
346  else pos=posInS(n,n->sl,n->P.p,n->P.ecart);
348  {
349  n->P.p = redtailBba(n->P.p,pos-1,n);
350  n->P.pCleardenom();
351  }
352  else
353  {
354  pNorm(n->P.p);
355  n->P.p = redtailBba(n->P.p,pos-1,n);
356  }
357  n->P.pLength=0;
358  if (TEST_OPT_DEBUG)
359  {
360  Print("new s(%d)->S:",n->nr);
361  pWrite(n->P.p);
362  }
363  enterpairs(n->P.p,n->sl,n->P.ecart,pos,n);
364  enterT(n->P,n);
365  n->enterS(n->P,pos,n, n->tl);
366 
367  /* construct D */
368  if (IDELEMS(fac)>1)
369  {
370  if (n->D==NULL)
371  {
372  n->D=idCopy(fac_copy);
373  idSkipZeroes(n->D);
374  }
375  else
376  {
377  idTest(n->D);
378  ideal r=idAdd(n->D,fac_copy);
379  idDelete(&n->D);
380  n->D=r;
381  }
382  if (TEST_OPT_DEBUG)
383  {
384  Print("new s(%d)->D:\n",n->nr);
385  iiWriteMatrix((matrix)n->D,"D",1,currRing,0);
386  PrintLn();
387  }
388  }
389 
390  fac_copy->m[i]=pCopy(fac->m[i]);
391  fac->m[i]=NULL;
392 
393  /* check for empty sets */
394  if (n->D!=NULL)
395  {
396  int j=IDELEMS(n->D)-1;
397  while(j>=0)
398  {
399  if (n->D->m[j]!=NULL)
400  {
401  poly r=kNF(n->Shdl,NULL,n->D->m[j],0,KSTD_NF_LAZY | KSTD_NF_NONORM);
402  if (r==NULL)
403  {
404  if (TEST_OPT_DEBUG)
405  {
406  Print("empty set s(%d) because D[%d]:",n->nr,j);
407  pWrite(n->D->m[j]);
408  messageSets(n);
409  }
410  while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
411  while (n->tl >= 0)
412  {
413  int i=n->sl;
414  while (i>=0)
415  {
416  if (n->S[i]==n->T[n->tl].p)
417  {
418  n->T[n->tl].p=NULL; n->S[i]=NULL;
419  break;
420  }
421  i--;
422  }
423  pDelete(&n->T[n->tl].p);
424  n->tl--;
425  }
426  memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
427  n->sl=-1;
428  if (strat==n) si=-1;
429  break;
430  }
431  else
432  {
433  pDelete(&r);
434  }
435  }
436  j--;
437  }
438  }
439  /* check for empty sets */
440  {
441  ideal_list Lj=FL;
442  while (Lj!=NULL)
443  {
444  if ((n->sl>=0)&&(n->S[0]!=NULL))
445  {
446  ideal r=kNF(n->Shdl,NULL,Lj->d,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
447  if (idIs0(r))
448  {
449  if (TEST_OPT_DEBUG)
450  {
451  Print("empty set because:L[%p]\n",(void *)Lj);
452  iiWriteMatrix((matrix)Lj->d,"L",1,currRing,0);
453  }
454  while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
455  while (n->tl >= 0)
456  {
457  int i=n->sl;
458  while (i>=0)
459  {
460  if (n->S[i]==n->T[n->tl].p)
461  {
462  n->T[n->tl].p=NULL; n->S[i]=NULL;
463  break;
464  }
465  i--;
466  }
467  pDelete(&n->T[n->tl].p);
468  n->tl--;
469  }
470  memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
471  n->sl=-1;
472  if (strat==n) si=-1;
473  idDelete(&r);
474  break;
475  }
476  idDelete(&r);
477  }
478  Lj=Lj->next;
479  }
480  }
481  } /* for */
482  for(i=0;i<IDELEMS(fac);i++) fac->m[i]=NULL;
483  idDelete(&fac);
484  idDelete(&fac_copy);
485  if ((strat->Ll>=0) && (strat->sl>=0)) break;
486  else si=strat->sl+1;
487  }
488 }
489 
490 ideal bbafac (ideal /*F*/, ideal Q,intvec */*w*/,kStrategy strat, ideal_list FL)
491 {
492  int olddeg,reduc=0;
493  int red_result = 1;
494  reduc = olddeg = 0;
495  /* compute------------------------------------------------------- */
496  if ((strat->Ll==-1) && (strat->sl>=0))
497  {
498  if (TEST_OPT_REDSB) completeReduceFac(strat,FL);
499  }
500  kTest_TS(strat);
501  while (strat->Ll >= 0)
502  {
503  if (TEST_OPT_DEBUG) messageSets(strat);
504  if (strat->Ll== 0) strat->interpt=TRUE;
506  && ((strat->honey
507  && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
508  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
509  {
510  /*
511  *stops computation if
512  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
513  *a predefined number Kstd1_deg
514  */
515  while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
516  break;
517  }
518  /* picks the last element from the lazyset L */
519  strat->P = strat->L[strat->Ll];
520  strat->Ll--;
521  if (pNext(strat->P.p) == strat->tail)
522  {
523  /* deletes the short spoly and computes */
524  pLmFree(strat->P.p);
525  /* the real one */
526  strat->P.p = ksOldCreateSpoly(strat->P.p1,
527  strat->P.p2,
528  strat->kNoether);
529  }
530  if (strat->honey)
531  {
532  if (TEST_OPT_PROT)
533  message(strat->P.ecart+currRing->pFDeg(strat->P.p,currRing),&olddeg,&reduc,strat, red_result);
534  }
535  else
536  {
537  if (TEST_OPT_PROT)
538  message(currRing->pFDeg(strat->P.p,currRing),&olddeg,&reduc,strat, red_result);
539  }
540  /* reduction of the element chosen from L */
541  kTest_TS(strat);
542  red_result = strat->red(&strat->P,strat);
543  if (strat->P.p != NULL)
544  {
545  /* statistic */
546  if (TEST_OPT_PROT) PrintS("s");
547  ideal fac;
548  ideal fac_copy;
549 
550  if (!k_factorize(strat->P.p,fac,fac_copy))
551  {
553  {
554  strat->P.p = redtailBba(strat->P.p,strat->sl,strat);
555  if (strat->redTailChange) strat->P.pCleardenom();
556  }
557  else
558  {
559  pNorm(strat->P.p);
560  strat->P.p = redtailBba(strat->P.p,strat->sl,strat);
561  }
562  if (strat->redTailChange)
563  {
564  idDelete(&fac);
565  idDelete(&fac_copy);
566  if (!k_factorize(strat->P.p,fac,fac_copy))
567  {
568  pDelete(&(fac->m[0]));
569  fac->m[0]=strat->P.p;
570  strat->P.p=NULL;
571  }
572  else
573  {
574  pDelete(&strat->P.p);
575  }
576  }
577  }
578  if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
579  int i;
580 
581  for(i=IDELEMS(fac)-1;i>=0;i--)
582  {
583  int ii;
584  kStrategy n=strat;
585  if (i>=1)
586  {
587  n=kStratCopy(strat); // includes memset(&n->P,0,sizeof(n->P));
588  kTest_TS(n);
589  n->next=strat->next;
590  strat->next=n;
591  }
592  else
593  {
594  n->P.Init(strat->tailRing);
595  }
596 
597  n->P.pLength=0;
598  n->P.p=fac->m[i];
599  n->initEcart(&n->P);
600  kTest_TS(n);
601 
602  /* enter P.p into s and L */
603  int pos;
604  if (n->sl==-1) pos=0;
605  else pos=posInS(n,n->sl,n->P.p,n->P.ecart);
606 
607  // we have already reduced all elements from fac....
609  {
610  n->P.p = redtailBba(n->P.p,pos-1,n);
611  if (n->redTailChange)
612  {
613  n->P.pCleardenom();
614  n->P.pLength=0;
615  }
616  }
617  else
618  {
619  pNorm(n->P.p);
620  n->P.p = redtailBba(n->P.p,pos-1,n);
621  if (n->redTailChange)
622  {
623  n->P.pLength=0;
624  }
625  }
626  kTest_TS(n);
627 
628  if (TEST_OPT_DEBUG)
629  {
630  PrintS("new s:");
631  wrp(n->P.p);
632  PrintLn();
633  }
634  enterpairs(n->P.p,n->sl,n->P.ecart,pos,n);
635  enterT(n->P,n);
636  n->enterS(n->P,pos,n, n->tl);
637  {
638  int i=n->Ll;
639  for(;i>=0;i--)
640  {
641  n->L[i].i_r1= -1;
642  for(ii=0; ii<=n->tl; ii++)
643  {
644  if (n->R[ii]->p==n->L[i].p1) { n->L[i].i_r1=ii;break; }
645  }
646  n->L[i].i_r2= -1;
647  for(ii=0; ii<=n->tl; ii++)
648  {
649  if (n->R[ii]->p==n->L[i].p2) { n->L[i].i_r2=ii;break; }
650  }
651  }
652  }
653  kTest_TS(n);
654  /* construct D */
655  if (IDELEMS(fac)>1)
656  {
657  if (n->D==NULL)
658  {
659  n->D=idCopy(fac_copy);
660  idSkipZeroes(n->D);
661  }
662  else
663  {
664  idTest(n->D);
665  ideal r=idAdd(n->D,fac_copy);
666  idDelete(&n->D);
667  n->D=r;
668  }
669  if (TEST_OPT_DEBUG)
670  {
671  PrintS("new D:\n");
672  iiWriteMatrix((matrix)n->D,"D",1,currRing,0);
673  PrintLn();
674  }
675  }
676 
677  fac_copy->m[i]=pCopy(fac->m[i]);
678  fac->m[i]=NULL;
679 
680  /* check for empty sets */
681  if (n->D!=NULL)
682  {
683  int j=IDELEMS(n->D)-1;
684  while(j>=0)
685  {
686  if (n->D->m[j]!=NULL)
687  {
688  poly r=kNF(n->Shdl,NULL,n->D->m[j],0,KSTD_NF_LAZY | KSTD_NF_NONORM);
689  if (r==NULL)
690  {
691  if (TEST_OPT_DEBUG)
692  {
693  Print("empty set s(%d) because: D[%d]:", n->nr,j);
694  pWrite(n->D->m[j]);
695  messageSets(n);
696  }
697  //if (n->Ll >=0) Print("Ll:%d|",n->Ll);
698  while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
699  //if (n->tl >=0) Print("tl:%d|",n->tl);
700  while (n->tl >= 0)
701  {
702  int i=n->sl;
703  while (i>=0)
704  {
705  if (n->S[i]==n->T[n->tl].p)
706  {
707  n->T[n->tl].p=NULL; n->S[i]=NULL;
708  break;
709  }
710  i--;
711  }
712  pDelete(&n->T[n->tl].p);
713  n->tl--;
714  }
715  memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
716  n->sl=-1;
717  break;
718  }
719  else
720  {
721  pDelete(&r);
722  }
723  }
724  j--;
725  }
726  }
727 
728  /* check for empty sets */
729  {
730  ideal_list Lj=FL;
731  while (Lj!=NULL)
732  {
733  if ((n->sl>=0)&&(n->S[0]!=NULL))
734  {
735  ideal r=kNF(n->Shdl,NULL,Lj->d,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
736  if (idIs0(r))
737  {
738  if (TEST_OPT_DEBUG)
739  {
740  #ifdef KDEBUG
741  Print("empty set s(%d) because:L[%d]\n",n->nr,Lj->nr);
742  #else
743  Print("empty set s(%d) because:\n",n->nr);
744  #endif
745  iiWriteMatrix((matrix)Lj->d,"L",1,currRing,0);
746  }
747  while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
748  while (n->tl >= 0)
749  {
750  int i=n->sl;
751  while (i>=0)
752  {
753  if (n->S[i]==n->T[n->tl].p)
754  {
755  n->T[n->tl].p=NULL; n->S[i]=NULL;
756  break;
757  }
758  i--;
759  }
760  pDelete(&n->T[n->tl].p);
761  n->tl--;
762  }
763  memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
764  n->sl=-1;
765  idDelete(&r);
766  break;
767  }
768  idDelete(&r);
769  }
770  Lj=Lj->next;
771  }
772  }
773  } /* for */
774  for(i=0;i<IDELEMS(fac);i++) fac->m[i]=NULL;
775  idDelete(&fac);
776  idDelete(&fac_copy);
777  }
778 #ifdef KDEBUG
779  strat->P.lcm=NULL;
780 #endif
781  kTest_TS(strat);
782  if ((strat->Ll==-1) && (strat->sl>=0))
783  {
784  if (TEST_OPT_REDSB) completeReduceFac(strat,FL);
785  }
786  kTest_TS(strat);
787  }
788 #ifdef KDEBUG
789  if (TEST_OPT_DEBUG) messageSets(strat);
790 #endif
791  /* complete reduction of the standard basis--------- */
792  /* release temp data-------------------------------- */
793  if (TEST_OPT_WEIGHTM)
794  {
796  if (ecartWeights)
797  {
798  omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
799  ecartWeights=NULL;
800  }
801  }
802  exitBuchMora(strat);
803  if (TEST_OPT_PROT) { PrintLn(); messageStat(0,strat); }
804  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
805  return (strat->Shdl);
806 }
807 
808 ideal_list kStdfac(ideal F, ideal Q, tHomog h,intvec ** w,ideal D)
809 {
810  ideal r;
811  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
812  BOOLEAN delete_w=(w==NULL);
814  kStrategy orgstrat=strat;
815  ideal_list L=NULL;
816 
818  strat->LazyPass=20;
819  else
820  strat->LazyPass=2;
821  strat->LazyDegree = 1;
822  strat->ak = id_RankFreeModule(F,currRing);
823  if (h==testHomog)
824  {
825  if (strat->ak==0)
826  {
827  h = (tHomog)idHomIdeal(F,Q);
828  w=NULL;
829  }
830  else
831  h = (tHomog)idHomModule(F,Q,w);
832  }
833  if (h==isHomog)
834  {
835  if ((w!=NULL) && (*w!=NULL))
836  {
837  kModW = *w;
838  strat->kModW = *w;
839  strat->pOrigFDeg = currRing->pFDeg;
840  strat->pOrigLDeg = currRing->pLDeg;
842  toReset = TRUE;
843  }
844  currRing->pLexOrder = TRUE;
845  strat->LazyPass*=2;
846  }
847  strat->homog=h;
848  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
849  initBuchMoraPos(strat);
850  initBba(strat);
851  initBuchMora(F, Q,strat);
852  if (D!=NULL)
853  {
854  strat->D=idCopy(D);
855  }
856 // Ende der Initalisierung
857  while (strat!=NULL)
858  {
859  if (TEST_OPT_DEBUG)
860  PrintS("====================================\n");
861  if (w!=NULL)
862  r=bbafac(F,Q,*w,strat,L);
863  else
864  r=bbafac(F,Q,NULL,strat,L);
865 #ifdef KDEBUG
866  int i;
867  for (i=0; i<IDELEMS(r); i++) pTest(r->m[i]);
868 #endif
869  idSkipZeroes(r);
870  // Testausgabe:
871  //if (!idIs0(r))
872  //{
873  // PrintS("===================================================\n");
874  // iiWriteMatrix((matrix)r,"S",1,currRing,0);
875  // PrintS("\n===================================================\n");
876  //}
877  //else
878  //{
879  // PrintS("=========empty============================\n");
880  //}
881  if(!idIs0(r))
882  {
883  ideal_list LL=(ideal_list)omAlloc(sizeof(*LL));
884  LL->d=r;
885 #ifndef SING_NDEBUG
886  LL->nr=strat->nr;
887 #endif
888  LL->next=L;
889  L=LL;
890  }
891  strat=strat->next;
892  }
893  /* check for empty sets */
894  if (L!=NULL)
895  {
896  ideal_list Lj=L->next;
897  ideal_list Lj_prev=L;
898  while (Lj!=NULL)
899  {
900  ideal_list Li=L;
901  while(Li!=Lj)
902  {
903  ideal r=kNF(Lj->d,NULL,Li->d,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
904  if (idIs0(r))
905  {
906 #ifdef KDEBUG
907  if (TEST_OPT_DEBUG)
908  {
909  Print("empty set L[%p] because:L[%p]\n",(void*)Lj,(void*)Li);
910  }
911 #endif
912  // delete L[j],
913  Li=L;
914  if (Lj_prev!=NULL)
915  {
916  Lj=Lj_prev;
917  if (Lj==L) Lj_prev=NULL;
918  else
919  {
920  Lj_prev=L;
921  while(Lj_prev->next!=Lj) Lj_prev=Lj_prev->next;
922  }
923  }
924  else Lj=NULL;
925  }
926  else
927  {
928  Li=Li->next;
929  }
930  idDelete (&r);
931  }
932  if (Lj!=NULL) Lj=Lj->next;
933  }
934  }
935 // Ende: aufraeumen
936  if (toReset)
937  {
939  kModW = NULL;
940  }
941  currRing->pLexOrder = b;
942  delete(strat);
943  strat=orgstrat;
944  while (strat!=NULL)
945  {
946  orgstrat=strat->next;
947  delete(strat);
948  strat=orgstrat;
949  }
950  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
951  return L;
952 }
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:278
const CanonicalForm int s
Definition: facAbsFact.cc:55
int nr
Definition: kutil.h:342
BOOLEAN honey
Definition: kutil.h:374
#define D(A)
Definition: gentable.cc:123
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
#define setmaxL
Definition: kutil.h:29
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
int syzComp
Definition: kutil.h:350
#define TEST_OPT_DEGBOUND
Definition: options.h:108
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9928
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7924
poly kHEdge
Definition: kutil.h:323
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
class sLObject LObject
Definition: kutil.h:60
TObject * TSet
Definition: kutil.h:61
ideal_list kStdfac(ideal F, ideal Q, tHomog h, intvec **w, ideal D)
Definition: kstdfac.cc:808
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7965
#define TEST_OPT_PROT
Definition: options.h:98
loop
Definition: myNF.cc:98
int Ll
Definition: kutil.h:347
#define FALSE
Definition: auxiliary.h:94
BOOLEAN noTailReduction
Definition: kutil.h:375
Compatiblity layer for legacy polynomial operations (over currRing)
int * S_2_R
Definition: kutil.h:338
return P p
Definition: myNF.cc:203
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10101
char news
Definition: kutil.h:397
short * ecartWeights
Definition: weight0.c:28
#define pTest(p)
Definition: polys.h:398
char newt
Definition: kutil.h:398
BOOLEAN * NotUsedAxis
Definition: kutil.h:328
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
BOOLEAN noetherSet
Definition: kutil.h:377
BOOLEAN * pairtest
Definition: kutil.h:329
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4935
poly kNoether
Definition: kutil.h:324
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether, ring r)
Definition: kInline.h:1073
int strat_nr
Definition: kstdfac.cc:27
int tl
Definition: kutil.h:346
int Bl
Definition: kutil.h:348
#define TRUE
Definition: auxiliary.h:98
#define TEST_OPT_REDSB
Definition: options.h:99
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1041
unsigned long * sevT
Definition: kutil.h:319
void * ADDRESS
Definition: auxiliary.h:115
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:281
void pWrite(poly p)
Definition: polys.h:290
int ak
Definition: kutil.h:349
void initBba(kStrategy strat)
Definition: kstd1.cc:1426
#define TEST_OPT_DEBUG
Definition: options.h:103
#define Q
Definition: sirandom.c:25
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:272
#define omAlloc(size)
Definition: omAllocDecl.h:210
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1091
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:275
int Bmax
Definition: kutil.h:348
int lastAxis
Definition: kutil.h:352
void iiWriteMatrix(matrix im, const char *n, int dim, const ring r, int spaces)
set spaces to zero by default
Definition: matpol.cc:746
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:540
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9478
int HCord
Definition: kutil.h:351
#define mflush()
Definition: reporter.h:57
pFDegProc pOrigFDeg
Definition: kutil.h:290
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1148
BOOLEAN interpt
Definition: kutil.h:368
void(* initEcart)(TObject *L)
Definition: kutil.h:274
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:284
int lV
Definition: kutil.h:365
BOOLEAN fromT
Definition: kutil.h:376
const ring r
Definition: syzextra.cc:208
pLDegProc pOrigLDeg
Definition: kutil.h:291
#define KSTD_NF_LAZY
Definition: kstd1.h:17
intvec * kModW
Definition: kstd1.cc:2206
BOOLEAN homog
Definition: kutil.h:369
#define TEST_OPT_INTSTRATEGY
Definition: options.h:105
Definition: intvec.h:14
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
#define kTest_TS(A)
Definition: kutil.h:654
tHomog
Definition: structs.h:37
int j
Definition: myNF.cc:70
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3496
BOOLEAN Gebauer
Definition: kutil.h:375
intset fromQ
Definition: kutil.h:315
#define messageSets(s)
Definition: kutil.h:538
kStrategy kStratCopy(kStrategy o)
Definition: kstdfac.cc:154
LObject * LSet
Definition: kutil.h:62
static void copyL(kStrategy o, kStrategy n)
Definition: kstdfac.cc:69
#define pLmInit(p)
like pInit, except that expvector is initialized to that of p, p must be != NULL
Definition: polys.h:64
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:280
LObject P
Definition: kutil.h:296
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9777
BOOLEAN update
Definition: kutil.h:378
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
poly tail
Definition: kutil.h:330
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:282
TObject ** R
Definition: kutil.h:336
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
polyset S
Definition: kutil.h:300
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
BOOLEAN sugarCrit
Definition: kutil.h:374
int tmax
Definition: kutil.h:346
ideal idCopy(ideal A)
Definition: ideals.h:60
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3508
int int kStrategy strat
Definition: myNF.cc:68
BOOLEAN kHEdgeFound
Definition: kutil.h:373
#define KSTD_NF_NONORM
Definition: kstd1.h:21
intset ecartS
Definition: kutil.h:303
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
#define TEST_OPT_WEIGHTM
Definition: options.h:115
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:285
LSet L
Definition: kutil.h:321
#define NULL
Definition: omList.c:10
BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:91
LSet B
Definition: kutil.h:322
int Lmax
Definition: kutil.h:347
int mu
Definition: kutil.h:344
ring tailRing
Definition: kutil.h:339
static void completeReduceFac(kStrategy strat, ideal_list FL)
Definition: kstdfac.cc:281
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:345
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
ideal D
Definition: kutil.h:298
const CanonicalForm & w
Definition: facAbsFact.cc:55
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5111
#define pDelete(p_ptr)
Definition: polys.h:169
intvec * kModW
Definition: kutil.h:331
BOOLEAN no_prod_crit
Definition: kutil.h:391
unsigned long * sevS
Definition: kutil.h:316
BOOLEAN posInLOldFlag
Definition: kutil.h:379
#define pNext(p)
Definition: monomials.h:43
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2208
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10410
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
int sl
Definition: kutil.h:344
TSet T
Definition: kutil.h:320
BOOLEAN k_factorize(poly p, ideal &rfac, ideal &fac_copy)
Definition: kstdfac.cc:245
ideal singclap_factorize(poly f, intvec **v, int with_exps, const ring r)
Definition: clapsing.cc:784
ideal idAdd(ideal h1, ideal h2)
h1 + h2
Definition: ideals.h:68
void wrp(poly p)
Definition: polys.h:292
int LazyPass
Definition: kutil.h:349
polyrec * poly
Definition: hilb.h:10
static LSet initL(int nr=setmaxL)
Definition: kutil.h:418
int Kstd1_deg
Definition: kutil.cc:236
ideal Shdl
Definition: kutil.h:297
ideal bbafac(ideal, ideal Q, intvec *, kStrategy strat, ideal_list FL)
Definition: kstdfac.cc:490
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:85
kStrategy next
Definition: kutil.h:271
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
const poly b
Definition: syzextra.cc:213
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2715
char redTailChange
Definition: kutil.h:396
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10177
BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
int LazyDegree
Definition: kutil.h:349
#define omAlloc0(size)
Definition: omAllocDecl.h:211
int l
Definition: cfEzgcd.cc:94
class sTObject TObject
Definition: kutil.h:59
static void copyT(kStrategy o, kStrategy n)
Definition: kstdfac.cc:31
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168
#define idTest(id)
Definition: ideals.h:47
#define Warn
Definition: emacs.cc:80