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

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