Loading...
Searching...
No Matches
kbuckets.h
Go to the documentation of this file.
#ifndef KBUCKETS_H
#define KBUCKETS_H
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
//#define HAVE_COEF_BUCKETS
/////////////////////////////////////////////////////////////////////////
// configuration
//
// define to not really use the bucket feature
// #define HAVE_PSEUDO_BUCKETS
//class kBucket; typedef kBucket* kBucket_pt; // ring.h
#include "polys/monomials/ring.h" // for ring->p_Procs->p_kBucketSetLm!
#include "polys/templates/p_Procs.h" // for p_kBucketSetLm_Proc_Ptr
//////////////////////////////////////////////////////////////////////////
// Creation/Destruction of buckets
//
kBucket_pt kBucketCreate(const ring r);
// only free memory allocated for bucket
void kBucketDestroy(kBucket_pt *bucket);
// frees polys/monomials in bucket and destroys bucket
void kBucketDeleteAndDestroy(kBucket_pt *bucket);
/////////////////////////////////////////////////////////////////////////////
// Conversion from/to Bpolys
//
// Converts p into a bucket poly (Bpoly) and destroys p
// Assumes length <= 0 || pLength(p) == length
void kBucketInit(kBucket_pt bucket, poly p, int length);
// Converts Bpoly into a poly and clears bucket
// i.e., afterwards Bpoly == 0
void kBucketClear(kBucket_pt bucket, poly *p, int *length);
inline poly kBucketClear(kBucket_pt bucket)
{
int dummy;
poly p;
kBucketClear(bucket, &p, &dummy);
return p;
}
/// Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in
/// one bucket: Returns number of bucket into which it is canonicalized
int kBucketCanonicalize(kBucket_pt bucket);
/// apply n_Normalize to all coefficients
void kBucketNormalize(kBucket_pt bucket);
/////////////////////////////////////////////////////////////////////////////
// Extracts lm of Bpoly, i.e. Bpoly is changed s.t.
// Bpoly == Bpoly - Lm(Bpoly)
//
inline poly kBucketExtractLm(kBucket_pt bucket);
/////////////////////////////////////////////////////////////////////////////
// Sets Lm of Bpoly, i.e. Bpoly is changed s.t.
// Bpoly = Bpoly + m
// assumes that m is larger than all monomials of Bpoly
void kBucketSetLm(kBucket_pt bucket, poly lm);
//////////////////////////////////////////////////////////////////////////
///
/// Bucket number i from bucket is out of length sync, resync
///
void kBucketAdjust(kBucket_pt bucket, int i);
/////////////////////////////////////////////////////////////////////////////
// Reduces Bpoly (say, q) with p, i.e.:
// q = (Lc(p) / gcd(Lc(p), Lc(q)))*q - (Lc(q)/gcd(Lc(p),Lc(q)))*p*(Lm(q)/Lm(p))
// Assumes p1 != NULL, Bpoly != NULL
// Lm(p1) divides Lm(Bpoly)
// pLength(p1) == l1
// Returns: Lc(p) / gcd(Lc(p), Lc(q))
number kBucketPolyRed(kBucket_pt bucket,
poly p, int l,
poly spNoether);
void kBucketPolyRedNF(kBucket_pt bucket,
poly p1, int l1,
poly spNoether);
/////////////////////////////////////////////////////////////////////////////
//
// Extract all monomials from bucket with component comp
// Return as a polynomial *p with length *l
// In other words, afterwards
// Bpoly == Bpoly - (poly consisting of all monomials with component comp)
// and components of monomials of *p are all 0
void kBucketTakeOutComp(kBucket_pt bucket,
long comp,
poly *p, int *l);
//////////////////////////////////////////////////////////////////////////
///
/// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
///
void kBucket_Mult_n(kBucket_pt bucket, number n);
//////////////////////////////////////////////////////////////////////////
///
/// Extract all monomials of bucket which are larger than q
/// Append those to append, and return last monomial of append
poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append);
//////////////////////////////////////////////////////////////////////////
///
/// Add to Bucket a poly ,i.e. Bpoly == Bpoly + q
///
void kBucket_Add_q(kBucket_pt bucket, poly q, int* lq);
// first, do ExtractLarger
// then add q
inline poly
kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
{
append = kBucket_ExtractLarger(bucket, q, append);
kBucket_Add_q(bucket, q, lq);
return append;
}
//////////////////////////////////////////////////////////////////////////
///
/// Bpoly == Bpoly - m*p; where m is a monom
/// Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?)
/// assume (*l <= 0 || pLength(p) == *l)
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
/// assume (l <= 0 || pLength(p) == l)
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l);
//////////////////////////////////////////////////////////////////////////
///
/// For changing the ring of the Bpoly to new_tailBin
///
void kBucketShallowCopyDelete(kBucket_pt bucket,
ring new_tailRing, omBin new_tailBin,
pShallowCopyDeleteProc p_shallow_copy_delete);
//////////////////////////////////////////////////////////////////////////
///
/// Tests
///
///
#ifdef KDEBUG
BOOLEAN kbTest(kBucket_pt bucket);
#else
#define kbTest(bucket) do {} while (0)
#endif
//////////////////////////////////////////////////////////////////////////
///
/// Bucket definition (should be no one elses business, though)
///
// define this if length of bucket polys are 2, 4, 8, etc
// instead of 4, 16, 64 ... --
// this seems to be less efficient, both, in theory and in practice
// #define BUCKET_TWO_BASE
#ifdef BUCKET_TWO_BASE
#define MAX_BUCKET 28
#else
#define MAX_BUCKET 14 // suitable for polys up to a length of 4^14 = 2^28
#endif
class kBucket
{
public:
#ifdef HAVE_PSEUDO_BUCKETS
poly p;
int l;
#else
poly buckets[MAX_BUCKET + 1]; // polys in bucket
#ifdef HAVE_COEF_BUCKETS
poly coef[MAX_BUCKET + 1]; // coeff of polys in bucket or NULL : 2..max
#endif
int buckets_length[MAX_BUCKET + 1]; // length if i-th poly
int buckets_used; // max number of used bucket
#endif
ring bucket_ring;
};
#ifndef HAVE_PSEUDO_BUCKETS
static inline void kBucketAdjustBucketsUsed(kBucket_pt bucket)
{
while ( bucket->buckets_used > 0 &&
bucket->buckets[bucket->buckets_used] == NULL)
(bucket->buckets_used)--;
}
#endif
/////////////////////////////////////////////////////////////////////////////
// Gets leading monom of bucket, does NOT change Bpoly!!!!!
// Returned monom is READ ONLY, i.e. no manipulations are allowed !!!!
//
inline poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
{
#ifdef HAVE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
#endif
poly& lead = bucket->buckets[0];
if (lead == NULL)
_p_kBucketSetLm(bucket);
#ifdef HAVE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
#endif
return lead;
}
inline poly kBucketGetLm(kBucket_pt bucket)
{
return kBucketGetLm(bucket, bucket->bucket_ring->p_Procs->p_kBucketSetLm); // TODO: needs ring :(
}
inline poly kBucketExtractLm(kBucket_pt bucket)
{
poly lm = kBucketGetLm(bucket);
#ifdef HAVE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
#endif
bucket->buckets[0] = NULL;
bucket->buckets_length[0] = 0;
return lm;
}
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i);
void kBucketSimpleContent(kBucket_pt bucket);
BOOLEAN kBucketIsCleared(kBucket_pt bucket);
int ksCheckCoeff(number *a, number *b, const coeffs r);
#endif /* KBUCKETS_H */
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
b
CanonicalForm b
Definition cfModGcd.cc:4111
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition facSparseHensel.h:25
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
kBucket::l
int l
Definition kbuckets.h:187
kBucketGetLm
poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
Definition kbuckets.h:212
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
kBucketCreate
kBucket_pt kBucketCreate(const ring r)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
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:660
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition kbuckets.cc:197
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:535
kBucketDeleteAndDestroy
void kBucketDeleteAndDestroy(kBucket_pt *bucket)
Definition kbuckets.cc:223
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
kBucket_Mult_n
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition kbuckets.cc:598
kBucketNormalize
void kBucketNormalize(kBucket_pt bucket)
apply n_Normalize to all coefficients
kBucket_ExtractLarger_Add_q
poly kBucket_ExtractLarger_Add_q(kBucket_pt bucket, poly append, poly q, int *lq)
Definition kbuckets.h:126
kBucketPolyRed
number kBucketPolyRed(kBucket_pt bucket, poly p, int l, poly spNoether)
Definition kbuckets.cc:1071
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
ksCheckCoeff
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition kbuckets.cc:1504
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition kbuckets.h:235
kBucketAdjust
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition kbuckets.cc:565
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:998
kBucketExtractLmOfBucket
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition kbuckets.cc:1455
kBucket::p
poly p
Definition kbuckets.h:186
kBucket::bucket_ring
ring bucket_ring
Definition kbuckets.h:196
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:815
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:722
kBucketTakeOutComp
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *p, int *l)
Definition kbuckets.cc:1032
kBucketPolyRedNF
void kBucketPolyRedNF(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition kbuckets.cc:1188
kBucketIsCleared
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket)
Definition kbuckets.cc:216
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though).
Definition kbuckets.h:179
kBucketSimpleContent
void kBucketSimpleContent(kBucket_pt bucket)
Definition kbuckets.cc:1283
kBucketInit
void kBucketInit(kBucket_pt bucket, poly p, int length)
Definition kbuckets.cc:493
kBucket
Definition kbuckets.h:183
assume
#define assume(x)
Definition mod2.h:389
coeffs
The main handler for Singular numbers which are suitable for Singular polynomials.
lq
Definition lq.h:40
NULL
#define NULL
Definition omList.c:12
omBin
omBin_t * omBin
Definition omStructs.h:12
p_Procs.h
p_kBucketSetLm_Proc_Ptr
void(* p_kBucketSetLm_Proc_Ptr)(kBucket_pt bucket)
Definition p_Procs.h:38
ring.h
kBucket_pt
kBucket * kBucket_pt
Definition ring.h:26
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:45