source: git/kernel/kbuckets.h @ 57bfa2

spielwiese
Last change on this file since 57bfa2 was ba4466, checked in by Hans Schönemann <hannes@…>, 17 years ago
*hannes: debug stuff git-svn-id: file:///usr/local/Singular/svn/trunk@10115 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 7.4 KB
Line 
1#ifndef KBUCKETS_H
2#define KBUCKETS_H
3/****************************************
4*  Computer Algebra System SINGULAR     *
5****************************************/
6/* $Id: kbuckets.h,v 1.7 2007-06-19 09:17:28 Singular Exp $ */
7#include "structs.h"
8#include "p_Procs.h"
9#include "pShallowCopyDelete.h"
10
11//#define HAVE_COEF_BUCKETS
12
13/////////////////////////////////////////////////////////////////////////
14// configuration
15//
16
17// define to not really use the bucket feature
18// #define HAVE_PSEUDO_BUCKETS
19
20//////////////////////////////////////////////////////////////////////////
21// Creation/Destruction of buckets
22//
23kBucket_pt kBucketCreate(ring r = currRing);
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);
41inline poly kBucketClear(kBucket_pt bucket)
42{
43  int dummy;
44  poly p;
45  kBucketClear(bucket, &p, &dummy);
46  return p;
47}
48
49// Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in
50// one bucket: Returns number of bucket into which it is canonicalized
51int kBucketCanonicalize(kBucket_pt bucket);
52
53/////////////////////////////////////////////////////////////////////////////
54// Gets leading monom of bucket, does NOT change Bpoly!!!!!
55// Returned monom is READ ONLY, i.e. no manipulations are allowed !!!!
56//
57inline const poly kBucketGetLm(kBucket_pt bucket);
58
59/////////////////////////////////////////////////////////////////////////////
60// Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
61// Bpoly == Bpoly - Lm(Bpoly)
62//
63inline poly kBucketExtractLm(kBucket_pt bucket);
64
65/////////////////////////////////////////////////////////////////////////////
66// Sets Lm of Bpoly, i.e. Bpoly is changed s.t.
67// Bpoly = Bpoly + m
68// assumes that m is larger than all monomials of Bpoly
69void kBucketSetLm(kBucket_pt bucket, poly lm);
70
71
72//////////////////////////////////////////////////////////////////////////
73///
74/// Bucket number i from bucket is out of length sync, resync
75///
76void kBucketAdjust(kBucket_pt bucket, int i);
77
78/////////////////////////////////////////////////////////////////////////////
79// Reduces Bpoly (say, q) with p, i.e.:
80// q = (Lc(p) / gcd(Lc(p), Lc(q)))*q - (Lc(q)/gcd(Lc(p),Lc(q)))*p*(Lm(q)/Lm(p))
81// Assumes p1 != NULL, Bpoly != NULL
82//         Lm(p1) divides Lm(Bpoly)
83//         pLength(p1) == l1
84// Returns: Lc(p) / gcd(Lc(p), Lc(q))
85number kBucketPolyRed(kBucket_pt bucket,
86                      poly p, int l,
87                      poly spNoether);
88
89
90/////////////////////////////////////////////////////////////////////////////
91//
92// Extract all monomials from bucket with component comp
93// Return as a polynomial *p with length *l
94// In other words, afterwards
95// Bpoly == Bpoly - (poly consisting of all monomials with component comp)
96// and components of monomials of *p are all 0
97
98void kBucketTakeOutComp(kBucket_pt bucket,
99                        Exponent_t comp,
100                        poly *p, int *l);
101
102// Here we only extract such monoms which have component == comp and
103// degree == order
104// ASSUME: monomial ordering is Order compatible, i.e., if m1, m2 Monoms then
105//         m1 >= m2 ==> pGetOrder(m1) >= pGetOrder(m2)
106void kBucketDecrOrdTakeOutComp(kBucket_pt bucket,
107                               Exponent_t comp, Order_t order,
108                               poly *p, int *l);
109
110//////////////////////////////////////////////////////////////////////////
111///
112/// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
113///
114void kBucket_Mult_n(kBucket_pt bucket, number n);
115
116//////////////////////////////////////////////////////////////////////////
117///
118/// Extract all monomials of bucket which are larger than q
119/// Append those to append, and return last monomial of append
120poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append);
121
122
123//////////////////////////////////////////////////////////////////////////
124///
125/// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
126///
127void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
128
129// first, do ExtractLarger
130// then add q
131inline poly
132kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
133{
134  append = kBucket_ExtractLarger(bucket, q, append);
135  kBucket_Add_q(bucket, q, lq);
136  return append;
137}
138
139//////////////////////////////////////////////////////////////////////////
140///
141/// Bpoly == Bpoly - m*p; where m is a monom
142/// Does not destroy p and m
143/// assume (*l <= 0 || pLength(p) == *l)
144void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
145                            poly spNother = NULL);
146
147//////////////////////////////////////////////////////////////////////////
148///
149/// Bpoly == Bpoly + m*p; where m is a monom
150/// Does not destroy p and m
151/// assume (l <= 0 || pLength(p) == l)
152void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l);
153
154//////////////////////////////////////////////////////////////////////////
155///
156/// For changing the ring of the Bpoly to new_tailBin
157///
158void kBucketShallowCopyDelete(kBucket_pt bucket,
159                              ring new_tailRing, omBin new_tailBin,
160                              pShallowCopyDeleteProc p_shallow_copy_delete);
161
162//////////////////////////////////////////////////////////////////////////
163///
164/// Tests
165///
166///
167#ifdef KDEBUG
168BOOLEAN kbTest(kBucket_pt bucket);
169#else
170#define kbTest(bucket)  ((void)0)
171#endif
172
173//////////////////////////////////////////////////////////////////////////
174///
175/// Bucket definition (should be no one elses business, though)
176///
177
178// define this if length of bucket polys are 2, 4, 8, etc
179// instead of 4, 16, 64 ... --
180// this seems to be less efficient, both, in theory and in practice
181// #define BUCKET_TWO_BASE
182#ifdef BUCKET_TWO_BASE
183#define MAX_BUCKET 28
184#else
185#define MAX_BUCKET 14 // suitable for polys up to a length of 4^14 = 2^28
186#endif
187
188class kBucket
189{
190public:
191#ifdef HAVE_PSEUDO_BUCKETS
192  poly p;
193  int l;
194#else
195  poly buckets[MAX_BUCKET + 1];        // polys in bucket
196#ifdef HAVE_COEF_BUCKETS
197  poly coef[MAX_BUCKET + 1];        // coeff of polys in bucket or NULL : 2..max
198#endif
199  int  buckets_length[MAX_BUCKET + 1]; // length if i-th poly
200  int buckets_used;                    // max number of used bucket
201#endif
202  ring bucket_ring;
203};
204
205#ifndef HAVE_PSEUDO_BUCKETS
206inline void kBucketAdjustBucketsUsed(kBucket_pt bucket)
207{
208  while ( bucket->buckets_used > 0 &&
209          bucket->buckets[bucket->buckets_used] == NULL)
210    (bucket->buckets_used)--;
211}
212#endif
213
214inline const poly kBucketGetLm(kBucket_pt bucket)
215{
216  #ifdef   HAVE_COEF_BUCKETS
217  assume(bucket->coef[0]==NULL);
218  #endif
219  if (bucket->buckets[0] == NULL)
220    bucket->bucket_ring->p_Procs->p_kBucketSetLm(bucket);
221  #ifdef  HAVE_COEF_BUCKETS
222  assume(bucket->coef[0]==NULL);
223  #endif
224  return bucket->buckets[0];
225}
226
227inline poly kBucketExtractLm(kBucket_pt bucket)
228{
229  poly lm = kBucketGetLm(bucket);
230  #ifdef   HAVE_COEF_BUCKETS
231  assume(bucket->coef[0]==NULL);
232  #endif
233  bucket->buckets[0] = NULL;
234  bucket->buckets_length[0] = 0;
235 
236  return lm;
237}
238
239poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i);
240void kBucketSimpleContent(kBucket_pt bucket);
241BOOLEAN kBucketIsCleared(kBucket_pt bucket);
242#endif /* KBUCKETS_H */
Note: See TracBrowser for help on using the repository browser.