source: git/kernel/sca.cc @ 232bbd5

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