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 | // |
---|
21 | kBucket_pt kBucketCreate(ring r); |
---|
22 | // only free memory allocated for bucket |
---|
23 | void kBucketDestroy(kBucket_pt *bucket); |
---|
24 | // frees polys/monomials in bucket and destroys bucket |
---|
25 | void 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 |
---|
34 | void kBucketInit(kBucket_pt bucket, poly p, int length); |
---|
35 | |
---|
36 | // Converts Bpoly into a poly and clears bucket |
---|
37 | // i.e., afterwards Bpoly == 0 |
---|
38 | void kBucketClear(kBucket_pt bucket, poly *p, int *length); |
---|
39 | inline 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 |
---|
49 | int kBucketCanonicalize(kBucket_pt bucket); |
---|
50 | |
---|
51 | ///////////////////////////////////////////////////////////////////////////// |
---|
52 | // Extracts lm of Bpoly, i.e. Bpoly is changed s.t. |
---|
53 | // Bpoly == Bpoly - Lm(Bpoly) |
---|
54 | // |
---|
55 | inline 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 |
---|
61 | void kBucketSetLm(kBucket_pt bucket, poly lm); |
---|
62 | |
---|
63 | |
---|
64 | ////////////////////////////////////////////////////////////////////////// |
---|
65 | /// |
---|
66 | /// Bucket number i from bucket is out of length sync, resync |
---|
67 | /// |
---|
68 | void 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)) |
---|
77 | number 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 | |
---|
90 | void 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 | /// |
---|
98 | void 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 |
---|
104 | poly 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 | /// |
---|
111 | void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq); |
---|
112 | |
---|
113 | // first, do ExtractLarger |
---|
114 | // then add q |
---|
115 | inline poly |
---|
116 | kBucket_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) |
---|
128 | void 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) |
---|
136 | void 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 | /// |
---|
142 | void 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 |
---|
152 | BOOLEAN 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 | |
---|
172 | class kBucket |
---|
173 | { |
---|
174 | public: |
---|
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 |
---|
190 | inline 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 | // |
---|
202 | inline 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 | |
---|
215 | inline 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 | |
---|
227 | poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i); |
---|
228 | void kBucketSimpleContent(kBucket_pt bucket); |
---|
229 | BOOLEAN kBucketIsCleared(kBucket_pt bucket); |
---|
230 | int ksCheckCoeff(number *a, number *b, const coeffs r); |
---|
231 | #endif /* KBUCKETS_H */ |
---|