source: git/libpolys/polys/kbuckets.h

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