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
78 {
79  assume( bt != NULL );
80  return sBucketGetRing(bt);
81 }
82 
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  extern void id_Delete (ideal*, const ring);
551 
552  id_Delete(const_cast<ideal*>(&m_idTails), m_rBaseRing); // TODO!!!
553 
554 /*if( m_sum_bucket != NULL )
555  {
556  assume ( sIsEmpty(m_sum_bucket) );
557  sBucketDestroy(&m_sum_bucket);
558  m_sum_bucket = NULL;
559  }*/
560 
561  if( m_spoly_bucket != NULL )
562  {
563  kBucketDestroy(&m_spoly_bucket);
564  m_spoly_bucket = NULL;
565  }
566 
567  for( TCache::iterator it = m_cache.begin(); it != m_cache.end(); it++ )
568  {
569  TP2PCache& T = it->second;
570 
571  for(TP2PCache::iterator vit = T.begin(); vit != T.end(); vit++ )
572  {
573  p_Delete( (&(vit->second)), m_rBaseRing);
574  p_Delete( const_cast<poly*>(&(vit->first)), m_rBaseRing);
575  }
576  }
577 }
578  /*
579  for( TTailTerms::const_iterator it = m_idTailTerms.begin(); it != m_idTailTerms.end(); it++ )
580  {
581  const TTail& v = *it;
582  for(TTail::const_iterator vit = v.begin(); vit != v.end(); vit++ )
583  delete const_cast<CTailTerm*>(*vit);
584  }
585  */
586 
587 
588 
589 int CReducerFinder::PreProcessTerm(const poly t, CReducerFinder& syzChecker) const
590 {
591  assume( t != NULL );
592 
593  if( UNLIKELY(OPT__DEBUG & OPT__TAILREDSYZ) )
594  assume( !IsDivisible(t) ); // each input term should NOT be in <L>
595 
596  const ring r = m_rBaseRing;
597 
598 
599  if( LIKELY(OPT__TAILREDSYZ) )
600  if( p_LmIsConstant(t, r) ) // most basic case of baing coprime with L, whatever that is...
601  return 1; // TODO: prove this...?
602 
603  // return false; // appears to be fine
604 
605  const long comp = p_GetComp(t, r);
606 
607  CReducersHash::const_iterator itr = m_hash.find(comp);
608 
609  if ( itr == m_hash.end() )
610  return 2; // no such leading component!!!
611 
612  assume( itr->first == comp );
613 
614  const bool bIdealCase = (comp == 0);
615  const bool bSyzCheck = syzChecker.IsNonempty(); // need to check even in ideal case????? proof? "&& !bIdealCase"
616 
617  if( LIKELY(OPT__TAILREDSYZ && (bIdealCase || bSyzCheck)) )
618  {
619  const TReducers& v = itr->second;
620  const int N = rVar(r);
621  // TODO: extract exps of t beforehand?!
622  bool coprime = true;
623  for(TReducers::const_iterator vit = v.begin(); (vit != v.end()) && coprime; ++vit )
624  {
625  assume( (*vit)->CheckLT( m_L ) );
626 
627  const poly p = (*vit)->lt();
628 
629  assume( p_GetComp(p, r) == comp );
630 
631  // TODO: check if coprime with Leads... if OPT__TAILREDSYZ !
632  for( int var = N; var > 0; --var )
633  if( (p_GetExp(p, var, r) != 0) && (p_GetExp(t, var, r) != 0) )
634  {
635 #ifndef SING_NDEBUG
636  if( OPT__DEBUG | 0)
637  {
638  PrintS("CReducerFinder::PreProcessTerm, 't' is NOT co-prime with the following leading term: \n");
639  dPrint(p, r, r, 0);
640  }
641 #endif
642  coprime = false; // t not coprime with p!
643  break;
644  }
645 
646  if( bSyzCheck && coprime )
647  {
648  poly ss = p_LmInit(t, r);
649  p_SetCoeff0(ss, n_Init(1, r->cf), r); // for delete & printout only!...
650  p_SetComp(ss, (*vit)->label() + 1, r); // coeff?
651  p_Setm(ss, r);
652 
653  coprime = ( syzChecker.IsDivisible(ss) );
654 
655 #ifndef SING_NDEBUG
656  if( OPT__DEBUG && !coprime)
657  {
658  PrintS("CReducerFinder::PreProcessTerm, 't' is co-prime with p but may lead to NOT divisible syz.term: \n");
659  dPrint(ss, r, r, 0);
660  }
661 #endif
662 
663  p_LmDelete(&ss, r); // deletes coeff as well???
664  }
665 
666  assume( p == (*vit)->lt() );
667  assume( (*vit)->CheckLT( m_L ) );
668  }
669 
670 #ifndef SING_NDEBUG
671  if( OPT__DEBUG && coprime )
672  PrintS("CReducerFinder::PreProcessTerm, the following 't' is 'co-prime' with all of leading terms! \n");
673 #endif
674 
675  return coprime? 3: 0; // t was coprime with all of leading terms!!!
676 
677  }
678  // return true; // delete the term
679 
680  return 0;
681 }
682 
683 
685 {
686  const ideal idTails = m_idTails;
687  assume( idTails != NULL );
688  assume( idTails->m != NULL );
689  const ring r = m_rBaseRing;
690 
691  unsigned long pp[4] = {0,0,0,0}; // count preprocessed terms...
692 
693 #ifndef SING_NDEBUG
694  if( OPT__DEBUG | 0)
695  {
696  PrintS("SchreyerSyzygyComputation::SetUpTailTerms(): Tails: \n");
697  dPrint(idTails, r, r, 0);
698  }
699 #endif
700 
701  for( int p = IDELEMS(idTails) - 1; p >= 0; --p )
702  for( poly* tt = &(idTails->m[p]); (*tt) != NULL; )
703  {
704  const poly t = *tt;
705  const int k = m_div.PreProcessTerm(t, m_checker); // 0..3
706  assume( 0 <= k && k <= 3 );
707 
708  pp[k]++; // collect stats
709 
710  if( k )
711  {
712 #ifndef SING_NDEBUG
713  if( OPT__DEBUG)
714  {
715  Print("SchreyerSyzygyComputation::SetUpTailTerms(): PP (%d) the following TT: \n", k);
716  dPrint(t, r, r, 0);
717  }
718 #endif
719 
720  (*tt) = p_LmDeleteAndNext(t, r); // delete the lead and next...
721  }
722  else
723  tt = &pNext(t); // go next?
724 
725  }
726 
727 #ifndef SING_NDEBUG
728  if( OPT__DEBUG | 0)
729  {
730  PrintS("SchreyerSyzygyComputation::SetUpTailTerms(): Preprocessed Tails: \n");
731  dPrint(idTails, r, r, 0);
732  }
733 #endif
734 
735  if( UNLIKELY(OPT__PROT) )
736  {
737  Print("(PP/ST: {c: %lu, C: %lu, P: %lu} + %lu)", pp[1], pp[2], pp[3], pp[0]);
738  m_stat[0] += pp [0]; m_stat[1] += pp [1]; m_stat[2] += pp [2]; m_stat[3] += pp [3];
739  }
740 }
741 
742 /*
743  m_idTailTerms.resize( IDELEMS(idTails) );
744 
745  for( unsigned int p = IDELEMS(idTails) - 1; p >= 0; p -- )
746  {
747  TTail& v = m_idTailTerms[p];
748  poly t = idTails->m[p];
749  v.resize( pLength(t) );
750 
751  unsigned int pp = 0;
752 
753  while( t != NULL )
754  {
755  assume( t != NULL );
756  // TODO: compute L:t!
757 // ideal reducers;
758 // CReducerFinder m_reducers
759 
760  CTailTerm* d = v[pp] = new CTailTerm();
761 
762  ++pp; pIter(t);
763  }
764  }
765 */
766 
768 {
769  Print("SchreyerSyzygyComputation Stats: (PP/ST: {c: %lu, C: %lu, P: %lu} + %lu, LOT: %lu, LCM: %lu, ST:%lu, LK: %lu {*: %lu})\n",
770  m_stat[1], m_stat[2], m_stat[3], m_stat[0],
771  m_stat[4], m_stat[5],
772  m_stat[8],
773  m_stat[6] + m_stat[7], m_stat[7]
774  );
775 }
776 
777 
779 {
780  const ideal& id = m_idLeads;
781  const ring& r = m_rBaseRing;
782 // const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
783 
784  assume(!OPT__LEAD2SYZ);
785 
786  // 1. set of components S?
787  // 2. for each component c from S: set of indices of leading terms
788  // with this component?
789  // 3. short exp. vectors for each leading term?
790 
791  const int size = IDELEMS(id);
792 
793  if( size < 2 )
794  {
795  const ideal newid = idInit(1, 0); newid->m[0] = NULL; // zero ideal...
796  return newid;
797  }
798 
799  // TODO/NOTE: input is supposed to be (reverse-) sorted wrt "(c,ds)"!??
800 
801  // components should come in groups: count elements in each group
802  // && estimate the real size!!!
803 
804 
805  // use just a vector instead???
806  const ideal newid = idInit( (size * (size-1))/2, size); // maximal size: ideal case!
807 
808  int k = 0;
809 
810  for (int j = 0; j < size; j++)
811  {
812  const poly p = id->m[j];
813  assume( p != NULL );
814  const int c = p_GetComp(p, r);
815 
816  for (int i = j - 1; i >= 0; i--)
817  {
818  const poly pp = id->m[i];
819  assume( pp != NULL );
820  const int cc = p_GetComp(pp, r);
821 
822  if( c != cc )
823  continue;
824 
825  const poly m = p_Init(r); // p_New???
826 
827  // m = LCM(p, pp) / p! // TODO: optimize: knowing the ring structure: (C/lp)!
828  for (int v = rVar(r); v > 0; v--)
829  {
830  assume( v > 0 );
831  assume( v <= rVar(r) );
832 
833  const short e1 = p_GetExp(p , v, r);
834  const short e2 = p_GetExp(pp, v, r);
835 
836  if( e1 >= e2 )
837  p_SetExp(m, v, 0, r);
838  else
839  p_SetExp(m, v, e2 - e1, r);
840 
841  }
842 
843  assume( (j > i) && (i >= 0) );
844 
845  p_SetComp(m, j + 1, r);
846  pNext(m) = NULL;
847  p_SetCoeff0(m, n_Init(1, r->cf), r); // for later...
848 
849  p_Setm(m, r); // should not do anything!!!
850 
851  newid->m[k++] = m;
852  }
853  }
854 
855 // if( OPT__DEBUG & FALSE )
856 // {
857 // PrintS("ComputeLeadingSyzygyTerms::Temp0: \n");
858 // dPrint(newid, r, r, 0);
859 // }
860 
861  // the rest of newid is assumed to be zeroes...
862 
863  // simplify(newid, 2 + 32)??
864  // sort(newid, "C,ds")[1]???
865  id_DelDiv(newid, r); // #define SIMPL_LMDIV 32
866 
867 // if( OPT__DEBUG & FALSE )
868 // {
869 // PrintS("ComputeLeadingSyzygyTerms::Temp1: \n");
870 // dPrint(newid, r, r, 0);
871 // }
872 
873  idSkipZeroes(newid); // #define SIMPL_NULL 2
874 
875 // if( OPT__DEBUG )
876 // {
877 // PrintS("ComputeLeadingSyzygyTerms::Output: \n");
878 // dPrint(newid, r, r, 0);
879 // }
880 
881  Sort_c_ds(newid, r);
882 
883  return newid;
884 }
885 
887 {
888  const ideal& id = m_idLeads;
889  const ring& r = m_rBaseRing;
890 // const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
891 
892  // 1. set of components S?
893  // 2. for each component c from S: set of indices of leading terms
894  // with this component?
895  // 3. short exp. vectors for each leading term?
896 
897  const int size = IDELEMS(id);
898 
899  if( size < 2 )
900  {
901  const ideal newid = idInit(1, 1); newid->m[0] = NULL; // zero module...
902  return newid;
903  }
904 
905 
906  // TODO/NOTE: input is supposed to be sorted wrt "C,ds"!??
907 
908  // components should come in groups: count elements in each group
909  // && estimate the real size!!!
910 
911 
912  // use just a vector instead???
913  ideal newid = idInit( (size * (size-1))/2, size); // maximal size: ideal case!
914 
915  int k = 0;
916 
917  for (int j = 0; j < size; j++)
918  {
919  const poly p = id->m[j];
920  assume( p != NULL );
921  const int c = p_GetComp(p, r);
922 
923  for (int i = j - 1; i >= 0; i--)
924  {
925  const poly pp = id->m[i];
926  assume( pp != NULL );
927  const int cc = p_GetComp(pp, r);
928 
929  if( c != cc )
930  continue;
931 
932  // allocate memory & zero it out!
933  const poly m = p_Init(r); const poly mm = p_Init(r);
934 
935 
936  // m = LCM(p, pp) / p! mm = LCM(p, pp) / pp!
937  // TODO: optimize: knowing the ring structure: (C/lp)!
938 
939  for (int v = rVar(r); v > 0; v--)
940  {
941  assume( v > 0 );
942  assume( v <= rVar(r) );
943 
944  const short e1 = p_GetExp(p , v, r);
945  const short e2 = p_GetExp(pp, v, r);
946 
947  if( e1 >= e2 )
948  p_SetExp(mm, v, e1 - e2, r); // p_SetExp(m, v, 0, r);
949  else
950  p_SetExp(m, v, e2 - e1, r); // p_SetExp(mm, v, 0, r);
951 
952  }
953 
954  assume( (j > i) && (i >= 0) );
955 
956  p_SetComp(m, j + 1, r);
957  p_SetComp(mm, i + 1, r);
958 
959  const number& lc1 = p_GetCoeff(p , r);
960  const number& lc2 = p_GetCoeff(pp, r);
961 
962 #if NODIVISION
963  assume( n_IsOne(lc1, r->cf) );
964  assume( n_IsOne(lc2, r->cf) );
965 
966  p_SetCoeff0( m, n_Init( 1, r->cf), r );
967  p_SetCoeff0(mm, n_Init(-1, r->cf), r );
968 #else
969  number g = n_Lcm( lc1, lc2, r->cf );
970  p_SetCoeff0(m , n_Div(g, lc1, r), r);
971  p_SetCoeff0(mm, n_InpNeg(n_Div(g, lc2, r), r), r);
972  n_Delete(&g, r);
973 #endif
974 
975  p_Setm(m, r); // should not do anything!!!
976  p_Setm(mm, r); // should not do anything!!!
977 
978  pNext(m) = mm; // pNext(mm) = NULL;
979 
980  newid->m[k++] = m;
981  }
982  }
983 
984 // if( OPT__DEBUG & FALSE )
985 // {
986 // PrintS("Compute2LeadingSyzygyTerms::Temp0: \n");
987 // dPrint(newid, r, r, 0);
988 // }
989 
990  if( UNLIKELY(!OPT__TAILREDSYZ) )
991  {
992  // simplify(newid, 2 + 32)??
993  // sort(newid, "C,ds")[1]???
994  id_DelDiv(newid, r); // #define SIMPL_LMDIV 32
995 
996 // if( OPT__DEBUG & FALSE )
997 // {
998 // PrintS("Compute2LeadingSyzygyTerms::Temp1 (deldiv): \n");
999 // dPrint(newid, r, r, 0);
1000 // }
1001  }
1002  else
1003  {
1004  // option(redSB); option(redTail);
1005  // TEST_OPT_REDSB
1006  // TEST_OPT_REDTAIL
1007  assume( r == currRing );
1008 
1009  BITSET _save_test; SI_SAVE_OPT1(_save_test);
1011 
1012  intvec* w=new intvec(IDELEMS(newid));
1013  ideal tmp = kStd(newid, currRing->qideal, isHomog, &w);
1014  delete w;
1015 
1016  SI_RESTORE_OPT1(_save_test)
1017 
1018  id_Delete(&newid, r);
1019  newid = tmp;
1020 
1021 // if( OPT__DEBUG & FALSE )
1022 // {
1023 // PrintS("Compute2LeadingSyzygyTerms::Temp1 (std): \n");
1024 // dPrint(newid, r, r, 0);
1025 // }
1026 
1027  }
1028 
1029  idSkipZeroes(newid);
1030 
1031  Sort_c_ds(newid, r);
1032 
1033  return newid;
1034 }
1035 
1037 {
1038 #ifndef SING_NDEBUG
1039  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1040 #endif
1041 
1042  const ideal& L = m_idLeads;
1043  const ideal& T = m_idTails;
1044 
1045  const ring& R = m_rBaseRing;
1046 
1047  const int r = p_GetComp(a, R) - 1;
1048 
1049  assume( r >= 0 && r < IDELEMS(T) );
1050  assume( r >= 0 && r < IDELEMS(L) );
1051 
1052  assume( a != NULL );
1053 
1054 #ifndef SING_NDEBUG
1055  if( OPT__DEBUG )
1056  {
1057  PrintS("SchreyerSyzygyComputation::TraverseNF(syz_lead, poly syz_2), \n");
1058  PrintS("syz_lead: \n");
1059  dPrint(a, R, R, 0);
1060  PrintS("syz_2: \n");
1061  dPrint(a2, R, R, 0);
1062  PrintLn();
1063  }
1064 #endif
1065 
1066  if( UNLIKELY(OPT__TREEOUTPUT) )
1067  {
1068  PrintS("{ \"proc\": \"TraverseNF\", \"nodelabel\": \"");
1069  writeLatexTerm(a, R);
1070  PrintS("\", \"children\": [");
1071  }
1072 
1073  poly aa = leadmonom(a, R); assume( aa != NULL); // :(
1074 
1075 #ifndef SING_NDEBUG
1076  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1077 #endif
1078 
1079  poly t = TraverseTail(aa, r);
1080 
1081  if( a2 != NULL )
1082  {
1083  assume( OPT__LEAD2SYZ );
1084 
1085  if( UNLIKELY(OPT__TREEOUTPUT) )
1086  {
1087 
1088  PrintS("{ \"proc\": \"TraverseNF2\", \"nodelabel\": \"");
1089  writeLatexTerm(a2, R);
1090  PrintS("\", \"children\": [");
1091  }
1092 
1093  // replace the following... ?
1094  const int r2 = p_GetComp(a2, R) - 1; poly aa2 = leadmonom(a2, R); // :(
1095 
1096  assume( r2 >= 0 && r2 < IDELEMS(T) );
1097 
1098  poly s = TraverseTail(aa2, r2);
1099 
1100  p_Delete(&aa2, R);
1101 
1102 
1103  if( UNLIKELY(OPT__TREEOUTPUT) )
1104  {
1105  PrintS("], \"noderesult\": \"");
1106  writeLatexTerm(s, R, true, false);
1107  PrintS("\" },");
1108  }
1109 
1110  t = p_Add_q(a2, p_Add_q(t, s, R), R);
1111 
1112 #ifndef SING_NDEBUG
1113  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1114 #endif
1115 
1116  } else
1117  t = p_Add_q(t, ReduceTerm(aa, L->m[r], a), R); // should be identical to bove with a2
1118 
1119  p_Delete(&aa, R);
1120 
1121  if( UNLIKELY(OPT__TREEOUTPUT) )
1122  {
1123 // poly tt = pp_Add_qq( a, t, R);
1124  PrintS("], \"noderesult\": \"");
1125  writeLatexTerm(t, R, true, false);
1126  PrintS("\" },");
1127 // p_Delete(&tt, R);
1128  }
1129 #ifndef SING_NDEBUG
1130  if( OPT__DEBUG )
1131  {
1132  PrintS("SchreyerSyzygyComputation::TraverseNF(syz_lead, poly syz_2), ==>>> \n");
1133  dPrint(t, R, R, 0);
1134  PrintLn();
1135  }
1136 #endif
1137 
1138 #ifndef SING_NDEBUG
1139  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1140 #endif
1141 
1142  return t;
1143 }
1144 
1146 {
1147 #ifndef SING_NDEBUG
1148  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1149 #endif
1150 
1151  assume( m_idLeads != NULL );
1152  assume( m_idTails != NULL );
1153 
1154  const ideal& L = m_idLeads;
1155  const ideal& T = m_idTails;
1156 
1157  ideal& TT = m_syzTails;
1158  const ring& R = m_rBaseRing;
1159 
1160 // if( m_sum_bucket == NULL )
1161 // m_sum_bucket = sBucketCreate(R);
1162 // assume ( sIsEmpty(m_sum_bucket) );
1163 
1164  if( m_spoly_bucket == NULL )
1165  m_spoly_bucket = kBucketCreate(R);
1166 
1167 
1168  assume( IDELEMS(L) == IDELEMS(T) );
1169 
1170 #ifdef SING_NDEBUG
1171  int t, r; // for rtimer benchmarking in prot realease mode
1172 #endif
1173 
1174  if( UNLIKELY(OPT__TREEOUTPUT) )
1175  Print("\n{ \"syzygylayer\": \"%d\", \"hybridnf\": \"%d\", \"diagrams\": \n[", OPT__SYZNUMBER, OPT__HYBRIDNF );
1176 
1177  if( UNLIKELY(OPT__PROT) ) Print("\n[%d]", OPT__SYZNUMBER );
1178 
1179  if( m_syzLeads == NULL )
1180  {
1181 #ifdef SING_NDEBUG
1182  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1183  {
1184  t = getTimer(); r = getRTimer();
1185  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: t: %d, r: %d\n", r, t, r);
1186  }
1187 #endif
1188 
1189  ComputeLeadingSyzygyTerms( OPT__LEAD2SYZ && !OPT__IGNORETAILS ); // 2 terms OR 1 term!
1190 
1191 #ifdef SING_NDEBUG
1192  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1193  {
1194  t = getTimer() - t; r = getRTimer() - r;
1195  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: dt: %d, dr: %d\n", getRTimer(), t, r);
1196  }
1197 #endif
1198 
1199  }
1200 
1201  assume( m_syzLeads != NULL );
1202  ideal& LL = m_syzLeads;
1203  const int size = IDELEMS(LL);
1204 
1205  TT = idInit(size, 0);
1206 
1207  if( size == 1 && LL->m[0] == NULL )
1208  {
1209  if( UNLIKELY(OPT__TREEOUTPUT) )
1210  PrintS("]},");
1211  return;
1212  }
1213 
1214 
1215  // use hybrid (Schreyer NF) method?
1216  const bool method = (OPT__HYBRIDNF == 1); // || (OPT__HYBRIDNF == 2 && OPT__SYZNUMBER < 3);
1217 
1218  if( UNLIKELY(OPT__PROT) ) Print("[%s NF|%s]",(method) ? "PR" : "TT", (NOPRODUCT == 1)? "_,_": "^*^" );
1219 
1220 
1221  if( LIKELY(!OPT__IGNORETAILS) )
1222  {
1223  if( T != NULL )
1224  {
1225 #ifdef SING_NDEBUG
1226  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1227  {
1228  t = getTimer(); r = getRTimer();
1229  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): t: %d, r: %d\n", r, t, r);
1230  }
1231 #endif
1232 
1233  SetUpTailTerms();
1234 
1235 #ifdef SING_NDEBUG
1236  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1237  {
1238  t = getTimer() - t; r = getRTimer() - r;
1239  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): dt: %d, dr: %d\n", getRTimer(), t, r);
1240  }
1241 #endif
1242  }
1243  }
1244 
1245 #ifdef SING_NDEBUG
1246  if( UNLIKELY(OPT__PROT & RTIMER_BENCHMARKING) )
1247  {
1248  t = getTimer(); r = getRTimer();
1249  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: t: %d, r: %d\n", r, t, r);
1250  }
1251 #endif
1252 
1253 #ifndef SING_NDEBUG
1254  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1255 #endif
1256 
1257 // for( int k = 0; k < size; ++k ) // TODO: should be fine now!
1258  for( int k = size - 1; k >= 0; --k )
1259  {
1260  const poly a = LL->m[k]; assume( a != NULL );
1261 
1262  poly a2 = pNext(a);
1263 
1264  // Splitting 2-terms Leading syzygy module
1265  if( a2 != NULL )
1266  pNext(a) = NULL;
1267 
1268  if( UNLIKELY(OPT__IGNORETAILS) )
1269  {
1270  TT->m[k] = NULL;
1271 
1272  assume( a2 != NULL );
1273 
1274  if( a2 != NULL )
1275  p_Delete(&a2, R);
1276 
1277  continue;
1278  }
1279 
1280  // TT->m[k] = a2;
1281 
1282 #ifndef SING_NDEBUG
1283  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1284 #endif
1285 
1286  poly nf;
1287 
1288  if( method )
1289  nf = SchreyerSyzygyNF(a, a2);
1290  else
1291  nf = TraverseNF(a, a2);
1292 
1293 #ifndef SING_NDEBUG
1294  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1295 #endif
1296 
1297  TT->m[k] = nf;
1298 
1299  if( UNLIKELY(OPT__SYZCHECK) )
1300  {
1301  // TODO: check the correctness (syzygy property): a + TT->m[k] should be a syzygy!!!
1302 
1303  poly s = pp_Add_qq( a, TT->m[k], R); // current syzygy
1304 
1305  poly vp = p_VectorProductLT(s, L, T, R);
1306 
1307  if( UNLIKELY( OPT__DEBUG && (vp != NULL) && ! OPT__TREEOUTPUT ) )
1308  {
1309  Warn("SchreyerSyzygyComputation::ComputeSyzygy: failed syzygy property for syzygy [%d], non-zero image is as follows: ", k);
1310  dPrint(vp, R, R, 0); p_Delete(&vp, R);
1311 
1312  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: Wrong syzygy is as follows: ");
1313  s = pp_Add_qq( a, TT->m[k], R);
1314  dPrint(s, R, R, 0); p_Delete(&s, R);
1315 
1316  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: Testing with the other method");
1317 
1318  if( !method )
1319  s = SchreyerSyzygyNF(a, a2);
1320  else
1321  s = TraverseNF(a, a2);
1322 
1323  s = p_Add_q( p_Copy(a, R), s, R); // another syzygy // :((((
1324  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: The other method gives the following syzygy: ");
1325  dPrint(s, R, R, 0);
1326 
1327  vp = p_VectorProductLT(s, L, T, R);
1328 
1329  if( vp == NULL )
1330  {
1331  PrintS("SchreyerSyzygyComputation::ComputeSyzygy: .... which is correct!!! ");
1332  } else
1333  {
1334  Warn("SchreyerSyzygyComputation::ComputeSyzygy: failed to compute syzygy tail[%d] with both methods!!! Non-zero image (2nd) is as follows: ", k);
1335  dPrint(vp, R, R, 0);
1336  }
1337 
1338 #ifndef SING_NDEBUG
1339  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1340 #endif
1341 
1342  } else
1343  assume( vp == NULL );
1344 
1345  if( UNLIKELY( OPT__PROT && (vp != NULL) ) ) Warn("ERROR: SyzCheck failed, wrong tail: [%d]\n\n", k); // check k'th syzygy failed
1346 
1347  p_Delete(&vp, R);
1348  }
1349 
1350 #ifndef SING_NDEBUG
1351  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1352 #endif
1353  }
1354 
1355 #ifdef SING_NDEBUG
1356  if( UNLIKELY( OPT__PROT & RTIMER_BENCHMARKING ) )
1357  {
1358  t = getTimer() - t; r = getRTimer() - r;
1359  Print("\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: dt: %d, dr: %d\n", getRTimer(), t, r);
1360  }
1361 #endif
1362 
1363  TT->rank = id_RankFreeModule(TT, R);
1364 
1365  if( UNLIKELY(OPT__TREEOUTPUT) )
1366  PrintS("\n]},");
1367 
1368  if( UNLIKELY(OPT__PROT) ) PrintLn();
1369 }
1370 
1372 {
1373 // const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
1374 
1375 // const BOOLEAN OPT__LEAD2SYZ = attributes.OPT__LEAD2SYZ;
1376 // const BOOLEAN OPT__TAILREDSYZ = attributes.OPT__TAILREDSYZ;
1377 
1378  assume( m_syzLeads == NULL );
1379 
1380  if( UNLIKELY(bComputeSecondTerms) )
1381  {
1382  assume( OPT__LEAD2SYZ );
1383 // m_syzLeads = FROM_NAMESPACE(INTERNAL, _Compute2LeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes));
1384  m_syzLeads = Compute2LeadingSyzygyTerms();
1385  }
1386  else
1387  {
1388  assume( !OPT__LEAD2SYZ );
1389 
1390  m_syzLeads = Compute1LeadingSyzygyTerms();
1391  }
1392 // m_syzLeads = FROM_NAMESPACE(INTERNAL, _ComputeLeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes));
1393 
1394  // NOTE: set m_LS if tails are to be reduced!
1395  assume( m_syzLeads!= NULL );
1396 
1397  if ( LIKELY( OPT__TAILREDSYZ && !OPT__IGNORETAILS && (IDELEMS(m_syzLeads) > 0) && !((IDELEMS(m_syzLeads) == 1) && (m_syzLeads->m[0] == NULL)) ) )
1398  {
1399  m_LS = m_syzLeads;
1400  m_checker.Initialize(m_syzLeads);
1401 #ifndef SING_NDEBUG
1402  if( OPT__DEBUG )
1403  {
1404  const ring& r = m_rBaseRing;
1405  PrintS("SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms: \n");
1406  PrintS("m_syzLeads: \n");
1407  dPrint(m_syzLeads, r, r, 0);
1408  PrintS("m_checker.Initialize(m_syzLeads) => \n");
1409  m_checker.DebugPrint();
1410  }
1411 #endif
1412  assume( m_checker.IsNonempty() ); // TODO: this always fails... BUG????
1413  }
1414 
1415  if( UNLIKELY( OPT__PROT ) ) Print("(L%dS:%d)", bComputeSecondTerms ? 2 : 1, IDELEMS(m_syzLeads));
1416 
1417 }
1418 
1420 {
1421  assume( !OPT__IGNORETAILS );
1422 
1423  const ideal& L = m_idLeads;
1424  const ideal& T = m_idTails;
1425  const ring& r = m_rBaseRing;
1426 
1427  assume( syz_lead != NULL );
1428 
1429 
1430 #ifndef SING_NDEBUG
1431  if( OPT__DEBUG )
1432  {
1433  PrintS("SchreyerSyzygyComputation::SchreyerSyzygyNF(syz_lead, poly syz_2), \n");
1434  PrintS("syz_lead: \n");
1435  dPrint(syz_lead, r, r, 0);
1436  PrintS("syz_2: \n");
1437  dPrint(syz_2, r, r, 0);
1438  PrintLn();
1439  }
1440 #endif
1441 
1442  if( UNLIKELY( OPT__TREEOUTPUT ) )
1443  {
1444  PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_lead, r);
1445  PrintS("\", \"children\": [");
1446  }
1447 
1448  if( syz_2 == NULL )
1449  {
1450  const int rr = p_GetComp(syz_lead, r) - 1;
1451 
1452  assume( rr >= 0 && rr < IDELEMS(T) );
1453  assume( rr >= 0 && rr < IDELEMS(L) );
1454 
1455 #if NOPRODUCT
1456  syz_2 = m_div.FindReducer(syz_lead, L->m[rr], syz_lead, m_checker);
1457  p_Test(syz_2, r);
1458 
1459  if( UNLIKELY( OPT__TREEOUTPUT ) )
1460  {
1461  PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_2, r); PrintS("\" },");
1462  }
1463 #else
1464  poly aa = leadmonom(syz_lead, r); assume( aa != NULL); // :(
1465  aa = p_Mult_mm(aa, L->m[rr], r);
1466 
1467  if( UNLIKELY( OPT__TREEOUTPUT ) )
1468  {
1469  PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_2, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(aa, r, false); PrintS("\" },");
1470  }
1471 
1472  syz_2 = m_div.FindReducer(aa, syz_lead, m_checker);
1473  p_Test(syz_2, r);
1474 
1475  p_Delete(&aa, r);
1476 #endif
1477 
1478  }
1479 
1480  assume( syz_2 != NULL ); // by construction of S-Polynomial
1481 
1482  assume( L != NULL );
1483  assume( T != NULL );
1484 
1485  assume( IDELEMS(L) == IDELEMS(T) );
1486 
1487  int c = p_GetComp(syz_lead, r) - 1;
1488 
1489  assume( c >= 0 && c < IDELEMS(T) );
1490 
1491  if( m_spoly_bucket == NULL )
1492  m_spoly_bucket = kBucketCreate(r);
1493 
1494  SBucketWrapper tail(r, m_sum_bucket_factory);
1495 
1496 
1497  kBucket_pt bucket = m_spoly_bucket; assume( bucket != NULL ); kbTest(bucket); m_spoly_bucket = NULL;
1498 
1499 // kBucketInit(bucket, NULL, 0); // not needed!?
1500 
1501  poly p = leadmonom(syz_lead, r); // :(
1502 // poly spoly = pp_Mult_qq(p, T->m[c], r);
1503  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // TODO: store pLength(T->m[c]) separately!?
1504  p_Delete(&p, r);
1505 
1506  kbTest(bucket);
1507 
1508  c = p_GetComp(syz_2, r) - 1;
1509  assume( c >= 0 && c < IDELEMS(T) );
1510 
1511  p = leadmonom(syz_2, r); // :(
1512 // spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r);
1513  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // pLength(T->m[c])?!
1514  kbTest(bucket);
1515  p_Delete(&p, r);
1516 
1517 // const bool bUsePolynomial = TEST_OPT_NOT_BUCKETS; // || (pLength(spoly) < MIN_LENGTH_BUCKET);
1518 // CPolynomialSummator tail(r, bUsePolynomial);
1519  tail.Add(syz_2, 1);
1520 
1521  kbTest(bucket);
1522  for( poly spoly = kBucketExtractLm(bucket); spoly != NULL; p_LmDelete(&spoly, r), spoly = kBucketExtractLm(bucket))
1523  {
1524  kbTest(bucket);
1525  poly t = m_div.FindReducer(spoly, NULL, m_checker);
1526  p_Test(t, r);
1527 
1528  if( t != NULL )
1529  {
1530  p = leadmonom(t, r); // :(
1531  c = p_GetComp(t, r) - 1;
1532 
1533  assume( c >= 0 && c < IDELEMS(T) );
1534 
1535  if(UNLIKELY( OPT__TREEOUTPUT ))
1536  {
1537  PrintS("{ \"nodelabel\": \""); writeLatexTerm(t, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(spoly, r, false); PrintS("\" },");
1538  }
1539 
1540  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // pLength(T->m[c])?
1541 // spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r);
1542 
1543  p_Delete(&p, r);
1544 
1545  tail.Add(t, 1);
1546  } // otherwise discard that leading term altogether!
1547  else
1548  if( UNLIKELY(OPT__PROT) ) ++ m_stat[4]; // PrintS("$"); // LOT
1549 
1550  kbTest(bucket);
1551  }
1552 
1553  kbTest(bucket);
1554 
1555  // now bucket must be empty!
1556  assume( kBucketClear(bucket) == NULL );
1557 
1558  const poly result = tail.ClearAdd(); // TODO: use Merge with sBucket???
1559 
1560 
1561  if( m_spoly_bucket == NULL )
1562  m_spoly_bucket = bucket;
1563  else
1564  kBucketDestroy(&bucket);
1565 
1566 
1567  if( UNLIKELY(OPT__TREEOUTPUT) )
1568  {
1569  PrintS("]},");
1570  }
1571 
1572 #ifndef SING_NDEBUG
1573  if( OPT__DEBUG )
1574  {
1575  PrintS("SchreyerSyzygyComputation::SchreyerSyzygyNF(syz_lead, poly syz_2) =>>> \n");
1576  dPrint(result, r, r, 0);
1577  PrintLn();
1578  // TODO: Add SyzCheck!!!???
1579  }
1580 #endif
1581 
1582  return result;
1583 }
1584 
1585 // namespace {
1586 
1587 // };
1588 
1589 
1590 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!
1591 
1592 // NOTE: need p_Copy?????? for image + multiplier!!???
1593 // NOTE: better store complete syz. terms!!?
1594 poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, const int tail) const
1595 {
1596 #ifndef SING_NDEBUG
1597  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1598 #endif
1599 
1600  const ring& r = m_rBaseRing;
1601 
1602  assume(m_idTails != NULL && m_idTails->m != NULL);
1603  assume( tail >= 0 && tail < IDELEMS(m_idTails) );
1604 
1605  p_Test(multiplier, r);
1606 
1607  if( UNLIKELY(OPT__NOCACHING) )
1608  return ComputeImage(multiplier, tail);
1609 
1610  // TODO: store (multiplier, tail) -.-^-.-^-.--> !
1611  TCache::iterator top_itr = m_cache.find(tail);
1612 
1613  if ( top_itr != m_cache.end() )
1614  {
1615  assume( top_itr->first == tail );
1616 
1617  TP2PCache& T = top_itr->second;
1618 
1619  TP2PCache::iterator itr = T.find(multiplier);
1620 
1621  if( itr != T.end() ) // Yey - Reuse!!!
1622  {
1623  assume( p_LmEqual(itr->first, multiplier, r) );
1624 
1625  if( itr->second == NULL ) // leadcoeff plays no role if value is NULL!
1626  return (NULL);
1627 
1628  if( UNLIKELY( OPT__TREEOUTPUT ) )
1629  {
1630 // PrintS("{ \"nodelabel\": \""); writeLatexTerm(multiplier, r, false);
1631 // Print(" \\\\GEN{%d}\", \"children\": [ ", tail + 1);
1632  PrintS("{ \"proc\": \"TTLookup\", \"nodelabel\": \"");
1633  writeLatexTerm(itr->first, r, false); Print(" \\\\GEN{%d}\", \"Lookup\": \"", tail + 1);
1634  writeLatexTerm(itr->second, r, true, false);
1635  PrintS("\", ");
1636  }
1637 
1638  poly p = p_Copy(itr->second, r); // COPY!!!
1639 
1640  p_Test(multiplier, r);
1641 
1642  if( !n_Equal( pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf) ) // normalize coeffs!?
1643  {
1644  number n = n_Div( pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf); // new number
1645 
1646  if( UNLIKELY( OPT__TREEOUTPUT ) )
1647  {
1648  StringSetS("");
1649  n_Write(n, r->cf);
1650  char* s = StringEndS();
1651  Print("\"recale\": \"%s\", ", s);
1652  omFree(s);
1653  }
1654 
1655  if( UNLIKELY( OPT__PROT ) ) ++ m_stat[7]; // PrintS("l*"); // lookup & rescale
1656 
1657  p = p_Mult_nn(p, n, r); // !
1658  n_Delete(&n, r->cf);
1659  } else
1660  if( UNLIKELY( OPT__PROT ) ) ++ m_stat[6]; // PrintS("l"); // lookup no rescale
1661 
1662  if( UNLIKELY(OPT__TREEOUTPUT) )
1663  {
1664  PrintS("\"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1665  }
1666 
1667 #ifndef SING_NDEBUG
1668  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1669 #endif
1670  p_Test(multiplier, r);
1671 
1672  return p;
1673  }
1674 
1675 
1676  if( UNLIKELY(OPT__TREEOUTPUT) )
1677  {
1678  Print("{ \"proc\": \"TTStore%d\", \"nodelabel\": \"", tail + 1); writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"children\": [", tail + 1);
1679  }
1680 
1681  p_Test(multiplier, r);
1682 
1683  const poly p = ComputeImage(multiplier, tail);
1684 
1685  if( UNLIKELY(OPT__TREEOUTPUT) )
1686  {
1687  PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1688  }
1689 
1690  if( UNLIKELY(OPT__PROT) ) ++ m_stat[8]; // PrintS("S"); // store
1691 
1692  p_Test(multiplier, r);
1693 
1694  T.insert( TP2PCache::value_type(myp_Head(multiplier, (p==NULL), r), p) ); // T[ multiplier ] = p;
1695 
1696  p_Test(multiplier, r);
1697 
1698 // if( p == NULL )
1699 // return (NULL);
1700 
1701 #ifndef SING_NDEBUG
1702  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1703 #endif
1704 
1705  return p_Copy(p, r);
1706  }
1707 
1708  CCacheCompare o(r); TP2PCache T(o);
1709 
1710  if( UNLIKELY(OPT__TREEOUTPUT) )
1711  {
1712  Print("{ \"proc\": \"TTStore%d\", \"nodelabel\": \"", 0); writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"children\": [", tail + 1);
1713  }
1714 
1715  const poly p = ComputeImage(multiplier, tail);
1716 
1717  if( UNLIKELY(OPT__TREEOUTPUT) )
1718  {
1719  PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1720  }
1721 
1722  if( UNLIKELY( OPT__PROT ) ) ++ m_stat[8]; // PrintS("S"); // store // %d", tail + 1);
1723 
1724  T.insert( TP2PCache::value_type(myp_Head(multiplier, (p==NULL), r), p) );
1725 
1726  m_cache.insert( TCache::value_type(tail, T) );
1727 
1728 // if( p == NULL )
1729 // return (NULL);
1730 
1731 #ifndef SING_NDEBUG
1732  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1733 #endif
1734 
1735  return p_Copy(p, r);
1736 }
1737 
1738 poly SchreyerSyzygyComputation::ComputeImage(poly multiplier, const int tail) const
1739 {
1740  const ring& r = m_rBaseRing;
1741 
1742  assume(m_idTails != NULL && m_idTails->m != NULL);
1743  assume( tail >= 0 && tail < IDELEMS(m_idTails) );
1744 
1745  p_Test(multiplier, r);
1746 
1747  const poly t = m_idTails->m[tail]; // !!!
1748 
1749  if(t != NULL)
1750  {
1751  if( UNLIKELY(OPT__TREEOUTPUT) )
1752  {
1753  PrintS("{ \"proc\": \"ComputeImage\", \"nodelabel\": \"");
1754  writeLatexTerm(multiplier, r, false);
1755  Print(" \\\\GEN{%d}\", \"edgelabel\": \"", tail + 1);
1756  writeLatexTerm(t, r, false);
1757  PrintS("\", \"children\": [");
1758  }
1759 
1760  const poly p = TraverseTail(multiplier, t);
1761 
1762  p_Test(multiplier, r);
1763 
1764  if( UNLIKELY(OPT__TREEOUTPUT) )
1765  {
1766  PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\" },");
1767  }
1768 
1769  return p;
1770 
1771  }
1772 
1773  return NULL;
1774 }
1775 
1776 
1778 {
1779  assume( !OPT__IGNORETAILS );
1780 
1781  const ideal& L = m_idLeads;
1782  const ideal& T = m_idTails;
1783  const ring& r = m_rBaseRing;
1784 
1785  assume( multiplier != NULL );
1786 
1787  assume( L != NULL );
1788  assume( T != NULL );
1789 
1790  p_Test(multiplier, r);
1791 
1792 #ifndef SING_NDEBUG
1793  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1794 #endif
1795 
1796  if( UNLIKELY( !( (!OPT__TAILREDSYZ) || m_lcm.Check(multiplier) )) )
1797  {
1798  if( UNLIKELY(OPT__TAILREDSYZ && OPT__PROT) )
1799  {
1800  ++ m_stat[5]; // PrintS("%"); // check LCM !
1801 #ifndef SING_NDEBUG
1802  if( OPT__DEBUG )
1803  {
1804  PrintS("\nTT,%:"); dPrint(multiplier, r, r, 0);
1805  PrintS(", * :"); dPrint(tail, r, r, 0);
1806  PrintLn();
1807  }
1808 #endif
1809  }
1810  return NULL;
1811  }
1812 
1813  // const bool bUsePolynomial = TEST_OPT_NOT_BUCKETS; // || (pLength(tail) < MIN_LENGTH_BUCKET);
1814 
1815  SBucketWrapper sum(r, m_sum_bucket_factory);
1816 /*
1817  sBucket_pt sum;
1818 
1819  if( m_sum_bucket == NULL )
1820  sum = sBucketCreate(r);
1821  else
1822  {
1823  if( !sIsEmpty(m_sum_bucket) )
1824  sum = sBucketCreate(r);
1825  else
1826  {
1827  sum = m_sum_bucket;
1828  m_sum_bucket = NULL;
1829  }
1830  }
1831 
1832 
1833  assume( sum != NULL ); assume ( sIsEmpty(sum) );
1834  assume( r == sBucketGetRing(sum) );
1835 */
1836 
1837 // poly s; int len;
1838 
1839  // CPolynomialSummator sum(r, bUsePolynomial);
1840  // poly s = NULL;
1841 
1842  if( UNLIKELY( OPT__TREEOUTPUT & 0 ) )
1843  {
1844  Print("{ \"proc\": \"TTPoly\", \"nodelabel\": \""); writeLatexTerm(multiplier, r, false); Print(" * \\\\ldots \", \"children\": [");
1845  }
1846 
1847  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1848  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1849  for(poly p = tail; p != NULL; p = pNext(p)) // iterate over the tail
1850  {
1851  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1852  const poly rt = ReduceTerm(multiplier, p, NULL); // TODO: also return/store length?
1853  sum.Add(rt);
1854  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1855  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1856  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1857 
1858 // const int lp = pLength(rt);
1859 // if( rt != NULL && lp != 0 )
1860 // sBucket_Add_p(sum, rt, lp);
1861  }
1862  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1863  // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1864 
1865 // sBucketClearAdd(sum, &s, &len); // Will Not Clear?!?
1866  const poly s = sum.ClearAdd();
1867 
1868 // assume( sum != NULL ); assume ( sIsEmpty(sum) );
1869 /*
1870  if( m_sum_bucket == NULL )
1871  m_sum_bucket = sum;
1872  else
1873  sBucketDestroy(&sum);
1874 
1875  assume( pLength(s) == len );
1876 */
1877 
1878 #ifndef SING_NDEBUG
1879  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1880 #endif
1881 
1882  if( UNLIKELY( OPT__TREEOUTPUT & 0 ) )
1883  {
1884  PrintS("], \"noderesult\": \""); writeLatexTerm(s, r, true, false); PrintS("\" },");
1885  }
1886 
1887  p_Test(multiplier, r);
1888 
1889  return s;
1890 }
1891 
1892 
1893 
1894 
1895 poly SchreyerSyzygyComputation::ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
1896 {
1897 #ifndef SING_NDEBUG
1898  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1899 #endif
1900 
1901  assume( !OPT__IGNORETAILS );
1902 
1903  const ideal& L = m_idLeads;
1904  const ideal& T = m_idTails;
1905  const ring& r = m_rBaseRing;
1906 
1907  assume( multiplier != NULL );
1908  assume( term4reduction != NULL );
1909 
1910 
1911  assume( L != NULL );
1912  assume( T != NULL );
1913 
1914  p_Test(multiplier, r);
1915 
1916  // simple implementation with FindReducer:
1917  poly s = NULL;
1918 
1919  if( (!OPT__TAILREDSYZ) || m_lcm.Check(multiplier) ) // TODO: UNLIKELY / LIKELY ????
1920  {
1921 #if NOPRODUCT
1922  s = m_div.FindReducer(multiplier, term4reduction, syztermCheck, m_checker); // s ????
1923  p_Test(s, r);
1924 
1925  p_Test(multiplier, r);
1926 
1927  if( s == NULL ) // No Reducer?
1928  {
1929  if( UNLIKELY(OPT__PROT) ) ++ m_stat[4]; // PrintS("$"); // LOT
1930  return NULL;
1931  }
1932 
1933  if( UNLIKELY( OPT__TREEOUTPUT ) )
1934  {
1935  poly product = pp_Mult_mm(multiplier, term4reduction, r);
1936  PrintS("{ \"proc\": \"RdTrmNoP\", \"nodelabel\": \""); writeLatexTerm(s, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(product, r, false);
1937  p_Delete(&product, r);
1938  }
1939 
1940 #else
1941  // NOTE: only LT(term4reduction) should be used in the following:
1942  poly product = pp_Mult_mm(multiplier, term4reduction, r);
1943  p_Test(product, r);
1944 
1945  s = m_div.FindReducer(product, syztermCheck, m_checker); // ??
1946  p_Test(s, r);
1947 
1948  p_Test(multiplier, r);
1949 
1950  if( s == NULL ) // No Reducer?
1951  {
1952  if( UNLIKELY(OPT__PROT) ) ++ m_stat[4]; // PrintS("$"); // LOT
1953  return NULL;
1954  }
1955 
1956  if( UNLIKELY(OPT__TREEOUTPUT) )
1957  {
1958  PrintS("{ \"proc\": \"RdTrmP\", \"nodelabel\": \""); writeLatexTerm(s, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(product, r, false);
1959  }
1960 
1961  p_Delete(&product, r);
1962 #endif
1963  }
1964 
1965 #ifndef SING_NDEBUG
1966  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
1967 #endif
1968 
1969  if( s == NULL ) // No Reducer?
1970  {
1971  if( UNLIKELY( OPT__TAILREDSYZ && OPT__PROT) )
1972  {
1973  ++ m_stat[5]; // PrintS("%"); // check LCM !
1974 #ifndef SING_NDEBUG
1975  if( OPT__DEBUG )
1976  {
1977  PrintS("\n%: RedTail("); dPrint(multiplier, r, r, 0);
1978  PrintS(" * : "); dPrint(term4reduction, r,r,0 );
1979  PrintS(", { "); dPrint(syztermCheck,r,r,0 );
1980  PrintS(" }) "); PrintLn();
1981  }
1982 #endif
1983  }
1984  return NULL;
1985  }
1986 
1987  p_Test(multiplier, r);
1988  p_Test(s, r);
1989 
1990  poly b = leadmonom(s, r);
1991 
1992  p_Test(b, r);
1993 
1994  const int c = p_GetComp(s, r) - 1;
1995  assume( c >= 0 && c < IDELEMS(T) );
1996 
1997 
1998  if( UNLIKELY( OPT__TREEOUTPUT ) )
1999  PrintS("\", \"children\": [");
2000 
2001  const poly t = TraverseTail(b, c); // T->m[c];
2002 
2003  if( UNLIKELY( OPT__TREEOUTPUT ) )
2004  {
2005 
2006  PrintS("], \"noderesult\": \"");
2007  writeLatexTerm(t, r, true, false);
2008  PrintS("\"");
2009 
2010  if( syztermCheck != NULL )
2011  {
2012  PrintS(", \"syztermCheck\":\"" );
2013  writeLatexTerm(syztermCheck, r, true, false);
2014  PrintS("\" },");
2015  } else
2016  PrintS(" },");
2017  }
2018 
2019  p_Test(multiplier, r);
2020 
2021  if( t != NULL )
2022  s = p_Add_q(s, t, r);
2023 
2024 
2025 #ifndef SING_NDEBUG
2026  if( OPT__DEBUG ) { m_div.Verify(); m_checker.Verify(); }
2027 #endif
2028 
2029  p_Test(multiplier, r);
2030 
2031  return s;
2032 }
2033 
2035  OPT__DEBUG( atGetInt(rootRingHdl,"DEBUG", 0) ),
2036  OPT__LEAD2SYZ( atGetInt(rootRingHdl, "LEAD2SYZ", 0) ),
2037  OPT__TAILREDSYZ( atGetInt(rootRingHdl, "TAILREDSYZ", 1) ),
2038  OPT__HYBRIDNF( atGetInt(rootRingHdl, "HYBRIDNF", 0) ),
2039  OPT__IGNORETAILS( atGetInt(rootRingHdl, "IGNORETAILS", 0) ),
2040  OPT__SYZNUMBER( atGetInt(rootRingHdl, "SYZNUMBER", 0) ),
2041  OPT__TREEOUTPUT( atGetInt(rootRingHdl, "TREEOUTPUT", 0) ),
2042  OPT__SYZCHECK( atGetInt(rootRingHdl, "SYZCHECK", 0) ),
2043  OPT__PROT(TEST_OPT_PROT),
2044  OPT__NOCACHING( atGetInt(rootRingHdl, "NOCACHING", 0) ),
2045  m_rBaseRing( rootRingHdl->data.uring )
2046 {
2047 #ifndef SING_NDEBUG
2048  if( OPT__DEBUG & 0 )
2049  {
2050  PrintS("SchreyerSyzygyComputationFlags: \n");
2051  Print(" DEBUG: \t%d\n", OPT__DEBUG);
2052 // Print(" SYZCHECK : \t%d\n", OPT__SYZCHECK);
2053  Print(" LEAD2SYZ: \t%d\n", OPT__LEAD2SYZ);
2054  Print(" TAILREDSYZ: \t%d\n", OPT__TAILREDSYZ);
2055  Print(" IGNORETAILS: \t%d\n", OPT__IGNORETAILS);
2056  Print(" TREEOUTPUT: \t%d\n", OPT__TREEOUTPUT);
2057  Print(" SYZCHECK: \t%d\n", OPT__SYZCHECK);
2058  }
2059 #endif
2060 
2061  // TODO: just current setting!
2062  assume( rootRingHdl == currRingHdl );
2063  assume( rootRingHdl->typ == RING_CMD );
2064  assume( m_rBaseRing == currRing );
2065  // move the global ring here inside???
2066 }
2067 
2068 
2069 
2070 CLeadingTerm::CLeadingTerm(unsigned int _label, const poly _lt, const ring R):
2071  m_sev( p_GetShortExpVector(_lt, R) ), m_label( _label ), m_lt( _lt )
2072 #ifndef SING_NDEBUG
2073  , _R(R), m_lt_copy( myp_Head(_lt, true, R) ) // note that p_LmEqual only tests exponents!
2074 #endif
2075 {
2076 #ifndef SING_NDEBUG
2077  assume( pNext(m_lt_copy) == NULL );
2078 #endif
2079  assume( sev() == p_GetShortExpVector(lt(), R) );
2080 }
2081 
2082 #ifndef SING_NDEBUG
2084 {
2087 
2088  poly p = const_cast<poly>(m_lt_copy);
2089  p_Delete(&p, _R);
2090 }
2091 poly CLeadingTerm::lt() const
2092 {
2095  return m_lt;
2096 }
2097 
2098 unsigned long CLeadingTerm::sev() const
2099 {
2102  return m_sev;
2103 }
2104 
2105 unsigned int CLeadingTerm::label() const
2106 {
2109  return m_label;
2110 }
2111 #endif
2112 
2113 
2114 
2116 {
2117  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++ )
2118  {
2119  const TReducers& v = it->second;
2120  for(TReducers::const_iterator vit = v.begin(); vit != v.end(); vit++ )
2121  delete const_cast<CLeadingTerm*>(*vit);
2122  }
2123 }
2124 
2125 
2126 void CReducerFinder::Initialize(const ideal L)
2127 {
2128  assume( m_L == NULL || m_L == L );
2129  if( m_L == NULL )
2130  m_L = L;
2131 
2132  assume( m_L == L );
2133 
2134  if( L != NULL )
2135  {
2136  const ring& R = m_rBaseRing;
2137  assume( R != NULL );
2138 
2139  for( int k = IDELEMS(L) - 1; k >= 0; k-- )
2140  {
2141  const poly a = L->m[k]; // assume( a != NULL );
2142 
2143  // NOTE: label is k \in 0 ... |L|-1!!!
2144  if( a != NULL )
2145  m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
2146  }
2147  }
2148 }
2149 
2152  m_L(const_cast<ideal>(L)), // for debug anyway
2153  m_hash()
2154 {
2155  assume( flags.m_rBaseRing == m_rBaseRing );
2156  if( L != NULL )
2157  Initialize(L);
2158 }
2159 
2160 /// _p_LmDivisibleByNoComp for a | b*c
2161 static inline BOOLEAN _p_LmDivisibleByNoComp(const poly a, const poly b, const poly c, const ring r)
2162 {
2163  int i=r->VarL_Size - 1;
2164  unsigned long divmask = r->divmask;
2165  unsigned long la, lb;
2166 
2167  if (r->VarL_LowIndex >= 0)
2168  {
2169  i += r->VarL_LowIndex;
2170  do
2171  {
2172  la = a->exp[i];
2173  lb = b->exp[i] + c->exp[i];
2174  if ((la > lb) ||
2175  (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
2176  {
2178  return FALSE;
2179  }
2180  i--;
2181  }
2182  while (i>=r->VarL_LowIndex);
2183  }
2184  else
2185  {
2186  do
2187  {
2188  la = a->exp[r->VarL_Offset[i]];
2189  lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
2190  if ((la > lb) ||
2191  (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
2192  {
2194  return FALSE;
2195  }
2196  i--;
2197  }
2198  while (i>=0);
2199  }
2200 #ifdef HAVE_RINGS
2201  assume( !rField_is_Ring(r) ); // not implemented for rings...!
2202 #endif
2203  return TRUE;
2204 }
2205 
2206 
2207 bool CLeadingTerm::CheckLT( const ideal & L ) const
2208 {
2209 // for( int i = IDELEMS(L); i >= 0; --i) assume( pNext(L->m[i]) == NULL ); // ???
2210  return ( L->m[label()] == lt() );
2211 }
2212 
2213 bool CLeadingTerm::DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const
2214 {
2215  // may have no coeff yet
2216 // assume ( !n_IsZero( p_GetCoeff(product, r), r ) );
2217 
2218  assume ( !n_IsZero( pGetCoeff(lt()), r->cf ) );
2219  assume( sev() == p_GetShortExpVector(lt(), r) );
2220 
2221  assume( product != NULL );
2222  assume( (p_GetComp(lt(), r) == p_GetComp(product, r)) || (p_GetComp(lt(), r) == 0) );
2223 
2224 #ifndef SING_NDEBUG
2225  assume( r == _R );
2226 #endif
2227 
2228 // const int k = label();
2229 // assume( m_L->m[k] == p );
2230 
2231  return p_LmShortDivisibleByNoComp(lt(), sev(), product, not_sev, r);
2232 
2233 }
2234 
2235 #if NOPRODUCT
2236 /// as DivisibilityCheck(multiplier * t, ...) for monomial 'm'
2237 /// and a module term 't'
2238 bool CLeadingTerm::DivisibilityCheck(const poly m, const poly t, const unsigned long not_sev, const ring r) const
2239 {
2240  assume ( !n_IsZero( pGetCoeff(lt()), r->cf ) );
2241  assume( sev() == p_GetShortExpVector(lt(), r) );
2242 
2243  assume( m != NULL );
2244  assume( t != NULL );
2245  assume ( !n_IsZero( pGetCoeff(m), r->cf ) );
2246  assume ( !n_IsZero( pGetCoeff(t), r->cf ) );
2247 
2248 // assume( p_GetComp(m, r) == 0 );
2249  assume( (p_GetComp(lt(), r) == p_GetComp(t, r)) || (p_GetComp(lt(), r) == 0) );
2250 
2251  p_Test(m, r);
2252  p_Test(t, r);
2253 // const int k = label();
2254 // assume( m_L->m[k] == p );
2255 
2256 #ifndef SING_NDEBUG
2257  assume( r == _R );
2258 #endif
2259 
2260  if (sev() & not_sev)
2261  return false;
2262 
2263  return _p_LmDivisibleByNoComp(lt(), m, t, r);
2264 // return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
2265 }
2266 #endif
2267 
2268 
2269 /// TODO:
2271 {
2272  private:
2275  const unsigned long m_not_sev;
2276  const long m_comp;
2277 
2278  CReducerFinder::CReducersHash::const_iterator m_itr;
2279  CReducerFinder::TReducers::const_iterator m_current, m_finish;
2280 
2281  bool m_active;
2282 
2283  public:
2284  CDivisorEnumerator(const CReducerFinder& self, const poly product):
2286  m_reds(self),
2287  m_product(product),
2288  m_not_sev(~p_GetShortExpVector(product, m_rBaseRing)),
2289  m_comp(p_GetComp(product, m_rBaseRing)),
2290  m_itr(), m_current(), m_finish(),
2291  m_active(false)
2292  {
2293  assume( m_comp >= 0 );
2294  assume( m_reds.m_L != NULL ); /// TODO: m_L should stay the same!!!
2295 
2296  assume( product != NULL ); // may have no coeff yet :(
2297 // assume ( !n_IsZero( p_GetCoeff(product, m_rBaseRing), m_rBaseRing ) );
2298 #ifndef SING_NDEBUG
2299  if( OPT__DEBUG ) m_reds.Verify();
2300 #endif
2301  }
2302 
2303  inline bool Reset()
2304  {
2305  m_active = false;
2306 
2307  m_itr = m_reds.m_hash.find(m_comp);
2308 
2309  if( m_itr == m_reds.m_hash.end() )
2310  return false;
2311 
2312  assume( m_itr->first == m_comp );
2313 
2314  m_current = (m_itr->second).begin();
2315  m_finish = (m_itr->second).end();
2316 
2317  if (m_current == m_finish)
2318  return false;
2319 
2320 // m_active = true;
2321  return true;
2322  }
2323 
2324  const CLeadingTerm& Current() const
2325  {
2326  assume( m_active );
2327  assume( m_current != m_finish );
2328 
2329  return *(*m_current);
2330  }
2331 
2332  inline bool MoveNext()
2333  {
2334  assume( m_current != m_finish );
2335 
2336  if( m_active )
2337  ++m_current;
2338  else
2339  m_active = true; // for Current()
2340 
2341  // looking for the next good entry
2342  for( ; m_current != m_finish; ++m_current )
2343  {
2344  assume( Current().CheckLT( m_reds.m_L ) );
2345 
2346  if( Current().DivisibilityCheck(m_product, m_not_sev, m_rBaseRing) )
2347  {
2348 #ifndef SING_NDEBUG
2349  if( OPT__DEBUG )
2350  {
2351  Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().label());
2352  dPrint(Current().lt(), m_rBaseRing, m_rBaseRing, 0);
2353  }
2354 #endif
2355 // m_active = true;
2356  assume( Current().CheckLT( m_reds.m_L ) );
2357  return true;
2358  }
2359  assume( Current().CheckLT( m_reds.m_L ) );
2360  }
2361 
2362  // the end... :(
2363  assume( m_current == m_finish );
2364 
2365  m_active = false;
2366  return false;
2367  }
2368 };
2369 
2370 
2371 
2372 bool CReducerFinder::IsDivisible(const poly product) const
2373 {
2374 #ifndef SING_NDEBUG
2375  if( OPT__DEBUG ) Verify();
2376 #endif
2377 
2378  assume( product != NULL );
2379 
2380  // NOTE: q may have no coeff!!!
2381 
2382  CDivisorEnumerator itr(*this, product);
2383  if( !itr.Reset() )
2384  return false;
2385 
2386  return itr.MoveNext();
2387 
2388 /*
2389  const ring& r = m_rBaseRing;
2390 
2391  const long comp = p_GetComp(product, r);
2392  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
2393 
2394  assume( comp >= 0 );
2395 
2396  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2397 
2398  assume( m_L != NULL );
2399 
2400  if( it == m_hash.end() )
2401  return false;
2402  // assume comp!
2403 
2404  const TReducers& reducers = it->second;
2405 
2406  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2407  {
2408  assume( (*vit)->CheckLT( m_L ) );
2409 
2410  if( (*vit)->DivisibilityCheck(product, not_sev, r) )
2411  {
2412  if( OPT__DEBUG )
2413  {
2414  Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + (*vit)->label());
2415  dPrint((*vit)->lt(), r, r, 0);
2416  }
2417 
2418  return true;
2419  }
2420  }
2421 
2422  return false;
2423 */
2424 }
2425 
2426 
2427 #ifndef SING_NDEBUG
2428 void CReducerFinder::Verify() const
2429 {
2430  const ring& r = m_rBaseRing;
2431 
2432  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
2433  {
2434  const TReducers& reducers = it->second;
2435 
2436  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2437  {
2438  assume( (*vit)->CheckLT( m_L ) );
2439 
2440  const poly p = (*vit)->lt();
2441 
2442  const unsigned long p_sev = (*vit)->sev();
2443  assume( p_sev == p_GetShortExpVector(p, r) );
2444 
2445  assume( p_GetComp(p, r) == it->first );
2446 
2447  const int k = (*vit)->label();
2448  assume( m_L->m[k] == p );
2449 
2450  pp_Test(p, r, r);
2451  }
2452  }
2453 }
2454 
2455 
2456 
2457 void CReducerFinder::DebugPrint() const
2458 {
2459  const ring& r = m_rBaseRing;
2460 
2461  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
2462  {
2463  Print("Hash Key: %ld, Values: \n", it->first);
2464  const TReducers& reducers = it->second;
2465 
2466  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2467  {
2468  assume( (*vit)->CheckLT( m_L ) );
2469 
2470  const int k = (*vit)->label();
2471  const poly p = (*vit)->lt();
2472 
2473  pp_Test(p, r, r);
2474 
2475  assume( m_L->m[k] == p );
2476 
2477  const unsigned long p_sev = (*vit)->sev();
2478  assume( p_sev == p_GetShortExpVector(p, r) );
2479 
2480  assume( p_GetComp(p, r) == it->first );
2481 
2482  Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %ld\n", p_sev);
2483 
2484  assume( m_L->m[k] == p );
2485  }
2486  }
2487 }
2488 #endif
2489 
2490 #if NOPRODUCT
2491 
2492 /// TODO:
2494 {
2495  private:
2497  const poly m_multiplier, m_term;
2498  const unsigned long m_not_sev;
2499  const long m_comp;
2500 
2501  CReducerFinder::CReducersHash::const_iterator m_itr;
2502  CReducerFinder::TReducers::const_iterator m_current, m_finish;
2503 
2504  bool m_active;
2505 
2506  public:
2507  CDivisorEnumerator2(const CReducerFinder& self, const poly m, const poly t):
2509  m_reds(self),
2510  m_multiplier(m), m_term(t),
2511  m_not_sev(~p_GetShortExpVector(m, t, m_rBaseRing)),
2512  m_comp(p_GetComp(t, m_rBaseRing)),
2513  m_itr(), m_current(), m_finish(),
2514  m_active(false)
2515  {
2516  assume( m_comp >= 0 );
2517  assume( m_reds.m_L != NULL );
2518  assume( m_multiplier != NULL );
2519  assume( m_term != NULL );
2520 
2521  assume( m != NULL );
2522  assume( t != NULL );
2523  assume ( !n_IsZero( pGetCoeff(m), m_rBaseRing->cf ) );
2524  assume ( !n_IsZero( pGetCoeff(t), m_rBaseRing->cf ) );
2525 
2526  p_Test(m, m_rBaseRing);
2527 
2528 // assume( p_GetComp(m_multiplier, m_rBaseRing) == 0 );
2529 #ifndef SING_NDEBUG
2530  if( OPT__DEBUG ) m_reds.Verify();
2531 #endif
2532  }
2533 
2534  inline bool Reset()
2535  {
2536  m_active = false;
2537 
2538  m_itr = m_reds.m_hash.find(m_comp);
2539 
2540  if( m_itr == m_reds.m_hash.end() )
2541  return false;
2542 
2543  assume( m_itr->first == m_comp );
2544 
2545  m_current = (m_itr->second).begin();
2546  m_finish = (m_itr->second).end();
2547 
2548  if (m_current == m_finish)
2549  return false;
2550 
2551  return true;
2552  }
2553 
2554  const CLeadingTerm& Current() const
2555  {
2556  assume( m_active );
2557  assume( m_current != m_finish );
2558 
2559  return *(*m_current);
2560  }
2561 
2562  inline bool MoveNext()
2563  {
2564  assume( m_current != m_finish );
2565 
2566  if( m_active )
2567  ++m_current;
2568  else
2569  m_active = true;
2570 
2571 
2572  // looking for the next good entry
2573  for( ; m_current != m_finish; ++m_current )
2574  {
2575  assume( Current().CheckLT( m_reds.m_L ) );
2576 
2577  if( Current().DivisibilityCheck(m_multiplier, m_term, m_not_sev, m_rBaseRing) )
2578  {
2579 #ifndef SING_NDEBUG
2580  if( OPT__DEBUG )
2581  {
2582  Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().label());
2583  dPrint(Current().lt(), m_rBaseRing, m_rBaseRing, 0);
2584  }
2585 #endif
2586 // m_active = true;
2587  assume( Current().CheckLT( m_reds.m_L ) );
2588  return true;
2589 
2590  }
2591  assume( Current().CheckLT( m_reds.m_L ) );
2592  }
2593 
2594  // the end... :(
2595  assume( m_current == m_finish );
2596 
2597  m_active = false;
2598  return false;
2599  }
2600 };
2601 
2602 poly CReducerFinder::FindReducer(const poly multiplier, const poly t,
2603  const poly syzterm,
2604  const CReducerFinder& syz_checker) const
2605 {
2606  const ring& r = m_rBaseRing;
2607 
2608 #ifndef SING_NDEBUG
2609  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2610 #endif
2611 
2612  p_Test(multiplier, r);
2613 
2614  CDivisorEnumerator2 itr(*this, multiplier, t);
2615  if( !itr.Reset() )
2616  return NULL;
2617 
2618  // don't care about the module component of multiplier (as it may be the syzygy term)
2619  // product = multiplier * t?
2620 
2621  assume( multiplier != NULL ); assume( t != NULL );
2622 
2623  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
2624 
2625  long c = 0;
2626 
2627  if (syzterm != NULL)
2628  c = p_GetComp(syzterm, r) - 1;
2629 
2630  assume( c >= 0 && c < IDELEMS(L) );
2631 
2632  p_Test(multiplier, r);
2633 
2634  if (UNLIKELY( OPT__DEBUG && (syzterm != NULL) ))
2635  {
2636  const poly m = L->m[c]; assume( m != NULL ); assume( pNext(m) == NULL );
2637 
2638  // def @@c = leadcomp(syzterm); int @@r = int(@@c);
2639  // def @@product = leadmonomial(syzterm) * L[@@r];
2640  poly lm = p_Mult_mm( leadmonom(syzterm, r, true), m, r); // !NC :(
2641  poly pr = p_Mult_q( leadmonom(multiplier, r, true), leadmonom(t, r, false), r); // !NC :(
2642 
2643  assume( p_EqualPolys(lm, pr, r) );
2644 
2645  p_Delete(&lm, r);
2646  p_Delete(&pr, r);
2647  }
2648 
2649 #ifndef SING_NDEBUG
2650  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2651 #endif
2652 
2653  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2654 
2655 // const poly q = p_One(r);
2656  const poly q = p_New(r); pNext(q) = NULL;
2657 
2658  if( UNLIKELY(OPT__DEBUG) )
2659  p_SetCoeff0(q, 0, r); // for printing q
2660 
2661  assume( pNext(q) == NULL );
2662 
2663  p_Test(multiplier, r);
2664  while( itr.MoveNext() )
2665  {
2666  assume( itr.Current().CheckLT( L ) ); // ???
2667 
2668  const poly p = itr.Current().lt(); // ???
2669  const int k = itr.Current().label();
2670 
2671  p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t // TODO: do it once?
2672  p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
2673 
2674  p_SetComp(q, k + 1, r);
2675  p_Setm(q, r);
2676 
2677  p_Test(multiplier, r);
2678 
2679  // cannot allow something like: a*gen(i) - a*gen(i)
2680  if (syzterm != NULL && (k == c))
2681  if (p_ExpVectorEqual(syzterm, q, r))
2682  {
2683 #ifndef SING_NDEBUG
2684  if( OPT__DEBUG )
2685  {
2686  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2687  dPrint(syzterm, r, r, 0);
2688  }
2689 #endif
2690  assume( itr.Current().CheckLT( L ) ); // ???
2691  continue;
2692  }
2693 
2694  // while the complement (the fraction) is not reducible by leading syzygies
2695  if( to_check && syz_checker.IsDivisible(q) )
2696  {
2697 #ifndef SING_NDEBUG
2698  if( OPT__DEBUG )
2699  {
2700  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2701  }
2702 #endif
2703  assume( itr.Current().CheckLT( L ) ); // ???
2704  continue;
2705  }
2706 
2707  number n = n_Mult( pGetCoeff(multiplier), pGetCoeff(t), r->cf);
2708 
2709 #if NODIVISION
2710  // we assume all leading coeffs to be 1!
2711  assume( n_IsOne(pGetCoeff(p), r->cf) );
2712 #else
2713  if( !n_IsOne( pGetCoeff(p), r ) )
2714  n = n_Div(n, pGetCoeff(p), r->cf);
2715 #endif
2716 
2717  p_SetCoeff0(q, n_InpNeg(n, r->cf), r);
2718 // n_Delete(&n, r);
2719 
2720 #ifndef SING_NDEBUG
2721  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2722 #endif
2723  p_Test(multiplier, r);
2724  p_Test(q, r);
2725 
2726  assume( itr.Current().CheckLT( L ) ); // ???
2727  return q;
2728  }
2729 
2730 /*
2731  const long comp = p_GetComp(t, r); assume( comp >= 0 );
2732  const unsigned long not_sev = ~p_GetShortExpVector(multiplier, t, r); // !
2733 
2734 // for( int k = IDELEMS(L)-1; k>= 0; k-- )
2735 // {
2736 // const poly p = L->m[k];
2737 //
2738 // if ( p_GetComp(p, r) != comp )
2739 // continue;
2740 //
2741 // const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
2742 
2743  // looking for an appropriate diviser p = L[k]...
2744  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2745 
2746  if( it == m_hash.end() )
2747  return NULL;
2748 
2749  // assume comp!
2750 
2751  assume( m_L != NULL );
2752 
2753  const TReducers& reducers = it->second;
2754 
2755  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2756  {
2757 
2758  const poly p = (*vit)->lt(); // ??
2759  const int k = (*vit)->label();
2760 
2761  assume( L->m[k] == p ); // CheckLT
2762 
2763 // const unsigned long p_sev = (*vit)->sev();
2764 // assume( p_sev == p_GetShortExpVector(p, r) );
2765 
2766 // if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2767 // continue;
2768 
2769  if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
2770  continue;
2771 
2772 
2773 // if (p_sev & not_sev) continue;
2774 // if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;
2775 
2776 
2777  p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t
2778  p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
2779 
2780  p_SetComp(q, k + 1, r);
2781  p_Setm(q, r);
2782 
2783  // cannot allow something like: a*gen(i) - a*gen(i)
2784  if (syzterm != NULL && (k == c))
2785  if (p_ExpVectorEqual(syzterm, q, r))
2786  {
2787  if( OPT__DEBUG )
2788  {
2789  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2790  dPrint(syzterm, r, r, 0);
2791  }
2792 
2793  continue;
2794  }
2795 
2796  // while the complement (the fraction) is not reducible by leading syzygies
2797  if( to_check && syz_checker.IsDivisible(q) )
2798  {
2799  if( OPT__DEBUG )
2800  {
2801  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2802  }
2803 
2804  continue;
2805  }
2806 
2807  number n = n_Mult( p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
2808  p_SetCoeff0(q, n_InpNeg( n_Div(n, p_GetCoeff(p, r), r), r), r);
2809  n_Delete(&n, r);
2810 
2811  return q;
2812  }
2813 */
2814 
2815  p_LmFree(q, r);
2816 
2817 #ifndef SING_NDEBUG
2818  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2819 #endif
2820 
2821  p_Test(multiplier, r);
2822 
2823  return NULL;
2824 
2825 }
2826 #endif
2827 
2828 
2829 poly CReducerFinder::FindReducer(const poly product, const poly syzterm, const CReducerFinder& syz_checker) const
2830 {
2831 
2832 #ifndef SING_NDEBUG
2833  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2834 #endif
2835 
2836  CDivisorEnumerator itr(*this, product);
2837  if( !itr.Reset() )
2838  return NULL;
2839 
2840 
2841 
2842  const ring& r = m_rBaseRing;
2843 
2844  assume( product != NULL );
2845 
2846  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
2847 
2848  long c = 0;
2849 
2850  if (syzterm != NULL)
2851  c = p_GetComp(syzterm, r) - 1;
2852 
2853  assume( c >= 0 && c < IDELEMS(L) );
2854 
2855  if (UNLIKELY( OPT__DEBUG && (syzterm != NULL) ))
2856  {
2857  const poly m = L->m[c];
2858 
2859  assume( m != NULL ); assume( pNext(m) == NULL );
2860 
2861  poly lm = p_Mult_mm(leadmonom(syzterm, r), m, r);
2862  assume( p_EqualPolys(lm, product, r) );
2863 
2864  // def @@c = leadcomp(syzterm); int @@r = int(@@c);
2865  // def @@product = leadmonomial(syzterm) * L[@@r];
2866 
2867  p_Delete(&lm, r);
2868  }
2869 
2870 #ifndef SING_NDEBUG
2871  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2872 #endif
2873 
2874  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2875 
2876  const poly q = p_New(r); pNext(q) = NULL;
2877 
2878  if( UNLIKELY(OPT__DEBUG) )
2879  p_SetCoeff0(q, 0, r); // ONLY for printing q
2880 
2881  while( itr.MoveNext() )
2882  {
2883  assume( itr.Current().CheckLT( L ) ); // ???
2884 
2885  const poly p = itr.Current().lt(); // ??
2886  const int k = itr.Current().label();
2887 
2888  p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2889  p_SetComp(q, k + 1, r);
2890  p_Setm(q, r);
2891 
2892  // cannot allow something like: a*gen(i) - a*gen(i)
2893  if (syzterm != NULL && (k == c))
2894  if (p_ExpVectorEqual(syzterm, q, r))
2895  {
2896 #ifndef SING_NDEBUG
2897  if( OPT__DEBUG )
2898  {
2899  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2900  dPrint(syzterm, r, r, 0);
2901  }
2902 #endif
2903  assume( itr.Current().CheckLT( L ) ); // ???
2904  continue;
2905  }
2906 
2907  // while the complement (the fraction) is not reducible by leading syzygies
2908  if( to_check && syz_checker.IsDivisible(q) ) // ?????
2909  {
2910 #ifndef SING_NDEBUG
2911  if( OPT__DEBUG )
2912  {
2913  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2914  }
2915 #endif
2916  assume( itr.Current().CheckLT( L ) ); // ???
2917  continue;
2918  }
2919 
2920 
2921 #if NODIVISION
2922  assume( n_IsOne(p_GetCoeff(p, r), r->cf) );
2923  p_SetCoeff0(q, n_InpNeg( n_Copy(pGetCoeff(product), r->cf), r->cf), r);
2924 #else
2925  p_SetCoeff0(q, n_InpNeg( n_Div( pGetCoeff(product), p_GetCoeff(p), r->cf), r->cf), r);
2926 #endif
2927 
2928  assume( itr.Current().CheckLT( L ) ); // ???
2929 
2930 #ifndef SING_NDEBUG
2931  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
2932 #endif
2933 
2934  return q;
2935  }
2936 
2937 
2938 
2939 /*
2940  const long comp = p_GetComp(product, r);
2941  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
2942 
2943  assume( comp >= 0 );
2944 
2945 // for( int k = IDELEMS(L)-1; k>= 0; k-- )
2946 // {
2947 // const poly p = L->m[k];
2948 //
2949 // if ( p_GetComp(p, r) != comp )
2950 // continue;
2951 //
2952 // const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
2953 
2954  // looking for an appropriate diviser p = L[k]...
2955  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2956 
2957  if( it == m_hash.end() )
2958  return NULL;
2959 
2960  assume( m_L != NULL );
2961 
2962  const TReducers& reducers = it->second;
2963 
2964  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2965 
2966  const poly q = p_New(r); pNext(q) = NULL;
2967 
2968  if( OPT__DEBUG )
2969  p_SetCoeff0(q, 0, r); // for printing q
2970 
2971  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2972  {
2973  const poly p = (*vit)->lt(); // ???
2974 
2975  assume( p_GetComp(p, r) == comp );
2976 
2977  const int k = (*vit)->label();
2978 
2979  assume( L->m[k] == p ); // CheckLT
2980 
2981  const unsigned long p_sev = (*vit)->sev();
2982 
2983  assume( p_sev == p_GetShortExpVector(p, r) );
2984 
2985  if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2986  continue;
2987 
2988 // // ... which divides the product, looking for the _1st_ appropriate one!
2989 // if( !p_LmDivisibleByNoComp(p, product, r) ) // included inside p_LmShortDivisibleBy!
2990 // continue;
2991 
2992  p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2993  p_SetComp(q, k + 1, r);
2994  p_Setm(q, r);
2995 
2996  // cannot allow something like: a*gen(i) - a*gen(i)
2997  if (syzterm != NULL && (k == c))
2998  if (p_ExpVectorEqual(syzterm, q, r))
2999  {
3000  if( OPT__DEBUG )
3001  {
3002  PrintS("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
3003  dPrint(syzterm, r, r, 0);
3004  }
3005 
3006  continue;
3007  }
3008 
3009  // while the complement (the fraction) is not reducible by leading syzygies
3010  if( to_check && syz_checker.IsDivisible(q) )
3011  {
3012  if( OPT__DEBUG )
3013  {
3014  PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
3015  }
3016 
3017  continue;
3018  }
3019 
3020  p_SetCoeff0(q, n_InpNeg( n_Div( p_GetCoeff(product, r), p_GetCoeff(p, r), r), r), r);
3021  return q;
3022  }
3023 */
3024 
3025  p_LmFree(q, r);
3026 
3027 #ifndef SING_NDEBUG
3028  if( OPT__DEBUG ) { Verify(); syz_checker.Verify(); }
3029 #endif
3030 
3031  return NULL;
3032 }
3033 
3034 
3035 
3037  SchreyerSyzygyComputationFlags(flags), std::vector<bool>(),
3038  m_compute(false), m_N(rVar(flags.m_rBaseRing))
3039 {
3040  const ring& R = m_rBaseRing;
3041  assume( flags.m_rBaseRing == R );
3042  assume( R != NULL );
3043 
3044  assume( L != NULL );
3045 
3046  if( LIKELY( OPT__TAILREDSYZ && !OPT__HYBRIDNF && (L != NULL) )) // TODO: not hybrid!?
3047  {
3048  const int l = IDELEMS(L);
3049 
3050  assume( l > 0 );
3051 
3052  resize(l, false);
3053 
3054  for( int k = l - 1; k >= 0; k-- )
3055  {
3056  const poly a = L->m[k]; assume( a != NULL );
3057 
3058  for (unsigned int j = m_N; j > 0; j--)
3059  if ( !(*this)[j] )
3060  (*this)[j] = (p_GetExp(a, j, R) > 0);
3061  }
3062 
3063  m_compute = true;
3064  }
3065 }
3066 
3067 
3068 bool CLCM::Check(const poly m) const
3069 {
3070  assume( m != NULL );
3071  if( m_compute && (m != NULL))
3072  {
3073  const ring& R = m_rBaseRing;
3074 
3076 
3077  for (unsigned int j = m_N; j > 0; j--)
3078  if ( (*this)[j] )
3079  if(p_GetExp(m, j, R) > 0)
3080  return true;
3081 
3082  return false;
3083 
3084  } else return true;
3085 }
3086 
3088 
3089 
3090 template class std::vector<bool>;
3091 template class std::vector<CLeadingTerm const*>;
3092 template class std::map< CReducerFinder::TComponentKey, CReducerFinder::TReducers >;
3093 
3094 template class std::map<TCacheKey, TCacheValue, struct CCacheCompare>;
3095 template class std::map<int, TP2PCache>;
3096 
3097 template class std::stack <sBucket_pt>;
3098 
3100 
3101 
3102 // 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:189
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:2498
const unsigned int m_label
index in the main L[] + 1
Definition: syzextra.h:290
#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:254
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:36
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:2496
const CLeadingTerm & Current() const
Definition: syzextra.cc:2324
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:2499
#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:1419
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:214
const int OPT__SYZCHECK
CheckSyzygyProperty: TODO.
Definition: syzextra.h:232
int getRTimer()
Definition: timer.cc:172
#define FALSE
Definition: auxiliary.h:95
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 bool _IsBucketEmpty(const Bucket &bt)
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:968
poly lt() const
static ring _GetBucketRing(const Bucket &bt)
get bucket ring
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:292
CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags &flags)
goes over all leading terms
Definition: syzextra.cc:2150
BOOLEAN p_DebugLmDivisibleByNoComp(poly a, poly b, ring r)
Definition: pDebug.cc:140
std::vector< const CLeadingTerm * > TReducers
Definition: syzextra.h:317
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:2274
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:580
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:99
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:329
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:2507
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:2602
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
CDivisorEnumerator(const CReducerFinder &self, const poly product)
Definition: syzextra.cc:2284
#define SI_SAVE_OPT1(A)
Definition: options.h:20
void PrintStats() const
print statistics about the used heuristics
Definition: syzextra.cc:767
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
const poly m_term
Definition: syzextra.cc:2497
#define UNLIKELY(expression)
Definition: tgb_internal.h:838
char * StringEndS()
Definition: reporter.cc:151
const poly m_lt_copy
original copy of LEAD(lt) (only for debug!!!)
Definition: syzextra.h:297
#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:2501
#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:103
ideal Compute2LeadingSyzygyTerms()
leading + second terms
Definition: syzextra.cc:886
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:1895
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:210
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:57
#define pIter(p)
Definition: monomials.h:44
#define SING_NDEBUG
Definition: factoryconf.h:260
CReducersHash m_hash
Definition: syzextra.h:356
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:1145
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:1036
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
void Verify() const
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
void DebugPrint() const
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:3036
bool my_p_LmCmp(poly a, poly b, const ring r)
Definition: syzextra.cc:1590
#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:2207
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:2238
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:2279
poly TraverseTail(poly multiplier, const int tail) const
High level caching function!!!
Definition: syzextra.cc:1594
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:684
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:1371
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:778
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:565
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:2126
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:2273
const unsigned int m_N
number of ring variables
Definition: syzextra.h:256
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
const unsigned long m_sev
not short exp. vector
Definition: syzextra.h:287
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:4320
#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:3068
const CLeadingTerm & Current() const
Definition: syzextra.cc:2554
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:4588
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:2161
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:135
p_LmTest(a, r)
sBucket Factory
Definition: syzextra.h:74
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477
#define NULL
Definition: omList.c:10
#define FROM_NAMESPACE(a, s)
const ring _R
Definition: syzextra.h:295
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:2275
SchreyerSyzygyComputationFlags(idhdl rootRingHdl)
Definition: syzextra.cc:2034
BEGIN_NAMESPACE_SINGULARXX const ring const bool bSetZeroComp
Definition: syzextra.h:47
const int OPT__TREEOUTPUT
output lifting tree
Definition: syzextra.h:229
const CanonicalForm & w
Definition: facAbsFact.cc:55
poly ComputeImage(poly multiplier, const int tail) const
low level computation...
Definition: syzextra.cc:1738
#define END_NAMESPACE
Base::value_type Bucket
Definition: syzextra.h:83
const ring m_rBaseRing
global base ring
Definition: syzextra.h:241
void putBucket(const Bucket &bt, const bool replace=false)
Definition: syzextra.h:135
#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:354
#define p_GetCoeff(p, r)
Definition: monomials.h:57
unsigned int label() const
CReducerFinder::CReducersHash::const_iterator m_itr
Definition: syzextra.cc:2278
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:2372
const int OPT__IGNORETAILS
ignore tails and compute the pure Schreyer frame
Definition: syzextra.h:218
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:2502
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:4334
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:86
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:589
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:2276
bool IsNonempty() const
Definition: syzextra.h:343
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