source: git/dyn_modules/syzextra/syzextra.h @ 5cecde

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