source: git/kernel/kstdfac.cc @ 8c6b3ee

spielwiese
Last change on this file since 8c6b3ee was 8c6b3ee, checked in by Hans Schönemann <hannes@…>, 19 years ago
*hannes: fix for emty sets git-svn-id: file:///usr/local/Singular/svn/trunk@7850 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 22.0 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: kstdfac.cc,v 1.3 2005-04-20 13:08:34 Singular Exp $ */
5/*
6*  ABSTRACT -  Kernel: factorizing alg. of Buchberger
7*/
8
9#include "mod2.h"
10#include "structs.h"
11#include "omalloc.h"
12#include "polys.h"
13#include "ideals.h"
14#include "febase.h"
15#include "kutil.h"
16#include "kstd1.h"
17#include "khstd.h"
18//#include "cntrlc.h"
19#include "weight.h"
20//#include "ipshell.h"
21#include "intvec.h"
22#ifdef HAVE_FACTORY
23#include "clapsing.h"
24#endif
25#include "ideals.h"
26#include "timer.h"
27#include "kstdfac.h"
28
29#ifdef HAVE_FACTORY
30/*3
31* copy o->T to n->T, assumes that n->S is already copied
32*/
33static void copyT (kStrategy o,kStrategy n)
34{
35  int i,j;
36  poly  p;
37  TSet t=(TSet)omAlloc0(o->tmax*sizeof(TObject));
38  TObject** r = (TObject**)omAlloc0(o->tmax*sizeof(TObject*));
39
40  for (j=0; j<=o->tl; j++)
41  {
42    t[j] = o->T[j];
43    r[t[j].i_r] = &t[j];
44    p = o->T[j].p;
45    i = -1;
46    loop
47    {
48      i++;
49      if (i>o->sl)
50      {
51        t[j].p=pCopy(p);
52        break;
53      }
54      if (p == o->S[i])
55      {
56        t[j].p=n->S[i];
57        break;
58      }
59    }
60    t[j].t_p = NULL; // ?? or t[j].p ??
61    t[j].max = NULL; // ?? or p_GetMaxExpP(t[j].t_p,o->tailRing); ??
62  }
63  n->T=t;
64  n->R=r;
65}
66
67/*3
68* copy o->L to n->L, assumes that n->T,n->tail is already copied
69*/
70static void copyL (kStrategy o,kStrategy n)
71{
72  int i,j;
73  poly  p;
74  LSet l=(LSet)omAlloc(o->Lmax*sizeof(LObject));
75
76  for (j=0; j<=o->Ll; j++)
77  {
78    l[j] = o->L[j];
79    // copy .p ----------------------------------------------
80    if (pNext(o->L[j].p)!=o->tail)
81      l[j].p=pCopy(o->L[j].p);
82    else
83    {
84      l[j].p=pHead(o->L[j].p);
85      pNext(l[j].p)=n->tail;
86    }
87    // copy .lcm ----------------------------------------------
88    if (o->L[j].lcm!=NULL)
89      l[j].lcm=pLmInit(o->L[j].lcm);
90    else
91      l[j].lcm=NULL;
92    l[j].p1=NULL;
93    l[j].p2=NULL;
94    l[j].t_p = NULL;
95
96    // copy .p1 , i_r1----------------------------------------------
97    p = o->L[j].p1;
98    i = -1;
99    loop
100    {
101      if(p==NULL) break;
102      i++;
103      if(i>o->tl)
104      {
105        Warn("poly p1 not found in T:");wrp(p);PrintLn();
106        l[j].p1=pCopy(p);
107        l[j].i_r1=-1;
108        break;
109      }
110      if (p == o->T[i].p)
111      {
112        l[j].p1=n->T[i].p;
113        l[j].i_r1=n->T[i].i_r;
114        break;
115      }
116    }
117
118    // copy .p2 , i_r2----------------------------------------------
119    p = o->L[j].p2;
120    i = -1;
121    loop
122    {
123      if(p==NULL) break;
124      i++;
125      if(i>o->tl)
126      {
127        Warn("poly p2 not found in T:");wrp(p);PrintLn();
128        l[j].p2=pCopy(p);
129        l[j].i_r2=-1;
130        break;
131      }
132      if (p == o->T[i].p)
133      {
134        l[j].p2=n->T[i].p;
135        l[j].i_r2=n->T[i].i_r;
136        break;
137      }
138    }
139
140    // copy .ecart ---------------------------------------------
141    l[j].ecart=o->L[j].ecart;
142    // copy .length --------------------------------------------
143    l[j].length=o->L[j].length;
144    // copy .pLength -------------------------------------------
145    l[j].pLength=o->L[j].pLength;
146    // copy .sev -----------------------------------------------
147    l[j].sev=o->L[j].sev;
148    l[j].i_r = o->L[j].i_r;
149    //l[j].i_r1 = o->L[j].i_r1;
150    //l[j].i_r2 = o->L[j].i_r2;
151  }
152  n->L=l;
153}
154
155kStrategy kStratCopy(kStrategy o)
156{
157  int i;
158  kTest_TS(o);
159  kStrategy s=new skStrategy;
160  s->next=NULL;
161  s->red=o->red;
162  s->initEcart=o->initEcart;
163  s->posInT=o->posInT;
164  s->posInL=o->posInL;
165  s->enterS=o->enterS;
166  s->initEcartPair=o->initEcartPair;
167  s->posInLOld=o->posInLOld;
168  s->Shdl=idCopy(o->Shdl);
169  s->S=s->Shdl->m;
170  s->tailRing = o->tailRing;
171  if (o->D!=NULL) s->D=idCopy(o->D);
172  else            s->D=NULL;
173  s->ecartS=(int *)omAlloc(IDELEMS(o->Shdl)*sizeof(int));
174  memcpy(s->ecartS,o->ecartS,IDELEMS(o->Shdl)*sizeof(int));
175  s->sevS=(unsigned long *)omAlloc(IDELEMS(o->Shdl)*sizeof(unsigned long));
176  memcpy(s->sevS,o->sevS,IDELEMS(o->Shdl)*sizeof(unsigned long));
177  s->S_2_R=(int*)omAlloc(IDELEMS(o->Shdl)*sizeof(int));
178  memcpy(s->S_2_R,o->S_2_R,IDELEMS(o->Shdl)*sizeof(int));
179  s->sevT=(unsigned long *)omAlloc(o->tmax*sizeof(unsigned long));
180  memcpy(s->sevT,o->sevT,o->tmax*sizeof(unsigned long));
181  if(o->fromQ!=NULL)
182  {
183    s->fromQ=(int *)omAlloc(IDELEMS(o->Shdl)*sizeof(int));
184    memcpy(s->fromQ,o->fromQ,IDELEMS(o->Shdl)*sizeof(int));
185  }
186  else
187    s->fromQ=NULL;
188  copyT(o,s);//s->T=...
189  s->tail = pInit();
190  copyL(o,s);//s->L=...
191  s->B=initL();
192  s->kHEdge=pCopy(o->kHEdge);
193  s->kNoether=pCopy(o->kNoether);
194  if (o->NotUsedAxis!=NULL)
195  {
196    s->NotUsedAxis=(BOOLEAN *)omAlloc(currRing->N*sizeof(BOOLEAN));
197    memcpy(s->NotUsedAxis,o->NotUsedAxis,currRing->N*sizeof(BOOLEAN));
198  }
199  s->kIdeal=NULL;
200  //s->P=s->L[s->Ll+1];
201  s->P.Init(o->tailRing);
202  s->update=o->update;
203  s->posInLOldFlag=o->posInLOldFlag;
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=setmax;
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;
232  s->noTailReduction=o->noTailReduction;
233  s->fromT=o->fromT;
234  s->noetherSet=o->noetherSet;
235  kTest_TS(s);
236  return s;
237}
238
239BOOLEAN k_factorize(poly p,ideal &rfac, ideal &fac_copy)
240{
241  int facdeg=pFDeg(p,currRing);
242  ideal fac=singclap_factorize(p,NULL,1);
243  int fac_elems;
244#ifndef HAVE_LIBFAC_P
245  if (fac==NULL)
246  {
247    fac=idInit(1,1);
248    fac->m[0]=pCopy(strat->P.p);
249    fac_elems=1;
250  }
251  else
252#endif
253    fac_elems=IDELEMS(fac);
254  rfac=fac;
255  fac_copy=idInit(fac_elems,1);
256
257  if ((fac_elems!=1)||(facdeg!=pFDeg(fac->m[0],currRing)))
258  {
259    if (TEST_OPT_DEBUG)
260    {
261      Print("-> %d factors\n",fac_elems);
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
281static 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    //if (strat->interpt) test_int_std(strat->kIdeal);
298    strat->S[si] = redtailBba(strat->S[si],si-1,strat);
299    if (TEST_OPT_INTSTRATEGY)
300    {
301      pCleardenom(strat->S[si]);
302    }
303    if (TEST_OPT_PROT)
304    {
305      PrintS("-");mflush();
306    }
307    ideal fac;
308    ideal fac_copy;
309
310    if (!k_factorize(strat->S[si],fac,fac_copy))
311    {
312      idDelete(&fac);
313      idDelete(&fac_copy);
314      continue;
315    }
316
317    deleteInS(si,strat);
318
319    int i;
320    for(i=IDELEMS(fac)-1;i>=0;i--)
321    {
322      kStrategy n=strat;
323      if (i>=1)
324      {
325        n=kStratCopy(strat); // includes: memset(&n->P,0,sizeof(n->P));
326        n->next=strat->next;
327        strat->next=n;
328      }
329      else
330      {
331        n->P.Init(strat->tailRing);
332      }
333
334      n->P.p=fac->m[i];
335      n->P.pLength=0;
336      n->initEcart(&n->P);
337
338      /* enter P.p into s and L */
339      int pos;
340      if (n->sl==-1) pos=0;
341      else pos=posInS(n,n->sl,n->P.p,n->P.ecart);
342      if (TEST_OPT_INTSTRATEGY)
343      {
344        n->P.p = redtailBba(n->P.p,pos-1,n);
345        pCleardenom(n->P.p);
346      }
347      else
348      {
349        pNorm(n->P.p);
350        n->P.p = redtailBba(n->P.p,pos-1,n);
351      }
352      if (TEST_OPT_DEBUG)
353      {
354        PrintS("new s:");
355        wrp(n->P.p);
356        PrintLn();
357      }
358      enterpairs(n->P.p,n->sl,n->P.ecart,pos,n);
359      enterT(n->P,n);
360      n->enterS(n->P,pos,n, n->tl);
361
362      /* construct D */
363      if (IDELEMS(fac)>1)
364      {
365        if (n->D==NULL)
366        {
367          n->D=idCopy(fac_copy);
368          idSkipZeroes(n->D);
369        }
370        else
371        {
372          idTest(n->D);
373          ideal r=idAdd(n->D,fac_copy);
374          idDelete(&n->D);
375          n->D=r;
376        }
377        if (TEST_OPT_DEBUG)
378        {
379          PrintS("new D:\n");
380          iiWriteMatrix((matrix)n->D,"D",1,0);
381          PrintLn();
382        }
383      }
384
385      fac_copy->m[i]=pCopy(fac->m[i]);
386      fac->m[i]=NULL;
387
388      /* check for empty sets */
389      if (n->D!=NULL)
390      {
391        int j=IDELEMS(n->D)-1;
392        while(j>=0)
393        {
394          if (n->D->m[j]!=NULL)
395          {
396            poly r=kNF(n->Shdl,NULL,n->D->m[j],0,TRUE);
397            if (r==NULL)
398            {
399              if (TEST_OPT_DEBUG)
400              {
401                PrintS("empty set because:");
402                wrp(n->D->m[j]);
403                PrintLn();
404                messageSets(n);
405              }
406              while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
407              while (n->tl >= 0)
408              {
409                int i=n->sl;
410                while (i>=0)
411                {
412                  if (n->S[i]==n->T[n->tl].p)
413                  {
414                    n->T[n->tl].p=NULL; n->S[i]=NULL;
415                    break;
416                  }
417                  i--;
418                }
419                pDelete(&n->T[n->tl].p);
420                n->tl--;
421              }
422              memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
423              n->sl=-1;
424              if (strat==n) si=-1;
425              break;
426            }
427            else
428            {
429              pDelete(&r);
430            }
431          }
432          j--;
433        }
434      }
435      /* check for empty sets */
436      {
437        ideal_list Lj=FL;
438        while (Lj!=NULL)
439        {
440          if ((n->sl>=0)&&(n->S[0]!=NULL))
441          {
442            ideal r=kNF(n->Shdl,NULL,Lj->d,0,TRUE);
443            if (idIs0(r))
444            {
445              if (TEST_OPT_DEBUG)
446              {
447                Print("empty set because:L[%x]\n",Lj);
448              }
449              while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
450              while (n->tl >= 0)
451              {
452                int i=n->sl;
453                while (i>=0)
454                {
455                  if (n->S[i]==n->T[n->tl].p)
456                  {
457                    n->T[n->tl].p=NULL; n->S[i]=NULL;
458                    break;
459                  }
460                  i--;
461                }
462                pDelete(&n->T[n->tl].p);
463                n->tl--;
464              }
465              memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
466              n->sl=-1;
467              if (strat==n) si=-1;
468              idDelete(&r);
469              break;
470            }
471            idDelete(&r);
472          }
473          Lj=Lj->next;
474        }
475      }
476    } /* for */
477    for(i=0;i<IDELEMS(fac);i++) fac->m[i]=NULL;
478    idDelete(&fac);
479    idDelete(&fac_copy);
480    if ((strat->Ll>=0) && (strat->sl>=0)) break;
481    else si=strat->sl+1;
482  }
483}
484
485ideal bbafac (ideal F, ideal Q,intvec *w,kStrategy strat, ideal_list FL)
486{
487  int   srmax,lrmax;
488  int   olddeg,reduc=0;
489  int red_result = 1;
490  srmax = strat->sl;
491  reduc = olddeg = lrmax = 0;
492  /* compute------------------------------------------------------- */
493  if ((strat->Ll==-1) && (strat->sl>=0))
494  {
495    if (TEST_OPT_REDSB) completeReduceFac(strat,FL);
496  }
497  kTest_TS(strat);
498  while (strat->Ll >= 0)
499  {
500    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
501    if (TEST_OPT_DEBUG) messageSets(strat);
502    //test_int_std(strat->kIdeal);
503    if (strat->Ll== 0) strat->interpt=TRUE;
504    if (TEST_OPT_DEGBOUND
505    && ((strat->honey
506        && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
507      || ((!strat->honey) && (pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
508    {
509      /*
510      *stops computation if
511      * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
512      *a predefined number Kstd1_deg
513      */
514      while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
515      break;
516    }
517    /* picks the last element from the lazyset L */
518    strat->P = strat->L[strat->Ll];
519    strat->Ll--;
520    if (pNext(strat->P.p) == strat->tail)
521    {
522      /* deletes the short spoly and computes */
523      pLmFree(strat->P.p);
524      /* the real one */
525      strat->P.p = ksOldCreateSpoly(strat->P.p1,
526                                    strat->P.p2,
527                                    strat->kNoether);
528    }
529    if (strat->honey)
530    {
531      if (TEST_OPT_PROT)
532        message(strat->P.ecart+pFDeg(strat->P.p,currRing),&olddeg,&reduc,strat, red_result);
533    }
534    else
535    {
536      if (TEST_OPT_PROT)
537        message(pFDeg(strat->P.p,currRing),&olddeg,&reduc,strat, red_result);
538    }
539    /* reduction of the element choosen from L */
540    kTest_TS(strat);
541    red_result = strat->red(&strat->P,strat);
542    if (strat->P.p != NULL)
543    {
544      /* statistic */
545      if (TEST_OPT_PROT) PrintS("s");
546      ideal fac;
547      ideal fac_copy;
548
549      if (!k_factorize(strat->P.p,fac,fac_copy))
550      {
551        if (TEST_OPT_INTSTRATEGY)
552        {
553          strat->P.p = redtailBba(strat->P.p,strat->sl,strat);
554          if (strat->redTailChange) pCleardenom(strat->P.p);
555        }
556        else
557        {
558          pNorm(strat->P.p);
559          strat->P.p = redtailBba(strat->P.p,strat->sl,strat);
560        }
561        if (strat->redTailChange)
562        {
563          idDelete(&fac);
564          idDelete(&fac_copy);
565          if (!k_factorize(strat->P.p,fac,fac_copy))
566          {
567            pDelete(&(fac->m[0]));
568            fac->m[0]=strat->P.p;
569            strat->P.p=NULL;
570          }
571          else
572          {
573            pDelete(&strat->P.p);
574          }
575        }
576      }
577      if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
578      int i;
579
580      for(i=IDELEMS(fac)-1;i>=0;i--)
581      {
582        int ii;
583        kStrategy n=strat;
584        if (i>=1)
585        {
586          n=kStratCopy(strat); // includes memset(&n->P,0,sizeof(n->P));
587          kTest_TS(n);
588          n->next=strat->next;
589          strat->next=n;
590        }
591        else
592        {
593          n->P.Init(strat->tailRing);
594        }
595
596        n->P.p=fac->m[i];
597        n->initEcart(&n->P);
598        kTest_TS(n);
599
600        /* enter P.p into s and L */
601        int pos;
602        if (n->sl==-1) pos=0;
603        else pos=posInS(n,n->sl,n->P.p,n->P.ecart);
604
605        // we have already reduced all elements from fac....
606        if (TEST_OPT_INTSTRATEGY)
607        {
608          n->P.p = redtailBba(n->P.p,pos-1,n);
609          if (n->redTailChange) pCleardenom(n->P.p);
610        }
611        else
612        {
613          pNorm(n->P.p);
614          n->P.p = redtailBba(n->P.p,pos-1,n);
615        }
616        kTest_TS(n);
617
618        if (TEST_OPT_DEBUG)
619        {
620          PrintS("new s:");
621          wrp(n->P.p);
622          PrintLn();
623        }
624        enterpairs(n->P.p,n->sl,n->P.ecart,pos,n);
625        enterT(n->P,n);
626        n->enterS(n->P,pos,n, n->tl);
627        {
628          int i=n->Ll;
629          for(;i>=0;i--)
630          {
631            n->L[i].i_r1= -1;
632            for(ii=0; ii<=n->tl; ii++)
633            {
634              if (n->R[ii]->p==n->L[i].p1)  { n->L[i].i_r1=ii;break; }
635            }
636            n->L[i].i_r2= -1;
637            for(ii=0; ii<=n->tl; ii++)
638            {
639              if (n->R[ii]->p==n->L[i].p2)  { n->L[i].i_r2=ii;break; }
640            }
641          }
642        }
643        kTest_TS(n);
644        if (n->sl>srmax) srmax = n->sl;
645
646        /* construct D */
647        if (IDELEMS(fac)>1)
648        {
649          if (n->D==NULL)
650          {
651            n->D=idCopy(fac_copy);
652            idSkipZeroes(n->D);
653          }
654          else
655          {
656            idTest(n->D);
657            ideal r=idAdd(n->D,fac_copy);
658            idDelete(&n->D);
659            n->D=r;
660          }
661          if (TEST_OPT_DEBUG)
662          {
663            PrintS("new D:\n");
664            iiWriteMatrix((matrix)n->D,"D",1,0);
665            PrintLn();
666          }
667        }
668
669        fac_copy->m[i]=pCopy(fac->m[i]);
670        fac->m[i]=NULL;
671
672        /* check for empty sets */
673        if (n->D!=NULL)
674        {
675          int j=IDELEMS(n->D)-1;
676          while(j>=0)
677          {
678            if (n->D->m[j]!=NULL)
679            {
680              poly r=kNF(n->Shdl,NULL,n->D->m[j],0,TRUE);
681              if (r==NULL)
682              {
683                if (TEST_OPT_DEBUG)
684                {
685                  PrintS("empty set because:");
686                  wrp(n->D->m[j]);
687                  PrintLn();
688                  messageSets(n);
689                }
690                //if (n->Ll >=0) Print("Ll:%d|",n->Ll);
691                while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
692                //if (n->tl >=0) Print("tl:%d|",n->tl);
693                while (n->tl >= 0)
694                {
695                  int i=n->sl;
696                  while (i>=0)
697                  {
698                    if (n->S[i]==n->T[n->tl].p)
699                    {
700                      n->T[n->tl].p=NULL; n->S[i]=NULL;
701                      break;
702                    }
703                    i--;
704                  }
705                  pDelete(&n->T[n->tl].p);
706                  n->tl--;
707                }
708                memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
709                n->sl=-1;
710                break;
711              }
712              else
713              {
714                pDelete(&r);
715              }
716            }
717            j--;
718          }
719        }
720
721        /* check for empty sets */
722        {
723          ideal_list Lj=FL;
724          while (Lj!=NULL)
725          {
726            if ((n->sl>=0)&&(n->S[0]!=NULL))
727            {
728              ideal r=kNF(n->Shdl,NULL,Lj->d,0,TRUE);
729              if (idIs0(r))
730              {
731                if (TEST_OPT_DEBUG)
732                {
733                  Print("empty set because:L[%x]\n",Lj);
734                }
735                while (n->Ll >= 0) deleteInL(n->L,&n->Ll,n->Ll,n);
736                while (n->tl >= 0)
737                {
738                  int i=n->sl;
739                  while (i>=0)
740                  {
741                    if (n->S[i]==n->T[n->tl].p)
742                    {
743                      n->T[n->tl].p=NULL; n->S[i]=NULL;
744                      break;
745                    }
746                    i--;
747                  }
748                  pDelete(&n->T[n->tl].p);
749                  n->tl--;
750                }
751                memset(n->Shdl->m,0,IDELEMS(n->Shdl)*sizeof(poly));
752                n->sl=-1;
753                idDelete(&r);
754                break;
755              }
756              idDelete(&r);
757            }
758            Lj=Lj->next;
759          }
760        }
761      } /* for */
762      for(i=0;i<IDELEMS(fac);i++) fac->m[i]=NULL;
763      idDelete(&fac);
764      idDelete(&fac_copy);
765    }
766#ifdef KDEBUG
767    strat->P.lcm=NULL;
768#endif
769    kTest_TS(strat);
770    if ((strat->Ll==-1) && (strat->sl>=0))
771    {
772      if (TEST_OPT_REDSB) completeReduceFac(strat,FL);
773    }
774    kTest_TS(strat);
775  }
776  if (TEST_OPT_DEBUG) messageSets(strat);
777  /* complete reduction of the standard basis--------- */
778  /* release temp data-------------------------------- */
779  exitBuchMora(strat);
780  if (TEST_OPT_WEIGHTM)
781  {
782    pRestoreDegProcs(pFDegOld, pLDegOld);
783    if (ecartWeights)
784    {
785      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
786      ecartWeights=NULL;
787    }
788  }
789  if (TEST_OPT_PROT) messageStat(srmax,lrmax,0,strat);
790  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
791  return (strat->Shdl);
792}
793#endif
794
795ideal_list kStdfac(ideal F, ideal Q, tHomog h,intvec ** w,ideal D)
796{
797#ifdef HAVE_FACTORY
798  ideal r;
799  BOOLEAN b=pLexOrder,toReset=FALSE;
800  BOOLEAN delete_w=(w==NULL);
801  kStrategy strat=new skStrategy;
802  kStrategy orgstrat=strat;
803  ideal_list L=NULL;
804
805  if (rField_has_simple_inverse())
806    strat->LazyPass=20;
807  else
808    strat->LazyPass=2;
809  strat->LazyDegree = 1;
810  strat->ak = idRankFreeModule(F);
811  if ((h==testHomog))
812  {
813    if (strat->ak==0)
814    {
815      h = (tHomog)idHomIdeal(F,Q);
816      w=NULL;
817    }
818    else
819      h = (tHomog)idHomModule(F,Q,w);
820  }
821  if (h==isHomog)
822  {
823    if ((w!=NULL) && (*w!=NULL))
824    {
825      kModW = *w;
826      strat->kModW = *w;
827      pFDegOld = pFDeg;
828      pLDegOld = pLDeg;
829      pSetDegProcs(kModDeg);
830      toReset = TRUE;
831    }
832    pLexOrder = TRUE;
833    strat->LazyPass*=2;
834  }
835  strat->homog=h;
836  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
837  initBuchMoraPos(strat);
838  initBba(F,strat);
839  initBuchMora(F, Q,strat);
840  if (D!=NULL)
841  {
842    strat->D=idCopy(D);
843  }
844// Ende der Initalisierung
845  while (strat!=NULL)
846  {
847    if (TEST_OPT_DEBUG)
848      PrintS("====================================\n");
849    if (w!=NULL)
850      r=bbafac(F,Q,*w,strat,L);
851    else
852      r=bbafac(F,Q,NULL,strat,L);
853#ifdef KDEBUG
854    int i;
855    for (i=0; i<IDELEMS(r); i++) pTest(r->m[i]);
856#endif
857    idSkipZeroes(r);
858    // Testausgabe:
859    //if (!idIs0(r))
860    //{
861    //  PrintS("===================================================\n");
862    //  iiWriteMatrix((matrix)r,"S",1,0);
863    //  PrintS("\n===================================================\n");
864    //}
865    //else
866    //{
867    //  PrintS("=========empty============================\n");
868    //}
869    strat=strat->next;
870    if(!idIs0(r))
871    {
872      ideal_list LL=(ideal_list)omAlloc(sizeof(*LL));
873      LL->d=r;
874      LL->next=L;
875      L=LL;
876    }
877  }
878  /* check for empty sets */
879  if (L!=NULL)
880  {
881    ideal_list Lj=L->next;
882    ideal_list Lj_prev=L;
883    while (Lj!=NULL)
884    {
885      ideal_list Li=L;
886      while(Li!=Lj)
887      {
888        ideal r=kNF(Lj->d,NULL,Li->d,0,TRUE);
889        if (idIs0(r))
890        {
891          if (TEST_OPT_DEBUG)
892          {
893            Print("empty set L[%x] because:L[%x]\n",Lj,Li);
894          }
895          // delete L[j],
896          Li=L; 
897          if (Lj_prev!=NULL)
898          {
899            Lj=Lj_prev;
900            if (Lj==L) Lj_prev=NULL;
901            else
902            {
903              Lj_prev=L;
904              while(Lj_prev->next!=Lj) Lj_prev=Lj_prev->next;
905            }
906          }
907          else Lj=NULL;
908        }
909        else
910        {
911          Li=Li->next;
912        }
913        idDelete (&r);
914      }
915      if (Lj!=NULL) Lj=Lj->next;
916    }
917  }
918// Ende: aufraeumen
919  if (toReset)
920  {
921    pRestoreDegProcs(pFDegOld, pLDegOld);
922    kModW = NULL;
923  }
924  pLexOrder = b;
925  delete(strat);
926  strat=orgstrat;
927  while (strat!=NULL)
928  {
929    orgstrat=strat->next;
930    delete(strat);
931    strat=orgstrat;
932  }
933  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
934  return L;
935#else
936  return NULL;
937#endif
938}
Note: See TracBrowser for help on using the repository browser.