My Project  debian-1:4.1.1-p2+ds-4build1
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 #include "kernel/ideals.h"
27 
28 class idrec; typedef idrec * idhdl;
29 
30 class kBucket; typedef kBucket* kBucket_pt;
31 
32 #ifndef NOPRODUCT
33 # define NOPRODUCT 1
34 #endif
35 
36 // set to 1 if all leading coeffs are assumed to be all =1...
37 // note the use of simplify on input in SSinit!
38 #ifndef NODIVISION
39 # define NODIVISION 1
40 #endif
41 
42 poly leadmonom(const poly p, const ring r, const bool bSetZeroComp = true);
43 
44 /// return the tail of a given polynomial or vector
45 /// returns NULL if input is NULL, otherwise
46 /// the result is a new polynomial/vector in the ring r
47 poly p_Tail(const poly p, const ring r);
48 
49 
50 /// return the tail of a given ideal or module
51 /// returns NULL if input is NULL, otherwise
52 /// the result is a new ideal/module in the ring r
53 /// NOTE: the resulting rank is autocorrected
54 ideal id_Tail(const ideal id, const ring r);
55 
56 /// inplace sorting of the module (ideal) id wrt <_(c,ds)
57 void Sort_c_ds(const ideal id, const ring r);
58 
59 
60 class sBucket; typedef sBucket* sBucket_pt;
61 
62 /** @class SBucketFactory syzextra.h
63  *
64  * sBucket Factory
65  *
66  * Cleate/store/reuse buckets
67  *
68  */
69 class SBucketFactory: private std::stack <sBucket_pt>
70 {
71  private:
72  typedef std::stack <sBucket_pt> Base;
73 
74  public:
75  typedef Base::value_type Bucket;
76 
77  SBucketFactory(const ring r)
78  {
79  push ( _CreateBucket(r) ); // start with at least one sBucket...?
80  assume( top() != NULL );
81  };
82 
84  {
85  while( !empty() )
86  {
87  _DestroyBucket( top() );
88  pop();
89  }
90  }
91 
92  Bucket getBucket(const ring r, const bool remove = true)
93  {
94  Bucket bt = NULL;
95 
96  if( !empty() )
97  {
98  bt = top();
99 
100  if( remove )
101  pop();
102  }
103  else
104  {
105  bt = _CreateBucket(r);
106 
107  if( !remove )
108  {
109  push(bt);
110  assume( bt == top() );
111  }
112  }
113 
114  assume( bt != NULL );
115 
116  return bt;
117  }
118 
119  // TODO: this may be spared if we give-out a smart Bucket (which returns here upon its destructor!)
120  void putBucket(const Bucket & bt, const bool replace = false)
121  {
122  assume( bt != NULL );
123 
124  if( empty() )
125  push( bt );
126  else
127  {
128  if( replace )
129  top() = bt;
130  else
131  {
132  if( bt != top() )
133  push( bt );
134  }
135  }
136 
137  assume( bt == top() );
138  }
139 
140  private:
141  /// inital allocation for new buckets
142  static Bucket _CreateBucket(const ring r);
143 
144  /// we only expect empty buckets to be left at the end for destructor
145  /// bt will be set to NULL
146  static void _DestroyBucket(Bucket & bt);
147 
148  private:
149  SBucketFactory();
151  void operator=(const SBucketFactory&);
152 
153 };
154 
155 
156 
157 
158 
159 
160 
161 /// Computation attribute storage
163 {
165 
174  {}
175 
176  /// output all the intermediate states
177  const int OPT__DEBUG; // DebugOutput;
178 
179  /// ?
180  const int OPT__LEAD2SYZ; // TwoLeadingSyzygyTerms;
181 
182  /// Reduce syzygy tails wrt the leading syzygy terms
183  const int OPT__TAILREDSYZ; // TailReducedSyzygies;
184 
185  /// Use the usual NF's S-poly reduction while dropping lower order terms
186  /// 2 means - smart selection!
187  const int OPT__HYBRIDNF; // UseHybridNF
188 
189 
190  /// ignore tails and compute the pure Schreyer frame
191  const int OPT__IGNORETAILS; // @IGNORETAILS
192 
193  /// Syzygy level (within a resolution)
194  mutable int OPT__SYZNUMBER;
195 
196  inline void nextSyzygyLayer() const
197  {
198  OPT__SYZNUMBER++;
199  }
200 
201  /// output lifting tree
202  const int OPT__TREEOUTPUT;
203 
204  /// CheckSyzygyProperty: TODO
205  const int OPT__SYZCHECK;
206 
207  /// TEST_OPT_PROT
208  const bool OPT__PROT;
209 
210  /// no caching/stores/lookups
211  const int OPT__NOCACHING;
212 
213  /// global base ring
214  const ring m_rBaseRing;
215 };
216 
218 
219 class CLCM: public SchreyerSyzygyComputationFlags, public std::vector<bool>
220 {
221  public:
222  CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags);
223 
224  bool Check(const poly m) const;
225 
226  private:
227  bool m_compute;
228 
229  const unsigned int m_N; ///< number of ring variables
230 };
231 
232 
234 {
235  public:
236  CLeadingTerm(unsigned int label, const poly lt, const ring);
237 
238 #if NOPRODUCT
239  bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const;
240 #endif
241  bool DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const;
242 
243  bool CheckLT( const ideal & L ) const;
244 
245  inline poly lt() const { return m_lt; };
246  inline unsigned long sev() const { return m_sev; };
247  inline unsigned int label() const { return m_label; };
248  private:
249  const unsigned long m_sev; ///< not short exp. vector
250 
251  // NOTE/TODO: either of the following should be enough:
252  const unsigned int m_label; ///< index in the main L[] + 1
253 
254  const poly m_lt; ///< the leading term itself L[label-1]
255 
256  // disable the following:
257  CLeadingTerm();
258  CLeadingTerm(const CLeadingTerm&);
259  void operator=(const CLeadingTerm&);
260 };
261 
262 
263 // TODO: needs a specialized variant without a component (hash!)
265 {
266 #if NOPRODUCT
267  friend class CDivisorEnumerator2;
268 #endif
269  friend class CDivisorEnumerator;
270 
271  public:
272  typedef long TComponentKey;
273  typedef std::vector<const CLeadingTerm*> TReducers;
274 
275  private:
276  typedef std::map< TComponentKey, TReducers> CReducersHash;
277 
278  public:
279  /// goes over all leading terms
280  CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags);
281 
282  void Initialize(const ideal L);
283 
284  ~CReducerFinder();
285 
286 
287 #if NOPRODUCT
288  poly
289  FindReducer(const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder& checker) const;
290 
291 #endif
292  // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
293  poly // const_iterator // TODO: return const_iterator it, s.th: it->m_lt is the needed
294  FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
295 
296  bool IsDivisible(const poly q) const;
297 
298 
299  inline bool IsNonempty() const { return !m_hash.empty(); }
300 
301  /// is the term to be "preprocessed" as lower order term or lead to only reducible syzygies...
302  int PreProcessTerm(const poly t, CReducerFinder& syzChecker) const;
303 
304  private:
305  ideal m_L; ///< only for debug
306 
307  CReducersHash m_hash; // can also be replaced with a vector indexed by components
308 
309  private:
311  void operator=(const CReducerFinder&);
312 };
313 
314 bool my_p_LmCmp (poly, poly, const ring);
315 
316 typedef poly TCacheKey;
317 typedef poly TCacheValue;
318 
320 {
321  const ring & m_ring;
322 
323  CCacheCompare();
324 
325  CCacheCompare(const ring& r): m_ring(r) { assume(r != NULL); }
326 
328  CCacheCompare& operator=(const CCacheCompare& lhs) { assume(lhs.m_ring != NULL); return (const_cast<CCacheCompare&>(lhs)); }
329 
330  inline bool operator() (const TCacheKey& l, const TCacheKey& r) const { assume(m_ring != NULL); return my_p_LmCmp(l, r, m_ring); }
331 };
332 
333 typedef std::map<TCacheKey, TCacheValue, CCacheCompare> TP2PCache; // deallocation??? !!!
334 typedef std::map<int, TP2PCache> TCache;
335 
336 
337 /** @class SchreyerSyzygyComputation syzextra.h
338  *
339  * Computing syzygies after Schreyer
340  *
341  * Storing/accumulating data during the computation requires some global
342  * object, like this class. Ideally the above global functions should not
343  * be used in favour of this class.
344  *
345  * @sa Schreyer Syzygy Computation Paper & Talk & Python prototype
346  */
348 {
349  friend class CLCM;
350  friend class CReducerFinder;
351 
352  public:
353  /// Construct a global object for given input data (separated into leads & tails)
354  SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting):
356  m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)),
358  m_LS(NULL), m_lcm(m_idLeads, setting),
359  m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
362  {
363  if( UNLIKELY(OPT__PROT) ) memset( &m_stat, 0, sizeof(m_stat) );
364  }
365 
366  /// Construct a global object for given input data (separated into leads & tails)
367  SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ideal syzLeads, const SchreyerSyzygyComputationFlags setting):
369  m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)),
370  m_syzLeads(syzLeads), m_syzTails(NULL),
371  m_LS(syzLeads), m_lcm(m_idLeads, setting),
372  m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
375  {
376  if( UNLIKELY(OPT__PROT) ) memset( &m_stat, 0, sizeof(m_stat) );
377 
379  {
380  if (syzLeads != NULL)
381  m_checker.Initialize(syzLeads);
382 // if( idTails != NULL )
383 // SetUpTailTerms();
384  }
385  }
386 
387  /// Destructor should not destruct the resulting m_syzLeads, m_syzTails.
389 
390  /// Convert the given ideal of tails into the internal representation (with reducers!)
391  /// Preprocess m_idTails as well...?
392  void SetUpTailTerms();
393 
394  /// print statistics about the used heuristics
395  void PrintStats() const;
396 
397  /// Read off the results while detaching them from this object
398  /// NOTE: no copy!
399  inline void ReadOffResult(ideal& syzL, ideal& syzT)
400  {
401  syzL = m_syzLeads; syzT = m_syzTails;
402 
403  m_syzLeads = m_syzTails = NULL; // m_LS ?
404 
405  if ( UNLIKELY(OPT__PROT) )
406  PrintStats();
407  }
408 
409 
410  /// The main driver function: computes
411  void ComputeSyzygy();
412 
413  /// Computes Syz(leads) or only LEAD of it.
414  /// The result is stored into m_syzLeads
415  void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms = true);
416 
417 
418 
419  /// Main HybridNF == 1: poly reduce + LOT + LCM?
420  poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2 = NULL) const;
421 
422 
423  // Main (HybridNF == 0) Tree Travers + LOT + LCM?
424  poly TraverseNF(const poly syz_lead, const poly syz_2 = NULL) const;
425 
426  /// High level caching function!!!
427  poly TraverseTail(poly multiplier, const int tail) const;
428 
429  // REMOVE?
430  /// called only from above and from outside (for testing)
431  poly TraverseTail(poly multiplier, poly tail) const;
432 
433  /// TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
434  poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
435 
436  /// low level computation...
437  poly ComputeImage(poly multiplier, const int tail) const;
438 
439 
440 
441  public:
442  /// just for testing via the wrapper below
443  inline poly _FindReducer(const poly product, const poly syzterm) const
444  { return m_div.FindReducer(product, syzterm, m_checker); }
445  private:
446  void CleanUp();
447  protected:
448 
449 
450  /// just leading terms
452 
453  /// leading + second terms
455 
456 
457 
458  private:
459  /// input leading terms
460  const ideal m_idLeads;
461 
462  /// input tails
463  const ideal m_idTails;
464 
465  /// output (syzygy) leading terms (+2nd terms?)
466  ideal m_syzLeads;
467 
468  /// output (syzygy) tails
469  ideal m_syzTails;
470 
471  /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
472 
473 
474  /// Bitmask for variables occuring in leading terms
475  const CLCM m_lcm;
476 
477  /// Divisor finder
479 
480  /// for checking tail-terms and makeing them irreducible (wrt m_LS!)
482 
483  mutable TCache m_cache; // cacher comp + poly -> poly! // mutable???
484 
485  /// used for simple summing up
486  mutable SBucketFactory m_sum_bucket_factory; // sBucket_pt
487 
488  /// for S-Polynomial reductions
489  mutable kBucket_pt m_spoly_bucket; // only used inside of SchreyerSyzygyNF! destruction by CleanUp()!
490 
491 
492  /// Statistics:
493  /// 0..3: as in SetUpTailTerms()::PreProcessTerm() // TODO!!??
494  /// 4: number of terms discarded due to LOT heuristics
495  /// 5: number of terms discarded due to LCM heuristics
496  /// 6, 7: lookups without & with rescale, 8: stores
497  mutable unsigned long m_stat[9];
498 };
499 
500 // The following wrappers are just for testing separate functions on highest level (within schreyer.lib)
501 
502 static inline void ComputeSyzygy(const ideal L, const ideal T, ideal& LL, ideal& TT, const SchreyerSyzygyComputationFlags A)
503 {
504  SchreyerSyzygyComputation syz(L, T, A);
505  syz.ComputeSyzygy();
506  syz.ReadOffResult(LL, TT);
507 }
508 
509 static inline ideal ComputeLeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
510 {
512  syz.ComputeLeadingSyzygyTerms(false);
513  ideal LL, TT;
514  syz.ReadOffResult(LL, TT);
515  return LL; // assume TT is NULL!
516 }
517 
518 static inline ideal Compute2LeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
519 {
521  syz.ComputeLeadingSyzygyTerms(true);
522  ideal LL, TT;
523  syz.ReadOffResult(LL, TT);
524  return LL; // assume TT is NULL!
525 }
526 
527 static inline poly FindReducer(poly product, poly syzterm,
528  ideal L, ideal LS, const SchreyerSyzygyComputationFlags A)
529 {
530  SchreyerSyzygyComputation syz(L, NULL, LS, A);
531  return syz._FindReducer(product, syzterm);
532 }
533 
534 static inline poly TraverseTail(poly multiplier, poly tail,
535  ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
536 {
537  SchreyerSyzygyComputation syz(L, T, LS, A);
538  return syz.TraverseTail(multiplier, tail);
539 }
540 
541 static inline poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck,
542  ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
543 {
544  SchreyerSyzygyComputation syz(L, T, LS, A);
545  return syz.ReduceTerm(multiplier, term4reduction, syztermCheck);
546 }
547 
548 
549 static inline poly SchreyerSyzygyNF(poly syz_lead, poly syz_2,
550  ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
551 {
552  SchreyerSyzygyComputation syz(L, T, LS, A);
553  return syz.SchreyerSyzygyNF(syz_lead, syz_2);
554 }
555 
556 #endif
557 /* #ifndef SYZEXTRA_H */
558 
559 // Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
560 
TCacheValue
poly TCacheValue
Definition: syzextra.h:317
singularxx_defs.h
CReducerFinder::operator=
void operator=(const CReducerFinder &)
SchreyerSyzygyComputationFlags::m_rBaseRing
const ring m_rBaseRing
global base ring
Definition: syzextra.h:214
CLeadingTerm::sev
unsigned long sev() const
Definition: syzextra.h:246
SchreyerSyzygyComputation::_FindReducer
poly _FindReducer(const poly product, const poly syzterm) const
just for testing via the wrapper below
Definition: syzextra.h:443
CReducerFinder::TComponentKey
long TComponentKey
Definition: syzextra.h:272
SchreyerSyzygyComputation::m_div
const CReducerFinder m_div
Divisor finder.
Definition: syzextra.h:478
CCacheCompare::m_ring
const ring & m_ring
Definition: syzextra.h:321
SchreyerSyzygyComputation::Compute1LeadingSyzygyTerms
ideal Compute1LeadingSyzygyTerms()
just leading terms
Definition: syzextra.cc:544
CDivisorEnumerator2
TODO:
Definition: syzextra.cc:1725
CLeadingTerm::m_lt
const poly m_lt
the leading term itself L[label-1]
Definition: syzextra.h:254
SchreyerSyzygyComputationFlags::OPT__HYBRIDNF
const int OPT__HYBRIDNF
Use the usual NF's S-poly reduction while dropping lower order terms 2 means - smart selection!
Definition: syzextra.h:187
CReducerFinder::~CReducerFinder
~CReducerFinder()
Definition: syzextra.cc:1470
SchreyerSyzygyComputation::SchreyerSyzygyComputation
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:354
SchreyerSyzygyComputation::m_sum_bucket_factory
SBucketFactory m_sum_bucket_factory
used for simple summing up
Definition: syzextra.h:486
CCacheCompare::CCacheCompare
CCacheCompare(const CCacheCompare &lhs)
Definition: syzextra.h:327
SBucketFactory::operator=
void operator=(const SBucketFactory &)
SchreyerSyzygyComputationFlags::SchreyerSyzygyComputationFlags
SchreyerSyzygyComputationFlags(idhdl rootRingHdl)
Definition: syzextra.cc:1442
CLCM::CLCM
CLCM(const ideal &L, const SchreyerSyzygyComputationFlags &flags)
Definition: syzextra.cc:2061
SchreyerSyzygyComputation::m_LS
ideal m_LS
leading syzygy terms used for reducing syzygy tails
Definition: syzextra.h:471
TCache
std::map< int, TP2PCache > TCache
Definition: syzextra.h:334
SchreyerSyzygyComputation::m_checker
CReducerFinder m_checker
for checking tail-terms and makeing them irreducible (wrt m_LS!)
Definition: syzextra.h:481
Sort_c_ds
void Sort_c_ds(const ideal id, const ring r)
inplace sorting of the module (ideal) id wrt <_(c,ds)
Definition: syzextra.cc:342
CCacheCompare::operator()
bool operator()(const TCacheKey &l, const TCacheKey &r) const
Definition: syzextra.h:330
CLCM
Definition: syzextra.h:219
SchreyerSyzygyComputation::~SchreyerSyzygyComputation
~SchreyerSyzygyComputation()
Destructor should not destruct the resulting m_syzLeads, m_syzTails.
Definition: syzextra.h:388
SchreyerSyzygyComputation::m_idTails
const ideal m_idTails
input tails
Definition: syzextra.h:463
SchreyerSyzygyComputation::PrintStats
void PrintStats() const
print statistics about the used heuristics
Definition: syzextra.cc:533
sattr
Definition: attrib.h:16
p_Tail
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:316
CLeadingTerm::CheckLT
bool CheckLT(const ideal &L) const
Definition: syzextra.cc:1562
LIKELY
#define LIKELY
Definition: auxiliary.h:420
flags
int status int void size_t count int const void size_t count const char int flags
Definition: si_signals.h:72
SchreyerSyzygyComputation::m_syzTails
ideal m_syzTails
output (syzygy) tails
Definition: syzextra.h:469
SBucketFactory
Definition: syzextra.h:69
ComputeSyzygy
static void ComputeSyzygy(const ideal L, const ideal T, ideal &LL, ideal &TT, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:502
CLeadingTerm::DivisibilityCheck
bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const
as DivisibilityCheck(multiplier * t, ...) for monomial 'm' and a module term 't'
Definition: syzextra.cc:1589
SchreyerSyzygyComputationFlags::OPT__PROT
const bool OPT__PROT
TEST_OPT_PROT.
Definition: syzextra.h:208
CLeadingTerm::m_label
const unsigned int m_label
index in the main L[] + 1
Definition: syzextra.h:252
CReducerFinder::CReducerFinder
CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags &flags)
goes over all leading terms
Definition: syzextra.cc:1505
CReducerFinder::FindReducer
poly FindReducer(const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder &checker) const
Definition: syzextra.cc:1823
SchreyerSyzygyComputationFlags::nextSyzygyLayer
void nextSyzygyLayer() const
Definition: syzextra.h:196
TP2PCache
std::map< TCacheKey, TCacheValue, CCacheCompare > TP2PCache
Definition: syzextra.h:333
TraverseTail
static poly TraverseTail(poly multiplier, poly tail, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:534
SchreyerSyzygyComputation::CleanUp
void CleanUp()
Clean up all the accumulated data.
Definition: syzextra.cc:363
SchreyerSyzygyComputation::SchreyerSyzygyNF
poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2=NULL) const
Main HybridNF == 1: poly reduce + LOT + LCM?
Definition: syzextra.cc:1013
FindReducer
static poly FindReducer(poly product, poly syzterm, ideal L, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:527
SchreyerSyzygyComputation::m_idLeads
const ideal m_idLeads
input leading terms
Definition: syzextra.h:460
CLCM::m_compute
bool m_compute
Definition: syzextra.h:227
Compute2LeadingSyzygyTerms
static ideal Compute2LeadingSyzygyTerms(const ideal &L, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:518
SchreyerSyzygyComputationFlags::OPT__TAILREDSYZ
const int OPT__TAILREDSYZ
Reduce syzygy tails wrt the leading syzygy terms.
Definition: syzextra.h:183
SchreyerSyzygyNF
static poly SchreyerSyzygyNF(poly syz_lead, poly syz_2, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:549
CLCM::Check
bool Check(const poly m) const
Definition: syzextra.cc:2093
my_p_LmCmp
bool my_p_LmCmp(poly, poly, const ring)
Definition: syzextra.cc:1140
SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms
void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms=true)
Computes Syz(leads) or only LEAD of it. The result is stored into m_syzLeads.
Definition: syzextra.cc:976
CReducerFinder::m_hash
CReducersHash m_hash
Definition: syzextra.h:307
SBucketFactory::putBucket
void putBucket(const Bucket &bt, const bool replace=false)
Definition: syzextra.h:120
sBucket_pt
sBucket * sBucket_pt
Definition: syzextra.h:60
CReducerFinder::PreProcessTerm
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:402
SBucketFactory::~SBucketFactory
~SBucketFactory()
Definition: syzextra.h:83
SchreyerSyzygyComputationFlags::OPT__IGNORETAILS
const int OPT__IGNORETAILS
ignore tails and compute the pure Schreyer frame
Definition: syzextra.h:191
T
static jList * T
Definition: janet.cc:31
SchreyerSyzygyComputation::TraverseNF
poly TraverseNF(const poly syz_lead, const poly syz_2=NULL) const
Definition: syzextra.cc:765
SchreyerSyzygyComputation::TraverseTail
poly TraverseTail(poly multiplier, const int tail) const
High level caching function!!!
Definition: syzextra.cc:1144
SchreyerSyzygyComputation::ComputeSyzygy
void ComputeSyzygy()
The main driver function: computes.
Definition: syzextra.cc:806
SchreyerSyzygyComputationFlags::SchreyerSyzygyComputationFlags
SchreyerSyzygyComputationFlags(const SchreyerSyzygyComputationFlags &attr)
Definition: syzextra.h:166
ReduceTerm
static poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck, ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:541
CReducerFinder::m_L
ideal m_L
only for debug
Definition: syzextra.h:305
SBucketFactory::getBucket
Bucket getBucket(const ring r, const bool remove=true)
Definition: syzextra.h:92
SchreyerSyzygyComputation::ReduceTerm
poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
Definition: syzextra.cc:1353
ComputeLeadingSyzygyTerms
static ideal ComputeLeadingSyzygyTerms(const ideal &L, const SchreyerSyzygyComputationFlags A)
Definition: syzextra.h:509
CReducerFinder::IsDivisible
bool IsDivisible(const poly q) const
Definition: syzextra.cc:1708
SBucketFactory::Base
std::stack< sBucket_pt > Base
Definition: syzextra.h:72
SchreyerSyzygyComputationFlags::OPT__SYZCHECK
const int OPT__SYZCHECK
CheckSyzygyProperty: TODO.
Definition: syzextra.h:205
SchreyerSyzygyComputation::ComputeImage
poly ComputeImage(poly multiplier, const int tail) const
low level computation...
Definition: syzextra.cc:1238
idhdl
idrec * idhdl
Definition: syzextra.h:28
CLeadingTerm::CLeadingTerm
CLeadingTerm()
SchreyerSyzygyComputationFlags::OPT__NOCACHING
const int OPT__NOCACHING
no caching/stores/lookups
Definition: syzextra.h:211
CReducerFinder
Definition: syzextra.h:264
SchreyerSyzygyComputationFlags
Computation attribute storage.
Definition: syzextra.h:162
sBucket
Definition: sbuckets.cc:31
kBucket_pt
kBucket * kBucket_pt
Definition: syzextra.h:30
CLeadingTerm::operator=
void operator=(const CLeadingTerm &)
CDivisorEnumerator
TODO:
Definition: syzextra.cc:1617
SBucketFactory::SBucketFactory
SBucketFactory(const ring r)
Definition: syzextra.h:77
SchreyerSyzygyComputation::m_cache
TCache m_cache
Definition: syzextra.h:483
SBucketFactory::SBucketFactory
SBucketFactory()
CLeadingTerm
Definition: syzextra.h:233
idrec
Definition: idrec.h:33
CCacheCompare
Definition: syzextra.h:319
SchreyerSyzygyComputation::Compute2LeadingSyzygyTerms
ideal Compute2LeadingSyzygyTerms()
leading + second terms
Definition: syzextra.cc:634
CCacheCompare::CCacheCompare
CCacheCompare(const ring &r)
Definition: syzextra.h:325
SchreyerSyzygyComputationFlags::OPT__LEAD2SYZ
const int OPT__LEAD2SYZ
?
Definition: syzextra.h:180
TCacheKey
poly TCacheKey
Definition: syzextra.h:316
SchreyerSyzygyComputation::ReadOffResult
void ReadOffResult(ideal &syzL, ideal &syzT)
Read off the results while detaching them from this object NOTE: no copy!
Definition: syzextra.h:399
CLeadingTerm::label
unsigned int label() const
Definition: syzextra.h:247
CLeadingTerm::m_sev
const unsigned long m_sev
not short exp. vector
Definition: syzextra.h:247
CCacheCompare::operator=
CCacheCompare & operator=(const CCacheCompare &lhs)
Definition: syzextra.h:328
UNLIKELY
#define UNLIKELY
Definition: auxiliary.h:421
id_Tail
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:325
SchreyerSyzygyComputation
Definition: syzextra.h:347
m
int m
Definition: cfEzgcd.cc:121
SBucketFactory::_DestroyBucket
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:72
assume
#define assume(x)
Definition: mod2.h:384
SchreyerSyzygyComputation::SchreyerSyzygyComputation
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:367
NULL
#define NULL
Definition: omList.c:9
SchreyerSyzygyComputation::m_stat
unsigned long m_stat[9]
Statistics: 0..3: as in SetUpTailTerms()::PreProcessTerm() // TODO!!?? 4: number of terms discarded d...
Definition: syzextra.h:497
CCacheCompare::CCacheCompare
CCacheCompare()
ideals.h
SchreyerSyzygyComputation::m_spoly_bucket
kBucket_pt m_spoly_bucket
for S-Polynomial reductions
Definition: syzextra.h:489
CReducerFinder::IsNonempty
bool IsNonempty() const
Definition: syzextra.h:299
l
int l
Definition: cfEzgcd.cc:93
kBucket
Definition: kbuckets.h:174
SchreyerSyzygyComputationFlags::OPT__SYZNUMBER
int OPT__SYZNUMBER
Syzygy level (within a resolution)
Definition: syzextra.h:194
CReducerFinder::Initialize
void Initialize(const ideal L)
Definition: syzextra.cc:1481
p
int p
Definition: cfModGcd.cc:4019
SchreyerSyzygyComputation::SetUpTailTerms
void SetUpTailTerms()
Convert the given ideal of tails into the internal representation (with reducers!) Preprocess m_idTai...
Definition: syzextra.cc:474
SBucketFactory::Bucket
Base::value_type Bucket
Definition: syzextra.h:75
CLCM::m_N
const unsigned int m_N
number of ring variables
Definition: syzextra.h:229
id_Copy
ideal id_Copy(ideal h1, const ring r)
copy an ideal
Definition: simpleideals.cc:403
SchreyerSyzygyComputationFlags::OPT__DEBUG
const int OPT__DEBUG
output all the intermediate states
Definition: syzextra.h:177
CReducerFinder::TReducers
std::vector< const CLeadingTerm * > TReducers
Definition: syzextra.h:273
leadmonom
poly leadmonom(const poly p, const ring r, const bool bSetZeroComp=true)
return a new term: leading coeff * leading monomial of p with 0 leading component!
Definition: syzextra.cc:288
A
#define A
Definition: sirandom.c:23
SchreyerSyzygyComputation::m_lcm
const CLCM m_lcm
Bitmask for variables occuring in leading terms.
Definition: syzextra.h:475
CLeadingTerm::lt
poly lt() const
Definition: syzextra.h:245
CReducerFinder::CReducersHash
std::map< TComponentKey, TReducers > CReducersHash
Definition: syzextra.h:276
SBucketFactory::_CreateBucket
static Bucket _CreateBucket(const ring r)
inital allocation for new buckets
Definition: syzextra.cc:64
SchreyerSyzygyComputation::m_syzLeads
ideal m_syzLeads
output (syzygy) leading terms (+2nd terms?)
Definition: syzextra.h:466
SchreyerSyzygyComputationFlags::OPT__TREEOUTPUT
const int OPT__TREEOUTPUT
output lifting tree
Definition: syzextra.h:202