syzextra.h
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.h
6  *
7  * Computation of Syzygies
8  *
9  * ABSTRACT: Computation of Syzygies due to Schreyer
10  *
11  * @author Oleksandr Motsak
12  *
13  **/
14 /*****************************************************************************/
15 
16 #ifndef SYZEXTRA_H
17 #define SYZEXTRA_H
18 
19 #include <vector>
20 #include <map>
21 #include <string.h>
22 #include <stack>
23 
24 // include basic definitions
25 #include "singularxx_defs.h"
26 
27 struct spolyrec; typedef struct spolyrec polyrec; typedef polyrec* poly;
28 struct ip_sring; typedef struct ip_sring* ring; typedef struct ip_sring const* const_ring;
29 
30 struct sip_sideal; typedef struct sip_sideal * ideal;
31 class idrec; typedef idrec * idhdl;
32 
33 class kBucket; typedef kBucket* kBucket_pt;
34 
35 #ifndef NOPRODUCT
36 # define NOPRODUCT 1
37 #endif
38 
39 // set to 1 if all leading coeffs are assumed to be all =1...
40 // note the use of simplify on input in SSinit!
41 #ifndef NODIVISION
42 # define NODIVISION 1
43 #endif
44 
46 
48 
49 /// return the tail of a given polynomial or vector
50 /// returns NULL if input is NULL, otherwise
51 /// the result is a new polynomial/vector in the ring r
52 poly p_Tail(const poly p, const ring r);
53 
54 
55 /// return the tail of a given ideal or module
56 /// returns NULL if input is NULL, otherwise
57 /// the result is a new ideal/module in the ring r
58 /// NOTE: the resulting rank is autocorrected
59 ideal id_Tail(const ideal id, const ring r);
60 
61 /// inplace sorting of the module (ideal) id wrt <_(c,ds)
62 void Sort_c_ds(const ideal id, const ring r);
63 
64 
65 class sBucket; typedef sBucket* sBucket_pt;
66 
67 /** @class SBucketFactory syzextra.h
68  *
69  * sBucket Factory
70  *
71  * Cleate/store/reuse buckets
72  *
73  */
74 class SBucketFactory: private std::stack <sBucket_pt>
75 {
76  private:
77  typedef std::stack <sBucket_pt> Base;
78 // typedef std::vector<Bucket> Memory;
79 // typedef std::deque <Bucket> Memory;
80 // typedef std::stack <Bucket, Memory > Base;
81 
82  public:
83  typedef Base::value_type Bucket;
84 
85  SBucketFactory(const ring r)
86 #ifndef SING_NDEBUG
87  : m_ring(r)
88 #endif
89  {
90  push ( _CreateBucket(r) ); // start with at least one sBucket...?
91  assume( top() != NULL );
92  };
93 
95  {
96  while( !empty() )
97  {
98  _DestroyBucket( top() );
99  pop();
100  }
101  }
102 
103  Bucket getBucket(const ring r, const bool remove = true)
104  {
105  assume( r == m_ring );
106 
107  Bucket bt = NULL;
108 
109  if( !empty() )
110  {
111  bt = top();
112 
113  if( remove )
114  pop();
115  }
116  else
117  {
118  bt = _CreateBucket(r);
119 
120  if( !remove )
121  {
122  push(bt);
123  assume( bt == top() );
124  }
125  }
126 
127  assume( bt != NULL );
128  assume( _IsBucketEmpty(bt) );
129  assume( r == _GetBucketRing(bt) );
130 
131  return bt;
132  }
133 
134  // TODO: this may be spared if we give-out a smart Bucket (which returns here upon its destructor!)
135  void putBucket(const Bucket & bt, const bool replace = false)
136  {
137  assume( bt != NULL );
138  assume( _IsBucketEmpty(bt) );
139  assume( m_ring == _GetBucketRing(bt) );
140 
141  if( empty() )
142  push( bt );
143  else
144  {
145  if( replace )
146  top() = bt;
147  else
148  {
149  if( bt != top() )
150  push( bt );
151  }
152  }
153 
154  assume( bt == top() );
155  }
156 
157  private:
158 
159 #ifndef SING_NDEBUG
160  const ring m_ring; ///< For debugging: all buckets are over the same ring... right?!
161 
162  /// get bucket ring
163  static ring _GetBucketRing(const Bucket& bt);
164 
165  static bool _IsBucketEmpty(const Bucket& bt);
166 #endif
167 
168  /// inital allocation for new buckets
169  static Bucket _CreateBucket(const ring r);
170 
171  /// we only expect empty buckets to be left at the end for destructor
172  /// bt will be set to NULL
173  static void _DestroyBucket(Bucket & bt);
174 
175  private:
176  SBucketFactory();
178  void operator=(const SBucketFactory&);
179 
180 };
181 
182 
183 
184 
185 
186 
187 
188 /// Computation attribute storage
190 {
192 
194  OPT__DEBUG(attr.OPT__DEBUG),
201  {}
202 
203  /// output all the intermediate states
204  const int OPT__DEBUG; // DebugOutput;
205 
206  /// ?
207  const int OPT__LEAD2SYZ; // TwoLeadingSyzygyTerms;
208 
209  /// Reduce syzygy tails wrt the leading syzygy terms
210  const int OPT__TAILREDSYZ; // TailReducedSyzygies;
211 
212  /// Use the usual NF's S-poly reduction while dropping lower order terms
213  /// 2 means - smart selection!
214  const int OPT__HYBRIDNF; // UseHybridNF
215 
216 
217  /// ignore tails and compute the pure Schreyer frame
218  const int OPT__IGNORETAILS; // @IGNORETAILS
219 
220  /// Syzygy level (within a resolution)
221  mutable int OPT__SYZNUMBER;
222 
223  inline void nextSyzygyLayer() const
224  {
225  OPT__SYZNUMBER++;
226  }
227 
228  /// output lifting tree
229  const int OPT__TREEOUTPUT;
230 
231  /// CheckSyzygyProperty: TODO
232  const int OPT__SYZCHECK;
233 
234  /// TEST_OPT_PROT
235  const bool OPT__PROT;
236 
237  /// no caching/stores/lookups
238  const int OPT__NOCACHING;
239 
240  /// global base ring
241  const ring m_rBaseRing;
242 };
243 
245 
246 class CLCM: public SchreyerSyzygyComputationFlags, public std::vector<bool>
247 {
248  public:
249  CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags);
250 
251  bool Check(const poly m) const;
252 
253  private:
254  bool m_compute;
255 
256  const unsigned int m_N; ///< number of ring variables
257 };
258 
259 
261 {
262  public:
263  CLeadingTerm(unsigned int label, const poly lt, const ring);
264 
265 #ifndef SING_NDEBUG
266  ~CLeadingTerm();
267 #endif
268 
269 #if NOPRODUCT
270  bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const;
271 #endif
272  bool DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const;
273 
274  bool CheckLT( const ideal & L ) const;
275 
276 #ifndef SING_NDEBUG
277  poly lt() const;
278  unsigned long sev() const;
279  unsigned int label() const;
280 #else
281  inline poly lt() const { return m_lt; };
282  inline unsigned long sev() const { return m_sev; };
283  inline unsigned int label() const { return m_label; };
284 #endif
285 
286  private:
287  const unsigned long m_sev; ///< not short exp. vector
288 
289  // NOTE/TODO: either of the following should be enough:
290  const unsigned int m_label; ///< index in the main L[] + 1
291 
292  const poly m_lt; ///< the leading term itself L[label-1]
293 
294 #ifndef SING_NDEBUG
295  const ring _R;
296 
297  const poly m_lt_copy; ///< original copy of LEAD(lt) (only for debug!!!)
298 #endif
299 
300  // disable the following:
301  CLeadingTerm();
302  CLeadingTerm(const CLeadingTerm&);
303  void operator=(const CLeadingTerm&);
304 };
305 
306 
307 // TODO: needs a specialized variant without a component (hash!)
309 {
310 #if NOPRODUCT
311  friend class CDivisorEnumerator2;
312 #endif
313  friend class CDivisorEnumerator;
314 
315  public:
316  typedef long TComponentKey;
317  typedef std::vector<const CLeadingTerm*> TReducers;
318 
319  private:
320  typedef std::map< TComponentKey, TReducers> CReducersHash;
321 
322  public:
323  /// goes over all leading terms
324  CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags);
325 
326  void Initialize(const ideal L);
327 
328  ~CReducerFinder();
329 
330 
331 #if NOPRODUCT
332  poly
333  FindReducer(const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder& checker) const;
334 
335 #endif
336  // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
337  poly // const_iterator // TODO: return const_iterator it, s.th: it->m_lt is the needed
338  FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
339 
340  bool IsDivisible(const poly q) const;
341 
342 
343  inline bool IsNonempty() const { return !m_hash.empty(); }
344 
345  /// is the term to be "preprocessed" as lower order term or lead to only reducible syzygies...
346  int PreProcessTerm(const poly t, CReducerFinder& syzChecker) const;
347 
348 #ifndef SING_NDEBUG
349  void DebugPrint() const;
350  void Verify() const;
351 #endif
352 
353  private:
354  ideal m_L; ///< only for debug
355 
356  CReducersHash m_hash; // can also be replaced with a vector indexed by components
357 
358  private:
360  void operator=(const CReducerFinder&);
361 };
362 
363 extern ideal id_Copy (const ideal, const ring);
364 bool my_p_LmCmp (poly, poly, const ring);
365 
366 typedef poly TCacheKey;
368 
370 {
371  const ring & m_ring;
372 
373  CCacheCompare();
374 
375  CCacheCompare(const ring& r): m_ring(r) { assume(r != NULL); }
376 
377  CCacheCompare(const CCacheCompare& lhs): m_ring(lhs.m_ring) { assume(m_ring != NULL); }
378  CCacheCompare& operator=(const CCacheCompare& lhs) { assume(lhs.m_ring != NULL); return (const_cast<CCacheCompare&>(lhs)); }
379 
380  inline bool operator() (const TCacheKey& l, const TCacheKey& r) const { assume(m_ring != NULL); return my_p_LmCmp(l, r, m_ring); }
381 };
382 
383 typedef std::map<TCacheKey, TCacheValue, CCacheCompare> TP2PCache; // deallocation??? !!!
384 typedef std::map<int, TP2PCache> TCache;
385 
386 
387 /** @class SchreyerSyzygyComputation syzextra.h
388  *
389  * Computing syzygies after Schreyer
390  *
391  * Storing/accumulating data during the computation requires some global
392  * object, like this class. Ideally the above global functions should not
393  * be used in favour of this class.
394  *
395  * @sa Schreyer Syzygy Computation Paper & Talk & Python prototype
396  */
398 {
399  friend class CLCM;
400  friend class CReducerFinder;
401 
402  public:
403  /// Construct a global object for given input data (separated into leads & tails)
404  SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting):
406  m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)),
407  m_syzLeads(NULL), m_syzTails(NULL),
408  m_LS(NULL), m_lcm(m_idLeads, setting),
409  m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
410  m_sum_bucket_factory(setting.m_rBaseRing),
411  m_spoly_bucket(NULL)
412  {
413  if( UNLIKELY(OPT__PROT) ) memset( &m_stat, 0, sizeof(m_stat) );
414  }
415 
416  /// Construct a global object for given input data (separated into leads & tails)
417  SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ideal syzLeads, const SchreyerSyzygyComputationFlags setting):
419  m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)),
420  m_syzLeads(syzLeads), m_syzTails(NULL),
421  m_LS(syzLeads), m_lcm(m_idLeads, setting),
422  m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
423  m_sum_bucket_factory(setting.m_rBaseRing),
424  m_spoly_bucket(NULL)
425  {
426  if( UNLIKELY(OPT__PROT) ) memset( &m_stat, 0, sizeof(m_stat) );
427 
429  {
430  if (syzLeads != NULL)
431  m_checker.Initialize(syzLeads);
432 // if( idTails != NULL )
433 // SetUpTailTerms();
434  }
435  }
436 
437  /// Destructor should not destruct the resulting m_syzLeads, m_syzTails.
439 
440  /// Convert the given ideal of tails into the internal representation (with reducers!)
441  /// Preprocess m_idTails as well...?
442  void SetUpTailTerms();
443 
444  /// print statistics about the used heuristics
445  void PrintStats() const;
446 
447  /// Read off the results while detaching them from this object
448  /// NOTE: no copy!
449  inline void ReadOffResult(ideal& syzL, ideal& syzT)
450  {
451  syzL = m_syzLeads; syzT = m_syzTails;
452 
453  m_syzLeads = m_syzTails = NULL; // m_LS ?
454 
455  if ( UNLIKELY(OPT__PROT) )
456  PrintStats();
457  }
458 
459 
460  /// The main driver function: computes
461  void ComputeSyzygy();
462 
463  /// Computes Syz(leads) or only LEAD of it.
464  /// The result is stored into m_syzLeads
465  void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms = true);
466 
467 
468 
469  /// Main HybridNF == 1: poly reduce + LOT + LCM?
470  poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2 = NULL) const;
471 
472 
473  // Main (HybridNF == 0) Tree Travers + LOT + LCM?
474  poly TraverseNF(const poly syz_lead, const poly syz_2 = NULL) const;
475 
476  /// High level caching function!!!
477  poly TraverseTail(poly multiplier, const int tail) const;
478 
479  // REMOVE?
480  /// called only from above and from outside (for testing)
481  poly TraverseTail(poly multiplier, poly tail) const;
482 
483  /// TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
484  poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
485 
486  /// low level computation...
487  poly ComputeImage(poly multiplier, const int tail) const;
488 
489 
490 
491  public:
492  /// just for testing via the wrapper below
493  inline poly _FindReducer(const poly product, const poly syzterm) const
494  { return m_div.FindReducer(product, syzterm, m_checker); }
495  private:
496  void CleanUp();
497  protected:
498 
499 
500  /// just leading terms
501  ideal Compute1LeadingSyzygyTerms();
502 
503  /// leading + second terms
505 
506 
507 
508  private:
509  /// input leading terms
510  const ideal m_idLeads;
511 
512  /// input tails
513  const ideal m_idTails;
514 
515  /// output (syzygy) leading terms (+2nd terms?)
516  ideal m_syzLeads;
517 
518  /// output (syzygy) tails
519  ideal m_syzTails;
520 
521  /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
522 
523 
524  /// Bitmask for variables occuring in leading terms
525  const CLCM m_lcm;
526 
527  /// Divisor finder
529 
530  /// for checking tail-terms and makeing them irreducible (wrt m_LS!)
532 
533  /*
534  // need more data here:
535  // (m_idLeads : m_tailterm) = (m, pos, compl), s.th: compl * m_tailterm divides m_idLeads[pos]
536  // but resulting sysygy compl * gen(pos) should not be in
537  // Idea: extend CReducerFinder??!!
538  struct CTailTerm
539  {
540  const poly m_tailterm;
541 
542  const CReducerFinder m_reducers; // positions are labels (in m_idLeads)...
543  // compl - to be computed if needed?
544 
545  CTailTerm(const poly tt, const CReducerFinder reds): m_tailterm(tt), m_reducers(reds) {}
546  };
547 
548  typedef std::vector<const CTailTerm*> TTail;
549  typedef std::vector<TTail> TTailTerms;
550 
551  TTailTerms m_idTailTerms;
552  */
553 
554  mutable TCache m_cache; // cacher comp + poly -> poly! // mutable???
555 
556 /// TODO: look into m_idTailTerms!!!!!!!!!!!!!!!!!!!!!!!! map? heaps???
557  // NOTE/TODO: the following globally shared buckets violate reentrance - they should rather belong to TLS!
558 
559  /// used for simple summing up
560  mutable SBucketFactory m_sum_bucket_factory; // sBucket_pt
561 
562  /// for S-Polynomial reductions
563  mutable kBucket_pt m_spoly_bucket; // only used inside of SchreyerSyzygyNF! destruction by CleanUp()!
564 
565 
566  /// Statistics:
567  /// 0..3: as in SetUpTailTerms()::PreProcessTerm() // TODO!!??
568  /// 4: number of terms discarded due to LOT heuristics
569  /// 5: number of terms discarded due to LCM heuristics
570  /// 6, 7: lookups without & with rescale, 8: stores
571  mutable unsigned long m_stat[9];
572 };
573 
574 // The following wrappers are just for testing separate functions on highest level (within schreyer.lib)
575 
576 static inline void ComputeSyzygy(const ideal L, const ideal T, ideal& LL, ideal& TT, const SchreyerSyzygyComputationFlags A)
577 {
578  SchreyerSyzygyComputation syz(L, T, A);
579  syz.ComputeSyzygy();
580  syz.ReadOffResult(LL, TT);
581 }
582 
583 static inline ideal ComputeLeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
584 {
585  SchreyerSyzygyComputation syz(L, NULL, A);
586  syz.ComputeLeadingSyzygyTerms(false);
587  ideal LL, TT;
588  syz.ReadOffResult(LL, TT);
589  return LL; // assume TT is NULL!
590 }
591 
592 static inline ideal Compute2LeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
593 {
594  SchreyerSyzygyComputation syz(L, NULL, A);
595  syz.ComputeLeadingSyzygyTerms(true);
596  ideal LL, TT;
597  syz.ReadOffResult(LL, TT);
598  return LL; // assume TT is NULL!
599 }
600 
601 static inline poly FindReducer(poly product, poly syzterm,
602  ideal L, ideal LS, const SchreyerSyzygyComputationFlags A)
603 {
604  SchreyerSyzygyComputation syz(L, NULL, LS, A);
605  return syz._FindReducer(product, syzterm);
606 }
607 
608 static inline poly TraverseTail(poly multiplier, poly tail,
609  ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
610 {
611  SchreyerSyzygyComputation syz(L, T, LS, A);
612  return syz.TraverseTail(multiplier, tail);
613 }
614 
615 static inline poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck,
616  ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
617 {
618  SchreyerSyzygyComputation syz(L, T, LS, A);
619  return syz.ReduceTerm(multiplier, term4reduction, syztermCheck);
620 }
621 
622 
623 static inline poly SchreyerSyzygyNF(poly syz_lead, poly syz_2,
624  ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
625 {
626  SchreyerSyzygyComputation syz(L, T, LS, A);
627  return syz.SchreyerSyzygyNF(syz_lead, syz_2);
628 }
629 
631 
633 
634 #endif
635 /* #ifndef SYZEXTRA_H */
636 
637 // Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
638 
Computation attribute storage.
Definition: syzextra.h:189
static ideal Compute2LeadingSyzygyTerms(const ideal &L, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:592
CCacheCompare(const ring &r)
Definition: syzextra.h:375
SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ideal syzLeads, const SchreyerSyzygyComputationFlags setting)
Construct a global object for given input data (separated into leads & tails)
Definition: syzextra.h:417
const unsigned int m_label
index in the main L[] + 1
Definition: syzextra.h:290
const ring & m_ring
Definition: syzextra.h:371
bool m_compute
Definition: syzextra.h:254
int OPT__SYZNUMBER
Syzygy level (within a resolution)
Definition: syzextra.h:221
static poly TraverseTail(poly multiplier, poly tail, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:608
poly TCacheValue
Definition: syzextra.h:367
std::stack< sBucket_pt > Base
Definition: syzextra.h:77
CCacheCompare(const CCacheCompare &lhs)
Definition: syzextra.h:377
static void ComputeSyzygy(const ideal L, const ideal T, ideal &LL, ideal &TT, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:576
Definition: attrib.h:15
ideal m_syzLeads
output (syzygy) leading terms (+2nd terms?)
Definition: syzextra.h:516
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
poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2=NULL) const
Main HybridNF == 1: poly reduce + LOT + LCM?
Definition: syzextra.cc:1419
const ideal m_idLeads
input leading terms
Definition: syzextra.h:510
SBucketFactory(const ring r)
Definition: syzextra.h:85
return P p
Definition: myNF.cc:203
const poly m_lt
the leading term itself L[label-1]
Definition: syzextra.h:292
bool IsNonempty() const
Definition: syzextra.h:343
std::vector< const CLeadingTerm * > TReducers
Definition: syzextra.h:317
void Sort_c_ds(const ideal id, const ring r)
inplace sorting of the module (ideal) id wrt <_(c,ds)
Definition: syzextra.cc:527
STL namespace.
Definition: ring.h:209
static poly SchreyerSyzygyNF(poly syz_lead, poly syz_2, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:623
ideal m_LS
leading syzygy terms used for reducing syzygy tails
Definition: syzextra.h:521
ideal m_syzTails
output (syzygy) tails
Definition: syzextra.h:519
#define UNLIKELY(expression)
Definition: tgb_internal.h:838
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
kBucket_pt m_spoly_bucket
for S-Polynomial reductions
Definition: syzextra.h:563
long TComponentKey
Definition: syzextra.h:316
const int OPT__DEBUG
output all the intermediate states
Definition: syzextra.h:204
CReducerFinder m_checker
for checking tail-terms and makeing them irreducible (wrt m_LS!)
Definition: syzextra.h:531
poly _FindReducer(const poly product, const poly syzterm) const
just for testing via the wrapper below
Definition: syzextra.h:493
~SchreyerSyzygyComputation()
Destructor should not destruct the resulting m_syzLeads, m_syzTails.
Definition: syzextra.h:438
#define BEGIN_NAMESPACE_SINGULARXX
Bucket getBucket(const ring r, const bool remove=true)
Definition: syzextra.h:103
Definition: idrec.h:34
const int OPT__TAILREDSYZ
Reduce syzygy tails wrt the leading syzygy terms.
Definition: syzextra.h:210
void nextSyzygyLayer() const
Definition: syzextra.h:223
CReducersHash m_hash
Definition: syzextra.h:356
void ComputeSyzygy()
The main driver function: computes.
Definition: syzextra.cc:1145
static poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:615
kBucket * kBucket_pt
Definition: syzextra.h:33
#define assume(x)
Definition: mod2.h:405
poly TCacheKey
Definition: syzextra.h:366
#define END_NAMESPACE_SINGULARXX
const bool OPT__PROT
TEST_OPT_PROT.
Definition: syzextra.h:235
#define A
Definition: sirandom.c:23
poly TraverseTail(poly multiplier, const int tail) const
High level caching function!!!
Definition: syzextra.cc:1594
void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms=true)
Computes Syz(leads) or only LEAD of it. The result is stored into m_syzLeads.
Definition: syzextra.cc:1371
int m
Definition: cfEzgcd.cc:119
const CReducerFinder m_div
Divisor finder.
Definition: syzextra.h:528
static poly FindReducer(poly product, poly syzterm, ideal L, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:601
void ReadOffResult(ideal &syzL, ideal &syzT)
Read off the results while detaching them from this object NOTE: no copy!
Definition: syzextra.h:449
const unsigned int m_N
number of ring variables
Definition: syzextra.h:256
const unsigned long m_sev
not short exp. vector
Definition: syzextra.h:287
std::map< int, TP2PCache > TCache
Definition: syzextra.h:384
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
poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
Definition: syzextra.cc:1895
Definition: syzextra.h:246
ideal id_Copy(const ideal, const ring)
copy an ideal
sBucket Factory
Definition: syzextra.h:74
polyrec * poly
Definition: syzextra.h:27
std::map< TComponentKey, TReducers > CReducersHash
Definition: syzextra.h:320
idrec * idhdl
Definition: syzextra.h:31
The following sip_sideal structure has many different uses thoughout Singular. Basic use-cases for it...
Definition: simpleideals.h:18
#define NULL
Definition: omList.c:10
const ring _R
Definition: syzextra.h:295
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
#define END_NAMESPACE
Base::value_type Bucket
Definition: syzextra.h:83
const ring m_rBaseRing
global base ring
Definition: syzextra.h:241
SBucketFactory m_sum_bucket_factory
TODO: look into m_idTailTerms!!!!!!!!!!!!!!!!!!!!!!!! map? heaps???
Definition: syzextra.h:560
void putBucket(const Bucket &bt, const bool replace=false)
Definition: syzextra.h:135
ideal m_L
only for debug
Definition: syzextra.h:354
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
#define const
Definition: fegetopt.c:41
const ring m_ring
For debugging: all buckets are over the same ring... right?!
Definition: syzextra.h:160
SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting)
Construct a global object for given input data (separated into leads & tails)
Definition: syzextra.h:404
const int OPT__IGNORETAILS
ignore tails and compute the pure Schreyer frame
Definition: syzextra.h:218
CCacheCompare & operator=(const CCacheCompare &lhs)
Definition: syzextra.h:378
const CLCM m_lcm
Bitmask for variables occuring in leading terms.
Definition: syzextra.h:525
SchreyerSyzygyComputationFlags(const SchreyerSyzygyComputationFlags &attr)
Definition: syzextra.h:193
Computing syzygies after Schreyer.
Definition: syzextra.h:397
const ideal m_idTails
input tails
Definition: syzextra.h:513
static jList * T
Definition: janet.cc:37
polyrec * poly
Definition: hilb.h:10
int status int void size_t count int const void size_t count const char int flags
Definition: si_signals.h:73
BEGIN_NAMESPACE_SINGULARXX BEGIN_NAMESPACE(SYZEXTRA) poly leadmonom(const poly p
BEGIN_NAMESPACE_SINGULARXX const ring r
Definition: syzextra.h:47
bool my_p_LmCmp(poly, poly, const ring)
Definition: syzextra.cc:1590
int l
Definition: cfEzgcd.cc:94
const int OPT__NOCACHING
no caching/stores/lookups
Definition: syzextra.h:238
static ideal ComputeLeadingSyzygyTerms(const ideal &L, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:583
std::map< TCacheKey, TCacheValue, CCacheCompare > TP2PCache
Definition: syzextra.h:383