source: git/dyn_modules/syzextra/syzextra.h @ 68fedf

spielwiese
Last change on this file since 68fedf was 68fedf, checked in by Oleksandr Motsak <motsak@…>, 11 years ago
Mixed hybrid/traverse syzygy computation mathod (2) add: attribute int SYZNUMBER = level in the resolution) add: detailed PP statistics cosmetics: some code reformatting
  • Property mode set to 100644
File size: 11.9 KB
Line 
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
22// include basic definitions
23#include "singularxx_defs.h"
24
25struct  spolyrec;
26typedef struct spolyrec    polyrec;
27typedef polyrec *          poly;
28
29struct ip_sring;
30typedef struct ip_sring *         ring;
31
32struct sip_sideal;
33typedef struct sip_sideal *       ideal;
34
35class idrec;
36typedef idrec *   idhdl;
37
38BEGIN_NAMESPACE_SINGULARXX    BEGIN_NAMESPACE(SYZEXTRA)
39
40poly leadmonom(const poly p, const ring r, const bool bSetZeroComp = true);
41
42/// return the tail of a given polynomial or vector
43/// returns NULL if input is NULL, otherwise
44/// the result is a new polynomial/vector in the ring r
45poly p_Tail(const poly p, const ring r);
46
47
48/// return the tail of a given ideal or module
49/// returns NULL if input is NULL, otherwise
50/// the result is a new ideal/module in the ring r
51/// NOTE: the resulting rank is autocorrected
52ideal id_Tail(const ideal id, const ring r);
53
54/// inplace sorting of the module (ideal) id wrt <_(c,ds)
55void Sort_c_ds(const ideal id, const ring r);
56
57
58
59
60
61/// Computation attribute storage
62struct SchreyerSyzygyComputationFlags
63{
64    SchreyerSyzygyComputationFlags(idhdl rootRingHdl);
65
66    SchreyerSyzygyComputationFlags(const SchreyerSyzygyComputationFlags& attr):
67        __DEBUG__(attr.__DEBUG__),
68  //      __SYZCHECK__(attr.__SYZCHECK__),
69        __LEAD2SYZ__(attr.__LEAD2SYZ__),  __TAILREDSYZ__(attr.__TAILREDSYZ__),
70        __HYBRIDNF__(attr.__HYBRIDNF__), __IGNORETAILS__(attr.__IGNORETAILS__),
71        __SYZNUMBER__(attr.__SYZNUMBER__), m_rBaseRing(attr.m_rBaseRing)
72    {}   
73
74  /// output all the intermediate states
75  const int __DEBUG__; // DebugOutput;
76
77  //  const bool __SYZCHECK__; // CheckSyzygyProperty: never tested here...
78
79  /// ?
80  const int __LEAD2SYZ__; // TwoLeadingSyzygyTerms;
81
82  /// Reduce syzygy tails wrt the leading syzygy terms
83  const int __TAILREDSYZ__; // TailReducedSyzygies;
84
85  /// Use the usual NF's S-poly reduction while dropping lower order terms
86  /// 2 means - smart selection!
87  const int __HYBRIDNF__; // UseHybridNF
88
89
90  /// ignore tails and compute the pure Schreyer frame
91  const int __IGNORETAILS__; // @IGNORETAILS
92
93  /// Syzygy level (within a resolution)
94  const int __SYZNUMBER__; 
95 
96  /// global base ring
97  const ring m_rBaseRing;
98};
99
100class SchreyerSyzygyComputation;
101
102class CLCM: public SchreyerSyzygyComputationFlags, public std::vector<bool>
103{
104  public:
105    CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags);
106
107    bool Check(const poly m) const;
108   
109  private:
110    bool m_compute;
111
112    const unsigned int m_N; ///< number of ring variables
113};
114
115
116class CLeadingTerm
117{
118  public: 
119    CLeadingTerm(unsigned int label,  const poly lt, const ring);
120
121  public:
122
123    const unsigned long m_sev; ///< not short exp. vector
124        // NOTE/TODO: either of the following should be enough:
125    const unsigned int  m_label; ///< index in the main L[] + 1
126    const poly          m_lt; ///< the leading term itself L[label-1]
127
128  public:
129    bool DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const;
130    bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const;
131
132  private:
133    // disable the following:
134    CLeadingTerm();
135    CLeadingTerm(const CLeadingTerm&);
136    void operator=(const CLeadingTerm&);
137};
138
139
140// TODO: needs a specialized variant without a component (hash!)
141class CReducerFinder: public SchreyerSyzygyComputationFlags
142{
143  friend class CDivisorEnumerator;
144  friend class CDivisorEnumerator2;
145  private:
146    typedef long TComponentKey;
147    typedef std::vector<const CLeadingTerm*> TReducers;
148    typedef std::map< TComponentKey, TReducers> CReducersHash;
149
150  public:
151    /// goes over all leading terms
152    CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags);
153
154    void Initialize(const ideal L);
155
156    ~CReducerFinder();
157
158    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
159    poly // const_iterator // TODO: return const_iterator it, s.th: it->m_lt is the needed
160    FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
161
162    bool IsDivisible(const poly q) const;
163
164    inline bool IsNonempty() const { return !m_hash.empty(); }
165
166    /// is the term to be "preprocessed" as lower order term or lead to only reducible syzygies...
167    int PreProcessTerm(const poly t, CReducerFinder& syzChecker) const;
168
169    poly FindReducer(const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder& checker) const;
170   
171#ifndef NDEBUG
172    void DebugPrint() const;
173#endif
174   
175  private:
176    ideal m_L; ///< only for debug
177
178    CReducersHash m_hash; // can also be replaced with a vector indexed by components
179
180  private:
181    CReducerFinder(const CReducerFinder&);
182    void operator=(const CReducerFinder&);
183};
184
185extern ideal id_Copy (const ideal, const ring);
186
187
188/** @class SchreyerSyzygyComputation syzextra.h
189 *
190 * Computing syzygies after Schreyer
191 *
192 * Storing/accumulating data during the computation requires some global
193 * object, like this class. Ideally the above global functions should not
194 * be used in favour of this class.
195 *
196 * @sa Schreyer Syzygy Computation Paper & Talk & Python prototype
197 */
198class SchreyerSyzygyComputation: public SchreyerSyzygyComputationFlags
199{
200  friend class CLCM;
201  friend class CReducerFinder;
202 
203  public:
204    /// Construct a global object for given input data (separated into leads & tails)
205    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting):
206        SchreyerSyzygyComputationFlags(setting),
207        m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)), 
208        m_syzLeads(NULL), m_syzTails(NULL), m_LS(NULL),
209        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
210    {
211    }
212
213    /// Construct a global object for given input data (separated into leads & tails)
214    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ideal syzLeads, const SchreyerSyzygyComputationFlags setting):
215        SchreyerSyzygyComputationFlags(setting),
216        m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)), 
217        m_syzLeads(syzLeads), m_syzTails(NULL), m_LS(syzLeads), 
218        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
219    {
220      if( __TAILREDSYZ__ && !__IGNORETAILS__)
221      {
222        if (syzLeads != NULL)
223          m_checker.Initialize(syzLeads);
224//        if( idTails != NULL )
225//          SetUpTailTerms();
226      }
227    }
228
229    /// Destructor should not destruct the resulting m_syzLeads, m_syzTails.
230    ~SchreyerSyzygyComputation(){ CleanUp(); } 
231
232    /// Convert the given ideal of tails into the internal representation (with reducers!)
233    /// Preprocess m_idTails as well...?
234    void SetUpTailTerms();
235   
236    /// Read off the results while detaching them from this object
237    /// NOTE: no copy!
238    inline void ReadOffResult(ideal& syzL, ideal& syzT)
239    {
240      syzL = m_syzLeads; syzT = m_syzTails; 
241
242      m_syzLeads = m_syzTails = NULL; // m_LS ?
243    }
244   
245    /// The main driver function: computes
246    void ComputeSyzygy();
247
248    /// Computes Syz(leads) or only LEAD of it.
249    /// The result is stored into m_syzLeads
250    void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms = true);
251
252    poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2 = NULL) const;
253
254    poly TraverseTail(poly multiplier, const int tail) const;
255
256    // called only from above and from outside (for testing)
257    poly TraverseTail(poly multiplier, poly tail) const;
258
259    // TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ?
260    poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
261
262    //
263    poly TraverseNF(const poly syz_lead, const poly syz_2 = NULL) const;
264
265   
266  public:
267    /// just for testing via the wrapper below
268    inline poly _FindReducer(const poly product, const poly syzterm) const
269        { return m_div.FindReducer(product, syzterm, m_checker); } 
270 private:
271    void CleanUp();
272  protected:
273
274
275    /// just leading terms
276    ideal Compute1LeadingSyzygyTerms();
277
278    /// leading + second terms
279    ideal Compute2LeadingSyzygyTerms();
280
281  private:
282    /// input leading terms
283    const ideal m_idLeads;
284
285    /// input tails
286    const ideal m_idTails;
287
288    /// output (syzygy) leading terms (+2nd terms?)
289    ideal m_syzLeads;
290
291    /// output (syzygy) tails
292    ideal m_syzTails;
293
294    /// Bitmask for variables occuring in leading terms
295    const CLCM m_lcm;
296
297    /// Divisor finder
298    const CReducerFinder m_div;
299
300    /// for checking tail-terms and makeing them irreducible (wrt m_LS!)
301    CReducerFinder m_checker;
302
303    /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
304
305    /*
306    // need more data here:
307    // (m_idLeads : m_tailterm) = (m, pos, compl), s.th: compl * m_tailterm divides m_idLeads[pos]
308    // but resulting sysygy compl * gen(pos) should not be in
309    // Idea: extend CReducerFinder??!!
310    struct CTailTerm
311    {
312      const poly m_tailterm;
313     
314      const CReducerFinder m_reducers; // positions are labels (in m_idLeads)...
315      // compl - to be computed if needed?
316
317      CTailTerm(const poly tt, const CReducerFinder reds): m_tailterm(tt), m_reducers(reds) {}
318    };
319
320    typedef std::vector<const CTailTerm*> TTail;
321    typedef std::vector<TTail> TTailTerms;
322   
323    TTailTerms m_idTailTerms;
324    */
325
326   
327/// TODO: look into m_idTailTerms!!!!!!!!!!!!!!!!!!!!!!!! map? heaps???
328};
329
330
331// The following wrappers are just for testing separate functions on highest level (within schreyer.lib)
332
333static inline void ComputeSyzygy(const ideal L, const ideal T, ideal& LL, ideal& TT, const SchreyerSyzygyComputationFlags A)
334{
335  SchreyerSyzygyComputation syz(L, T, A);
336  syz.ComputeSyzygy();
337  syz.ReadOffResult(LL, TT);
338}
339
340static inline ideal ComputeLeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
341{
342  SchreyerSyzygyComputation syz(L, NULL, A);
343  syz.ComputeLeadingSyzygyTerms(false);
344  ideal LL, TT;
345  syz.ReadOffResult(LL, TT);
346  return LL; // assume TT is NULL!
347}
348
349static inline ideal Compute2LeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
350{
351  SchreyerSyzygyComputation syz(L, NULL, A);
352  syz.ComputeLeadingSyzygyTerms(true);
353  ideal LL, TT;
354  syz.ReadOffResult(LL, TT);
355  return LL; // assume TT is NULL!
356}
357
358static inline poly FindReducer(poly product, poly syzterm,
359                               ideal L, ideal LS, const SchreyerSyzygyComputationFlags A)
360{
361  SchreyerSyzygyComputation syz(L, NULL, LS, A);
362  return syz._FindReducer(product, syzterm);
363}
364
365static inline poly TraverseTail(poly multiplier, poly tail, 
366                                ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
367{
368  SchreyerSyzygyComputation syz(L, T, LS, A);
369  return syz.TraverseTail(multiplier, tail);
370}
371
372static inline poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck,
373                              ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
374{
375  SchreyerSyzygyComputation syz(L, T, LS, A);
376  return syz.ReduceTerm(multiplier, term4reduction, syztermCheck);
377}
378
379
380static inline poly SchreyerSyzygyNF(poly syz_lead, poly syz_2,
381                                    ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
382{
383  SchreyerSyzygyComputation syz(L, T, LS, A);
384  return syz.SchreyerSyzygyNF(syz_lead, syz_2);
385}
386
387END_NAMESPACE
388   
389END_NAMESPACE_SINGULARXX
390
391#endif
392/* #ifndef SYZEXTRA_H */
393
394// Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
395
Note: See TracBrowser for help on using the repository browser.