syzextra.cc
Go to the documentation of this file.
1 // -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 /*****************************************************************************\
3  * Computer Algebra System SINGULAR
4 \*****************************************************************************/
5 /** @file syzextra.cc
6  *
7  * New implementations for the computation of syzygies and resolutions
8  *
9  * ABSTRACT: Computation of Syzygies due to Schreyer
10  *
11  * @author Oleksandr Motsak
12  *
13  **/
14 /*****************************************************************************/
15 // include header file
16 #include <kernel/mod2.h>
17 #ifndef _GNU_SOURCE
18 #define _GNU_SOURCE /*for qsort_r on cygwin, must be before system includes*/
19 #endif
20 
21 #include <string.h>
22 
23 
24 #include "syzextra.h"
25 
26 #include "DebugPrint.h"
27 
28 #include <omalloc/omalloc.h>
29 
30 #include <misc/intvec.h>
31 #include <misc/options.h>
32 
33 #include <coeffs/coeffs.h>
34 
36 #include <polys/monomials/ring.h>
37 #include <polys/simpleideals.h>
38 
39 #include <polys/kbuckets.h> // for kBucket*
40 #include <polys/sbuckets.h> // for sBucket*
41 //#include <polys/nc/summator.h> // for CPolynomialSummator
42 #include <polys/operations/p_Mult_q.h> // for MIN_LENGTH_BUCKET
43 
44 #include <kernel/GBEngine/kstd1.h>
45 #include <kernel/polys.h>
46 #include <kernel/GBEngine/syz.h>
47 #include <kernel/ideals.h>
48 
49 #include <kernel/oswrapper/timer.h>
50 
51 
52 #include <Singular/tok.h>
53 #include <Singular/ipid.h>
54 #include <Singular/lists.h>
55 #include <Singular/attrib.h>
56 
57 #include <Singular/ipid.h>
58 #include <Singular/ipshell.h> // For iiAddCproc
59 
60 #include <stdio.h>
61 #include <stdlib.h>
62 
63 #ifndef RTIMER_BENCHMARKING
64 # define RTIMER_BENCHMARKING 0
65 #endif
66 
67 // USING_NAMESPACE_SINGULARXX;
68 USING_NAMESPACE( SINGULARXXNAME :: DEBUG )
69 
70 
72 
73 
75 
76 #ifndef SING_NDEBUG
77 ring SBucketFactory::_GetBucketRing(const SBucketFactory::Bucket& bt)
78 {
79  assume( bt != NULL );
80  return sBucketGetRing(bt);
81 }
82 
83 bool SBucketFactory::_IsBucketEmpty(const SBucketFactory::Bucket& bt)
84 {
85  assume( bt != NULL );
86  return sIsEmpty(bt);
87 }
88 #endif
89 
91 {
92  const Bucket bt = sBucketCreate(r);
93 
94  assume( bt != NULL );
95  assume( _IsBucketEmpty(bt) );
96  assume( r == _GetBucketRing(bt) );
97 
98  return bt;
99 }
100 
102 {
103  if( bt != NULL )
104  {
105  assume( _IsBucketEmpty(bt) );
106  sBucketDestroy( &bt );
107  bt = NULL;
108  }
109 }
110 
112 {
114 
115  private:
116  Bucket m_bucket;
117 
119  public:
120  SBucketWrapper(const ring r, SBucketFactory& factory):
121  m_bucket( factory.getBucket(r) ),
122  m_factory( factory )
123  {}
124 
126  {
127  m_factory.putBucket( m_bucket );
128  }
129 
130  public:
131 
132  /// adds p to the internal bucket
133  /// destroys p, l == length(p)
134  inline void Add( poly p, const int l )
135  {
136  assume( pLength(p) == l );
137  sBucket_Add_p( m_bucket, p, l );
138  }
139 
140  /// adds p to the internal bucket
141  /// destroys p
142  inline void Add( poly p ){ Add(p, pLength(p)); }
143 
145  {
146  poly p; int l;
147  sBucketClearAdd(m_bucket, &p, &l);
148  assume( pLength(p) == l );
149  return p;
150  }
151 };
152 
153 static FORCE_INLINE poly pp_Add_qq( const poly a, const poly b, const ring R)
154 {
155  return p_Add_q( p_Copy(a, R), p_Copy(b, R), R );
156 }
157 
158 static FORCE_INLINE poly p_VectorProductLT( poly s, const ideal& L, const ideal& T, const ring& R)
159 {
160  assume( IDELEMS(L) == IDELEMS(T) );
161  poly vp = NULL; // resulting vector product
162 
163  while( s != NULL )
164  {
165  const poly nxt = pNext(s);
166  pNext(s) = NULL;
167 
168  if( !n_IsZero( pGetCoeff(s), R->cf) )
169  {
170  const int i = p_GetComp(s, R) - 1;
171  assume( i >= 0 ); assume( i < IDELEMS(L) );
172  p_SetComp(s, 0, R); p_SetmComp(s, R);
173 
174  vp = p_Add_q( vp, pp_Mult_qq( s, L->m[i], R ), R);
175  vp = p_Add_q( vp, pp_Mult_qq( s, T->m[i], R ), R);
176  }
177 
178  p_Delete(&s, R);
179 
180  s = nxt;
181  };
182 
183  assume( s == NULL );
184 
185  return vp;
186 }
187 
188 static FORCE_INLINE int atGetInt(idhdl rootRingHdl, const char* attribute, long def)
189 {
190  return ((int)(long)(atGet(rootRingHdl, attribute, INT_CMD, (void*)def)));
191 }
192 
194 
195 BEGIN_NAMESPACE(SORT_c_ds)
196 
197 #if (defined(HAVE_QSORT_R) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9))
198 static int cmp_c_ds(void *R, const void *p1, const void *p2){
199 #elif (defined(HAVE_QSORT_R) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
200 static int cmp_c_ds(const void *p1, const void *p2, void *R){
201 #else
202 static int cmp_c_ds(const void *p1, const void *p2){ void *R = currRing;
203 #endif
204  assume(R != NULL);
205  const int YES = 1;
206  const int NO = -1;
207 
208  const ring r = (const ring) R; // TODO/NOTE: the structure is known: C, lp!!!
209 
210  assume( r == currRing ); // for now...
211 
212  const poly a = *(const poly*)p1;
213  const poly b = *(const poly*)p2;
214 
215  assume( a != NULL );
216  assume( b != NULL );
217 
218  p_LmTest(a, r);
219  p_LmTest(b, r);
220 
221 
222  const signed long iCompDiff = p_GetComp(a, r) - p_GetComp(b, r);
223 
224  // TODO: test this!!!!!!!!!!!!!!!!
225 
226  //return -( compare (c, qsorts) )
227 
228 #ifndef SING_NDEBUG
229  const int OPT__DEBUG = 0;
230  if( OPT__DEBUG )
231  {
232  PrintS("cmp_c_ds: a, b: \np1: "); dPrint(a, r, r, 0);
233  PrintS("b: "); dPrint(b, r, r, 0);
234  PrintLn();
235  }
236 #endif
237 
238 
239  if( iCompDiff > 0 )
240  return YES;
241 
242  if( iCompDiff < 0 )
243  return NO;
244 
245  assume( iCompDiff == 0 );
246 
247  const signed long iDegDiff = p_Totaldegree(a, r) - p_Totaldegree(b, r);
248 
249  if( iDegDiff > 0 )
250  return YES;
251 
252  if( iDegDiff < 0 )
253  return NO;
254 
255  assume( iDegDiff == 0 );
256 
257 #ifndef SING_NDEBUG
258  if( OPT__DEBUG )
259  {
260  PrintS("cmp_c_ds: a & b have the same comp & deg! "); PrintLn();
261  }
262 #endif
263 
264  for (int v = rVar(r); v > 0; v--)
265  {
266  assume( v > 0 );
267  assume( v <= rVar(r) );
268 
269  const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
270 
271  if( d > 0 )
272  return YES;
273 
274  if( d < 0 )
275  return NO;
276 
277  assume( d == 0 );
278  }
279 
280  return 0;
281 }
282 
283 /*
284 static int cmp_poly(const poly &a, const poly &b)
285 {
286  const int YES = 1;
287  const int NO = -1;
288 
289  const ring r = (const ring) currRing; // TODO/NOTE: the structure is known: C, lp!!!
290 
291  assume( r == currRing );
292 
293  assume( a != NULL );
294  assume( b != NULL );
295 
296  p_LmTest(a, r);
297  p_LmTest(b, r);
298  assume( p_GetComp(a, r) == 0 );
299  assume( p_GetComp(b, r) == 0 );
300 
301 #ifndef SING_NDEBUG
302  const int OPT__DEBUG = 0;
303  if( OPT__DEBUG )
304  {
305  PrintS("cmp_lex: a, b: \np1: "); dPrint(a, r, r, 0);
306  PrintS("b: "); dPrint(b, r, r, 0);
307  PrintLn();
308  }
309 #endif
310 
311  for (int v = rVar(r); v > 0; v--)
312  {
313  assume( v > 0 );
314  assume( v <= rVar(r) );
315 
316  const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
317 
318  if( d > 0 )
319  return YES;
320 
321  if( d < 0 )
322  return NO;
323 
324  assume( d == 0 );
325  }
326 
327  return 0;
328 }
329 */
330 
332 /* namespace SORT_c_ds */
333 
334 /// writes a monomial (p),
335 /// uses form x*gen(.) if ko != coloumn number of p
336 static void writeLatexTerm(const poly t, const ring r, const bool bCurrSyz = true, const bool bLTonly = true)
337 {
338  if( t == NULL )
339  {
340  PrintS(" 0 ");
341  return;
342  }
343 
344  assume( r != NULL );
345  const coeffs C = r->cf; assume(C != NULL);
346 
347  poly p = t;
348  BOOLEAN writePlus = FALSE;
349 
350  do {
351  assume( p != NULL );
352 
353  // write coef...
354  number& n = p_GetCoeff(p, r);
355 
356  n_Normalize(n, C);
357 
358  BOOLEAN writeMult = FALSE; ///< needs * before pp or module generator
359 
360  BOOLEAN writeOne = FALSE; ///< need to write something after '-'!
361 
362  if( n_IsZero(n, C) )
363  {
364  PrintS( writePlus? " + 0" : " 0 " ); writePlus = TRUE; writeMult = TRUE;
365 // return; // yes?
366  }
367 
368  if (n_IsMOne(n, C))
369  {
370  PrintS(" - "); writeOne = TRUE; writePlus = FALSE;
371  }
372  else if (!n_IsOne(n, C))
373  {
374  if( writePlus && n_GreaterZero(n, C) )
375  PrintS(" + ");
376 
377  StringSetS(""); n_WriteLong(n, C);
378  if (true)
379  {
380  char *s = StringEndS(); PrintS(s); omFree(s);
381  }
382 
383 
384  writeMult = TRUE;
385  writePlus = TRUE;
386  } else
387  writeOne = TRUE;
388 
389  // missing '1' if no PP and gen...!?
390  // write monom...
391  const short N = rVar(r);
392 
393  BOOLEAN wrotePP = FALSE; ///< needs * before module generator?
394 
395  for (short i = 0; i < N; i++)
396  {
397  const long ee = p_GetExp(p, i+1, r);
398 
399  if (ee!=0L)
400  {
401  if (writeMult)
402  {
403  PrintS(" ");
404  writeMult = FALSE;
405  } else
406  if( writePlus )
407  PrintS(" + ");
408 
409  writePlus = FALSE;
410 
411  if (ee != 1L)
412  Print(" %s^{%ld} ", rRingVar(i, r), ee);
413  else
414  Print(" %s ", rRingVar(i, r));
415 
416  writeOne = FALSE;
417  wrotePP = TRUE;
418  }
419  }
420 
421  writePlus = writePlus || wrotePP;
422  writeMult = writeMult || wrotePP;
423 
424  // write module gen...
425  const long comp = p_GetComp(p, r);
426 
427  if (comp > 0 )
428  {
429  if (writeMult)
430  PrintS(" ");
431  else
432  if( writePlus )
433  PrintS(" + ");
434 
435  if (bCurrSyz)
436  Print(" \\\\GEN{%ld} ", comp);
437  else
438  Print(" \\\\GENP{%ld} ", comp);
439 
440  writeOne = FALSE;
441  }
442 
443  if ( writeOne )
444  PrintS( writePlus? " + 1 " : " 1 " );
445 
446 
447  pIter(p);
448 
449  writePlus = TRUE;
450  } while( (!bLTonly) && (p != NULL) );
451 
452 }
453 
454 
455 
456 static FORCE_INLINE poly myp_Head(const poly p, const bool bIgnoreCoeff, const ring r)
457 {
458  assume( p != NULL ); p_LmCheckPolyRing1(p, r);
459 
460  poly np; omTypeAllocBin(poly, np, r->PolyBin);
461  p_SetRingOfLm(np, r);
462  memcpy(np->exp, p->exp, r->ExpL_Size*sizeof(long));
463  pNext(np) = NULL;
464  pSetCoeff0(np, (bIgnoreCoeff)? NULL : n_Copy(pGetCoeff(p), r->cf));
465 
466  p_LmCheckPolyRing1(np, r);
467  return np;
468 }
469 
470 
471 /// return a new term: leading coeff * leading monomial of p
472 /// with 0 leading component!
473 poly leadmonom(const poly p, const ring r, const bool bSetZeroComp)
474 {
475  if( UNLIKELY(p == NULL ) )
476  return NULL;
477 
478  assume( p != NULL );
479  p_LmTest(p, r);
480 
481  poly m = p_LmInit(p, r);
482  p_SetCoeff0(m, n_Copy(pGetCoeff(p), r->cf), r);
483 
484  if( bSetZeroComp )
485  p_SetComp(m, 0, r);
486 
487  p_Setm(m, r);
488 
489  assume( m != NULL );
490  assume( pNext(m) == NULL );
491  p_LmTest(m, r);
492 
493  if( bSetZeroComp )
494  assume( p_GetComp(m, r) == 0 );
495 
496  return m;
497 }
498 
499 
500 
501 poly p_Tail(const poly p, const ring r)
502 {
503  if( UNLIKELY(p == NULL) )
504  return NULL;
505  else
506  return p_Copy( pNext(p), r );
507 }
508 
509 
510 ideal id_Tail(const ideal id, const ring r)
511 {
512  if( UNLIKELY(id == NULL) )
513  return NULL;
514 
515  const ideal newid = idInit(IDELEMS(id),id->rank);
516 
517  for (int i=IDELEMS(id) - 1; i >= 0; i--)
518  newid->m[i] = p_Tail( id->m[i], r );
519 
520  newid->rank = id_RankFreeModule(newid, currRing);
521 
522  return newid;
523 }
524 
525 
526 
527 void Sort_c_ds(const ideal id, const ring r)
528 {
529  const int sizeNew = IDELEMS(id);
530 
531 #if ( (defined(HAVE_QSORT_R)) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9) )
532 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, r, cmp)
533 #elif ( (defined(HAVE_QSORT_R)) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
534 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, cmp, r)
535 #else
536 #define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, cmp)
537 #endif
538 
539  if( sizeNew >= 2 )
540  qsort_my(id->m, sizeNew, sizeof(poly), r, FROM_NAMESPACE(SORT_c_ds, cmp_c_ds));
541 
542 #undef qsort_my
543 
544  id->rank = id_RankFreeModule(id, r);
545 }
546 
547 /// Clean up all the accumulated data
549 {
550  id_Delete(const_cast<ideal*>(&m_idTails), m_rBaseRing); // TODO!!!
551 
552 /*if( m_sum_bucket != NULL )
553  {
554  assume ( sIsEmpty(m_sum_bucket) );
555  sBucketDestroy(&m_sum_bucket);
556  m_sum_bucket = NULL;
557  }*/
558 
559  if( m_spoly_bucket != NULL )
560  {
561  kBucketDestroy(&m_spoly_bucket);
562  m_spoly_bucket = NULL;
563  }
564 
565  for( TCache::iterator it = m_cache.begin(); it != m_cache.end(); it++ )
566  {
567  TP2PCache& T = it->second;
568 
569  for(TP2PCache::iterator vit = T.begin(); vit != T.end(); vit++ )
570  {
571  p_Delete( (&(vit->second)), m_rBaseRing);
572  p_Delete( const_cast<poly*>(&(vit->first)), m_rBaseRing);
573  }
574  }
575 }
576  /*
577  for( TTailTerms::const_iterator it = m_idTailTerms.begin(); it != m_idTailTerms.end(); it++ )
578  {
579  const TTail& v = *it;
580  for(TTail::const_iterator vit = v.begin(); vit != v.end(); vit++ )
581  delete const_cast<CTailTerm*>(*vit);
582  }
583  */
584 
585 
586 
587 int CReducerFinder::PreProcessTerm(const poly t, CReducerFinder& syzChecker) const
588 {
589  assume( t != NULL );
590 
591  if( UNLIKELY(OPT__DEBUG & OPT__TAILREDSYZ) )
592  assume( !IsDivisible(t) ); // each input term should NOT be in <L>
593 
594  const ring r = m_rBaseRing;
595 
596 
597  if( LIKELY(OPT__TAILREDSYZ) )
598  if( p_LmIsConstant(t, r) ) // most basic case of baing coprime with L, whatever that is...
599  return 1; // TODO: prove this...?
600 
601  // return false; // appears to be fine
602 
603  const long comp = p_GetComp(t, r);
604 
605  CReducersHash::const_iterator itr = m_hash.find(comp);
606 
607  if ( itr == m_hash.end() )
608  return 2; // no such leading component!!!
609 
610  assume( itr->first == comp );
611 
612  const bool bIdealCase = (comp == 0);
613  const bool bSyzCheck = syzChecker.IsNonempty(); // need to check even in ideal case????? proof? "&& !bIdealCase"
614 
615  if( LIKELY(OPT__TAILREDSYZ && (bIdealCase || bSyzCheck)) )
616  {
617  const TReducers& v = itr->second;
618  const int N = rVar(r);
619  // TODO: extract exps of t beforehand?!
620  bool coprime = true;
621  for(TReducers::const_iterator vit = v.begin(); (vit != v.end()) && coprime; ++vit )
622  {
623  assume( (*vit)->CheckLT( m_L ) );
624 
625  const poly p = (*vit)->lt();
626 
627  assume( p_GetComp(p, r) == comp );
628 
629  // TODO: check if coprime with Leads... if OPT__TAILREDSYZ !
630  for( int var = N; var > 0; --var )
631  if( (p_GetExp(p, var, r) != 0) && (p_GetExp(t, var, r) != 0) )
632  {
633 #ifndef SING_NDEBUG
634  if( OPT__DEBUG | 0)
635  {
636  PrintS("CReducerFinder::PreProcessTerm, 't' is NOT co-prime with the following leading term: \n");
637  dPrint(p, r, r, 0);
638  }
639 #endif
640  coprime = false; // t not coprime with p!
641  break;
642  }
643 
644  if( bSyzCheck && coprime )
645  {
646  poly ss = p_LmInit(t, r);
647  p_SetCoeff0(ss, n_Init(1, r->cf), r); // for delete & printout only!...
648  p_SetComp(ss, (*vit)->label() + 1, r); // coeff?
649  p_Setm(ss, r);
650 
651  coprime = ( syzChecker.IsDivisible(ss) );
652 
653 #ifndef SING_NDEBUG
654  if( OPT__DEBUG && !coprime)
655  {
656  PrintS("CReducerFinder::PreProcessTerm, 't' is co-prime with p but may lead to NOT divisible syz.term: \n");
657  dPrint(ss, r, r, 0);
658  }
659 #endif
660 
661  p_LmDelete(&ss, r); // deletes coeff as well???
662  }
663 
664  assume( p == (*vit)->lt() );
665  assume( (*vit)->CheckLT( m_L ) );
666  }
667 
668 #ifndef SING_NDEBUG
669  if( OPT__DEBUG && coprime )
670  PrintS("CReducerFinder::PreProcessTerm, the following 't' is 'co-prime' with all of leading terms! \n");
671 #endif
672 
673  return coprime? 3: 0; // t was coprime with all of leading terms!!!
674 
675  }
676  // return true; // delete the term
677 
678  return 0;
679 }
680 
681 
683 {
684  const ideal idTails = m_idTails;
685  assume( idTails != NULL );
686  assume( idTails->m != NULL );
687  const ring r = m_rBaseRing;
688 
689  unsigned long pp[4] = {0,0,0,0}; // count preprocessed terms...
690 
691 #ifndef SING_NDEBUG
692  if( OPT__DEBUG | 0)
693  {
694  PrintS("SchreyerSyzygyComputation::SetUpTailTerms(): Tails: \n");
695  dPrint(idTails, r, r, 0);
696  }
697 #endif
698 
699  for( int p = IDELEMS(idTails) - 1; p >= 0; --p )
700  for( poly* tt = &(idTails->m[p]); (*tt) != NULL; )
701  {
702  const poly t = *tt;
703  const int k = m_div.PreProcessTerm(t, m_checker); // 0..3
704  assume( 0 <= k && k <= 3 );
705 
706  pp[k]++; // collect stats
707 
708  if( k )
709  {
710 #ifndef SING_NDEBUG
711  if( OPT__DEBUG)
712  {
713  Print("SchreyerSyzygyComputation::SetUpTailTerms(): PP (%d) the following TT: \n", k);
714  dPrint(t, r, r, 0);
715  }
716 #endif
717 
718  (*tt) = p_LmDeleteAndNext(t, r); // delete the lead and next...
719  }
720  else
721  tt = &pNext(t); // go next?
722 
723  }
724 
725 #ifndef SING_NDEBUG
726  if( OPT__DEBUG | 0)
727  {
728  PrintS("SchreyerSyzygyComputation::SetUpTailTerms(): Preprocessed Tails: \n");
729  dPrint(idTails, r, r, 0);
730  }
731 #endif
732 
733  if( UNLIKELY(OPT__PROT) )
734  {
735  Print("(PP/ST: {c: %lu, C: %lu, P: %lu} + %lu)", pp[1], pp[2], pp[3], pp[0]);
736  m_stat[0] += pp [0]; m_stat[1] += pp [1]; m_stat[2] += pp [2]; m_stat[3] += pp [3];
737  }
738 }
739 
740 /*
741  m_idTailTerms.resize( IDELEMS(idTails) );
742 
743  for( unsigned int p = IDELEMS(idTails) - 1; p >= 0; p -- )
744  {
745  TTail& v = m_idTailTerms[p];
746  poly t = idTails->m[p];
747  v.resize( pLength(t) );
748 
749  unsigned int pp = 0;
750 
751  while( t != NULL )
752  {
753  assume( t != NULL );
754  // TODO: compute L:t!
755 // ideal reducers;
756 // CReducerFinder m_reducers
757 
758  CTailTerm* d = v[pp] = new CTailTerm();
759 
760  ++pp; pIter(t);
761  }
762  }
763 */
764 
766 {
767  Print("SchreyerSyzygyComputation Stats: (PP/ST: {c: %lu, C: %lu, P: %lu} + %lu, LOT: %lu, LCM: %lu, ST:%lu, LK: %lu {*: %lu})\n",
768  m_stat[1], m_stat[2], m_stat[3], m_stat[0],
769  m_stat[4], m_stat[5],
770  m_stat[8],
771  m_stat[6] + m_stat[7], m_stat[7]
772  );
773 }
774 
775 
777 {
778  const ideal& id = m_idLeads;
779  const ring& r = m_rBaseRing;
780 // const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
781 
782  assume(!OPT__LEAD2SYZ);
783 
784  // 1. set of components S?
785  // 2. for each component c from S: set of indices of leading terms
786  // with this component?
787  // 3. short exp. vectors for each leading term?
788 
789  const int size = IDELEMS(id);
790 
791  if( size < 2 )
792  {
793  const ideal newid = idInit(1, 0); newid->m[0] = NULL; // zero ideal...
794  return newid;
795  }
796 
797  // TODO/NOTE: input is supposed to be (reverse-) sorted wrt "(c,ds)"!??
798 
799  // components should come in groups: count elements in each group
800  // && estimate the real size!!!
801 
802 
803  // use just a vector instead???
804  const ideal newid = idInit( (size * (size-1))/2, size); // maximal size: ideal case!
805 
806  int k = 0;
807 
808  for (int j = 0; j < size; j++)
809  {
810  const poly p = id->m[j];
811  assume( p != NULL );
812  const int c = p_GetComp(p, r);
813 
814  for (int i = j - 1; i >= 0; i--)
815  {
816  const poly pp = id->m[i];
817  assume( pp != NULL );
818  const int cc = p_GetComp(pp, r);
819 
820  if( c != cc )
821  continue;
822 
823  const poly m = p_Init(r); // p_New???
824 
825  // m = LCM(p, pp) / p! // TODO: optimize: knowing the ring structure: (C/lp)!
826  for (int v = rVar(r); v > 0; v--)
827  {
828  assume( v > 0 );
829  assume( v <= rVar(r) );
830 
831  const short e1 = p_GetExp(p , v, r);
832  const short e2 = p_GetExp(pp, v, r);
833 
834  if( e1 >= e2 )
835  p_SetExp(m, v, 0, r);
836  else
837  p_SetExp(m, v, e2 - e1, r);
838 
839  }
840 
841  assume( (j > i) && (i >= 0) );
842 
843  p_SetComp(m, j + 1, r);
844  pNext(m) = NULL;
845  p_SetCoeff0(m, n_Init(1, r->cf), r); // for later...
846 
847  p_Setm(m, r); // should not do anything!!!
848 
849  newid->m[k++] = m;
850  }
851  }
852 
853 // if( OPT__DEBUG & FALSE )
854 // {
855 // PrintS("ComputeLeadingSyzygyTerms::Temp0: \n");
856 // dPrint(newid, r, r, 0);
857 // }
858 
859  // the rest of newid is assumed to be zeroes...
860 
861  // simplify(newid, 2 + 32)??
862  // sort(newid, "C,ds")[1]???
863  id_DelDiv(newid, r); // #define SIMPL_LMDIV 32
864 
865 // if( OPT__DEBUG & FALSE )
866 // {
867 // PrintS("ComputeLeadingSyzygyTerms::Temp1: \n");
868 // dPrint(newid, r, r, 0);
869 // }
870 
871  idSkipZeroes(newid); // #define SIMPL_NULL 2
872 
873 // if( OPT__DEBUG )
874 // {
875 // PrintS("ComputeLeadingSyzygyTerms::Output: \n");
876 // dPrint(newid, r, r, 0);
877 // }
878 
879  Sort_c_ds(newid, r);
880 
881  return newid;
882 }
883 
885 {
886  const ideal& id = m_idLeads;
887  const ring& r = m_rBaseRing;
888 // const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
889 
890  // 1. set of components S?
891  // 2. for each component c from S: set of indices of leading terms
892  // with this component?
893  // 3. short exp. vectors for each leading term?
894 
895  const int size = IDELEMS(id);
896 
897  if( size < 2 )
898  {
899  const ideal newid = idInit(1, 1); newid->m[0] = NULL; // zero module...
900  return newid;
901  }
902 
903 
904  // TODO/NOTE: input is supposed to be sorted wrt "C,ds"!??
905 
906  // components should come in groups: count elements in each group
907  // && estimate the real size!!!
908 
909 
910  // use just a vector instead???
911  ideal newid = idInit( (size * (size-1))/2, size); // maximal size: ideal case!
912 
913  int k = 0;
914 
915  for (int j = 0; j < size; j++)
916  {
917  const poly p = id->m[j];
918  assume( p != NULL );
919  const int c = p_GetComp(p, r);
920 
921  for (int i = j - 1; i >= 0; i--)
922  {
923  const poly pp = id->m[i];
924  assume( pp != NULL );
925  const int cc = p_GetComp(pp, r);
926 
927  if( c != cc )
928  continue;
929 
930  // allocate memory & zero it out!
931  const poly m = p_Init(r); const poly mm = p_Init(r);
932 
933 
934  // m = LCM(p, pp) / p! mm = LCM(p, pp) / pp!
935  // TODO: optimize: knowing the ring structure: (C/lp)!
936 
937  for (int v = rVar(r); v > 0; v--)
938  {
939  assume( v > 0 );
940  assume( v <= rVar(r) );
941 
942  const short e1 = p_GetExp(p , v, r);
943  const short e2 = p_GetExp(pp, v, r);
944 
945  if( e1 >= e2 )
946  p_SetExp(mm, v, e1 - e2, r); // p_SetExp(m, v, 0, r);
947  else
948  p_SetExp(m, v, e2 - e1, r); // p_SetExp(mm, v, 0, r);
949 
950  }
951 
952  assume( (j > i) && (i >= 0) );
953 
954  p_SetComp(m, j + 1, r);
955  p_SetComp(mm, i + 1, r);
956 
957  const number& lc1 = p_GetCoeff(p , r);
958  const number& lc2 = p_GetCoeff(pp, r);
959 
960 #if NODIVISION
961  assume( n_IsOne(lc1, r->cf) );
962  assume( n_IsOne(lc2, r->cf) );
963 
964  p_SetCoeff0( m, n_Init( 1, r->cf), r );
965  p_SetCoeff0(mm, n_Init(-1, r->cf), r );
966 #else
967  number g = n_Lcm( lc1, lc2, r->cf );
968  p_SetCoeff0(m , n_Div(g, lc1, r), r);
969  p_SetCoeff0(mm, n_InpNeg(n_Div(g, lc2, r), r), r);
970  n_Delete(&g, r);
971 #endif
972 
973  p_Setm(m, r); // should not do anything!!!
974  p_Setm(mm, r); // should not do anything!!!
975 
976  pNext(m) = mm; // pNext(mm) = NULL;
977 
978  newid->m[k++] = m;
979  }
980  }
981 
982 // if( OPT__DEBUG & FALSE )
983 // {
984 // PrintS("Compute2LeadingSyzygyTerms::Temp0: \n");
985 // dPrint(newid, r, r, 0);
986 // }
987 
988  if( UNLIKELY(!OPT__TAILREDSYZ) )
989  {
990  // simplify(newid, 2 + 32)??
991  // sort(newid, "C,ds")[1]???
992  id_DelDiv(newid, r); // #define SIMPL_LMDIV 32
993 
994 // if( OPT__DEBUG & FALSE )
995 // {
996 // PrintS("Compute2LeadingSyzygyTerms::Temp1 (deldiv): \n");
997 // dPrint(newid, r, r, 0);
998 // }
999  }
1000  else
1001  {
1002  // option(redSB); option(redTail);
1003  // TEST_OPT_REDSB
1004  // TEST_OPT_REDTAIL
1005  assume( r == currRing );
1006 
1007  BITSET _save_test; SI_SAVE_OPT1(_save_test);
1009 
1010  intvec* w=new intvec(IDELEMS(newid));
1011  ideal tmp = kStd(newid, currRing->qideal, isHomog, &w);
1012  delete w;
1013 
1014  SI_RESTORE_OPT1(_save_test)
1015 
1016  id_Delete(&newid, r);
1017  newid = tmp;
1018 
1019 // if( OPT__DEBUG & FALSE )
1020 // {
1021 // PrintS("Compute2LeadingSyzygyTerms::Temp1 (std): \n");
1022 // dPrint(newid, r, r, 0);
1023 // }
1024 
1025  }
1026 
1027  idSkipZeroes(newid);
1028 
1029  Sort_c_ds(newid, r);
1030 
1031  return newid;
1032 }
1033 
1035 {
1036 #ifndef SING_NDEBUG
1037  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1038 #endif
1039 
1040  const ideal& L = m_idLeads;
1041  const ideal& T = m_idTails;
1042 
1043  const ring& R = m_rBaseRing;
1044 
1045  const int r = p_GetComp(a, R) - 1;
1046 
1047  assume( r >= 0 && r < IDELEMS(T) );
1048  assume( r >= 0 && r < IDELEMS(L) );
1049 
1050  assume( a != NULL );
1051 
1052 #ifndef SING_NDEBUG
1053  if( OPT__DEBUG )
1054  {
1055  PrintS("SchreyerSyzygyComputation::TraverseNF(syz_lead, poly syz_2), \n");
1056  PrintS("syz_lead: \n");
1057  dPrint(a, R, R, 0);
1058  PrintS("syz_2: \n");
1059  dPrint(a2, R, R, 0);
1060  PrintLn();
1061  }
1062 #endif
1063 
1064  if( UNLIKELY(OPT__TREEOUTPUT) )
1065  {
1066  PrintS("{ \"proc\": \"TraverseNF\", \"nodelabel\": \"");
1067  writeLatexTerm(a, R);
1068  PrintS("\", \"children\": [");
1069  }
1070 
1071  poly aa = leadmonom(a, R); assume( aa != NULL); // :(
1072 
1073 #ifndef SING_NDEBUG
1074  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1075 #endif
1076 
1077  poly t = TraverseTail(aa, r);
1078 
1079  if( a2 != NULL )
1080  {
1081  assume( OPT__LEAD2SYZ );
1082 
1083  if( UNLIKELY(OPT__TREEOUTPUT) )
1084  {
1085 
1086  PrintS("{ \"proc\": \"TraverseNF2\", \"nodelabel\": \"");
1087  writeLatexTerm(a2, R);
1088  PrintS("\", \"children\": [");
1089  }
1090 
1091  // replace the following... ?
1092  const int r2 = p_GetComp(a2, R) - 1; poly aa2 = leadmonom(a2, R); // :(
1093 
1094  assume( r2 >= 0 && r2 < IDELEMS(T) );
1095 
1096  poly s = TraverseTail(aa2, r2);
1097 
1098  p_Delete(&aa2, R);
1099 
1100 
1101  if( UNLIKELY(OPT__TREEOUTPUT) )
1102  {
1103  PrintS("], \"noderesult\": \"");
1104  writeLatexTerm(s, R, true, false);
1105  PrintS("\" },");
1106  }
1107 
1108  t = p_Add_q(a2, p_Add_q(t, s, R), R);
1109 
1110 #ifndef SING_NDEBUG
1111  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1112 #endif
1113 
1114  } else
1115  t = p_Add_q(t, ReduceTerm(aa, L->m[r], a), R); // should be identical to bove with a2
1116 
1117  p_Delete(&aa, R);
1118 
1119  if( UNLIKELY(OPT__TREEOUTPUT) )
1120  {
1121 // poly tt = pp_Add_qq( a, t, R);
1122  PrintS("], \"noderesult\": \"");
1123  writeLatexTerm(t, R, true, false);
1124  PrintS("\" },");
1125 // p_Delete(&tt, R);
1126  }
1127 #ifndef SING_NDEBUG
1128  if( OPT__DEBUG )
1129  {
1130  PrintS("SchreyerSyzygyComputation::TraverseNF(syz_lead, poly syz_2), ==>>> \n");
1131  dPrint(t, R, R, 0);
1132  PrintLn();
1133  }
1134 #endif
1135 
1136 #ifndef SING_NDEBUG
1137  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1138 #endif
1139 
1140  return t;
1141 }
1142 
1144 {
1145 #ifndef SING_NDEBUG
1146  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1147 #endif
1148 
1149  assume( m_idLeads != NULL );
1150  assume( m_idTails != NULL );
1151 
1152  const ideal& L = m_idLeads;
1153  const ideal& T = m_idTails;
1154 
1155  ideal& TT = m_syzTails;
1156  const ring& R = m_rBaseRing;
1157 
1158 // if( m_sum_bucket == NULL )
1159 // m_sum_bucket = sBucketCreate(R);
1160 // assume ( sIsEmpty(m_sum_bucket) );
1161 
1162  if( m_spoly_bucket == NULL )
1163  m_spoly_bucket = kBucketCreate(R);
1164 
1165 
1166  assume( IDELEMS(L) == IDELEMS(T) );
1167 
1168 #ifdef SING_NDEBUG
1169  int t, r; // for rtimer benchmarking in prot realease mode
1170 #endif
1171 
1172  if( UNLIKELY(OPT__TREEOUTPUT) )
1173  Print("\n{ \"syzygylayer\": \"%d\", \"hybridnf\": \"%d\", \"diagrams\": \n[", OPT__SYZNUMBER, OPT__HYBRIDNF );
1174 
1175  if( UNLIKELY(OPT__PROT) ) Print("\n[%d]", OPT__SYZNUMBER );
1176 
1177  if( m_syzLeads == NULL )
1178  {
1179 #ifdef SING_NDEBUG
1180  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1181  {
1182  t = getTimer(); r = getRTimer();
1183  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: t: %d, r: %d\n", r, t, r);
1184  }
1185 #endif
1186 
1187  ComputeLeadingSyzygyTerms( OPT__LEAD2SYZ && !OPT__IGNORETAILS ); // 2 terms OR 1 term!
1188 
1189 #ifdef SING_NDEBUG
1190  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1191  {
1192  t = getTimer() - t; r = getRTimer() - r;
1193  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: dt: %d, dr: %d\n", getRTimer(), t, r);
1194  }
1195 #endif
1196 
1197  }
1198 
1199  assume( m_syzLeads != NULL );
1200  ideal& LL = m_syzLeads;
1201  const int size = IDELEMS(LL);
1202 
1203  TT = idInit(size, 0);
1204 
1205  if( size == 1 && LL->m[0] == NULL )
1206  {
1207  if( UNLIKELY(OPT__TREEOUTPUT) )
1208  PrintS("]},");
1209  return;
1210  }
1211 
1212 
1213  // use hybrid (Schreyer NF) method?
1214  const bool method = (OPT__HYBRIDNF == 1); // || (OPT__HYBRIDNF == 2 && OPT__SYZNUMBER < 3);
1215 
1216  if( UNLIKELY(OPT__PROT) ) Print("[%s NF|%s]",(method) ? "PR" : "TT", (NOPRODUCT == 1)? "_,_": "^*^" );
1217 
1218 
1219  if( LIKELY(!OPT__IGNORETAILS) )
1220  {
1221  if( T != NULL )
1222  {
1223 #ifdef SING_NDEBUG
1224  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1225  {
1226  t = getTimer(); r = getRTimer();
1227  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): t: %d, r: %d\n", r, t, r);
1228  }
1229 #endif
1230 
1231  SetUpTailTerms();
1232 
1233 #ifdef SING_NDEBUG
1234  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1235  {
1236  t = getTimer() - t; r = getRTimer() - r;
1237  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): dt: %d, dr: %d\n", getRTimer(), t, r);
1238  }
1239 #endif
1240  }
1241  }
1242 
1243 #ifdef SING_NDEBUG
1244  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1245  {
1246  t = getTimer(); r = getRTimer();
1247  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: t: %d, r: %d\n", r, t, r);
1248  }
1249 #endif
1250 
1251 #ifndef SING_NDEBUG
1252  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1253 #endif
1254 
1255 // for( int k = 0; k < size; ++k ) // TODO: should be fine now!
1256  for( int k = size - 1; k >= 0; --k )
1257  {
1258  const poly a = LL->m[k]; assume( a != NULL );
1259 
1260  poly a2 = pNext(a);
1261 
1262  // Splitting 2-terms Leading syzygy module
1263  if( a2 != NULL )
1264  pNext(a) = NULL;
1265 
1266  if( UNLIKELY(OPT__IGNORETAILS) )
1267  {
1268  TT->m[k] = NULL;
1269 
1270  assume( a2 != NULL );
1271 
1272  if( a2 != NULL )
1273  p_Delete(&a2, R);
1274 
1275  continue;
1276  }
1277 
1278  // TT->m[k] = a2;
1279 
1280 #ifndef SING_NDEBUG
1281  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1282 #endif
1283 
1284  poly nf;
1285 
1286  if( method )
1287  nf = SchreyerSyzygyNF(a, a2);
1288  else
1289  nf = TraverseNF(a, a2);
1290 
1291 #ifndef SING_NDEBUG
1292  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1293 #endif
1294 
1295  TT->m[k] = nf;
1296 
1297  if( UNLIKELY(OPT__SYZCHECK) )
1298  {
1299  // TODO: check the correctness (syzygy property): a + TT->m[k] should be a syzygy!!!
1300 
1301  poly s = pp_Add_qq( a, TT->m[k], R); // current syzygy
1302 
1303  poly vp = p_VectorProductLT(s, L, T, R);
1304 
1305  if( UNLIKELY( OPT__DEBUG && (vp != NULL) && ! OPT__TREEOUTPUT ) )
1306  {
1307  Warn("SchreyerSyzygyComputation::ComputeSyzygy: failed syzygy property for syzygy [%d], non-zero image is as follows: ", k);
1308  dPrint(vp, R, R, 0); p_Delete(&vp, R);
1309 
1310  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: Wrong syzygy is as follows: ");
1311  s = pp_Add_qq( a, TT->m[k], R);
1312  dPrint(s, R, R, 0); p_Delete(&s, R);
1313 
1314  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: Testing with the other method");
1315 
1316  if( !method )
1317  s = SchreyerSyzygyNF(a, a2);
1318  else
1319  s = TraverseNF(a, a2);
1320 
1321  s = p_Add_q( p_Copy(a, R), s, R); // another syzygy // :((((
1322  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: The other method gives the following syzygy: ");
1323  dPrint(s, R, R, 0);
1324 
1325  vp = p_VectorProductLT(s, L, T, R);
1326 
1327  if( vp == NULL )
1328  {
1329  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: .... which is correct!!! ");
1330  } else
1331  {
1332  Warn("SchreyerSyzygyComputation::ComputeSyzygy: failed to compute syzygy tail[%d] with both methods!!! Non-zero image (2nd) is as follows: ", k);
1333  dPrint(vp, R, R, 0);
1334  }
1335 
1336 #ifndef SING_NDEBUG
1337  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1338 #endif
1339 
1340  } else
1341  assume( vp == NULL );
1342 
1343  if( UNLIKELY( OPT__PROT && (vp != NULL) ) ) Warn("ERROR: SyzCheck failed, wrong tail: [%d]\n\n", k); // check k'th syzygy failed
1344 
1345  p_Delete(&vp, R);
1346  }
1347 
1348 #ifndef SING_NDEBUG
1349  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1350 #endif
1351  }
1352 
1353 #ifdef SING_NDEBUG
1354  if( UNLIKELY( OPT__PROT & RTIMER_BENCHMARKING ) )
1355  {
1356  t = getTimer() - t; r = getRTimer() - r;
1357  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: dt: %d, dr: %d\n", getRTimer(), t, r);
1358  }
1359 #endif
1360 
1361  TT->rank = id_RankFreeModule(TT, R);
1362 
1363  if( UNLIKELY(OPT__TREEOUTPUT) )
1364  PrintS("\n]},");
1365 
1366  if( UNLIKELY(OPT__PROT) ) PrintLn();
1367 }
1368 
1370 {
1371 // const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
1372 
1373 // const BOOLEAN OPT__LEAD2SYZ = attributes.OPT__LEAD2SYZ;
1374 // const BOOLEAN OPT__TAILREDSYZ = attributes.OPT__TAILREDSYZ;
1375 
1376  assume( m_syzLeads == NULL );
1377 
1378  if( UNLIKELY(bComputeSecondTerms) )
1379  {
1380  assume( OPT__LEAD2SYZ );
1381 // m_syzLeads = FROM_NAMESPACE(INTERNAL, _Compute2LeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes));
1382  m_syzLeads = Compute2LeadingSyzygyTerms();
1383  }
1384  else
1385  {
1386  assume( !OPT__LEAD2SYZ );
1387 
1388  m_syzLeads = Compute1LeadingSyzygyTerms();
1389  }
1390 // m_syzLeads = FROM_NAMESPACE(INTERNAL, _ComputeLeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes));
1391 
1392  // NOTE: set m_LS if tails are to be reduced!
1393  assume( m_syzLeads!= NULL );
1394 
1395  if ( LIKELY( OPT__TAILREDSYZ && !OPT__IGNORETAILS && (IDELEMS(m_syzLeads) > 0) && !((IDELEMS(m_syzLeads) == 1) && (m_syzLeads->m[0] == NULL)) ) )
1396  {
1397  m_LS = m_syzLeads;
1398  m_checker.Initialize(m_syzLeads);
1399 #ifndef SING_NDEBUG
1400  if( OPT__DEBUG )
1401  {
1402  const ring& r = m_rBaseRing;
1403  PrintS("SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms: \n");
1404  PrintS("m_syzLeads: \n");
1405  dPrint(m_syzLeads, r, r, 0);
1406  PrintS("m_checker.Initialize(m_syzLeads) => \n");
1407  m_checker.DebugPrint();
1408  }
1409 #endif
1410  assume( m_checker.IsNonempty() ); // TODO: this always fails... BUG????
1411  }
1412 
1413  if( UNLIKELY( OPT__PROT ) ) Print("(L%dS:%d)", bComputeSecondTerms ? 2 : 1, IDELEMS(m_syzLeads));
1414 
1415 }
1416 
1418 {
1419  assume( !OPT__IGNORETAILS );
1420 
1421  const ideal& L = m_idLeads;
1422  const ideal& T = m_idTails;
1423  const ring& r = m_rBaseRing;
1424 
1425  assume( syz_lead != NULL );
1426 
1427 
1428 #ifndef SING_NDEBUG
1429  if( OPT__DEBUG )
1430  {
1431  PrintS("SchreyerSyzygyComputation::SchreyerSyzygyNF(syz_lead, poly syz_2), \n");
1432  PrintS("syz_lead: \n");
1433  dPrint(syz_lead, r, r, 0);
1434  PrintS("syz_2: \n");
1435  dPrint(syz_2, r, r, 0);
1436  PrintLn();
1437  }
1438 #endif
1439 
1440  if( UNLIKELY( OPT__TREEOUTPUT ) )
1441  {
1442  PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_lead, r);
1443  PrintS("\", \"children\": [");
1444  }
1445 
1446  if( syz_2 == NULL )
1447  {
1448  const int rr = p_GetComp(syz_lead, r) - 1;
1449 
1450  assume( rr >= 0 && rr < IDELEMS(T) );
1451  assume( rr >= 0 && rr < IDELEMS(L) );
1452 
1453 #if NOPRODUCT
1454  syz_2 = m_div.FindReducer(syz_lead, L->m[rr], syz_lead, m_checker);
1455  p_Test(syz_2, r);
1456 
1457  if( UNLIKELY( OPT__TREEOUTPUT ) )
1458  {
1459  PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_2, r); PrintS("\" },");
1460  }
1461 #else
1462  poly aa = leadmonom(syz_lead, r); assume( aa != NULL); // :(
1463  aa = p_Mult_mm(aa, L->m[rr], r);
1464 
1465  if( UNLIKELY( OPT__TREEOUTPUT ) )
1466  {
1467  PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_2, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(aa, r, false); PrintS("\" },");
1468  }
1469 
1470  syz_2 = m_div.FindReducer(aa, syz_lead, m_checker);
1471  p_Test(syz_2, r);
1472 
1473  p_Delete(&aa, r);
1474 #endif
1475 
1476  }
1477 
1478  assume( syz_2 != NULL ); // by construction of S-Polynomial
1479 
1480  assume( L != NULL );
1481  assume( T != NULL );
1482 
1483  assume( IDELEMS(L) == IDELEMS(T) );
1484 
1485  int c = p_GetComp(syz_lead, r) - 1;
1486 
1487  assume( c >= 0 && c < IDELEMS(T) );
1488 
1489  if( m_spoly_bucket == NULL )
1490  m_spoly_bucket = kBucketCreate(r);
1491 
1492  SBucketWrapper tail(r, m_sum_bucket_factory);
1493 
1494 
1495  kBucket_pt bucket = m_spoly_bucket; assume( bucket != NULL ); kbTest(bucket); m_spoly_bucket = NULL;
1496 
1497 // kBucketInit(bucket, NULL, 0); // not needed!?
1498 
1499  poly p = leadmonom(syz_lead, r); // :(
1500 // poly spoly = pp_Mult_qq(p, T->m[c], r);
1501  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // TODO: store pLength(T->m[c]) separately!?
1502  p_Delete(&p, r);
1503 
1504  kbTest(bucket);
1505 
1506  c = p_GetComp(syz_2, r) - 1;
1507  assume( c >= 0 && c < IDELEMS(T) );
1508 
1509  p = leadmonom(syz_2, r); // :(
1510 // spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r);
1511  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // pLength(T->m[c])?!
1512  kbTest(bucket);
1513  p_Delete(&p, r);
1514 
1515 // const bool bUsePolynomial = TEST_OPT_NOT_BUCKETS; // || (pLength(spoly) < MIN_LENGTH_BUCKET);
1516 // CPolynomialSummator tail(r, bUsePolynomial);
1517  tail.Add(syz_2, 1);
1518 
1519  kbTest(bucket);
1520  for( poly spoly = kBucketExtractLm(bucket); spoly != NULL; p_LmDelete(&spoly, r), spoly = kBucketExtractLm(bucket))
1521  {
1522  kbTest(bucket);
1523  poly t = m_div.FindReducer(spoly, NULL, m_checker);
1524  p_Test(t, r);
1525 
1526  if( t != NULL )
1527  {
1528  p = leadmonom(t, r); // :(
1529  c = p_GetComp(t, r) - 1;
1530 
1531  assume( c >= 0 && c < IDELEMS(T) );
1532 
1533  if(UNLIKELY( OPT__TREEOUTPUT ))
1534  {
1535  PrintS("{ \"nodelabel\": \""); writeLatexTerm(t, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(spoly, r, false); PrintS("\" },");
1536  }
1537 
1538  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // pLength(T->m[c])?
1539 // spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r);
1540 
1541  p_Delete(&p, r);
1542 
1543  tail.Add(t, 1);
1544  } // otherwise discard that leading term altogether!
1545  else
1546  if( UNLIKELY(OPT__PROT) ) ++ m_stat[4]; // PrintS("$"); // LOT
1547 
1548  kbTest(bucket);
1549  }
1550 
1551  kbTest(bucket);
1552 
1553  // now bucket must be empty!
1554  assume( kBucketClear(bucket) == NULL );
1555 
1556  const poly result = tail.ClearAdd(); // TODO: use Merge with sBucket???
1557 
1558 
1559  if( m_spoly_bucket == NULL )
1560  m_spoly_bucket = bucket;
1561  else
1562  kBucketDestroy(&bucket);
1563 
1564 
1565  if( UNLIKELY(OPT__TREEOUTPUT) )
1566  {
1567  PrintS("]},");
1568  }
1569 
1570 #ifndef SING_NDEBUG
1571  if( OPT__DEBUG )
1572  {
1573  PrintS("SchreyerSyzygyComputation::SchreyerSyzygyNF(syz_lead, poly syz_2) =>>> \n");
1574  dPrint(result, r, r, 0);
1575  PrintLn();
1576  // TODO: Add SyzCheck!!!???
1577  }
1578 #endif
1579 
1580  return result;
1581 }
1582 
1583 // namespace {
1584 
1585 // };
1586 
1587 
1588 bool my_p_LmCmp (poly a, poly b, const ring r) { return p_LmCmp(a, b, r) == -1; } // TODO: change to simple lex. memory compare!
1589 
1590 // NOTE: need p_Copy?????? for image + multiplier!!???
1591 // NOTE: better store complete syz. terms!!?
1592 poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, const int tail) const
1593 {
1594 #ifndef SING_NDEBUG
1595  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1596 #endif
1597 
1598  const ring& r = m_rBaseRing;
1599 
1600  assume(m_idTails != NULL && m_idTails->m != NULL);
1601  assume( tail >= 0 && tail < IDELEMS(m_idTails) );
1602 
1603  p_Test(multiplier, r);
1604 
1605  if( UNLIKELY(OPT__NOCACHING) )
1606  return ComputeImage(multiplier, tail);
1607 
1608  // TODO: store (multiplier, tail) -.-^-.-^-.--> !
1609  TCache::iterator top_itr = m_cache.find(tail);
1610 
1611  if ( top_itr != m_cache.end() )
1612  {
1613  assume( top_itr->first == tail );
1614 
1615  TP2PCache& T = top_itr->second;
1616 
1617  TP2PCache::iterator itr = T.find(multiplier);
1618 
1619  if( itr != T.end() ) // Yey - Reuse!!!
1620  {
1621  assume( p_LmEqual(itr->first, multiplier, r) );
1622 
1623  if( itr->second == NULL ) // leadcoeff plays no role if value is NULL!
1624  return (NULL);
1625 
1626  if( UNLIKELY( OPT__TREEOUTPUT ) )
1627  {
1628 // PrintS("{ \"nodelabel\": \""); writeLatexTerm(multiplier, r, false);
1629 // Print(" \\\\GEN{%d}\", \"children\": [ ", tail + 1);
1630  PrintS("{ \"proc\": \"TTLookup\", \"nodelabel\": \"");
1631  writeLatexTerm(itr->first, r, false); Print(" \\\\GEN{%d}\", \"Lookup\": \"", tail + 1);
1632  writeLatexTerm(itr->second, r, true, false);
1633  PrintS("\", ");
1634  }
1635 
1636  poly p = p_Copy(itr->second, r); // COPY!!!
1637 
1638  p_Test(multiplier, r);
1639 
1640  if( !n_Equal( pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf) ) // normalize coeffs!?
1641  {
1642  number n = n_Div( pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf); // new number
1643 
1644  if( UNLIKELY( OPT__TREEOUTPUT ) )
1645  {
1646  StringSetS("");
1647  n_Write(n, r->cf);
1648  char* s = StringEndS();
1649  Print("\"recale\": \"%s\", ", s);
1650  omFree(s);
1651  }
1652 
1653  if( UNLIKELY( OPT__PROT ) ) ++ m_stat[7]; // PrintS("l*"); // lookup & rescale
1654 
1655  p = p_Mult_nn(p, n, r); // !
1656  n_Delete(&n, r->cf);
1657  } else
1658  if( UNLIKELY( OPT__PROT ) ) ++ m_stat[6]; // PrintS("l"); // lookup no rescale
1659 
1660  if( UNLIKELY(OPT__TREEOUTPUT) )
1661  {
1662  PrintS("\"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1663  }
1664 
1665 #ifndef SING_NDEBUG
1666  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1667 #endif
1668  p_Test(multiplier, r);
1669 
1670  return p;
1671  }
1672 
1673 
1674  if( UNLIKELY(OPT__TREEOUTPUT) )
1675  {
1676  Print("{ \"proc\": \"TTStore%d\", \"nodelabel\": \"", tail + 1); writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"children\": [", tail + 1);
1677  }
1678 
1679  p_Test(multiplier, r);
1680 
1681  const poly p = ComputeImage(multiplier, tail);
1682 
1683  if( UNLIKELY(OPT__TREEOUTPUT) )
1684  {
1685  PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1686  }
1687 
1688  if( UNLIKELY(OPT__PROT) ) ++ m_stat[8]; // PrintS("S"); // store
1689 
1690  p_Test(multiplier, r);
1691 
1692  T.insert( TP2PCache::value_type(myp_Head(multiplier, (p==NULL), r), p) ); // T[ multiplier ] = p;
1693 
1694  p_Test(multiplier, r);
1695 
1696 // if( p == NULL )
1697 // return (NULL);
1698 
1699 #ifndef SING_NDEBUG
1700  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1701 #endif
1702 
1703  return p_Copy(p, r);
1704  }
1705 
1706  CCacheCompare o(r); TP2PCache T(o);
1707 
1708  if( UNLIKELY(OPT__TREEOUTPUT) )
1709  {
1710  Print("{ \"proc\": \"TTStore%d\", \"nodelabel\": \"", 0); writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"children\": [", tail + 1);
1711  }
1712 
1713  const poly p = ComputeImage(multiplier, tail);
1714 
1715  if( UNLIKELY(OPT__TREEOUTPUT) )
1716  {
1717  PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1718  }
1719 
1720  if( UNLIKELY( OPT__PROT ) ) ++ m_stat[8]; // PrintS("S"); // store // %d", tail + 1);
1721 
1722  T.insert( TP2PCache::value_type(myp_Head(multiplier, (p==NULL), r), p) );
1723 
1724  m_cache.insert( TCache::value_type(tail, T) );
1725 
1726 // if( p == NULL )
1727 // return (NULL);
1728 
1729 #ifndef SING_NDEBUG
1730  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1731 #endif
1732 
1733  return p_Copy(p, r);
1734 }
1735 
1736 poly SchreyerSyzygyComputation::ComputeImage(poly multiplier, const int tail) const
1737 {
1738  const ring& r = m_rBaseRing;
1739 
1740  assume(m_idTails != NULL && m_idTails->m != NULL);
1741  assume( tail >= 0 && tail < IDELEMS(m_idTails) );
1742 
1743  p_Test(multiplier, r);
1744 
1745  const poly t = m_idTails->m[tail]; // !!!
1746 
1747  if(t != NULL)
1748  {
1749  if( UNLIKELY(OPT__TREEOUTPUT) )
1750  {
1751  PrintS("{ \"proc\": \"ComputeImage\", \"nodelabel\": \"");
1752  writeLatexTerm(multiplier, r, false);
1753  Print(" \\\\GEN{%d}\", \"edgelabel\": \"", tail + 1);
1754  writeLatexTerm(t, r, false);
1755  PrintS("\", \"children\": [");
1756  }
1757 
1758  const poly p = TraverseTail(multiplier, t);
1759 
1760  p_Test(multiplier, r);
1761 
1762  if( UNLIKELY(OPT__TREEOUTPUT) )
1763  {
1764  PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1765  }
1766 
1767  return p;
1768 
1769  }
1770 
1771  return NULL;
1772 }
1773 
1774 
1776 {
1777  assume( !OPT__IGNORETAILS );
1778 
1779  const ideal& L = m_idLeads;
1780  const ideal& T = m_idTails;
1781  const ring& r = m_rBaseRing;
1782 
1783  assume( multiplier != NULL );
1784 
1785  assume( L != NULL );
1786  assume( T != NULL );
1787 
1788  p_Test(multiplier, r);
1789 
1790 #ifndef SING_NDEBUG
1791  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1792 #endif
1793 
1794  if( UNLIKELY( !( (!OPT__TAILREDSYZ) || m_lcm.Check(multiplier) )) )
1795  {
1796  if( UNLIKELY(OPT__TAILREDSYZ && OPT__PROT) )
1797  {
1798  ++ m_stat[5]; // PrintS("%"); // check LCM !
1799 #ifndef SING_NDEBUG
1800  if( OPT__DEBUG )
1801  {
1802  PrintS("\nTT,%:"); dPrint(multiplier, r, r, 0);
1803  PrintS(", * :"); dPrint(tail, r, r, 0);
1804  PrintLn();
1805  }
1806 #endif
1807  }
1808  return NULL;
1809  }
1810 
1811  // const bool bUsePolynomial = TEST_OPT_NOT_BUCKETS; // || (pLength(tail) < MIN_LENGTH_BUCKET);
1812 
1813  SBucketWrapper sum(r, m_sum_bucket_factory);
1814 /*
1815  sBucket_pt sum;
1816 
1817  if( m_sum_bucket == NULL )
1818  sum = sBucketCreate(r);
1819  else
1820  {
1821  if( !sIsEmpty(m_sum_bucket) )
1822  sum = sBucketCreate(r);
1823  else
1824  {
1825  sum = m_sum_bucket;
1826  m_sum_bucket = NULL;
1827  }
1828  }
1829 
1830 
1831  assume( sum != NULL ); assume ( sIsEmpty(sum) );
1832  assume( r == sBucketGetRing(sum) );
1833 */
1834 
1835 // poly s; int len;
1836 
1837  // CPolynomialSummator sum(r, bUsePolynomial);
1838  // poly s = NULL;
1839 
1840  if( UNLIKELY( OPT__TREEOUTPUT & 0 ) )
1841  {
1842  Print("{ \"proc\": \"TTPoly\", \"nodelabel\": \""); writeLatexTerm(multiplier, r, false); Print(" * \\\\ldots \", \"children\": [");
1843  }
1844 
1845  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1846  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1847  for(poly p = tail; p != NULL; p = pNext(p)) // iterate over the tail
1848  {
1849  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1850  const poly rt = ReduceTerm(multiplier, p, NULL); // TODO: also return/store length?
1851  sum.Add(rt);
1852  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1853  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1854  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1855 
1856 // const int lp = pLength(rt);
1857 // if( rt != NULL && lp != 0 )
1858 // sBucket_Add_p(sum, rt, lp);
1859  }
1860  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1861  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1862 
1863 // sBucketClearAdd(sum, &s, &len); // Will Not Clear?!?
1864  const poly s = sum.ClearAdd();
1865 
1866 // assume( sum != NULL ); assume ( sIsEmpty(sum) );
1867 /*
1868  if( m_sum_bucket == NULL )
1869  m_sum_bucket = sum;
1870  else
1871  sBucketDestroy(&sum);
1872 
1873  assume( pLength(s) == len );
1874 */
1875 
1876 #ifndef SING_NDEBUG
1877  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1878 #endif
1879 
1880  if( UNLIKELY( OPT__TREEOUTPUT & 0 ) )
1881  {
1882  PrintS("], \"noderesult\": \""); writeLatexTerm(s, r, true, false); PrintS("\" },");
1883  }
1884 
1885  p_Test(multiplier, r);
1886 
1887  return s;
1888 }
1889 
1890 
1891 
1892 
1893 poly SchreyerSyzygyComputation::ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
1894 {
1895 #ifndef SING_NDEBUG
1896  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1897 #endif
1898 
1899  assume( !OPT__IGNORETAILS );
1900 
1901  const ideal& L = m_idLeads;
1902  const ideal& T = m_idTails;
1903  const ring& r = m_rBaseRing;
1904 
1905  assume( multiplier != NULL );
1906  assume( term4reduction != NULL );
1907 
1908 
1909  assume( L != NULL );
1910  assume( T != NULL );
1911 
1912  p_Test(multiplier, r);
1913 
1914  // simple implementation with FindReducer:
1915  poly s = NULL;
1916 
1917  if( (!OPT__TAILREDSYZ) || m_lcm.Check(multiplier) ) // TODO: UNLIKELY / LIKELY ????
1918  {
1919 #if NOPRODUCT
1920  s = m_div.FindReducer(multiplier, term4reduction, syztermCheck, m_checker); // s ????
1921  p_Test(s, r);
1922 
1923  p_Test(multiplier, r);
1924 
1925  if( s == NULL ) // No Reducer?
1926  {
1927  if( UNLIKELY(OPT__PROT) ) ++ m_stat[4]; // PrintS("$"); // LOT
1928  return NULL;
1929  }
1930 
1931  if( UNLIKELY( OPT__TREEOUTPUT ) )
1932  {
1933  poly product = pp_Mult_mm(multiplier, term4reduction, r);
1934  PrintS("{ \"proc\": \"RdTrmNoP\", \"nodelabel\": \""); writeLatexTerm(s, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(product, r, false);
1935  p_Delete(&product, r);
1936  }
1937 
1938 #else
1939  // NOTE: only LT(term4reduction) should be used in the following:
1940  poly product = pp_Mult_mm(multiplier, term4reduction, r);
1941  p_Test(product, r);
1942 
1943  s = m_div.FindReducer(product, syztermCheck, m_checker); // ??
1944  p_Test(s, r);
1945 
1946  p_Test(multiplier, r);
1947 
1948  if( s == NULL ) // No Reducer?
1949  {
1950  if( UNLIKELY(OPT__PROT) ) ++ m_stat[4]; // PrintS("$"); // LOT
1951  return NULL;
1952  }
1953 
1954  if( UNLIKELY(OPT__TREEOUTPUT) )
1955  {
1956  PrintS("{ \"proc\": \"RdTrmP\", \"nodelabel\": \""); writeLatexTerm(s, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(product, r, false);
1957  }
1958 
1959  p_Delete(&product, r);
1960 #endif
1961  }
1962 
1963 #ifndef SING_NDEBUG
1964  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1965 #endif
1966 
1967  if( s == NULL ) // No Reducer?
1968  {
1969  if( UNLIKELY( OPT__TAILREDSYZ && OPT__PROT) )
1970  {
1971  ++ m_stat[5]; // PrintS("%"); // check LCM !
1972 #ifndef SING_NDEBUG
1973  if( OPT__DEBUG )
1974  {
1975  PrintS("\n%: RedTail("); dPrint(multiplier, r, r, 0);
1976  PrintS(" * : "); dPrint(term4reduction, r,r,0 );
1977  PrintS(", { "); dPrint(syztermCheck,r,r,0 );
1978  PrintS(" }) "); PrintLn();
1979  }
1980 #endif
1981  }
1982  return NULL;
1983  }
1984 
1985  p_Test(multiplier, r);
1986  p_Test(s, r);
1987 
1988  poly b = leadmonom(s, r);
1989 
1990  p_Test(b, r);
1991 
1992  const int c = p_GetComp(s, r) - 1;
1993  assume( c >= 0 && c < IDELEMS(T) );
1994 
1995 
1996  if( UNLIKELY( OPT__TREEOUTPUT ) )
1997  PrintS("\", \"children\": [");
1998 
1999  const poly t = TraverseTail(b, c); // T->m[c];
2000 
2001  if( UNLIKELY( OPT__TREEOUTPUT ) )
2002  {
2003 
2004  PrintS("], \"noderesult\": \"");
2005  writeLatexTerm(t, r, true, false);
2006  PrintS("\"");
2007 
2008  if( syztermCheck != NULL )
2009  {
2010  PrintS(", \"syztermCheck\":\"" );
2011  writeLatexTerm(syztermCheck, r, true, false);
2012  PrintS("\" },");
2013  } else
2014  PrintS(" },");
2015  }
2016 
2017  p_Test(multiplier, r);
2018 
2019  if( t != NULL )
2020  s = p_Add_q(s, t, r);
2021 
2022 
2023 #ifndef SING_NDEBUG
2024  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
2025 #endif
2026 
2027  p_Test(multiplier, r);
2028 
2029  return s;
2030 }
2031 
2033  OPT__DEBUG( atGetInt(rootRingHdl,"DEBUG", 0) ),
2034  OPT__LEAD2SYZ( atGetInt(rootRingHdl, "LEAD2SYZ", 0) ),
2035  OPT__TAILREDSYZ( atGetInt(rootRingHdl, "TAILREDSYZ", 1) ),
2036  OPT__HYBRIDNF( atGetInt(rootRingHdl, "HYBRIDNF", 0) ),
2037  OPT__IGNORETAILS( atGetInt(rootRingHdl, "IGNORETAILS", 0) ),
2038  OPT__SYZNUMBER( atGetInt(rootRingHdl, "SYZNUMBER", 0) ),
2039  OPT__TREEOUTPUT( atGetInt(rootRingHdl, "TREEOUTPUT", 0) ),
2040  OPT__SYZCHECK( atGetInt(rootRingHdl, "SYZCHECK", 0) ),
2041  OPT__PROT(TEST_OPT_PROT),
2042  OPT__NOCACHING( atGetInt(rootRingHdl, "NOCACHING", 0) ),
2043  m_rBaseRing( rootRingHdl->data.uring )
2044 {
2045 #ifndef SING_NDEBUG
2046  if( OPT__DEBUG & 0 )
2047  {
2048  PrintS("SchreyerSyzygyComputationFlags: \n");
2049  Print(" DEBUG: \t%d\n", OPT__DEBUG);
2050 // Print(" SYZCHECK : \t%d\n", OPT__SYZCHECK);
2051  Print(" LEAD2SYZ: \t%d\n", OPT__LEAD2SYZ);
2052  Print(" TAILREDSYZ: \t%d\n", OPT__TAILREDSYZ);
2053  Print(" IGNORETAILS: \t%d\n", OPT__IGNORETAILS);
2054  Print(" TREEOUTPUT: \t%d\n", OPT__TREEOUTPUT);
2055  Print(" SYZCHECK: \t%d\n", OPT__SYZCHECK);
2056  }
2057 #endif
2058 
2059  // TODO: just current setting!
2060  assume( rootRingHdl == currRingHdl );
2061  assume( rootRingHdl->typ == RING_CMD );
2062  assume( m_rBaseRing == currRing );
2063  // move the global ring here inside???
2064 }
2065 
2066 
2067 
2068 CLeadingTerm::CLeadingTerm(unsigned int _label, const poly _lt, const ring R):
2069  m_sev( p_GetShortExpVector(_lt, R) ), m_label( _label ), m_lt( _lt )
2070 #ifndef SING_NDEBUG
2071  , _R(R), m_lt_copy( myp_Head(_lt, true, R) ) // note that p_LmEqual only tests exponents!
2072 #endif
2073 {
2074 #ifndef SING_NDEBUG
2075  assume( pNext(m_lt_copy) == NULL );
2076 #endif
2077  assume( sev() == p_GetShortExpVector(lt(), R) );
2078 }
2079 
2080 #ifndef SING_NDEBUG
2081 CLeadingTerm::~CLeadingTerm()
2082 {
2083  assume( p_LmEqual(m_lt, m_lt_copy, _R) );
2084  assume( m_sev == p_GetShortExpVector(m_lt, _R) );
2085 
2086  poly p = const_cast<poly>(m_lt_copy);
2087  p_Delete(&p, _R);
2088 }
2089 poly CLeadingTerm::lt() const
2090 {
2091  assume( p_LmEqual(m_lt, m_lt_copy, _R) );
2092  assume( m_sev == p_GetShortExpVector(m_lt, _R) );
2093  return m_lt;
2094 }
2095 
2096 unsigned long CLeadingTerm::sev() const
2097 {
2098  assume( p_LmEqual(m_lt, m_lt_copy, _R) );
2099  assume( m_sev == p_GetShortExpVector(m_lt, _R) );
2100  return m_sev;
2101 }
2102 
2103 unsigned int CLeadingTerm::label() const
2104 {
2105  assume( p_LmEqual(m_lt, m_lt_copy, _R) );
2106  assume( m_sev == p_GetShortExpVector(m_lt, _R) );
2107  return m_label;
2108 }
2109 #endif
2110 
2111 
2112 
2114 {
2115  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++ )
2116  {
2117  const TReducers& v = it->second;
2118  for(TReducers::const_iterator vit = v.begin(); vit != v.end(); vit++ )
2119  delete const_cast<CLeadingTerm*>(*vit);
2120  }
2121 }
2122 
2123 
2124 void CReducerFinder::Initialize(const ideal L)
2125 {
2126  assume( m_L == NULL || m_L == L );
2127  if( m_L == NULL )
2128  m_L = L;
2129 
2130  assume( m_L == L );
2131 
2132  if( L != NULL )
2133  {
2134  const ring& R = m_rBaseRing;
2135  assume( R != NULL );
2136 
2137  for( int k = IDELEMS(L) - 1; k >= 0; k-- )
2138  {
2139  const poly a = L->m[k]; // assume( a != NULL );
2140 
2141  // NOTE: label is k \in 0 ... |L|-1!!!
2142  if( a != NULL )
2143  m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
2144  }
2145  }
2146 }
2147 
2150  m_L(const_cast<ideal>(L)), // for debug anyway
2151  m_hash()
2152 {
2153  assume( flags.m_rBaseRing == m_rBaseRing );
2154  if( L != NULL )
2155  Initialize(L);
2156 }
2157 
2158 /// _p_LmDivisibleByNoComp for a | b*c
2159 static inline BOOLEAN _p_LmDivisibleByNoComp(const poly a, const poly b, const poly c, const ring r)
2160 {
2161  int i=r->VarL_Size - 1;
2162  unsigned long divmask = r->divmask;
2163  unsigned long la, lb;
2164 
2165  if (r->VarL_LowIndex >= 0)
2166  {
2167  i += r->VarL_LowIndex;
2168  do
2169  {
2170  la = a->exp[i];
2171  lb = b->exp[i] + c->exp[i];
2172  if ((la > lb) ||
2173  (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
2174  {
2176  return FALSE;
2177  }
2178  i--;
2179  }
2180  while (i>=r->VarL_LowIndex);
2181  }
2182  else
2183  {
2184  do
2185  {
2186  la = a->exp[r->VarL_Offset[i]];
2187  lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
2188  if ((la > lb) ||
2189  (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
2190  {
2192  return FALSE;
2193  }
2194  i--;
2195  }
2196  while (i>=0);
2197  }
2198 #ifdef HAVE_RINGS
2199  assume( !rField_is_Ring(r) ); // not implemented for rings...!
2200 #endif
2201  return TRUE;
2202 }
2203 
2204 
2205 bool CLeadingTerm::CheckLT( const ideal & L ) const
2206 {
2207 // for( int i = IDELEMS(L); i >= 0; --i) assume( pNext(L->m[i]) == NULL ); // ???
2208  return ( L->m[label()] == lt() );
2209 }
2210 
2211 bool CLeadingTerm::DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const
2212 {
2213  // may have no coeff yet
2214 // assume ( !n_IsZero( p_GetCoeff(product, r), r ) );
2215 
2216  assume ( !n_IsZero( pGetCoeff(lt()), r->cf ) );
2217  assume( sev() == p_GetShortExpVector(lt(), r) );
2218 
2219  assume( product != NULL );
2220  assume( (p_GetComp(lt(), r) == p_GetComp(product, r)) || (p_GetComp(lt(), r) == 0) );
2221 
2222 #ifndef SING_NDEBUG
2223  assume( r == _R );
2224 #endif
2225 
2226 // const int k = label();
2227 // assume( m_L->m[k] == p );
2228 
2229  return p_LmShortDivisibleByNoComp(lt(), sev(), product, not_sev, r);
2230 
2231 }
2232 
2233 #if NOPRODUCT
2234 /// as DivisibilityCheck(multiplier * t, ...) for monomial 'm'
2235 /// and a module term 't'
2236 bool CLeadingTerm::DivisibilityCheck(const poly m, const poly t, const unsigned long not_sev, const ring r) const
2237 {
2238  assume ( !n_IsZero( pGetCoeff(lt()), r->cf ) );
2239  assume( sev() == p_GetShortExpVector(lt(), r) );
2240 
2241  assume( m != NULL );
2242  assume( t != NULL );
2243  assume ( !n_IsZero( pGetCoeff(m), r->cf ) );
2244  assume ( !n_IsZero( pGetCoeff(t), r->cf ) );
2245 
2246 // assume( p_GetComp(m, r) == 0 );
2247  assume( (p_GetComp(lt(), r) == p_GetComp(t, r)) || (p_GetComp(lt(), r) == 0) );
2248 
2249  p_Test(m, r);
2250  p_Test(t, r);
2251 // const int k = label();
2252 // assume( m_L->m[k] == p );
2253 
2254 #ifndef SING_NDEBUG
2255  assume( r == _R );
2256 #endif
2257 
2258  if (sev() & not_sev)
2259  return false;
2260 
2261  return _p_LmDivisibleByNoComp(lt(), m, t, r);
2262 // return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
2263 }
2264 #endif
2265 
2266 
2267 /// TODO:
2269 {
2270  private:
2273  const unsigned long m_not_sev;
2274  const long m_comp;
2275 
2276  CReducerFinder::CReducersHash::const_iterator m_itr;
2277  CReducerFinder::TReducers::const_iterator m_current, m_finish;
2278 
2279  bool m_active;
2280 
2281  public:
2282  CDivisorEnumerator(const CReducerFinder& self, const poly product):
2284  m_reds(self),
2285  m_product(product),
2286  m_not_sev(~p_GetShortExpVector(product, m_rBaseRing)),
2287  m_comp(p_GetComp(product, m_rBaseRing)),
2288  m_itr(), m_current(), m_finish(),
2289  m_active(false)
2290  {
2291  assume( m_comp >= 0 );
2292  assume( m_reds.m_L != NULL ); /// TODO: m_L should stay the same!!!
2293 
2294  assume( product != NULL ); // may have no coeff yet :(
2295 // assume ( !n_IsZero( p_GetCoeff(product, m_rBaseRing), m_rBaseRing ) );
2296 #ifndef SING_NDEBUG
2297  if( OPT__DEBUG ) m_reds.Verify();
2298 #endif
2299  }
2300 
2301  inline bool Reset()
2302  {
2303  m_active = false;
2304 
2305  m_itr = m_reds.m_hash.find(m_comp);
2306 
2307  if( m_itr == m_reds.m_hash.end() )
2308  return false;
2309 
2310  assume( m_itr->first == m_comp );
2311 
2312  m_current = (m_itr->second).begin();
2313  m_finish = (m_itr->second).end();
2314 
2315  if (m_current == m_finish)
2316  return false;
2317 
2318 // m_active = true;
2319  return true;
2320  }
2321 
2322  const CLeadingTerm& Current() const
2323  {
2324  assume( m_active );
2325  assume( m_current != m_finish );
2326 
2327  return *(*m_current);
2328  }
2329 
2330  inline bool MoveNext()
2331  {
2332  assume( m_current != m_finish );
2333 
2334  if( m_active )
2335  ++m_current;
2336  else
2337  m_active = true; // for Current()
2338 
2339  // looking for the next good entry
2340  for( ; m_current != m_finish; ++m_current )
2341  {
2342  assume( Current().CheckLT( m_reds.m_L ) );
2343 
2344  if( Current().DivisibilityCheck(m_product, m_not_sev, m_rBaseRing) )
2345  {
2346 #ifndef SING_NDEBUG
2347  if( OPT__DEBUG )
2348  {
2349  Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().label());
2350  dPrint(Current().lt(), m_rBaseRing, m_rBaseRing, 0);
2351  }
2352 #endif
2353 // m_active = true;
2354  assume( Current().CheckLT( m_reds.m_L ) );
2355  return true;
2356  }
2357  assume( Current().CheckLT( m_reds.m_L ) );
2358  }
2359 
2360  // the end... :(
2361  assume( m_current == m_finish );
2362 
2363  m_active = false;
2364  return false;
2365  }
2366 };
2367 
2368 
2369 
2370 bool CReducerFinder::IsDivisible(const poly product) const
2371 {
2372 #ifndef SING_NDEBUG
2373  if( OPT__DEBUG ) Verify();
2374 #endif
2375 
2376  assume( product != NULL );
2377 
2378  // NOTE: q may have no coeff!!!
2379 
2380  CDivisorEnumerator itr(*this, product);
2381  if( !itr.Reset() )
2382  return false;
2383 
2384  return itr.MoveNext();
2385 
2386 /*
2387  const ring& r = m_rBaseRing;
2388 
2389  const long comp = p_GetComp(product, r);
2390  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
2391 
2392  assume( comp >= 0 );
2393 
2394  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2395 
2396  assume( m_L != NULL );
2397 
2398  if( it == m_hash.end() )
2399  return false;
2400  // assume comp!
2401 
2402  const TReducers& reducers = it->second;
2403 
2404  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2405  {
2406  assume( (*vit)->CheckLT( m_L ) );
2407 
2408  if( (*vit)->DivisibilityCheck(product, not_sev, r) )
2409  {
2410  if( OPT__DEBUG )
2411  {
2412  Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + (*vit)->label());
2413  dPrint((*vit)->lt(), r, r, 0);
2414  }
2415 
2416  return true;
2417  }
2418  }
2419 
2420  return false;
2421 */
2422 }
2423 
2424 
2425 #ifndef SING_NDEBUG
2426 void CReducerFinder::Verify() const
2427 {
2428  const ring& r = m_rBaseRing;
2429 
2430  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
2431  {
2432  const TReducers& reducers = it->second;
2433 
2434  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2435  {
2436  assume( (*vit)->CheckLT( m_L ) );
2437 
2438  const poly p = (*vit)->lt();
2439 
2440  const unsigned long p_sev = (*vit)->sev();
2441  assume( p_sev == p_GetShortExpVector(p, r) );
2442 
2443  assume( p_GetComp(p, r) == it->first );
2444 
2445  const int k = (*vit)->label();
2446  assume( m_L->m[k] == p );
2447 
2448  pp_Test(p, r, r);
2449  }
2450  }
2451 }
2452 
2453 
2454 
2455 void CReducerFinder::DebugPrint() const
2456 {
2457  const ring& r = m_rBaseRing;
2458 
2459  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
2460  {
2461  Print("Hash Key: %ld, Values: \n", it->first);
2462  const TReducers& reducers = it->second;
2463 
2464  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2465  {
2466  assume( (*vit)->CheckLT( m_L ) );
2467 
2468  const int k = (*vit)->label();
2469  const poly p = (*vit)->lt();
2470 
2471  pp_Test(p, r, r);
2472 
2473  assume( m_L->m[k] == p );
2474 
2475  const unsigned long p_sev = (*vit)->sev();
2476  assume( p_sev == p_GetShortExpVector(p, r) );
2477 
2478  assume( p_GetComp(p, r) == it->first );
2479 
2480  Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %ld\n", p_sev);
2481 
2482  assume( m_L->m[k] == p );
2483  }
2484  }
2485 }
2486 #endif
2487 
2488 #if NOPRODUCT
2489 
2490 /// TODO:
2492 {
2493  private:
2495  const poly m_multiplier, m_term;
2496  const unsigned long m_not_sev;
2497  const long m_comp;
2498 
2499  CReducerFinder::CReducersHash::const_iterator m_itr;
2500  CReducerFinder::TReducers::const_iterator m_current, m_finish;
2501 
2502  bool m_active;
2503 
2504  public:
2505  CDivisorEnumerator2(const CReducerFinder& self, const poly m, const poly t):
2507  m_reds(self),
2508  m_multiplier(m), m_term(t),
2509  m_not_sev(~p_GetShortExpVector(m, t, m_rBaseRing)),
2510  m_comp(p_GetComp(t, m_rBaseRing)),
2511  m_itr(), m_current(), m_finish(),
2512  m_active(false)
2513  {
2514  assume( m_comp >= 0 );
2515  assume( m_reds.m_L != NULL );
2516  assume( m_multiplier != NULL );
2517  assume( m_term != NULL );
2518 
2519  assume( m != NULL );
2520  assume( t != NULL );
2521  assume ( !n_IsZero( pGetCoeff(m), m_rBaseRing->cf ) );
2522  assume ( !n_IsZero( pGetCoeff(t), m_rBaseRing->cf ) );
2523 
2524  p_Test(m, m_rBaseRing);
2525 
2526 // assume( p_GetComp(m_multiplier, m_rBaseRing) == 0 );
2527 #ifndef SING_NDEBUG
2528  if( OPT__DEBUG ) m_reds.Verify();
2529 #endif
2530  }
2531 
2532  inline bool Reset()
2533  {
2534  m_active = false;
2535 
2536  m_itr = m_reds.m_hash.find(m_comp);
2537 
2538  if( m_itr == m_reds.m_hash.end() )
2539  return false;
2540 
2541  assume( m_itr->first == m_comp );
2542 
2543  m_current = (m_itr->second).begin();
2544  m_finish = (m_itr->second).end();
2545 
2546  if (m_current == m_finish)
2547  return false;
2548 
2549  return true;
2550  }
2551 
2552  const CLeadingTerm& Current() const
2553  {
2554  assume( m_active );
2555  assume( m_current != m_finish );
2556 
2557  return *(*m_current);
2558  }
2559 
2560  inline bool MoveNext()
2561  {
2562  assume( m_current != m_finish );
2563 
2564  if( m_active )
2565  ++m_current;
2566  else
2567  m_active = true;
2568 
2569 
2570  // looking for the next good entry
2571  for( ; m_current != m_finish; ++m_current )
2572  {
2573  assume( Current().CheckLT( m_reds.m_L ) );
2574 
2575  if( Current().DivisibilityCheck(m_multiplier, m_term, m_not_sev, m_rBaseRing) )
2576  {
2577 #ifndef SING_NDEBUG
2578  if( OPT__DEBUG )
2579  {
2580  Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().label());
2581  dPrint(Current().lt(), m_rBaseRing, m_rBaseRing, 0);
2582  }
2583 #endif
2584 // m_active = true;
2585  assume( Current().CheckLT( m_reds.m_L ) );
2586  return true;
2587 
2588  }
2589  assume( Current().CheckLT( m_reds.m_L ) );
2590  }
2591 
2592  // the end... :(
2593  assume( m_current == m_finish );
2594 
2595  m_active = false;
2596  return false;
2597  }
2598 };
2599 
2600 poly CReducerFinder::FindReducer(const poly multiplier, const poly t,
2601  const poly syzterm,
2602  const CReducerFinder& syz_checker) const
2603 {
2604  const ring& r = m_rBaseRing;
2605 
2606 #ifndef SING_NDEBUG
2607  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2608 #endif
2609 
2610  p_Test(multiplier, r);
2611 
2612  CDivisorEnumerator2 itr(*this, multiplier, t);
2613  if( !itr.Reset() )
2614  return NULL;
2615 
2616  // don't care about the module component of multiplier (as it may be the syzygy term)
2617  // product = multiplier * t?
2618 
2619  assume( multiplier != NULL ); assume( t != NULL );
2620 
2621  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
2622 
2623  long c = 0;
2624 
2625  if (syzterm != NULL)
2626  c = p_GetComp(syzterm, r) - 1;
2627 
2628  assume( c >= 0 && c < IDELEMS(L) );
2629 
2630  p_Test(multiplier, r);
2631 
2632  if (UNLIKELY( OPT__DEBUG && (syzterm != NULL) ))
2633  {
2634  const poly m = L->m[c]; assume( m != NULL ); assume( pNext(m) == NULL );
2635 
2636  // def @@c = leadcomp(syzterm); int @@r = int(@@c);
2637  // def @@product = leadmonomial(syzterm) * L[@@r];
2638  poly lm = p_Mult_mm( leadmonom(syzterm, r, true), m, r); // !NC :(
2639  poly pr = p_Mult_q( leadmonom(multiplier, r, true), leadmonom(t, r, false), r); // !NC :(
2640 
2641  assume( p_EqualPolys(lm, pr, r) );
2642 
2643  p_Delete(&lm, r);
2644  p_Delete(&pr, r);
2645  }
2646 
2647 #ifndef SING_NDEBUG
2648  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2649 #endif
2650 
2651  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2652 
2653 // const poly q = p_One(r);
2654  const poly q = p_New(r); pNext(q) = NULL;
2655 
2656  if( UNLIKELY(OPT__DEBUG) )
2657  p_SetCoeff0(q, 0, r); // for printing q
2658 
2659  assume( pNext(q) == NULL );
2660 
2661  p_Test(multiplier, r);
2662  while( itr.MoveNext() )
2663  {
2664  assume( itr.Current().CheckLT( L ) ); // ???
2665 
2666  const poly p = itr.Current().lt(); // ???
2667  const int k = itr.Current().label();
2668 
2669  p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t // TODO: do it once?
2670  p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
2671 
2672  p_SetComp(q, k + 1, r);
2673  p_Setm(q, r);
2674 
2675  p_Test(multiplier, r);
2676 
2677  // cannot allow something like: a*gen(i) - a*gen(i)
2678  if (syzterm != NULL && (k == c))
2679  if (p_ExpVectorEqual(syzterm, q, r))
2680  {
2681 #ifndef SING_NDEBUG
2682  if( OPT__DEBUG )
2683  {
2684  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2685  dPrint(syzterm, r, r, 0);
2686  }
2687 #endif
2688  assume( itr.Current().CheckLT( L ) ); // ???
2689  continue;
2690  }
2691 
2692  // while the complement (the fraction) is not reducible by leading syzygies
2693  if( to_check && syz_checker.IsDivisible(q) )
2694  {
2695 #ifndef SING_NDEBUG
2696  if( OPT__DEBUG )
2697  {
2698  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2699  }
2700 #endif
2701  assume( itr.Current().CheckLT( L ) ); // ???
2702  continue;
2703  }
2704 
2705  number n = n_Mult( pGetCoeff(multiplier), pGetCoeff(t), r->cf);
2706 
2707 #if NODIVISION
2708  // we assume all leading coeffs to be 1!
2709  assume( n_IsOne(pGetCoeff(p), r->cf) );
2710 #else
2711  if( !n_IsOne( pGetCoeff(p), r ) )
2712  n = n_Div(n, pGetCoeff(p), r->cf);
2713 #endif
2714 
2715  p_SetCoeff0(q, n_InpNeg(n, r->cf), r);
2716 // n_Delete(&n, r);
2717 
2718 #ifndef SING_NDEBUG
2719  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2720 #endif
2721  p_Test(multiplier, r);
2722  p_Test(q, r);
2723 
2724  assume( itr.Current().CheckLT( L ) ); // ???
2725  return q;
2726  }
2727 
2728 /*
2729  const long comp = p_GetComp(t, r); assume( comp >= 0 );
2730  const unsigned long not_sev = ~p_GetShortExpVector(multiplier, t, r); // !
2731 
2732 // for( int k = IDELEMS(L)-1; k>= 0; k-- )
2733 // {
2734 // const poly p = L->m[k];
2735 //
2736 // if ( p_GetComp(p, r) != comp )
2737 // continue;
2738 //
2739 // const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
2740 
2741  // looking for an appropriate diviser p = L[k]...
2742  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2743 
2744  if( it == m_hash.end() )
2745  return NULL;
2746 
2747  // assume comp!
2748 
2749  assume( m_L != NULL );
2750 
2751  const TReducers& reducers = it->second;
2752 
2753  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2754  {
2755 
2756  const poly p = (*vit)->lt(); // ??
2757  const int k = (*vit)->label();
2758 
2759  assume( L->m[k] == p ); // CheckLT
2760 
2761 // const unsigned long p_sev = (*vit)->sev();
2762 // assume( p_sev == p_GetShortExpVector(p, r) );
2763 
2764 // if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2765 // continue;
2766 
2767  if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
2768  continue;
2769 
2770 
2771 // if (p_sev & not_sev) continue;
2772 // if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;
2773 
2774 
2775  p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t
2776  p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
2777 
2778  p_SetComp(q, k + 1, r);
2779  p_Setm(q, r);
2780 
2781  // cannot allow something like: a*gen(i) - a*gen(i)
2782  if (syzterm != NULL && (k == c))
2783  if (p_ExpVectorEqual(syzterm, q, r))
2784  {
2785  if( OPT__DEBUG )
2786  {
2787  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2788  dPrint(syzterm, r, r, 0);
2789  }
2790 
2791  continue;
2792  }
2793 
2794  // while the complement (the fraction) is not reducible by leading syzygies
2795  if( to_check && syz_checker.IsDivisible(q) )
2796  {
2797  if( OPT__DEBUG )
2798  {
2799  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2800  }
2801 
2802  continue;
2803  }
2804 
2805  number n = n_Mult( p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
2806  p_SetCoeff0(q, n_InpNeg( n_Div(n, p_GetCoeff(p, r), r), r), r);
2807  n_Delete(&n, r);
2808 
2809  return q;
2810  }
2811 */
2812 
2813  p_LmFree(q, r);
2814 
2815 #ifndef SING_NDEBUG
2816  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2817 #endif
2818 
2819  p_Test(multiplier, r);
2820 
2821  return NULL;
2822 
2823 }
2824 #endif
2825 
2826 
2827 poly CReducerFinder::FindReducer(const poly product, const poly syzterm, const CReducerFinder& syz_checker) const
2828 {
2829 
2830 #ifndef SING_NDEBUG
2831  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2832 #endif
2833 
2834  CDivisorEnumerator itr(*this, product);
2835  if( !itr.Reset() )
2836  return NULL;
2837 
2838 
2839 
2840  const ring& r = m_rBaseRing;
2841 
2842  assume( product != NULL );
2843 
2844  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
2845 
2846  long c = 0;
2847 
2848  if (syzterm != NULL)
2849  c = p_GetComp(syzterm, r) - 1;
2850 
2851  assume( c >= 0 && c < IDELEMS(L) );
2852 
2853  if (UNLIKELY( OPT__DEBUG && (syzterm != NULL) ))
2854  {
2855  const poly m = L->m[c];
2856 
2857  assume( m != NULL ); assume( pNext(m) == NULL );
2858 
2859  poly lm = p_Mult_mm(leadmonom(syzterm, r), m, r);
2860  assume( p_EqualPolys(lm, product, r) );
2861 
2862  // def @@c = leadcomp(syzterm); int @@r = int(@@c);
2863  // def @@product = leadmonomial(syzterm) * L[@@r];
2864 
2865  p_Delete(&lm, r);
2866  }
2867 
2868 #ifndef SING_NDEBUG
2869  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2870 #endif
2871 
2872  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2873 
2874  const poly q = p_New(r); pNext(q) = NULL;
2875 
2876  if( UNLIKELY(OPT__DEBUG) )
2877  p_SetCoeff0(q, 0, r); // ONLY for printing q
2878 
2879  while( itr.MoveNext() )
2880  {
2881  assume( itr.Current().CheckLT( L ) ); // ???
2882 
2883  const poly p = itr.Current().lt(); // ??
2884  const int k = itr.Current().label();
2885 
2886  p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2887  p_SetComp(q, k + 1, r);
2888  p_Setm(q, r);
2889 
2890  // cannot allow something like: a*gen(i) - a*gen(i)
2891  if (syzterm != NULL && (k == c))
2892  if (p_ExpVectorEqual(syzterm, q, r))
2893  {
2894 #ifndef SING_NDEBUG
2895  if( OPT__DEBUG )
2896  {
2897  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2898  dPrint(syzterm, r, r, 0);
2899  }
2900 #endif
2901  assume( itr.Current().CheckLT( L ) ); // ???
2902  continue;
2903  }
2904 
2905  // while the complement (the fraction) is not reducible by leading syzygies
2906  if( to_check && syz_checker.IsDivisible(q) ) // ?????
2907  {
2908 #ifndef SING_NDEBUG
2909  if( OPT__DEBUG )
2910  {
2911  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2912  }
2913 #endif
2914  assume( itr.Current().CheckLT( L ) ); // ???
2915  continue;
2916  }
2917 
2918 
2919 #if NODIVISION
2920  assume( n_IsOne(p_GetCoeff(p, r), r->cf) );
2921  p_SetCoeff0(q, n_InpNeg( n_Copy(pGetCoeff(product), r->cf), r->cf), r);
2922 #else
2923  p_SetCoeff0(q, n_InpNeg( n_Div( pGetCoeff(product), p_GetCoeff(p), r->cf), r->cf), r);
2924 #endif
2925 
2926  assume( itr.Current().CheckLT( L ) ); // ???
2927 
2928 #ifndef SING_NDEBUG
2929  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2930 #endif
2931 
2932  return q;
2933  }
2934 
2935 
2936 
2937 /*
2938  const long comp = p_GetComp(product, r);
2939  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
2940 
2941  assume( comp >= 0 );
2942 
2943 // for( int k = IDELEMS(L)-1; k>= 0; k-- )
2944 // {
2945 // const poly p = L->m[k];
2946 //
2947 // if ( p_GetComp(p, r) != comp )
2948 // continue;
2949 //
2950 // const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
2951 
2952  // looking for an appropriate diviser p = L[k]...
2953  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2954 
2955  if( it == m_hash.end() )
2956  return NULL;
2957 
2958  assume( m_L != NULL );
2959 
2960  const TReducers& reducers = it->second;
2961 
2962  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2963 
2964  const poly q = p_New(r); pNext(q) = NULL;
2965 
2966  if( OPT__DEBUG )
2967  p_SetCoeff0(q, 0, r); // for printing q
2968 
2969  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2970  {
2971  const poly p = (*vit)->lt(); // ???
2972 
2973  assume( p_GetComp(p, r) == comp );
2974 
2975  const int k = (*vit)->label();
2976 
2977  assume( L->m[k] == p ); // CheckLT
2978 
2979  const unsigned long p_sev = (*vit)->sev();
2980 
2981  assume( p_sev == p_GetShortExpVector(p, r) );
2982 
2983  if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2984  continue;
2985 
2986 // // ... which divides the product, looking for the _1st_ appropriate one!
2987 // if( !p_LmDivisibleByNoComp(p, product, r) ) // included inside p_LmShortDivisibleBy!
2988 // continue;
2989 
2990  p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2991  p_SetComp(q, k + 1, r);
2992  p_Setm(q, r);
2993 
2994  // cannot allow something like: a*gen(i) - a*gen(i)
2995  if (syzterm != NULL && (k == c))
2996  if (p_ExpVectorEqual(syzterm, q, r))
2997  {
2998  if( OPT__DEBUG )
2999  {
3000  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
3001  dPrint(syzterm, r, r, 0);
3002  }
3003 
3004  continue;
3005  }
3006 
3007  // while the complement (the fraction) is not reducible by leading syzygies
3008  if( to_check && syz_checker.IsDivisible(q) )
3009  {
3010  if( OPT__DEBUG )
3011  {
3012  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
3013  }
3014 
3015  continue;
3016  }
3017 
3018  p_SetCoeff0(q, n_InpNeg( n_Div( p_GetCoeff(product, r), p_GetCoeff(p, r), r), r), r);
3019  return q;
3020  }
3021 */
3022 
3023  p_LmFree(q, r);
3024 
3025 #ifndef SING_NDEBUG
3026  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
3027 #endif
3028 
3029  return NULL;
3030 }
3031 
3032 
3033 
3035  SchreyerSyzygyComputationFlags(flags), std::vector<bool>(),
3036  m_compute(false), m_N(rVar(flags.m_rBaseRing))
3037 {
3038  const ring& R = m_rBaseRing;
3039  assume( flags.m_rBaseRing == R );
3040  assume( R != NULL );
3041 
3042  assume( L != NULL );
3043 
3044  if( LIKELY( OPT__TAILREDSYZ && !OPT__HYBRIDNF && (L != NULL) )) // TODO: not hybrid!?
3045  {
3046  const int l = IDELEMS(L);
3047 
3048  assume( l > 0 );
3049 
3050  resize(l, false);
3051 
3052  for( int k = l - 1; k >= 0; k-- )
3053  {
3054  const poly a = L->m[k]; assume( a != NULL );
3055 
3056  for (unsigned int j = m_N; j > 0; j--)
3057  if ( !(*this)[j] )
3058  (*this)[j] = (p_GetExp(a, j, R) > 0);
3059  }
3060 
3061  m_compute = true;
3062  }
3063 }
3064 
3065 
3066 bool CLCM::Check(const poly m) const
3067 {
3068  assume( m != NULL );
3069  if( m_compute && (m != NULL))
3070  {
3071  const ring& R = m_rBaseRing;
3072 
3074 
3075  for (unsigned int j = m_N; j > 0; j--)
3076  if ( (*this)[j] )
3077  if(p_GetExp(m, j, R) > 0)
3078  return true;
3079 
3080  return false;
3081 
3082  } else return true;
3083 }
3084 
3086 
3087 
3088 template class std::vector<bool>;
3089 template class std::vector<CLeadingTerm const*>;
3090 template class std::map< CReducerFinder::TComponentKey, CReducerFinder::TReducers >;
3091 
3092 template class std::map<TCacheKey, TCacheValue, struct CCacheCompare>;
3093 template class std::map<int, TP2PCache>;
3094 
3095 template class std::stack <sBucket_pt>;
3096 
3098 
3099 
3100 // Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
#define OPT_REDSB
Definition: options.h:71
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:495
Computation attribute storage.
Definition: syzextra.h:190
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:181
static ideal Compute2LeadingSyzygyTerms(const ideal &L, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:592
const unsigned long m_not_sev
Definition: syzextra.cc:2496
const unsigned int m_label
index in the main L[] + 1
Definition: syzextra.h:291
#define qsort_my(m, s, ss, r, cmp)
const CanonicalForm int s
Definition: facAbsFact.cc:55
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
bool m_compute
Definition: syzextra.h:255
static poly TraverseTail(poly multiplier, poly tail, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:608
#define NOPRODUCT
Definition: syzextra.h:37
void Sort_c_ds(const ideal id, const ring r)
inplace sorting of the module (ideal) id wrt <_(c,ds)
Definition: syzextra.cc:527
const CReducerFinder & m_reds
Definition: syzextra.cc:2494
const CLeadingTerm & Current() const
Definition: syzextra.cc:2322
const poly a
Definition: syzextra.cc:212
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:720
Definition: tok.h:95
SBucketFactory & m_factory
Definition: syzextra.cc:118
#define RTIMER_BENCHMARKING
Definition: syzextra.cc:64
const long m_comp
Definition: syzextra.cc:2497
#define TEST_OPT_PROT
Definition: options.h:98
poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2=NULL) const
Main HybridNF == 1: poly reduce + LOT + LCM?
Definition: syzextra.cc:1417
poly leadmonom(const poly p, const ring r, const bool bSetZeroComp)
return a new term: leading coeff * leading monomial of p with 0 leading component! ...
Definition: syzextra.cc:473
const int OPT__HYBRIDNF
Use the usual NF&#39;s S-poly reduction while dropping lower order terms 2 means - smart selection! ...
Definition: syzextra.h:215
const int OPT__SYZCHECK
CheckSyzygyProperty: TODO.
Definition: syzextra.h:233
int getRTimer()
Definition: timer.cc:172
#define FALSE
Definition: auxiliary.h:94
Compatiblity layer for legacy polynomial operations (over currRing)
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:472
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:968
poly lt() const
Definition: syzextra.h:282
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:242
Detailed print for debugging.
#define p_GetComp(p, r)
Definition: monomials.h:72
const poly m_lt
the leading term itself L[label-1]
Definition: syzextra.h:293
CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags &flags)
goes over all leading terms
Definition: syzextra.cc:2148
BOOLEAN p_DebugLmDivisibleByNoComp(poly a, poly b, ring r)
Definition: pDebug.cc:140
std::vector< const CLeadingTerm * > TReducers
Definition: syzextra.h:318
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:542
const poly m_product
Definition: syzextra.cc:2272
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:583
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
STL namespace.
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:957
#define TRUE
Definition: auxiliary.h:98
static poly SchreyerSyzygyNF(poly syz_lead, poly syz_2, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:623
#define FORCE_INLINE
Definition: auxiliary.h:328
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2231
CDivisorEnumerator2(const CReducerFinder &self, const poly m, const poly t)
Definition: syzextra.cc:2505
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1430
poly FindReducer(const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder &checker) const
Definition: syzextra.cc:2600
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:582
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:201
unsigned long sev() const
Definition: syzextra.h:283
CDivisorEnumerator(const CReducerFinder &self, const poly product)
Definition: syzextra.cc:2282
#define SI_SAVE_OPT1(A)
Definition: options.h:20
void PrintStats() const
print statistics about the used heuristics
Definition: syzextra.cc:765
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
const poly m_term
Definition: syzextra.cc:2495
#define UNLIKELY(expression)
Definition: tgb_internal.h:838
char * StringEndS()
Definition: reporter.cc:151
#define LIKELY(expression)
Definition: tgb_internal.h:837
poly p_Tail(const poly p, const ring r)
return the tail of a given polynomial or vector returns NULL if input is NULL, otherwise the result i...
Definition: syzextra.cc:501
#define omTypeAllocBin(type, addr, bin)
Definition: omAllocDecl.h:203
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
#define BITSET
Definition: structs.h:18
CReducerFinder::CReducersHash::const_iterator m_itr
Definition: syzextra.cc:2499
#define BEGIN_NAMESPACE_SINGULARXX
const signed long iCompDiff
Definition: syzextra.cc:222
#define Sy_bit(x)
Definition: options.h:30
Bucket getBucket(const ring r, const bool remove=true)
Definition: syzextra.h:104
ideal Compute2LeadingSyzygyTerms()
leading + second terms
Definition: syzextra.cc:884
static void p_LmFree(poly p, ring)
Definition: p_polys.h:678
static FORCE_INLINE void n_WriteLong(number n, const coeffs r)
write to the output buffer of the currently used reporter
Definition: coeffs.h:587
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:485
Definition: idrec.h:34
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
poly pp
Definition: myNF.cc:296
const signed long iDegDiff
Definition: syzextra.cc:247
poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
Definition: syzextra.cc:1893
Computation of Syzygies.
static FORCE_INLINE int atGetInt(idhdl rootRingHdl, const char *attribute, long def)
Definition: syzextra.cc:188
const int OPT__TAILREDSYZ
Reduce syzygy tails wrt the leading syzygy terms.
Definition: syzextra.h:211
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
static BOOLEAN p_LmIsConstant(const poly p, const ring r)
Definition: p_polys.h:949
Definition: gnumpfl.cc:27
#define pIter(p)
Definition: monomials.h:44
#define SING_NDEBUG
Definition: factoryconf.h:276
CReducersHash m_hash
Definition: syzextra.h:357
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
void ComputeSyzygy()
The main driver function: computes.
Definition: syzextra.cc:1143
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
poly TraverseNF(const poly syz_lead, const poly syz_2=NULL) const
Definition: syzextra.cc:1034
USING_NAMESPACE(SINGULARXXNAME ::DEBUG) BEGIN_NAMESPACE_SINGULARXX BEGIN_NAMESPACE(SYZEXTRA) BEGIN_NAMESPACE_NONAME SBucketFactory
Definition: syzextra.cc:68
static poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:615
const ring r
Definition: syzextra.cc:208
Coefficient rings, fields and other domains suitable for Singular polynomials.
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:200
Definition: intvec.h:14
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
#define OPT_REDTAIL
Definition: options.h:86
int j
Definition: myNF.cc:70
CLCM(const ideal &L, const SchreyerSyzygyComputationFlags &flags)
Definition: syzextra.cc:3034
bool my_p_LmCmp(poly a, poly b, const ring r)
Definition: syzextra.cc:1588
#define omFree(addr)
Definition: omAllocDecl.h:261
#define p_SetRingOfLm(p, r)
Definition: monomials.h:152
SBucketWrapper(const ring r, SBucketFactory &factory)
Definition: syzextra.cc:120
bool CheckLT(const ideal &L) const
Definition: syzextra.cc:2205
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:127
The main handler for Singular numbers which are suitable for Singular polynomials.
void StringSetS(const char *st)
Definition: reporter.cc:128
#define END_NAMESPACE_SINGULARXX
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1070
static void _DestroyBucket(Bucket &bt)
we only expect empty buckets to be left at the end for destructor bt will be set to NULL ...
Definition: syzextra.cc:101
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:162
bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const
as DivisibilityCheck(multiplier * t, ...) for monomial &#39;m&#39; and a module term &#39;t&#39;
Definition: syzextra.cc:2236
void CleanUp()
Clean up all the accumulated data.
Definition: syzextra.cc:548
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:120
const ring R
Definition: DebugPrint.cc:36
#define BEGIN_NAMESPACE_NONAME
static FORCE_INLINE void n_Write(number n, const coeffs r, const BOOLEAN bShortOut=TRUE)
Definition: coeffs.h:595
CReducerFinder::TReducers::const_iterator m_finish
Definition: syzextra.cc:2277
poly TraverseTail(poly multiplier, const int tail) const
High level caching function!!!
Definition: syzextra.cc:1592
idhdl currRingHdl
Definition: ipid.cc:65
void SetUpTailTerms()
Convert the given ideal of tails into the internal representation (with reducers!) Preprocess m_idTai...
Definition: syzextra.cc:682
P bucket
Definition: myNF.cc:79
void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms=true)
Computes Syz(leads) or only LEAD of it. The result is stored into m_syzLeads.
Definition: syzextra.cc:1369
return false
Definition: cfModGcd.cc:84
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1467
int m
Definition: cfEzgcd.cc:119
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:561
ideal Compute1LeadingSyzygyTerms()
just leading terms
Definition: syzextra.cc:776
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static char * rRingVar(short i, const ring r)
Definition: ring.h:568
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:895
SBucketFactory::Bucket Bucket
Definition: syzextra.cc:113
void Add(poly p, const int l)
adds p to the internal bucket destroys p, l == length(p)
Definition: syzextra.cc:134
static BOOLEAN p_LmShortDivisibleByNoComp(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1822
#define p_LmCheckPolyRing1(p, r)
Definition: monomials.h:185
void Initialize(const ideal L)
Definition: syzextra.cc:2124
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define IDELEMS(i)
Definition: simpleideals.h:24
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
const CReducerFinder & m_reds
Definition: syzextra.cc:2271
const unsigned int m_N
number of ring variables
Definition: syzextra.h:257
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
const unsigned long m_sev
not short exp. vector
Definition: syzextra.h:284
static FORCE_INLINE number n_Lcm(number a, number b, const coeffs r)
in Z: return the lcm of &#39;a&#39; and &#39;b&#39; in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:716
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4367
#define p_Test(p, r)
Definition: p_polys.h:160
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
bool Check(const poly m) const
Definition: syzextra.cc:3066
const CLeadingTerm & Current() const
Definition: syzextra.cc:2552
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
static Bucket _CreateBucket(const ring r)
inital allocation for new buckets
#define p_SetmComp
Definition: p_polys.h:239
ring sBucketGetRing(const sBucket_pt bucket)
Returns bucket ring.
Definition: sbuckets.cc:51
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4635
static BOOLEAN _p_LmDivisibleByNoComp(const poly a, const poly b, const poly c, const ring r)
_p_LmDivisibleByNoComp for a | b*c
Definition: syzextra.cc:2159
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1611
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1397
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
void * atGet(idhdl root, const char *name, int t, void *defaultReturnValue)
Definition: attrib.cc:137
p_LmTest(a, r)
sBucket Factory
Definition: syzextra.h:75
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477
#define NULL
Definition: omList.c:10
#define FROM_NAMESPACE(a, s)
END_NAMESPACE BEGIN_NAMESPACE(SORT_c_ds) static int cmp_c_ds(const void *p1
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:455
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l) ...
Definition: kbuckets.cc:795
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:619
const unsigned long m_not_sev
Definition: syzextra.cc:2273
SchreyerSyzygyComputationFlags(idhdl rootRingHdl)
Definition: syzextra.cc:2032
BEGIN_NAMESPACE_SINGULARXX const ring const bool bSetZeroComp
Definition: syzextra.h:48
const int OPT__TREEOUTPUT
output lifting tree
Definition: syzextra.h:230
const CanonicalForm & w
Definition: facAbsFact.cc:55
poly ComputeImage(poly multiplier, const int tail) const
low level computation...
Definition: syzextra.cc:1736
#define END_NAMESPACE
Base::value_type Bucket
Definition: syzextra.h:84
const ring m_rBaseRing
global base ring
Definition: syzextra.h:242
void putBucket(const Bucket &bt, const bool replace=false)
Definition: syzextra.h:136
#define pNext(p)
Definition: monomials.h:43
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:464
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1258
#define pDivAssume(x)
Definition: p_polys.h:1205
int typ
Definition: idrec.h:43
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
const int YES
Definition: syzextra.cc:205
const int NO
Definition: syzextra.cc:206
#define pSetCoeff0(p, n)
Definition: monomials.h:67
ideal m_L
only for debug
Definition: syzextra.h:355
#define p_GetCoeff(p, r)
Definition: monomials.h:57
unsigned int label() const
Definition: syzextra.h:284
CReducerFinder::CReducersHash::const_iterator m_itr
Definition: syzextra.cc:2276
ideal id_Tail(const ideal id, const ring r)
return the tail of a given ideal or module returns NULL if input is NULL, otherwise the result is a n...
Definition: syzextra.cc:510
bool IsDivisible(const poly q) const
Definition: syzextra.cc:2370
const int OPT__IGNORETAILS
ignore tails and compute the pure Schreyer frame
Definition: syzextra.h:219
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:706
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:68
void Add(poly p)
adds p to the internal bucket destroys p
Definition: syzextra.cc:142
END_NAMESPACE const void * p2
Definition: syzextra.cc:202
CReducerFinder::TReducers::const_iterator m_finish
Definition: syzextra.cc:2500
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the additive inverse of the one element, i.e. -1.
Definition: coeffs.h:476
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:498
static void p_ExpVectorSum(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1348
static BOOLEAN p_ExpVectorEqual(poly p1, poly p2, const ring r1, const ring r2)
Definition: p_polys.cc:4381
Bucket m_bucket
Definition: syzextra.cc:116
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition: sbuckets.cc:55
static jList * T
Definition: janet.cc:37
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
int status int void size_t count int const void size_t count const char int flags
Definition: si_signals.h:73
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:193
int getTimer()
Definition: timer.cc:97
poly ClearAdd()
Definition: syzextra.cc:144
static poly p_New(const ring, omBin bin)
Definition: p_polys.h:659
void dPrint(const ideal id, const ring lmRing=currRing, const ring tailRing=currRing, const int nTerms=0)
prints an ideal, optionally with details
int BOOLEAN
Definition: auxiliary.h:85
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1243
const poly b
Definition: syzextra.cc:213
#define SI_RESTORE_OPT1(A)
Definition: options.h:23
int PreProcessTerm(const poly t, CReducerFinder &syzChecker) const
is the term to be "preprocessed" as lower order term or lead to only reducible syzygies...
Definition: syzextra.cc:587
static FORCE_INLINE poly myp_Head(const poly p, const bool bIgnoreCoeff, const ring r)
Definition: syzextra.cc:456
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020
static END_NAMESPACE void writeLatexTerm(const poly t, const ring r, const bool bCurrSyz=true, const bool bLTonly=true)
writes a monomial (p), uses form x*gen(.) if ko != coloumn number of p
Definition: syzextra.cc:336
assume(R !=NULL)
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:270
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
static FORCE_INLINE poly p_VectorProductLT(poly s, const ideal &L, const ideal &T, const ring &R)
Definition: syzextra.cc:158
const long m_comp
Definition: syzextra.cc:2274
bool IsNonempty() const
Definition: syzextra.h:344
static ideal ComputeLeadingSyzygyTerms(const ideal &L, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:583
static FORCE_INLINE poly pp_Add_qq(const poly a, const poly b, const ring R)
Definition: syzextra.cc:153
#define Warn
Definition: emacs.cc:80
std::map< TCacheKey, TCacheValue, CCacheCompare > TP2PCache
Definition: syzextra.h:383