source: git/libpolys/polys/kbuckets.h @ 85bcd6

spielwiese
Last change on this file since 85bcd6 was 6ce030f, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
removal of the $Id$ svn tag from everywhere NOTE: the git SHA1 may be used instead (only on special places) NOTE: the libraries Singular/LIB/*.lib still contain the marker due to our current use of svn
  • Property mode set to 100644
File size: 7.0 KB
Line 
1#ifndef KBUCKETS_H
2#define KBUCKETS_H
3/****************************************
4*  Computer Algebra System SINGULAR     *
5****************************************/
6#include <polys/monomials/ring.h>
7#include <polys/templates/p_Procs.h>
8
9//#define HAVE_COEF_BUCKETS
10
11/////////////////////////////////////////////////////////////////////////
12// configuration
13//
14
15// define to not really use the bucket feature
16// #define HAVE_PSEUDO_BUCKETS
17
18//////////////////////////////////////////////////////////////////////////
19// Creation/Destruction of buckets
20//
21kBucket_pt kBucketCreate(ring r);
22// only free memory allocated for bucket
23void kBucketDestroy(kBucket_pt *bucket);
24// frees polys/monomials in bucket and destroys bucket
25void kBucketDeleteAndDestroy(kBucket_pt *bucket);
26
27
28/////////////////////////////////////////////////////////////////////////////
29// Convertion from/to Bpolys
30//
31
32// Converts p into a bucket poly (Bpoly) and destroys p
33// Assumes length <= 0 || pLength(p) == length
34void kBucketInit(kBucket_pt bucket, poly p, int length);
35
36// Converts Bpoly into a poly and clears bucket
37// i.e., afterwards Bpoly == 0
38void kBucketClear(kBucket_pt bucket, poly *p, int *length);
39inline poly kBucketClear(kBucket_pt bucket)
40{
41  int dummy;
42  poly p;
43  kBucketClear(bucket, &p, &dummy);
44  return p;
45}
46
47// Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in
48// one bucket: Returns number of bucket into which it is canonicalized
49int kBucketCanonicalize(kBucket_pt bucket);
50
51/////////////////////////////////////////////////////////////////////////////
52// Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
53// Bpoly == Bpoly - Lm(Bpoly)
54//
55inline poly kBucketExtractLm(kBucket_pt bucket);
56
57/////////////////////////////////////////////////////////////////////////////
58// Sets Lm of Bpoly, i.e. Bpoly is changed s.t.
59// Bpoly = Bpoly + m
60// assumes that m is larger than all monomials of Bpoly
61void kBucketSetLm(kBucket_pt bucket, poly lm);
62
63
64//////////////////////////////////////////////////////////////////////////
65///
66/// Bucket number i from bucket is out of length sync, resync
67///
68void kBucketAdjust(kBucket_pt bucket, int i);
69
70/////////////////////////////////////////////////////////////////////////////
71// Reduces Bpoly (say, q) with p, i.e.:
72// q = (Lc(p) / gcd(Lc(p), Lc(q)))*q - (Lc(q)/gcd(Lc(p),Lc(q)))*p*(Lm(q)/Lm(p))
73// Assumes p1 != NULL, Bpoly != NULL
74//         Lm(p1) divides Lm(Bpoly)
75//         pLength(p1) == l1
76// Returns: Lc(p) / gcd(Lc(p), Lc(q))
77number kBucketPolyRed(kBucket_pt bucket,
78                      poly p, int l,
79                      poly spNoether);
80
81
82/////////////////////////////////////////////////////////////////////////////
83//
84// Extract all monomials from bucket with component comp
85// Return as a polynomial *p with length *l
86// In other words, afterwards
87// Bpoly == Bpoly - (poly consisting of all monomials with component comp)
88// and components of monomials of *p are all 0
89
90void kBucketTakeOutComp(kBucket_pt bucket,
91                        long comp,
92                        poly *p, int *l);
93
94//////////////////////////////////////////////////////////////////////////
95///
96/// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
97///
98void kBucket_Mult_n(kBucket_pt bucket, number n);
99
100//////////////////////////////////////////////////////////////////////////
101///
102/// Extract all monomials of bucket which are larger than q
103/// Append those to append, and return last monomial of append
104poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append);
105
106
107//////////////////////////////////////////////////////////////////////////
108///
109/// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
110///
111void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
112
113// first, do ExtractLarger
114// then add q
115inline poly
116kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
117{
118  append = kBucket_ExtractLarger(bucket, q, append);
119  kBucket_Add_q(bucket, q, lq);
120  return append;
121}
122
123//////////////////////////////////////////////////////////////////////////
124///
125/// Bpoly == Bpoly - m*p; where m is a monom
126/// Does not destroy p and m
127/// assume (*l <= 0 || pLength(p) == *l)
128void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
129                            poly spNother = NULL);
130
131//////////////////////////////////////////////////////////////////////////
132///
133/// Bpoly == Bpoly + m*p; where m is a monom
134/// Does not destroy p and m
135/// assume (l <= 0 || pLength(p) == l)
136void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l);
137
138//////////////////////////////////////////////////////////////////////////
139///
140/// For changing the ring of the Bpoly to new_tailBin
141///
142void kBucketShallowCopyDelete(kBucket_pt bucket,
143                              ring new_tailRing, omBin new_tailBin,
144                              pShallowCopyDeleteProc p_shallow_copy_delete);
145
146//////////////////////////////////////////////////////////////////////////
147///
148/// Tests
149///
150///
151#ifdef KDEBUG
152BOOLEAN kbTest(kBucket_pt bucket);
153#else
154#define kbTest(bucket)  ((void)0)
155#endif
156
157//////////////////////////////////////////////////////////////////////////
158///
159/// Bucket definition (should be no one elses business, though)
160///
161
162// define this if length of bucket polys are 2, 4, 8, etc
163// instead of 4, 16, 64 ... --
164// this seems to be less efficient, both, in theory and in practice
165// #define BUCKET_TWO_BASE
166#ifdef BUCKET_TWO_BASE
167#define MAX_BUCKET 28
168#else
169#define MAX_BUCKET 14 // suitable for polys up to a length of 4^14 = 2^28
170#endif
171
172class kBucket
173{
174public:
175#ifdef HAVE_PSEUDO_BUCKETS
176  poly p;
177  int l;
178#else
179  poly buckets[MAX_BUCKET + 1];        // polys in bucket
180#ifdef HAVE_COEF_BUCKETS
181  poly coef[MAX_BUCKET + 1];        // coeff of polys in bucket or NULL : 2..max
182#endif
183  int  buckets_length[MAX_BUCKET + 1]; // length if i-th poly
184  int buckets_used;                    // max number of used bucket
185#endif
186  ring bucket_ring;
187};
188
189#ifndef HAVE_PSEUDO_BUCKETS
190inline void kBucketAdjustBucketsUsed(kBucket_pt bucket)
191{
192  while ( bucket->buckets_used > 0 &&
193          bucket->buckets[bucket->buckets_used] == NULL)
194    (bucket->buckets_used)--;
195}
196#endif
197
198/////////////////////////////////////////////////////////////////////////////
199// Gets leading monom of bucket, does NOT change Bpoly!!!!!
200// Returned monom is READ ONLY, i.e. no manipulations are allowed !!!!
201//
202inline poly kBucketGetLm(kBucket_pt bucket)
203{
204  #ifdef   HAVE_COEF_BUCKETS
205  assume(bucket->coef[0]==NULL);
206  #endif
207  if (bucket->buckets[0] == NULL)
208    bucket->bucket_ring->p_Procs->p_kBucketSetLm(bucket);
209  #ifdef  HAVE_COEF_BUCKETS
210  assume(bucket->coef[0]==NULL);
211  #endif
212  return bucket->buckets[0];
213}
214
215inline poly kBucketExtractLm(kBucket_pt bucket)
216{
217  poly lm = kBucketGetLm(bucket);
218  #ifdef   HAVE_COEF_BUCKETS
219  assume(bucket->coef[0]==NULL);
220  #endif
221  bucket->buckets[0] = NULL;
222  bucket->buckets_length[0] = 0;
223 
224  return lm;
225}
226
227poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i);
228void kBucketSimpleContent(kBucket_pt bucket);
229BOOLEAN kBucketIsCleared(kBucket_pt bucket);
230int ksCheckCoeff(number *a, number *b, const coeffs r);
231#endif /* KBUCKETS_H */
Note: See TracBrowser for help on using the repository browser.