source: git/kernel/GBEngine/sca.cc @ c858487

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