source: git/kernel/GBEngine/sca.cc @ 88615db

spielwiese
Last change on this file since 88615db was 88615db, checked in by jgmbenoit <quatermaster@…>, 9 years ago
correct some spelling errors: Correct spelling error as reported by lintian in some binraries; meant to silence lintian.
  • Property mode set to 100644
File size: 29.4 KB
Line 
1#define PLURAL_INTERNAL_DECLARATIONS
2
3
4
5
6#include <kernel/mod2.h>
7#include <misc/auxiliary.h>
8
9#include <misc/options.h>
10
11#include <polys/simpleideals.h>
12#include <polys/prCopy.h>
13
14#include <polys/nc/sca.h>
15#include <polys/nc/gb_hack.h>
16
17#include <kernel/polys.h>
18#include <kernel/ideals.h>
19#include <kernel/GBEngine/kstd1.h>
20#include <kernel/GBEngine/kutil.h>
21
22#include <kernel/GBEngine/nc.h>
23
24/// nc_gr_initBba is needed for sca_gr_bba and gr_bba.
25void nc_gr_initBba(ideal F, kStrategy strat); // from gr_kstd2.cc!
26
27void addLObject(LObject& h, kStrategy& strat)
28{
29  if(h.IsNull()) return;
30
31  strat->initEcart(&h);
32  h.sev=0; // pGetShortExpVector(h.p);
33
34  // add h into S and L
35  int pos=posInS(strat, strat->sl, h.p, h.ecart);
36
37  if ( (pos <= strat->sl) && (p_ComparePolys(h.p, strat->S[pos], currRing)) )
38  {
39    if (TEST_OPT_PROT)
40      PrintS("d\n");
41  }
42  else
43  {
44    if (TEST_OPT_INTSTRATEGY)
45    {
46      p_Cleardenom(h.p, currRing);
47    }
48    else
49    {
50      pNorm(h.p);
51      p_Content(h.p,currRing);
52    }
53
54    if ((strat->syzComp==0)||(!strat->homog))
55    {
56      h.p = redtailBba(h.p,pos-1,strat);
57
58      if (TEST_OPT_INTSTRATEGY)
59      {
60//        pCleardenom(h.p);
61        p_Content(h.p,currRing);
62      }
63      else
64      {
65        pNorm(h.p);
66      }
67    }
68
69    if(h.IsNull()) return;
70
71    // statistic
72    if (TEST_OPT_PROT)
73    {
74      PrintS("s\n");
75    }
76
77#ifdef KDEBUG
78    if (TEST_OPT_DEBUG)
79    {
80      PrintS("new s:");
81      wrp(h.p);
82      PrintLn();
83    }
84#endif
85
86    enterpairs(h.p, strat->sl, h.ecart, 0, strat);
87
88    pos=0;
89
90    if (strat->sl!=-1) pos = posInS(strat, strat->sl, h.p, h.ecart);
91    strat->enterS(h, pos, strat, -1);
92//    enterT(h, strat); // ?!
93
94    if (h.lcm!=NULL) pLmFree(h.lcm);
95  }
96
97
98}
99
100
101ideal sca_gr_bba(const ideal F, const ideal Q, const intvec *, const intvec *, kStrategy strat, const ring _currRing)
102{
103  const ring save = currRing;
104  if( currRing != _currRing ) rChangeCurrRing(_currRing);
105  assume( currRing == _currRing );
106
107
108#if MYTEST
109   PrintS("<sca_gr_bba>\n");
110#endif
111
112  assume(rIsSCA(currRing));
113
114#ifndef SING_NDEBUG
115  idTest(F);
116  idTest(Q);
117#endif
118
119#ifdef HAVE_PLURAL
120#if MYTEST
121  PrintS("currRing: \n");
122  rWrite(currRing);
123#ifdef RDEBUG
124  rDebugPrint(currRing);
125#endif
126
127  PrintS("F: \n");
128  idPrint(F);
129  PrintS("Q: \n");
130  idPrint(Q);
131#endif
132#endif
133
134
135  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
136  const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
137
138  ideal tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
139  ideal tempQ = Q;
140
141  if(Q == currRing->qideal)
142    tempQ = SCAQuotient(currRing);
143
144  strat->z2homog = id_IsSCAHomogeneous(tempF, NULL, NULL, currRing); // wCx == wCy == NULL!
145  // redo: no_prod_crit
146  const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
147  strat->no_prod_crit   = ! bIsSCA;
148
149//  strat->homog = strat->homog && strat->z2homog; // ?
150
151#if MYTEST
152  {
153    PrintS("ideal tempF: \n");
154    idPrint(tempF);
155    PrintS("ideal tempQ: \n");
156    idPrint(tempQ);
157  }
158#endif
159
160  int olddeg, reduc;
161  int red_result = 1;
162//  int hilbeledeg = 1, minimcnt = 0;
163  int hilbcount = 0;
164
165  initBuchMoraCrit(strat); // set Gebauer, honey, sugarCrit
166
167  nc_gr_initBba(tempF,strat); // set enterS, red, initEcart, initEcartPair
168
169  initBuchMoraPos(strat);
170
171
172  // ?? set spSpolyShort, reduce ???
173
174  initBuchMora(tempF, tempQ, strat); // SCAQuotient(currRing) instead of Q == squares!!!!!!!
175
176  strat->posInT=posInT110; // !!!
177
178  reduc = olddeg = 0;
179
180
181  // compute-------------------------------------------------------
182  for(; strat->Ll >= 0;
183#ifdef KDEBUG
184    strat->P.lcm = NULL,
185#endif
186    kTest(strat)
187    )
188  {
189#ifdef KDEBUG
190    if (TEST_OPT_DEBUG) messageSets(strat);
191#endif
192
193    if (strat->Ll== 0) strat->interpt=TRUE;
194
195    if (TEST_OPT_DEGBOUND
196    && ((strat->honey
197    && (strat->L[strat->Ll].ecart+ currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
198       || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
199    {
200      // stops computation if
201      // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
202      // a predefined number Kstd1_deg
203      while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
204      break;
205    }
206
207    // picks the last element from the lazyset L
208    strat->P = strat->L[strat->Ll];
209    strat->Ll--;
210
211    //kTest(strat);
212
213//    assume(pNext(strat->P.p) != strat->tail); // !???
214    if(strat->P.IsNull()) continue;
215
216
217    if( pNext(strat->P.p) == strat->tail )
218    {
219      // deletes the int spoly and computes SPoly
220      pLmFree(strat->P.p); // ???
221      strat->P.p = nc_CreateSpoly(strat->P.p1, strat->P.p2, currRing);
222    }
223
224    if(strat->P.IsNull()) continue;
225
226//     poly save = NULL;
227//
228//     if(pNext(strat->P.p) != NULL)
229//       save = p_Copy(strat->P.p, currRing);
230
231    strat->initEcart(&strat->P); // remove it?
232
233    if (TEST_OPT_PROT)
234      message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(), &olddeg,&reduc,strat, red_result);
235
236    // reduction of the element chosen from L wrt S
237    strat->red(&strat->P,strat);
238
239    if(strat->P.IsNull()) continue;
240
241    addLObject(strat->P, strat);
242
243    const poly save = strat->P.p;
244
245#ifdef PDEBUG
246      p_Test(save, currRing);
247#endif
248    assume( save != NULL );
249
250    // SCA Specials:
251
252    {
253      const poly p_next = pNext(save);
254
255      if( p_next != NULL )
256      for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
257      if( p_GetExp(save, i, currRing) != 0 )
258      {
259        assume(p_GetExp(save, i, currRing) == 1);
260
261        const poly tt = sca_pp_Mult_xi_pp(i, p_next, currRing);
262
263#ifdef PDEBUG
264        p_Test(tt, currRing);
265#endif
266
267        if( tt == NULL) continue;
268
269        LObject h(tt); // h = x_i * P
270
271        if (TEST_OPT_INTSTRATEGY)
272        {
273//           h.pCleardenom(); // also does a p_Content
274          p_Content(h.p,currRing);
275        }
276        else
277        {
278          h.pNorm();
279        }
280
281        strat->initEcart(&h);
282
283
284//         if (pOrdSgn==-1)
285//         {
286//           cancelunit(&h);  // tries to cancel a unit
287//           deleteHC(&h, strat);
288//         }
289
290//         if(h.IsNull()) continue;
291
292//         if (TEST_OPT_PROT)
293//           message((strat->honey ? h.ecart : 0) + h.pFDeg(), &olddeg, &reduc, strat, red_result);
294
295//         strat->red(&h, strat); // wrt S
296//         if(h.IsNull()) continue;
297
298//         poly save = p_Copy(h.p, currRing);
299
300        int pos;
301
302        if (strat->Ll==-1)
303          pos =0;
304        else
305          pos = strat->posInL(strat->L,strat->Ll,&h,strat);
306
307        h.sev = pGetShortExpVector(h.p);
308        enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
309
310  //       h.p = save;
311  //       addLObject(h, strat);
312      }
313
314      // p_Delete( &save, currRing );
315    }
316
317
318  } // for(;;)
319
320
321#ifdef KDEBUG
322  if (TEST_OPT_DEBUG) messageSets(strat);
323#endif
324
325  if (TEST_OPT_REDSB){
326    completeReduce(strat); // ???
327  }
328
329  // release temp data--------------------------------
330  exitBuchMora(strat);
331
332//  if (TEST_OPT_WEIGHTM)
333//  {
334//    pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
335//     if (ecartWeights)
336//     {
337//       omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(int));
338//       ecartWeights=NULL;
339//     }
340//  }
341
342  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
343
344  if (tempQ!=NULL) updateResult(strat->Shdl,tempQ,strat);
345
346  id_Delete(&tempF, currRing);
347
348
349  // complete reduction of the standard basis---------
350  if (TEST_OPT_REDSB){
351    ideal I = strat->Shdl;
352    ideal erg = kInterRedOld(I,tempQ);
353    assume(I!=erg);
354    id_Delete(&I, currRing);
355    strat->Shdl = erg;
356  }
357
358
359#if MYTEST
360//   PrintS("</sca_gr_bba>\n");
361#endif
362
363  if( currRing != save )     rChangeCurrRing(save);
364
365  return (strat->Shdl);
366}
367
368
369
370///////////////////////////////////////////////////////////////////////////////////////
371//************* SCA BBA *************************************************************//
372///////////////////////////////////////////////////////////////////////////////////////
373
374// Under development!!!
375ideal sca_bba (const ideal F, const ideal Q, const intvec */*w*/, const intvec * /*hilb*/, kStrategy strat, const ring _currRing)
376{
377  const ring save = currRing;
378  if( currRing != _currRing ) rChangeCurrRing(_currRing);
379  assume( currRing == _currRing );
380
381#if MYTEST
382  PrintS("\n\n<sca_bba>\n\n");
383#endif
384
385  assume(rIsSCA(currRing));
386
387#ifndef SING_NDEBUG
388  idTest(F);
389  idTest(Q);
390#endif
391
392#if MYTEST
393  PrintS("\ncurrRing: \n");
394  rWrite(currRing);
395#ifdef RDEBUG
396//  rDebugPrint(currRing);
397#endif
398
399  PrintS("\n\nF: \n");
400  idPrint(F);
401  PrintS("\n\nQ: \n");
402  idPrint(Q);
403
404  PrintLn();
405#endif
406
407
408  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
409  const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
410
411  ideal tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
412
413  ideal tempQ = Q;
414
415  if(Q == currRing->qideal)
416    tempQ = SCAQuotient(currRing);
417
418  // Q or tempQ will not be used below :(((
419
420
421#if MYTEST
422
423  PrintS("tempF: \n");
424  idPrint(tempF);
425  PrintS("tempQ: \n");
426  idPrint(tempQ);
427#endif
428
429  strat->z2homog = id_IsSCAHomogeneous(tempF, NULL, NULL, currRing); // wCx == wCy == NULL!
430   // redo no_prod_crit:
431  const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
432  strat->no_prod_crit   = ! bIsSCA;
433
434//  strat->homog = strat->homog && strat->z2homog; // ?
435
436  int   red_result = 1;
437  int   olddeg, reduc;
438
439//  int hilbeledeg = 1, minimcnt = 0;
440  int hilbcount = 0;
441
442  BOOLEAN withT = FALSE;
443
444  initBuchMoraCrit(strat); // sets Gebauer, honey, sugarCrit // sca - ok???
445  initBuchMoraPos(strat); // sets strat->posInL, strat->posInT // check!! (Plural's: )
446
447//   initHilbCrit(F, Q, &hilb, strat);
448
449//  nc_gr_initBba(F,strat);
450  initBba(tempF, strat); // set enterS, red, initEcart, initEcartPair
451
452  // set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair
453  // ?? set spSpolyShort, reduce ???
454  initBuchMora(tempF, tempQ, strat); // tempQ = Q without squares!!!
455
456//   if (strat->minim>0) strat->M = idInit(IDELEMS(F),F->rank);
457
458  reduc = olddeg = 0;
459
460#define NO_BUCKETS
461
462#ifndef NO_BUCKETS
463  if (!TEST_OPT_NOT_BUCKETS)
464    strat->use_buckets = 1;
465#endif
466
467  // redtailBBa against T for inhomogenous input
468  if (!TEST_OPT_OLDSTD)
469    withT = ! strat->homog;
470
471  // strat->posInT = posInT_pLength;
472  kTest_TS(strat);
473
474#undef HAVE_TAIL_RING
475
476#ifdef HAVE_TAIL_RING
477  if(!idIs0(F) &&(!rField_is_Ring()))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
478    kStratInitChangeTailRing(strat);
479#endif
480  if (BVERBOSE(23))
481  {
482    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
483    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
484    kDebugPrint(strat);
485  }
486
487
488  ///////////////////////////////////////////////////////////////
489  // SCA:
490
491  //  due to std( SB, p).
492  // Note that after initBuchMora :: initSSpecial all these additional
493  // elements are in S and T (and some pairs are in L, which also has no initiall
494  // elements!!!)
495  if(TEST_OPT_SB_1)
496  {
497    // For all additional elements...
498    for (int iNewElement = strat->newIdeal; iNewElement < IDELEMS(tempF); iNewElement++)
499    {
500      const poly pSave = tempF->m[iNewElement];
501
502      if( pSave != NULL )
503      {
504//        tempF->m[iNewElement] = NULL;
505
506        const poly p_next = pNext(pSave);
507
508        if(p_next != NULL)
509          for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
510            if( p_GetExp(pSave, i, currRing) != 0 )
511            {
512              assume(p_GetExp(pSave, i, currRing) == 1);
513
514              const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
515
516#ifdef PDEBUG
517              p_Test(p_new, currRing);
518#endif
519
520              if( p_new == NULL) continue;
521
522              LObject h(p_new); // h = x_i * strat->P
523              h.is_special = TRUE;
524
525              if (TEST_OPT_INTSTRATEGY)
526                h.pCleardenom(); // also does a p_Content
527              else
528                h.pNorm();
529
530              strat->initEcart(&h);
531              h.sev = pGetShortExpVector(h.p);
532
533              int pos = 0;
534
535              if (strat->Ll != -1)
536                pos = strat->posInL(strat->L,strat->Ll,&h,strat);
537
538              enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
539            }
540      }
541    }
542  }
543
544  // compute-------------------------------------------------------
545  while (strat->Ll >= 0)
546  {
547#ifdef KDEBUG
548//     loop_count++;
549    if (TEST_OPT_DEBUG) messageSets(strat);
550#endif
551
552    if (strat->Ll== 0) strat->interpt=TRUE;
553
554    if (TEST_OPT_DEGBOUND
555        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
556            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
557    {
558
559#ifdef KDEBUG
560//      if (TEST_OPT_DEBUG){PrintS("^^^^?");}
561#endif
562
563      // *stops computation if
564      // * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
565      // *a predefined number Kstd1_deg
566      while ((strat->Ll >= 0)
567        && ( (strat->homog==isHomog) || strat->L[strat->Ll].is_special || ((strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)) )
568        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
569            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
570            )
571      {
572#ifdef KDEBUG
573//        if (TEST_OPT_DEBUG){PrintS("^^^^^^^^^^^^!!!!");}
574#endif
575        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
576//        if (TEST_OPT_PROT) PrintS("^!");
577      }
578      if (strat->Ll<0) break;
579      else strat->noClearS=TRUE;
580    }
581
582    // picks the last element from the lazyset L
583    strat->P = strat->L[strat->Ll];
584    strat->Ll--;
585
586
587//    assume(pNext(strat->P.p) != strat->tail);
588
589    if(strat->P.IsNull()) continue;
590
591    if (pNext(strat->P.p) == strat->tail)
592    {
593      // deletes the short spoly
594      pLmFree(strat->P.p);
595
596      strat->P.p = nc_CreateSpoly(strat->P.p1, strat->P.p2, currRing);
597      if (strat->P.p!=NULL) strat->initEcart(&strat->P);
598    }//    else
599
600
601    if(strat->P.IsNull()) continue;
602
603    if (strat->P.p1 == NULL)
604    {
605//       if (strat->minim > 0)
606//         strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
607
608
609      // for input polys, prepare reduction
610        strat->P.PrepareRed(strat->use_buckets);
611    }
612
613    if (TEST_OPT_PROT)
614      message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
615              &olddeg,&reduc,strat, red_result);
616
617    // reduction of the element chosen from L
618    red_result = strat->red(&strat->P,strat);
619
620
621    // reduction to non-zero new poly
622    if (red_result == 1)
623    {
624      // statistic
625      if (TEST_OPT_PROT) PrintS("s");
626
627      // get the polynomial (canonicalize bucket, make sure P.p is set)
628      strat->P.GetP(strat->lmBin);
629
630      int pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
631
632      // reduce the tail and normalize poly
633      if (TEST_OPT_INTSTRATEGY)
634      {
635        strat->P.pCleardenom();
636        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
637        {
638          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT); // !!!
639          strat->P.pCleardenom();
640        }
641      }
642      else
643      {
644        strat->P.pNorm();
645        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
646          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
647      }
648      strat->P.is_normalized=nIsOne(pGetCoeff(strat->P.p));
649
650#ifdef KDEBUG
651      if (TEST_OPT_DEBUG){PrintS(" ns:");p_wrp(strat->P.p,currRing);PrintLn();}
652#endif
653
654//       // min_std stuff
655//       if ((strat->P.p1==NULL) && (strat->minim>0))
656//       {
657//         if (strat->minim==1)
658//         {
659//           strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
660//           p_Delete(&strat->P.p2, currRing, strat->tailRing);
661//         }
662//         else
663//         {
664//           strat->M->m[minimcnt]=strat->P.p2;
665//           strat->P.p2=NULL;
666//         }
667//         if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
668//           pNext(strat->M->m[minimcnt])
669//             = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
670//                                            strat->tailRing, currRing,
671//                                            currRing->PolyBin);
672//         minimcnt++;
673//       }
674
675      // enter into S, L, and T
676      //if(withT)
677      {
678        strat->P.SetpFDeg();
679        enterT(strat->P, strat);
680      }
681
682      // L
683      enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
684
685      // posInS only depends on the leading term
686      strat->enterS(strat->P, pos, strat, strat->tl);
687
688//       if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
689
690//      Print("[%d]",hilbeledeg);
691      if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
692
693      // //////////////////////////////////////////////////////////
694      // SCA:
695      const poly pSave = strat->P.p;
696      const poly p_next = pNext(pSave);
697
698//       if(0)
699      if( p_next != NULL )
700      for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
701      if( p_GetExp(pSave, i, currRing) != 0 )
702      {
703        assume(p_GetExp(pSave, i, currRing) == 1);
704        const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
705
706#ifdef PDEBUG
707        p_Test(p_new, currRing);
708#endif
709
710        if( p_new == NULL) continue;
711
712        LObject h(p_new); // h = x_i * strat->P
713
714        h.is_special = TRUE;
715
716        if (TEST_OPT_INTSTRATEGY)
717        {
718//          p_Content(h.p);
719          h.pCleardenom(); // also does a p_Content
720        }
721        else
722        {
723          h.pNorm();
724        }
725
726        strat->initEcart(&h);
727        h.sev = pGetShortExpVector(h.p);
728
729        int pos = 0;
730
731        if (strat->Ll != -1)
732          pos = strat->posInL(strat->L,strat->Ll,&h,strat);
733
734        enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
735
736
737
738
739#if 0
740        h.sev = pGetShortExpVector(h.p);
741        strat->initEcart(&h);
742
743        h.PrepareRed(strat->use_buckets);
744
745        // reduction of the element chosen from L(?)
746        red_result = strat->red(&h,strat);
747
748        // reduction to non-zero new poly
749        if (red_result != 1) continue;
750
751
752        int pos = posInS(strat,strat->sl,h.p,h.ecart);
753
754        // reduce the tail and normalize poly
755        if (TEST_OPT_INTSTRATEGY)
756        {
757          h.pCleardenom();
758          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
759          {
760            h.p = redtailBba(&(h),pos-1,strat, withT); // !!!
761            h.pCleardenom();
762          }
763        }
764        else
765        {
766          h.pNorm();
767          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
768            h.p = redtailBba(&(h),pos-1,strat, withT);
769        }
770
771#ifdef KDEBUG
772        if (TEST_OPT_DEBUG){PrintS(" N:");h.wrp();PrintLn();}
773#endif
774
775//        h.PrepareRed(strat->use_buckets); // ???
776
777        h.sev = pGetShortExpVector(h.p);
778        strat->initEcart(&h);
779
780        if (strat->Ll==-1)
781          pos = 0;
782        else
783          pos = strat->posInL(strat->L,strat->Ll,&h,strat);
784
785         enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
786// the end of "#if 0" (comment)
787#endif
788
789      } // for all x_i \in Ann(lm(P))
790    } // if red(P) != NULL
791
792//     else if (strat->P.p1 == NULL && strat->minim > 0)
793//     {
794//       p_Delete(&strat->P.p2, currRing, strat->tailRing);
795//     }
796
797#ifdef KDEBUG
798//    memset(&(strat->P), 0, sizeof(strat->P));
799#endif
800
801    kTest_TS(strat); // even of T is not used!
802
803//     Print("\n$\n");
804
805  }
806
807#ifdef KDEBUG
808  if (TEST_OPT_DEBUG) messageSets(strat);
809#endif
810
811  // complete reduction of the standard basis---------
812
813  if (TEST_OPT_REDSB)
814  {
815    completeReduce(strat);
816  }
817
818  //release temp data--------------------------------
819
820  exitBuchMora(strat); // cleanT!
821
822  id_Delete(&tempF, currRing);
823
824//  if (TEST_OPT_WEIGHTM)
825//  {
826//    pRestoreDegProcs(currRing, pFDegOld, pLDegOld);
827//     if (ecartWeights)
828//     {
829//       omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
830//       ecartWeights=NULL;
831//     }
832//  }
833
834  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
835
836
837
838  if (tempQ!=NULL) updateResult(strat->Shdl,tempQ,strat);
839
840
841  if (TEST_OPT_REDSB) // ???
842  {
843    // must be at the very end (after exitBuchMora) as it changes the S set!!!
844    ideal I = strat->Shdl;
845    ideal erg = kInterRedOld(I,tempQ);
846    assume(I!=erg);
847    id_Delete(&I, currRing);
848    strat->Shdl = erg;
849  }
850
851#if MYTEST
852  PrintS("\n\n</sca_bba>\n\n");
853#endif
854
855  if( currRing != save )     rChangeCurrRing(save);
856
857  return (strat->Shdl);
858}
859
860// //////////////////////////////////////////////////////////////////////////////
861// sca mora...
862
863// returns TRUE if mora should use buckets, false otherwise
864#ifdef MORA_USE_BUCKETS
865static BOOLEAN kMoraUseBucket(kStrategy strat)
866#else
867static BOOLEAN kMoraUseBucket(kStrategy)
868#endif
869{
870#ifdef MORA_USE_BUCKETS
871  if (TEST_OPT_NOT_BUCKETS)
872    return FALSE;
873  if (strat->red == redFirst)
874  {
875#ifdef NO_LDEG
876    if (!strat->syzComp)
877      return TRUE;
878#else
879    if ((strat->homog || strat->honey) && !strat->syzComp)
880      return TRUE;
881#endif
882  }
883  else
884  {
885    assume(strat->red == redEcart);
886    if (strat->honey && !strat->syzComp)
887      return TRUE;
888  }
889#endif
890  return FALSE;
891}
892
893#ifdef HAVE_ASSUME
894static int sca_mora_count = 0;
895static int sca_mora_loop_count;
896#endif
897
898// ideal sca_mora (ideal F, ideal Q, intvec *w, intvec *, kStrategy strat)
899ideal sca_mora(const ideal F, const ideal Q, const intvec */*w*/, const intvec *, kStrategy strat, const ring _currRing)
900{
901  const ring save = currRing;
902  if( currRing != _currRing ) rChangeCurrRing(_currRing);
903  assume( currRing == _currRing );
904
905  assume(rIsSCA(currRing));
906
907  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
908  const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
909
910  ideal tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
911
912  ideal tempQ = Q;
913
914  if(Q == currRing->qideal)
915    tempQ = SCAQuotient(currRing);
916
917  bool bIdHomog = id_IsSCAHomogeneous(tempF, NULL, NULL, currRing); // wCx == wCy == NULL!
918
919  assume( !bIdHomog || strat->homog ); //  bIdHomog =====[implies]>>>>> strat->homog
920
921  strat->homog = strat->homog && bIdHomog;
922
923#ifdef PDEBUG
924  assume( strat->homog == bIdHomog );
925#endif
926
927#ifdef HAVE_ASSUME
928  sca_mora_count++;
929  sca_mora_loop_count = 0;
930#endif
931
932  strat->update = TRUE;
933  //- setting global variables ------------------- -
934  initBuchMoraCrit(strat);
935//   initHilbCrit(F,NULL,&hilb,strat); // no Q!
936  initMora(tempF, strat);
937  initBuchMoraPos(strat);
938  //Shdl=
939    initBuchMora(tempF, tempQ, strat); // temp Q, F!
940//   if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
941  // updateS in initBuchMora has Hecketest
942  // * and could have put strat->kHEdgdeFound FALSE
943#if 0
944  if (ppNoether!=NULL)
945  {
946    strat->kHEdgeFound = TRUE;
947  }
948  if (strat->kHEdgeFound && strat->update)
949  {
950    firstUpdate(strat);
951    updateLHC(strat);
952    reorderL(strat);
953  }
954  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
955  {
956    strat->posInLOld = strat->posInL;
957    strat->posInLOldFlag = FALSE;
958    strat->posInL = posInL10;
959    updateL(strat);
960    reorderL(strat);
961  }
962#endif
963  strat->use_buckets = kMoraUseBucket(strat);
964
965  kTest_TS(strat);
966
967
968  int olddeg = 0;
969  int reduc = 0;
970  int red_result = 1;
971//  int hilbeledeg=1;
972  int hilbcount=0;
973
974
975  //- compute-------------------------------------------
976
977#undef HAVE_TAIL_RING
978
979#ifdef HAVE_TAIL_RING
980//  if (strat->homog && strat->red == redFirst)
981//     kStratInitChangeTailRing(strat);
982#endif
983
984
985
986
987
988//  due to std( SB, p)
989  if(TEST_OPT_SB_1)
990  {
991    for (int iNewElement = strat->newIdeal; iNewElement < IDELEMS(tempF); iNewElement++)
992    {
993
994      const poly pSave = tempF->m[iNewElement];
995
996      if( pSave != NULL )
997      {
998//        tempF->m[iNewElement] = NULL;
999
1000        const poly p_next = pNext(pSave);
1001
1002        if(p_next != NULL)
1003          for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
1004            if( p_GetExp(pSave, i, currRing) != 0 )
1005            {
1006
1007              assume(p_GetExp(pSave, i, currRing) == 1);
1008
1009              const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
1010
1011#ifdef PDEBUG
1012              p_Test(p_new, currRing);
1013#endif
1014
1015              if( p_new == NULL) continue;
1016
1017              LObject h(p_new); // h = x_i * strat->P
1018
1019              if (TEST_OPT_INTSTRATEGY)
1020                h.pCleardenom(); // also does a p_Content
1021              else
1022                h.pNorm();
1023
1024              strat->initEcart(&h);
1025              h.sev = pGetShortExpVector(h.p);
1026
1027              int pos = 0;
1028
1029              if (strat->Ll != -1)
1030                pos = strat->posInL(strat->L,strat->Ll,&h,strat);
1031
1032              enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
1033            }
1034      }
1035
1036    }
1037  }
1038
1039
1040
1041
1042  while (strat->Ll >= 0)
1043  {
1044#ifdef HAVE_ASSUME
1045    sca_mora_loop_count++;
1046#endif
1047    //test_int_std(strat->kIdeal);
1048#ifdef KDEBUG
1049    if (TEST_OPT_DEBUG) messageSets(strat);
1050#endif
1051    if (TEST_OPT_DEGBOUND
1052    && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1053    {
1054      // * stops computation if
1055      // * - 24 (degBound)
1056      // *   && upper degree is bigger than Kstd1_deg
1057      while ((strat->Ll >= 0)
1058        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1059        && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1060      )
1061      {
1062        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1063        //if (TEST_OPT_PROT)
1064        //{
1065        //   PrintS("D"); mflush();
1066        //}
1067      }
1068      if (strat->Ll<0) break;
1069      else strat->noClearS=TRUE;
1070    }
1071    strat->P = strat->L[strat->Ll];// - picks the last element from the lazyset L -
1072    if (strat->Ll==0) strat->interpt=TRUE;
1073    strat->Ll--;
1074
1075    // create the real Spoly
1076//    assume(pNext(strat->P.p) != strat->tail);
1077
1078    if(strat->P.IsNull()) continue;
1079
1080
1081    if( pNext(strat->P.p) == strat->tail )
1082    {
1083      // deletes the int spoly and computes SPoly
1084      pLmFree(strat->P.p); // ???
1085      strat->P.p = nc_CreateSpoly(strat->P.p1, strat->P.p2, currRing);
1086    }
1087
1088
1089
1090    if (strat->P.p1 == NULL)
1091    {
1092      // for input polys, prepare reduction (buckets !)
1093      strat->P.SetLength(strat->length_pLength);
1094      strat->P.PrepareRed(strat->use_buckets);
1095    }
1096
1097    if (!strat->P.IsNull())
1098    {
1099      // might be NULL from noether !!!
1100      if (TEST_OPT_PROT)
1101        message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1102      // reduce
1103      red_result = strat->red(&strat->P,strat);
1104    }
1105
1106    if (! strat->P.IsNull())
1107    {
1108      strat->P.GetP();
1109      // statistics
1110      if (TEST_OPT_PROT) PrintS("s");
1111      // normalization
1112      if (!TEST_OPT_INTSTRATEGY)
1113        strat->P.pNorm();
1114      // tailreduction
1115      strat->P.p = redtail(&(strat->P),strat->sl,strat);
1116      // set ecart -- might have changed because of tail reductions
1117      if ((!strat->noTailReduction) && (!strat->honey))
1118        strat->initEcart(&strat->P);
1119      // cancel unit
1120      cancelunit(&strat->P);
1121      // for char 0, clear denominators
1122      if (TEST_OPT_INTSTRATEGY)
1123        strat->P.pCleardenom();
1124
1125      // put in T
1126      enterT(strat->P,strat);
1127      // build new pairs
1128      enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1129      // put in S
1130      strat->enterS(strat->P,
1131                    posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
1132                    strat, strat->tl);
1133
1134
1135      // clear strat->P
1136      if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
1137      strat->P.lcm=NULL;
1138
1139      // //////////////////////////////////////////////////////////
1140      // SCA:
1141      const poly pSave = strat->P.p;
1142      const poly p_next = pNext(pSave);
1143
1144      if(p_next != NULL)
1145      for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
1146      if( p_GetExp(pSave, i, currRing) != 0 )
1147      {
1148
1149        assume(p_GetExp(pSave, i, currRing) == 1);
1150
1151        const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
1152
1153#ifdef PDEBUG
1154        p_Test(p_new, currRing);
1155#endif
1156
1157        if( p_new == NULL) continue;
1158
1159        LObject h(p_new); // h = x_i * strat->P
1160
1161        if (TEST_OPT_INTSTRATEGY)
1162           h.pCleardenom(); // also does a p_Content
1163        else
1164          h.pNorm();
1165
1166        strat->initEcart(&h);
1167        h.sev = pGetShortExpVector(h.p);
1168
1169        int pos = 0;
1170
1171        if (strat->Ll != -1)
1172          pos = strat->posInL(strat->L,strat->Ll,&h,strat);
1173
1174        enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
1175      }
1176
1177#ifdef KDEBUG
1178      // make sure kTest_TS does not complain about strat->P
1179      memset(&strat->P,0,sizeof(strat->P));
1180#endif
1181    }
1182#if 0
1183    if (strat->kHEdgeFound)
1184    {
1185      if ((TEST_OPT_FINDET)
1186      || ((TEST_OPT_MULTBOUND) && (scMult0Int((strat->Shdl)) < mu)))
1187      {
1188        // obachman: is this still used ???
1189        // * stops computation if strat->kHEdgeFound and
1190        // * - 27 (finiteDeterminacyTest)
1191        // * or
1192        // * - 23
1193        // *   (multBound)
1194        // *   && multiplicity of the ideal is smaller then a predefined number mu
1195        while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1196      }
1197    }
1198#endif
1199    kTest_TS(strat);
1200  }
1201  // - complete reduction of the standard basis------------------------ -
1202  if (TEST_OPT_REDSB) completeReduce(strat);
1203  // - release temp data------------------------------- -
1204  exitBuchMora(strat);
1205  // - polynomials used for HECKE: HC, noether -
1206  if (TEST_OPT_FINDET)
1207  {
1208    if (strat->kHEdge!=NULL)
1209      Kstd1_mu=currRing->pFDeg(strat->kHEdge,currRing);
1210    else
1211      Kstd1_mu=-1;
1212  }
1213  pDelete(&strat->kHEdge);
1214  strat->update = TRUE; //???
1215  strat->lastAxis = 0; //???
1216  pDelete(&strat->kNoether);
1217  omFreeSize((ADDRESS)strat->NotUsedAxis,(rVar(currRing)+1)*sizeof(BOOLEAN));
1218  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
1219//  if (TEST_OPT_WEIGHTM)
1220//  {
1221//    pRestoreDegProcs(currRing, pFDegOld, pLDegOld);
1222//     if (ecartWeights)
1223//     {
1224//       omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1225//       ecartWeights=NULL;
1226//     }
1227//  }
1228  if (tempQ!=NULL) updateResult(strat->Shdl,tempQ,strat);
1229  idTest(strat->Shdl);
1230
1231  id_Delete( &tempF, currRing);
1232
1233  if( currRing != save )     rChangeCurrRing(save);
1234
1235  return (strat->Shdl);
1236}
1237
Note: See TracBrowser for help on using the repository browser.