source: git/libpolys/polys/kbuckets.h @ 75e126

spielwiese
Last change on this file since 75e126 was b0ae38, checked in by Hans Schoenemann <hannes@…>, 8 years ago
const for ring par. in buckets
  • Property mode set to 100644
File size: 7.5 KB
Line 
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
15class  kBucket; typedef kBucket* kBucket_pt;
16struct spolyrec; typedef struct spolyrec polyrec; typedef polyrec* poly;
17struct 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//
25kBucket_pt kBucketCreate(const ring r);
26// only free memory allocated for bucket
27void kBucketDestroy(kBucket_pt *bucket);
28// frees polys/monomials in bucket and destroys bucket
29void kBucketDeleteAndDestroy(kBucket_pt *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
38void kBucketInit(kBucket_pt bucket, poly p, int length);
39
40// Converts Bpoly into a poly and clears bucket
41// i.e., afterwards Bpoly == 0
42void kBucketClear(kBucket_pt bucket, poly *p, int *length);
43
44inline poly kBucketClear(kBucket_pt bucket)
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
54int kBucketCanonicalize(kBucket_pt bucket);
55
56/////////////////////////////////////////////////////////////////////////////
57// Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
58// Bpoly == Bpoly - Lm(Bpoly)
59//
60inline 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
66void kBucketSetLm(kBucket_pt bucket, poly lm);
67
68
69//////////////////////////////////////////////////////////////////////////
70///
71/// Bucket number i from bucket is out of length sync, resync
72///
73void 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))
82number 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
95void 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///
103void 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
109poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append);
110
111
112//////////////////////////////////////////////////////////////////////////
113///
114/// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
115///
116void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
117
118// first, do ExtractLarger
119// then add q
120inline poly
121kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
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)
133void 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)
141void 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///
147void kBucketShallowCopyDelete(kBucket_pt bucket,
148                              ring new_tailRing, omBin new_tailBin,
149                              pShallowCopyDeleteProc p_shallow_copy_delete);
150
151//////////////////////////////////////////////////////////////////////////
152///
153/// Tests
154///
155///
156#ifdef KDEBUG
157BOOLEAN 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
177class kBucket
178{
179public:
180#ifdef HAVE_PSEUDO_BUCKETS
181  poly p;
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
191  ring bucket_ring;
192};
193
194#ifndef HAVE_PSEUDO_BUCKETS
195static 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//
207inline 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
225inline poly kBucketGetLm(kBucket_pt bucket)
226{
227  return kBucketGetLm(bucket, bucket->bucket_ring->p_Procs->p_kBucketSetLm); // TODO: needs ring :(
228}
229
230inline poly kBucketExtractLm(kBucket_pt bucket)
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
242poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i);
243void kBucketSimpleContent(kBucket_pt bucket);
244BOOLEAN kBucketIsCleared(kBucket_pt bucket);
245int ksCheckCoeff(number *a, number *b, const coeffs r);
246#endif /* KBUCKETS_H */
Note: See TracBrowser for help on using the repository browser.