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

jengelh-datetimespielwiese
Last change on this file since 026171 was 026171, checked in by Oleksandr Motsak <motsak@…>, 11 years ago
introduced a bitmask of `leading` variables NOTE: this is the 2nd Schreyer's optimization idea chg: further removal of unused variables
  • Property mode set to 100644
File size: 7.5 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
21// include basic definitions
22#include "singularxx_defs.h"
23
24struct  spolyrec;
25typedef struct spolyrec    polyrec;
26typedef polyrec *          poly;
27
28struct ip_sring;
29typedef struct ip_sring *         ring;
30
31struct sip_sideal;
32typedef struct sip_sideal *       ideal;
33
34class idrec;
35typedef idrec *   idhdl;
36
37BEGIN_NAMESPACE_SINGULARXX    BEGIN_NAMESPACE(SYZEXTRA)
38
39poly leadmonom(const poly p, const ring r);
40
41/// return the tail of a given polynomial or vector
42/// returns NULL if input is NULL, otherwise
43/// the result is a new polynomial/vector in the ring r
44poly p_Tail(const poly p, const ring r);
45
46
47/// return the tail of a given ideal or module
48/// returns NULL if input is NULL, otherwise
49/// the result is a new ideal/module in the ring r
50/// NOTE: the resulting rank is autocorrected
51ideal id_Tail(const ideal id, const ring r);
52
53/// inplace sorting of the module (ideal) id wrt <_(c,ds)
54void Sort_c_ds(const ideal id, const ring r);
55
56
57
58
59
60/// Computation attribute storage
61struct SchreyerSyzygyComputationFlags
62{
63  SchreyerSyzygyComputationFlags(idhdl rootRingHdl);
64 
65  /// output all the intermediate states
66  const bool __DEBUG__; // DebugOutput;
67
68  /// ?
69  const bool __SYZCHECK__; // CheckSyzygyProperty;
70
71  /// ?
72  const bool __LEAD2SYZ__; // TwoLeadingSyzygyTerms;
73
74  /// Reduce syzygy tails wrt the leading syzygy terms
75  const bool __TAILREDSYZ__; // TailReducedSyzygies;
76
77  /// Use the usual NF's S-poly reduction while dropping lower order terms
78  const bool __HYBRIDNF__; // UseHybridNF
79
80};
81
82class SchreyerSyzygyComputation;
83
84class CLCM: public std::vector<bool>
85{
86  public:
87    CLCM(const SchreyerSyzygyComputation& data);
88
89    bool Check(const poly m) const;
90   
91  private:
92    const SchreyerSyzygyComputation& m_data;
93
94    bool m_compute;
95};
96
97
98/** @class SchreyerSyzygyComputation syzextra.h
99 *
100 * Computing syzygies after Schreyer
101 *
102 * Storing/accumulating data during the computation requires some global
103 * object, like this class. Ideally the above global functions should not
104 * be used in favour of this class.
105 *
106 * @sa Schreyer Syzygy Computation Paper & Talk & Python prototype
107 */
108class SchreyerSyzygyComputation
109{
110  friend class CLCM;
111 
112  public:
113
114    /// Construct a global object for given input data (separated into leads & tails)
115    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ring rBaseRing, const SchreyerSyzygyComputationFlags attribues):
116        m_rBaseRing(rBaseRing),
117        m_idLeads(idLeads), m_idTails(idTails), 
118        m_syzLeads(NULL), m_syzTails(NULL), m_LS(NULL), m_atttributes(attribues),
119        m_lcm(*this)
120    {
121    }
122
123
124    /// Construct a global object for given input data (separated into leads & tails)
125    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const ideal syzLeads, const ring rBaseRing, const SchreyerSyzygyComputationFlags attribues):
126        m_rBaseRing(rBaseRing),
127        m_idLeads(idLeads), m_idTails(idTails), 
128        m_syzLeads(NULL), m_syzTails(NULL), m_LS(syzLeads), m_atttributes(attribues),
129        m_lcm(*this)
130    {
131    }
132
133   
134    /// Destructor should not destruct the resulting m_syzLeads, m_syzTails.
135    ~SchreyerSyzygyComputation(){ CleanUp(); }
136
137    /// Read off the results while detaching them from this object
138    /// NOTE: no copy!
139    inline void ReadOffResult(ideal& syzL, ideal& syzT)
140    {
141      syzL = m_syzLeads; syzT = m_syzTails; 
142
143      m_syzLeads = m_syzTails = NULL; // m_LS ?
144    }
145   
146    /// The main driver function: computes
147    void ComputeSyzygy();
148
149    /// Computes Syz(leads) or only LEAD of it.
150    /// The result is stored into m_syzLeads
151    void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms = true);
152
153    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
154    poly FindReducer(poly product, poly syzterm) const;
155   
156    poly SchreyerSyzygyNF(poly syz_lead, poly syz_2) const;
157
158    // TODO: store m * @tail -.-^-.-^-.--> ?
159    poly TraverseTail(poly multiplier, poly tail) const;
160
161    // TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ?
162    poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
163
164  protected:
165
166    /// just leading terms
167    ideal Compute1LeadingSyzygyTerms();
168
169    /// leading + second terms
170    ideal Compute2LeadingSyzygyTerms();
171
172    /// Clean up all the accumulated data
173    void CleanUp() {}
174
175  private:
176    /// global base ring
177    const ring  m_rBaseRing;
178
179    /// input leading terms
180    const ideal m_idLeads;
181
182    /// input tails
183    const ideal m_idTails;
184
185    /// output (syzygy) leading terms (+2nd terms?)
186    ideal m_syzLeads;
187
188    /// output (syzygy) tails
189    ideal m_syzTails;
190
191    /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
192
193    const SchreyerSyzygyComputationFlags m_atttributes;
194
195    /// Bitmask for variables occuring in leading terms
196    const CLCM m_lcm;
197};
198
199
200// The following wrappers are just for testing separate functions on highest level (within schreyer.lib)
201
202static inline void ComputeSyzygy(const ideal L, const ideal T, ideal& LL, ideal& TT, const ring R, const SchreyerSyzygyComputationFlags A)
203{
204  SchreyerSyzygyComputation syz(L, T, R, A);
205  syz.ComputeSyzygy();
206  syz.ReadOffResult(LL, TT);
207}
208
209static inline ideal ComputeLeadingSyzygyTerms(const ideal& L, const ring R, const SchreyerSyzygyComputationFlags A)
210{
211  SchreyerSyzygyComputation syz(L, NULL, R, A);
212  syz.ComputeLeadingSyzygyTerms(false);
213  ideal LL, TT;
214  syz.ReadOffResult(LL, TT);
215  return LL; // assume TT is NULL!
216}
217
218static inline ideal Compute2LeadingSyzygyTerms(const ideal& L, const ring R, const SchreyerSyzygyComputationFlags A)
219{
220  SchreyerSyzygyComputation syz(L, NULL, R, A);
221  syz.ComputeLeadingSyzygyTerms(true);
222  ideal LL, TT;
223  syz.ReadOffResult(LL, TT);
224  return LL; // assume TT is NULL!
225}
226
227static inline poly FindReducer(poly product, poly syzterm,
228                               ideal L, ideal LS, const ring R, const SchreyerSyzygyComputationFlags A)
229{
230  SchreyerSyzygyComputation syz(L, NULL, LS, R, A);
231  return syz.FindReducer(product, syzterm);
232}
233
234static inline poly TraverseTail(poly multiplier, poly tail, 
235                                ideal L, ideal T, ideal LS, const ring R, const SchreyerSyzygyComputationFlags A)
236{
237  SchreyerSyzygyComputation syz(L, T, LS, R, A);
238  return syz.TraverseTail(multiplier, tail);
239}
240
241static inline poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck,
242                              ideal L, ideal T, ideal LS, const ring R, const SchreyerSyzygyComputationFlags A)
243{
244  SchreyerSyzygyComputation syz(L, T, LS, R, A);
245  return syz.ReduceTerm(multiplier, term4reduction, syztermCheck);
246}
247
248
249static inline poly SchreyerSyzygyNF(poly syz_lead, poly syz_2,
250                                    ideal L, ideal T, ideal LS, const ring R, const SchreyerSyzygyComputationFlags A)
251{
252  SchreyerSyzygyComputation syz(L, T, LS, R, A);
253  return syz.SchreyerSyzygyNF(syz_lead, syz_2);
254}
255
256END_NAMESPACE
257   
258END_NAMESPACE_SINGULARXX
259
260#endif
261/* #ifndef SYZEXTRA_H */
262
263// Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
264
Note: See TracBrowser for help on using the repository browser.