kbuckets.h
Go to the documentation of this file.
1 #ifndef KBUCKETS_H
2 #define KBUCKETS_H
3 /****************************************
4 * Computer Algebra System SINGULAR *
5 ****************************************/
6 
7 //#define HAVE_COEF_BUCKETS
8 
9 /////////////////////////////////////////////////////////////////////////
10 // configuration
11 //
12 
13 // define to not really use the bucket feature
14 // #define HAVE_PSEUDO_BUCKETS
15 class kBucket; typedef kBucket* kBucket_pt;
16 struct spolyrec; typedef struct spolyrec polyrec; typedef polyrec* poly;
17 struct ip_sring; typedef struct ip_sring* ring; typedef struct ip_sring const* const_ring;
18 
19 #include <polys/monomials/ring.h> // for ring->p_Procs->p_kBucketSetLm!
20 #include <polys/templates/p_Procs.h> // for p_kBucketSetLm_Proc_Ptr
21 
22 //////////////////////////////////////////////////////////////////////////
23 // Creation/Destruction of buckets
24 //
25 kBucket_pt kBucketCreate(const ring r);
26 // only free memory allocated for bucket
28 // frees polys/monomials in bucket and destroys bucket
30 
31 
32 /////////////////////////////////////////////////////////////////////////////
33 // Convertion from/to Bpolys
34 //
35 
36 // Converts p into a bucket poly (Bpoly) and destroys p
37 // Assumes length <= 0 || pLength(p) == length
38 void kBucketInit(kBucket_pt bucket, poly p, int length);
39 
40 // Converts Bpoly into a poly and clears bucket
41 // i.e., afterwards Bpoly == 0
42 void kBucketClear(kBucket_pt bucket, poly *p, int *length);
43 
45 {
46  int dummy;
47  poly p;
48  kBucketClear(bucket, &p, &dummy);
49  return p;
50 }
51 
52 // Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in
53 // one bucket: Returns number of bucket into which it is canonicalized
55 
56 /////////////////////////////////////////////////////////////////////////////
57 // Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
58 // Bpoly == Bpoly - Lm(Bpoly)
59 //
60 inline poly kBucketExtractLm(kBucket_pt bucket);
61 
62 /////////////////////////////////////////////////////////////////////////////
63 // Sets Lm of Bpoly, i.e. Bpoly is changed s.t.
64 // Bpoly = Bpoly + m
65 // assumes that m is larger than all monomials of Bpoly
66 void kBucketSetLm(kBucket_pt bucket, poly lm);
67 
68 
69 //////////////////////////////////////////////////////////////////////////
70 ///
71 /// Bucket number i from bucket is out of length sync, resync
72 ///
73 void kBucketAdjust(kBucket_pt bucket, int i);
74 
75 /////////////////////////////////////////////////////////////////////////////
76 // Reduces Bpoly (say, q) with p, i.e.:
77 // q = (Lc(p) / gcd(Lc(p), Lc(q)))*q - (Lc(q)/gcd(Lc(p),Lc(q)))*p*(Lm(q)/Lm(p))
78 // Assumes p1 != NULL, Bpoly != NULL
79 // Lm(p1) divides Lm(Bpoly)
80 // pLength(p1) == l1
81 // Returns: Lc(p) / gcd(Lc(p), Lc(q))
82 number kBucketPolyRed(kBucket_pt bucket,
83  poly p, int l,
84  poly spNoether);
85 
86 
87 /////////////////////////////////////////////////////////////////////////////
88 //
89 // Extract all monomials from bucket with component comp
90 // Return as a polynomial *p with length *l
91 // In other words, afterwards
92 // Bpoly == Bpoly - (poly consisting of all monomials with component comp)
93 // and components of monomials of *p are all 0
94 
95 void kBucketTakeOutComp(kBucket_pt bucket,
96  long comp,
97  poly *p, int *l);
98 
99 //////////////////////////////////////////////////////////////////////////
100 ///
101 /// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
102 ///
103 void kBucket_Mult_n(kBucket_pt bucket, number n);
104 
105 //////////////////////////////////////////////////////////////////////////
106 ///
107 /// Extract all monomials of bucket which are larger than q
108 /// Append those to append, and return last monomial of append
110 
111 
112 //////////////////////////////////////////////////////////////////////////
113 ///
114 /// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
115 ///
116 void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
117 
118 // first, do ExtractLarger
119 // then add q
120 inline poly
122 {
123  append = kBucket_ExtractLarger(bucket, q, append);
124  kBucket_Add_q(bucket, q, lq);
125  return append;
126 }
127 
128 //////////////////////////////////////////////////////////////////////////
129 ///
130 /// Bpoly == Bpoly - m*p; where m is a monom
131 /// Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?)
132 /// assume (*l <= 0 || pLength(p) == *l)
133 void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
134  poly spNother = NULL);
135 
136 //////////////////////////////////////////////////////////////////////////
137 ///
138 /// Bpoly == Bpoly + m*p; where m is a monom
139 /// Does not destroy p and m
140 /// assume (l <= 0 || pLength(p) == l)
141 void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l);
142 
143 //////////////////////////////////////////////////////////////////////////
144 ///
145 /// For changing the ring of the Bpoly to new_tailBin
146 ///
148  ring new_tailRing, omBin new_tailBin,
149  pShallowCopyDeleteProc p_shallow_copy_delete);
150 
151 //////////////////////////////////////////////////////////////////////////
152 ///
153 /// Tests
154 ///
155 ///
156 #ifdef KDEBUG
157 BOOLEAN kbTest(kBucket_pt bucket);
158 #else
159 #define kbTest(bucket) do {} while (0)
160 #endif
161 
162 //////////////////////////////////////////////////////////////////////////
163 ///
164 /// Bucket definition (should be no one elses business, though)
165 ///
166 
167 // define this if length of bucket polys are 2, 4, 8, etc
168 // instead of 4, 16, 64 ... --
169 // this seems to be less efficient, both, in theory and in practice
170 // #define BUCKET_TWO_BASE
171 #ifdef BUCKET_TWO_BASE
172 #define MAX_BUCKET 28
173 #else
174 #define MAX_BUCKET 14 // suitable for polys up to a length of 4^14 = 2^28
175 #endif
176 
177 class kBucket
178 {
179 public:
180 #ifdef HAVE_PSEUDO_BUCKETS
182  int l;
183 #else
184  poly buckets[MAX_BUCKET + 1]; // polys in bucket
185 #ifdef HAVE_COEF_BUCKETS
186  poly coef[MAX_BUCKET + 1]; // coeff of polys in bucket or NULL : 2..max
187 #endif
188  int buckets_length[MAX_BUCKET + 1]; // length if i-th poly
189  int buckets_used; // max number of used bucket
190 #endif
192 };
193 
194 #ifndef HAVE_PSEUDO_BUCKETS
195 static inline void kBucketAdjustBucketsUsed(kBucket_pt bucket)
196 {
197  while ( bucket->buckets_used > 0 &&
198  bucket->buckets[bucket->buckets_used] == NULL)
199  (bucket->buckets_used)--;
200 }
201 #endif
202 
203 /////////////////////////////////////////////////////////////////////////////
204 // Gets leading monom of bucket, does NOT change Bpoly!!!!!
205 // Returned monom is READ ONLY, i.e. no manipulations are allowed !!!!
206 //
207 inline poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
208 {
209 #ifdef HAVE_COEF_BUCKETS
210  assume(bucket->coef[0]==NULL);
211 #endif
212 
213  poly& lead = bucket->buckets[0];
214 
215  if (lead == NULL)
216  _p_kBucketSetLm(bucket);
217 
218 #ifdef HAVE_COEF_BUCKETS
219  assume(bucket->coef[0]==NULL);
220 #endif
221 
222  return lead;
223 }
224 
226 {
227  return kBucketGetLm(bucket, bucket->bucket_ring->p_Procs->p_kBucketSetLm); // TODO: needs ring :(
228 }
229 
231 {
232  poly lm = kBucketGetLm(bucket);
233  #ifdef HAVE_COEF_BUCKETS
234  assume(bucket->coef[0]==NULL);
235  #endif
236  bucket->buckets[0] = NULL;
237  bucket->buckets_length[0] = 0;
238 
239  return lm;
240 }
241 
243 void kBucketSimpleContent(kBucket_pt bucket);
245 int ksCheckCoeff(number *a, number *b, const coeffs r);
246 #endif /* KBUCKETS_H */
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
poly kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
Definition: kbuckets.h:121
void kBucketShallowCopyDelete(kBucket_pt bucket, ring new_tailRing, omBin new_tailBin, pShallowCopyDeleteProc p_shallow_copy_delete)
For changing the ring of the Bpoly to new_tailBin.
Definition: kbuckets.cc:509
const poly a
Definition: syzextra.cc:212
omBin_t * omBin
Definition: omStructs.h:12
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:539
void kBucketSimpleContent(kBucket_pt bucket)
Definition: kbuckets.cc:1154
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l) ...
Definition: kbuckets.cc:795
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:181
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:495
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition: kbuckets.cc:1249
return P p
Definition: myNF.cc:203
kBucket * kBucket_pt
Definition: kbuckets.h:15
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNother=NULL)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m (TODO: rename into kBucket_Minus_mm...
Definition: kbuckets.cc:690
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:174
Definition: ring.h:255
void kBucketInit(kBucket_pt bucket, poly p, int length)
Definition: kbuckets.cc:467
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.h:230
void kBucket_Add_q(kBucket_pt bucket, poly q, int *lq)
Add to Bucket a poly ,i.e. Bpoly == Bpoly + q.
Definition: kbuckets.cc:628
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
kBucket_pt kBucketCreate(const ring r)
Creation/Destruction of buckets.
Definition: kbuckets.cc:193
void kBucketDeleteAndDestroy(kBucket_pt *bucket)
Definition: kbuckets.cc:207
const ring r
Definition: syzextra.cc:208
polyrec * poly
Definition: kbuckets.h:16
void kBucketDestroy(kBucket_pt *bucket)
Definition: kbuckets.cc:200
ring bucket_ring
Definition: kbuckets.h:191
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:572
#define assume(x)
Definition: mod2.h:394
The main handler for Singular numbers which are suitable for Singular polynomials.
void kBucketSetLm(kBucket_pt bucket, poly lm)
P bucket
Definition: myNF.cc:79
int m
Definition: cfEzgcd.cc:119
poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
Extract all monomials of bucket which are larger than q Append those to append, and return last monom...
Definition: kbuckets.cc:978
int i
Definition: cfEzgcd.cc:123
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *p, int *l)
Definition: kbuckets.cc:1012
void(* p_kBucketSetLm_Proc_Ptr)(kBucket_pt bucket)
Definition: p_Procs.h:43
poly(* pShallowCopyDeleteProc)(poly s_p, ring source_r, ring dest_r, omBin dest_bin)
returns a poly from dest_r which is a ShallowCopy of s_p from source_r assumes that source_r->N == de...
Definition: ring.h:52
poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
Definition: kbuckets.h:207
#define NULL
Definition: omList.c:10
int l
Definition: kbuckets.h:182
poly p
Definition: kbuckets.h:181
#define const
Definition: fegetopt.c:41
number kBucketPolyRed(kBucket_pt bucket, poly p, int l, poly spNoether)
Definition: kbuckets.cc:1053
polyrec * poly
Definition: hilb.h:10
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
int BOOLEAN
Definition: auxiliary.h:85
int kBucketCanonicalize(kBucket_pt bucket)
const poly b
Definition: syzextra.cc:213
int l
Definition: cfEzgcd.cc:94
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition: kbuckets.cc:1298