My Project  debian-1:4.1.1-p2+ds-4build2
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; // 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 //
23 kBucket_pt kBucketCreate(const ring r);
24 // only free memory allocated for bucket
25 void kBucketDestroy(kBucket_pt *bucket);
26 // frees polys/monomials in bucket and destroys 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
36 void kBucketInit(kBucket_pt bucket, poly p, int length);
37 
38 // Converts Bpoly into a poly and clears bucket
39 // i.e., afterwards Bpoly == 0
40 void kBucketClear(kBucket_pt bucket, poly *p, int *length);
41 
42 inline 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
53 
54 /////////////////////////////////////////////////////////////////////////////
55 // Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
56 // Bpoly == Bpoly - Lm(Bpoly)
57 //
58 inline poly kBucketExtractLm(kBucket_pt bucket);
59 
60 /////////////////////////////////////////////////////////////////////////////
61 // Sets Lm of Bpoly, i.e. Bpoly is changed s.t.
62 // Bpoly = Bpoly + m
63 // assumes that m is larger than all monomials of Bpoly
64 void kBucketSetLm(kBucket_pt bucket, poly lm);
65 
66 
67 //////////////////////////////////////////////////////////////////////////
68 ///
69 /// Bucket number i from bucket is out of length sync, resync
70 ///
71 void kBucketAdjust(kBucket_pt bucket, int i);
72 
73 /////////////////////////////////////////////////////////////////////////////
74 // Reduces Bpoly (say, q) with p, i.e.:
75 // q = (Lc(p) / gcd(Lc(p), Lc(q)))*q - (Lc(q)/gcd(Lc(p),Lc(q)))*p*(Lm(q)/Lm(p))
76 // Assumes p1 != NULL, Bpoly != NULL
77 // Lm(p1) divides Lm(Bpoly)
78 // pLength(p1) == l1
79 // Returns: Lc(p) / gcd(Lc(p), Lc(q))
80 number kBucketPolyRed(kBucket_pt bucket,
81  poly p, int l,
82  poly spNoether);
83 
84 
85 /////////////////////////////////////////////////////////////////////////////
86 //
87 // Extract all monomials from bucket with component comp
88 // Return as a polynomial *p with length *l
89 // In other words, afterwards
90 // Bpoly == Bpoly - (poly consisting of all monomials with component comp)
91 // and components of monomials of *p are all 0
92 
93 void kBucketTakeOutComp(kBucket_pt bucket,
94  long comp,
95  poly *p, int *l);
96 
97 //////////////////////////////////////////////////////////////////////////
98 ///
99 /// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
100 ///
101 void kBucket_Mult_n(kBucket_pt bucket, number n);
102 
103 //////////////////////////////////////////////////////////////////////////
104 ///
105 /// Extract all monomials of bucket which are larger than q
106 /// Append those to append, and return last monomial of append
107 poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append);
108 
109 
110 //////////////////////////////////////////////////////////////////////////
111 ///
112 /// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
113 ///
114 void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
115 
116 // first, do ExtractLarger
117 // then add q
118 inline poly
119 kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
120 {
121  append = kBucket_ExtractLarger(bucket, q, append);
122  kBucket_Add_q(bucket, q, lq);
123  return append;
124 }
125 
126 //////////////////////////////////////////////////////////////////////////
127 ///
128 /// Bpoly == Bpoly - m*p; where m is a monom
129 /// Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?)
130 /// assume (*l <= 0 || pLength(p) == *l)
131 void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
132  poly spNother = NULL);
133 
134 //////////////////////////////////////////////////////////////////////////
135 ///
136 /// Bpoly == Bpoly + m*p; where m is a monom
137 /// Does not destroy p and m
138 /// assume (l <= 0 || pLength(p) == l)
139 void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l);
140 
141 //////////////////////////////////////////////////////////////////////////
142 ///
143 /// For changing the ring of the Bpoly to new_tailBin
144 ///
146  ring new_tailRing, omBin new_tailBin,
147  pShallowCopyDeleteProc p_shallow_copy_delete);
148 
149 //////////////////////////////////////////////////////////////////////////
150 ///
151 /// Tests
152 ///
153 ///
154 #ifdef KDEBUG
155 BOOLEAN kbTest(kBucket_pt bucket);
156 #else
157 #define kbTest(bucket) do {} while (0)
158 #endif
159 
160 //////////////////////////////////////////////////////////////////////////
161 ///
162 /// Bucket definition (should be no one elses business, though)
163 ///
164 
165 // define this if length of bucket polys are 2, 4, 8, etc
166 // instead of 4, 16, 64 ... --
167 // this seems to be less efficient, both, in theory and in practice
168 // #define BUCKET_TWO_BASE
169 #ifdef BUCKET_TWO_BASE
170 #define MAX_BUCKET 28
171 #else
172 #define MAX_BUCKET 14 // suitable for polys up to a length of 4^14 = 2^28
173 #endif
174 
175 class kBucket
176 {
177 public:
178 #ifdef HAVE_PSEUDO_BUCKETS
179  poly p;
180  int l;
181 #else
182  poly buckets[MAX_BUCKET + 1]; // polys in bucket
183 #ifdef HAVE_COEF_BUCKETS
184  poly coef[MAX_BUCKET + 1]; // coeff of polys in bucket or NULL : 2..max
185 #endif
186  int buckets_length[MAX_BUCKET + 1]; // length if i-th poly
187  int buckets_used; // max number of used bucket
188 #endif
190 };
191 
192 #ifndef HAVE_PSEUDO_BUCKETS
193 static inline void kBucketAdjustBucketsUsed(kBucket_pt bucket)
194 {
195  while ( bucket->buckets_used > 0 &&
196  bucket->buckets[bucket->buckets_used] == NULL)
197  (bucket->buckets_used)--;
198 }
199 #endif
200 
201 /////////////////////////////////////////////////////////////////////////////
202 // Gets leading monom of bucket, does NOT change Bpoly!!!!!
203 // Returned monom is READ ONLY, i.e. no manipulations are allowed !!!!
204 //
205 inline poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
206 {
207 #ifdef HAVE_COEF_BUCKETS
208  assume(bucket->coef[0]==NULL);
209 #endif
210 
211  poly& lead = bucket->buckets[0];
212 
213  if (lead == NULL)
214  _p_kBucketSetLm(bucket);
215 
216 #ifdef HAVE_COEF_BUCKETS
217  assume(bucket->coef[0]==NULL);
218 #endif
219 
220  return lead;
221 }
222 
223 inline poly kBucketGetLm(kBucket_pt bucket)
224 {
225  return kBucketGetLm(bucket, bucket->bucket_ring->p_Procs->p_kBucketSetLm); // TODO: needs ring :(
226 }
227 
228 inline poly kBucketExtractLm(kBucket_pt bucket)
229 {
230  poly lm = kBucketGetLm(bucket);
231  #ifdef HAVE_COEF_BUCKETS
232  assume(bucket->coef[0]==NULL);
233  #endif
234  bucket->buckets[0] = NULL;
235  bucket->buckets_length[0] = 0;
236 
237  return lm;
238 }
239 
240 poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i);
241 void kBucketSimpleContent(kBucket_pt bucket);
243 int ksCheckCoeff(number *a, number *b, const coeffs r);
244 #endif /* KBUCKETS_H */
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket)
Definition: kbuckets.cc:213
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
kBucketExtractLmOfBucket
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition: kbuckets.cc:1334
p_Procs.h
kBucket_ExtractLarger
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:986
kBucket_Mult_n
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:580
kBucketDeleteAndDestroy
void kBucketDeleteAndDestroy(kBucket_pt *bucket)
Definition: kbuckets.cc:220
kBucket_Plus_mm_Mult_pp
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:803
lq
Definition: lq.h:39
kBucketInit
void kBucketInit(kBucket_pt bucket, poly p, int length)
Definition: kbuckets.cc:475
kBucketAdjust
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:547
kBucketTakeOutComp
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *p, int *l)
Definition: kbuckets.cc:1020
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:172
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
kBucket::l
int l
Definition: kbuckets.h:180
b
CanonicalForm b
Definition: cfModGcd.cc:4044
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:503
kBucketCreate
kBucket_pt kBucketCreate(const ring r)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
ksCheckCoeff
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition: kbuckets.cc:1383
i
int i
Definition: cfEzgcd.cc:125
p_kBucketSetLm_Proc_Ptr
void(* p_kBucketSetLm_Proc_Ptr)(kBucket_pt bucket)
Definition: p_Procs.h:39
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
coeffs
kBucketPolyRed
number kBucketPolyRed(kBucket_pt bucket, poly p, int l, poly spNoether)
Definition: kbuckets.cc:1061
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
kBucketGetLm
poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
Definition: kbuckets.h:205
kBucket_ExtractLarger_Add_q
poly kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
Definition: kbuckets.h:119
ring.h
omBin
omBin_t * omBin
Definition: omStructs.h:12
kBucket_Add_q
void kBucket_Add_q(kBucket_pt bucket, poly q, int *lq)
Add to Bucket a poly ,i.e. Bpoly == Bpoly + q.
Definition: kbuckets.cc:636
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.h:228
kBucket::bucket_ring
ring bucket_ring
Definition: kbuckets.h:189
kBucketSimpleContent
void kBucketSimpleContent(kBucket_pt bucket)
Definition: kbuckets.cc:1162
kBucket::p
poly p
Definition: kbuckets.h:179
m
int m
Definition: cfEzgcd.cc:121
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
kBucketIsCleared
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
l
int l
Definition: cfEzgcd.cc:93
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:194
kBucket
Definition: kbuckets.h:175
p
int p
Definition: cfModGcd.cc:4019
pShallowCopyDeleteProc
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:51
kBucket_Minus_m_Mult_p
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:698
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
kBucketShallowCopyDelete
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:517