source: git/dyn_modules/syzextra/syzextra.h @ c81423

jengelh-datetimespielwiese
Last change on this file since c81423 was c81423, checked in by Oleksandr Motsak <motsak@…>, 11 years ago
better condition for running "m_checker.Initialize(m_syzLeads);" in SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms add: CReducerFinder::DebugPrint() for hash output
  • Property mode set to 100644
File size: 9.6 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);
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
62class SchreyerSyzygyComputationFlags
63{
64  public: 
65    SchreyerSyzygyComputationFlags(idhdl rootRingHdl);
66
67    SchreyerSyzygyComputationFlags(const SchreyerSyzygyComputationFlags& attr):
68        __DEBUG__(attr.__DEBUG__),
69  //      __SYZCHECK__(attr.__SYZCHECK__),
70        __LEAD2SYZ__(attr.__LEAD2SYZ__),  __TAILREDSYZ__(attr.__TAILREDSYZ__),
71        __HYBRIDNF__(attr.__HYBRIDNF__), __IGNORETAILS__(attr.__IGNORETAILS__),
72        m_rBaseRing(attr.m_rBaseRing)
73    {}   
74
75  /// output all the intermediate states
76  const bool __DEBUG__; // DebugOutput;
77
78  //  const bool __SYZCHECK__; // CheckSyzygyProperty: never tested here...
79
80  /// ?
81  const bool __LEAD2SYZ__; // TwoLeadingSyzygyTerms;
82
83  /// Reduce syzygy tails wrt the leading syzygy terms
84  const bool __TAILREDSYZ__; // TailReducedSyzygies;
85
86  /// Use the usual NF's S-poly reduction while dropping lower order terms
87  const bool __HYBRIDNF__; // UseHybridNF
88
89
90  /// ignore tails and compute the pure Schreyer frame
91  const bool __IGNORETAILS__; // @IGNORETAILS
92 
93  /// global base ring
94  const ring m_rBaseRing;
95
96};
97
98class SchreyerSyzygyComputation;
99
100class CLCM: public SchreyerSyzygyComputationFlags, public std::vector<bool>
101{
102  public:
103    CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags);
104
105    bool Check(const poly m) const;
106   
107  private:
108    bool m_compute;
109
110    const unsigned int m_N; ///< number of ring variables
111};
112
113
114class CReducerFinder: public SchreyerSyzygyComputationFlags
115{
116  private:
117    class CLeadingTerm
118    {
119      public: 
120        CLeadingTerm(unsigned int id,  const poly p, const ring);
121
122      private:
123        CLeadingTerm();
124
125      public:
126
127        const unsigned long m_sev; ///< not short exp. vector
128        // NOTE/TODO: either of the following should be enough:
129        const unsigned int  m_label; ///< index in the main L[] + 1
130        const poly          m_lt; ///< the leading term itself L[label-1]
131    };
132
133    typedef long TComponentKey;
134    typedef std::vector<const CLeadingTerm*> TReducers;
135    typedef std::map< TComponentKey, TReducers> CReducersHash;
136   
137  public:
138    /// goes over all leading terms
139    CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags);
140
141    void Initialize(const ideal L);
142
143    ~CReducerFinder();
144
145    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?   
146    poly FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
147
148    bool IsDivisible(const poly q) const;
149
150    bool IsNonempty() const { return !m_hash.empty(); }
151
152#ifndef NDEBUG
153    void DebugPrint() const;
154#endif
155   
156  private:
157    ideal m_L; ///< only for debug
158
159    CReducersHash m_hash; // can also be replaced with a vector indexed by components
160};
161
162
163
164/** @class SchreyerSyzygyComputation syzextra.h
165 *
166 * Computing syzygies after Schreyer
167 *
168 * Storing/accumulating data during the computation requires some global
169 * object, like this class. Ideally the above global functions should not
170 * be used in favour of this class.
171 *
172 * @sa Schreyer Syzygy Computation Paper & Talk & Python prototype
173 */
174class SchreyerSyzygyComputation: public SchreyerSyzygyComputationFlags
175{
176  friend class CLCM;
177  friend class CReducerFinder;
178 
179  public:
180
181    /// Construct a global object for given input data (separated into leads & tails)
182    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting):
183        SchreyerSyzygyComputationFlags(setting),
184        m_idLeads(idLeads), m_idTails(idTails), 
185        m_syzLeads(NULL), m_syzTails(NULL), m_LS(NULL),
186        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
187    {
188    }
189
190    /// Construct a global object for given input data (separated into leads & tails)
191    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ideal syzLeads, const SchreyerSyzygyComputationFlags setting):
192        SchreyerSyzygyComputationFlags(setting),
193        m_idLeads(idLeads), m_idTails(idTails), 
194        m_syzLeads(syzLeads), m_syzTails(NULL), m_LS(syzLeads), 
195        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
196    {
197      if( __TAILREDSYZ__ && !__IGNORETAILS__ && syzLeads != NULL )
198        m_checker.Initialize(syzLeads);
199    }
200
201   
202    /// Destructor should not destruct the resulting m_syzLeads, m_syzTails.
203    ~SchreyerSyzygyComputation(){ CleanUp(); }
204
205    /// Read off the results while detaching them from this object
206    /// NOTE: no copy!
207    inline void ReadOffResult(ideal& syzL, ideal& syzT)
208    {
209      syzL = m_syzLeads; syzT = m_syzTails; 
210
211      m_syzLeads = m_syzTails = NULL; // m_LS ?
212    }
213   
214    /// The main driver function: computes
215    void ComputeSyzygy();
216
217    /// Computes Syz(leads) or only LEAD of it.
218    /// The result is stored into m_syzLeads
219    void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms = true);
220
221    poly SchreyerSyzygyNF(poly syz_lead, poly syz_2) const;
222
223    // TODO: store m * @tail -.-^-.-^-.--> ?
224    poly TraverseTail(poly multiplier, poly tail) const;
225
226    // TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ?
227    poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
228
229  public:
230    /// just for testing via the wrapper below
231    inline poly _FindReducer(const poly product, const poly syzterm) const
232        { return m_div.FindReducer(product, syzterm, m_checker); } 
233   
234  protected:
235
236    /// just leading terms
237    ideal Compute1LeadingSyzygyTerms();
238
239    /// leading + second terms
240    ideal Compute2LeadingSyzygyTerms();
241
242    /// Clean up all the accumulated data
243    void CleanUp() {}
244
245  private:
246    /// input leading terms
247    const ideal m_idLeads;
248
249    /// input tails
250    const ideal m_idTails;
251
252    /// output (syzygy) leading terms (+2nd terms?)
253    ideal m_syzLeads;
254
255    /// output (syzygy) tails
256    ideal m_syzTails;
257
258    /// Bitmask for variables occuring in leading terms
259    const CLCM m_lcm;
260
261    /// Divisor finder
262    const CReducerFinder m_div;
263
264    /// for checking tail-terms and makeing them irreducible (wrt m_LS!)
265    CReducerFinder m_checker;
266
267    /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
268};
269
270
271// The following wrappers are just for testing separate functions on highest level (within schreyer.lib)
272
273static inline void ComputeSyzygy(const ideal L, const ideal T, ideal& LL, ideal& TT, const SchreyerSyzygyComputationFlags A)
274{
275  SchreyerSyzygyComputation syz(L, T, A);
276  syz.ComputeSyzygy();
277  syz.ReadOffResult(LL, TT);
278}
279
280static inline ideal ComputeLeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
281{
282  SchreyerSyzygyComputation syz(L, NULL, A);
283  syz.ComputeLeadingSyzygyTerms(false);
284  ideal LL, TT;
285  syz.ReadOffResult(LL, TT);
286  return LL; // assume TT is NULL!
287}
288
289static inline ideal Compute2LeadingSyzygyTerms(const ideal& L, const SchreyerSyzygyComputationFlags A)
290{
291  SchreyerSyzygyComputation syz(L, NULL, A);
292  syz.ComputeLeadingSyzygyTerms(true);
293  ideal LL, TT;
294  syz.ReadOffResult(LL, TT);
295  return LL; // assume TT is NULL!
296}
297
298static inline poly FindReducer(poly product, poly syzterm,
299                               ideal L, ideal LS, const SchreyerSyzygyComputationFlags A)
300{
301  SchreyerSyzygyComputation syz(L, NULL, LS, A);
302  return syz._FindReducer(product, syzterm);
303}
304
305static inline poly TraverseTail(poly multiplier, poly tail, 
306                                ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
307{
308  SchreyerSyzygyComputation syz(L, T, LS, A);
309  return syz.TraverseTail(multiplier, tail);
310}
311
312static inline poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck,
313                              ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
314{
315  SchreyerSyzygyComputation syz(L, T, LS, A);
316  return syz.ReduceTerm(multiplier, term4reduction, syztermCheck);
317}
318
319
320static inline poly SchreyerSyzygyNF(poly syz_lead, poly syz_2,
321                                    ideal L, ideal T, ideal LS, const SchreyerSyzygyComputationFlags A)
322{
323  SchreyerSyzygyComputation syz(L, T, LS, A);
324  return syz.SchreyerSyzygyNF(syz_lead, syz_2);
325}
326
327END_NAMESPACE
328   
329END_NAMESPACE_SINGULARXX
330
331#endif
332/* #ifndef SYZEXTRA_H */
333
334// Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
335
Note: See TracBrowser for help on using the repository browser.