Loading...
Searching...
No Matches
p_Mult_q.cc File Reference
`#include "misc/auxiliary.h"`
`#include "factory/factory.h"`
`#include "misc/options.h"`
`#include "coeffs/numbers.h"`
`#include "polys/monomials/p_polys.h"`
`#include "polys/kbuckets.h"`
`#include "polys/clapsing.h"`
`#include "polys/templates/p_Procs.h"`
`#include "polys/templates/p_MemCmp.h"`
`#include "polys/templates/p_MemAdd.h"`
`#include "polys/templates/p_MemCopy.h"`
`#include "polys/flintconv.h"`
`#include "polys/flint_mpoly.h"`
`#include "p_Mult_q.h"`

Go to the source code of this file.

## Macros

#define | MIN_LENGTH_MAX 81
#define | MIN_FLINT_QQ 60
#define | MIN_FLINT_Zp 80
#define | MIN_FLINT_Z 60

## Functions

BOOLEAN | pqLength (poly p, poly q, int &lp, int &lq, const int min)
| return TRUE and lp == pLength(p), lq == pLength(q), if min(pLength(p), pLength(q)) >= min FALSE if min(pLength(p), pLength(q)) < min and lp >= lq if pLength(p) >= pLength(lq) lp < lq if pLength(p) < pLength(q)
static void | pqLengthApprox (poly p, poly q, int &lp, int &lq, const int min)
poly | _p_Mult_q_Bucket (poly p, const int lp, poly q, const int lq, const int copy, const ring r)
poly | _p_Mult_q_Normal_ZeroDiv (poly p, poly q, const int copy, const ring r)
poly | _p_Mult_q_Normal (poly p, poly q, const int copy, const ring r)
poly | _p_Mult_q (poly p, poly q, const int copy, const ring r)
| Returns: p * q, Destroys: if !copy then p, q Assumes: pLength(p) >= 2 pLength(q) >=2, !rIsPluralRing(r), nCoeff_is_Domain.

## Macro Definition Documentation

## MIN_FLINT_QQ

#define MIN_FLINT_QQ 60

Definition at line 302 of file p_Mult_q.cc.

## MIN_FLINT_Z

#define MIN_FLINT_Z 60

Definition at line 304 of file p_Mult_q.cc.

## MIN_FLINT_Zp

#define MIN_FLINT_Zp 80

Definition at line 303 of file p_Mult_q.cc.

## MIN_LENGTH_MAX

#define MIN_LENGTH_MAX 81

Definition at line 301 of file p_Mult_q.cc.

## Function Documentation

## _p_Mult_q()

poly _p_Mult_q | ( | poly | p,
|  | poly | q,
|  | const int | copy,
|  | const ring | r )

Returns: p * q, Destroys: if !copy then p, q Assumes: pLength(p) >= 2 pLength(q) >=2, !rIsPluralRing(r), nCoeff_is_Domain.

Definition at line 309 of file p_Mult_q.cc.

{
assume(r != NULL);
int lp=0, lq=0;
poly pt;
BOOLEAN pure_polys=(p_GetComp(p,r)==0) && (p_GetComp(q,r)==0);
#ifdef HAVE_FLINT
#if __FLINT_RELEASE >= 20503
if (pure_polys)
{
pqLengthApprox(p, q, lp, lq, MIN_LENGTH_MAX);
if (lp < lq)
{
int l;
pt = p;
p = q;
q = pt;
l = lp;
lp = lq;
lq = l;
}
if ((lq>MIN_FLINT_QQ) && rField_is_Q(r))
{
fmpq_mpoly_ctx_t ctx;
if (!convSingRFlintR(ctx,r))
{
// lq is a lower bound for the length of p and q
poly res=Flint_Mult_MP(p,lq,q,lq,ctx,r);
if (!copy)
{
p_Delete(&p,r);
p_Delete(&q,r);
}
return res;
}
}
else if ((lq>MIN_FLINT_Zp) && rField_is_Zp(r))
{
nmod_mpoly_ctx_t ctx;
if (!convSingRFlintR(ctx,r))
{
// lq is a lower bound for the length of p and q
poly res=Flint_Mult_MP(p,lq,q,lq,ctx,r);
if (!copy)
{
p_Delete(&p,r);
p_Delete(&q,r);
}
return res;
}
}
else if ((lq>MIN_FLINT_Z) && rField_is_Z(r))
{
fmpz_mpoly_ctx_t ctx;
if (!convSingRFlintR(ctx,r))
{
// lq is a lower bound for the length of p and q
poly res=Flint_Mult_MP(p,lq,q,lq,ctx,r);
if (!copy)
{
p_Delete(&p,r);
p_Delete(&q,r);
}
return res;
}
}
}
#endif
#endif
if (lp==0)
pqLengthApprox(p, q, lp, lq, MIN_LENGTH_BUCKET);
if (lp < lq)
{
int l;
pt = p;
p = q;
q = pt;
l = lp;
lp = lq;
lq = l;
}
if (lq < MIN_LENGTH_BUCKET || TEST_OPT_NOT_BUCKETS)
return _p_Mult_q_Normal(p, q, copy, r);
#if 0
else if (pure_polys
&& ((r->cf->extRing==NULL)||(r->cf->extRing->qideal!=NULL))
/* exclude trans. extensions: may contain rat.funct as cf */
&& (lq >= MIN_LENGTH_FACTORY)
&& (r->cf->convSingNFactoryN!=ndConvSingNFactoryN))
{
poly h=singclap_pmult(p,q,r);
if (!copy)
{
p_Delete(&p,r);
p_Delete(&q,r);
}
return h;
}
#endif
else
{
lp=pLength(p);
lq=pLength(q);
if (lp < lq)
{
int l;
pt = p;
p = q;
q = pt;
l = lp;
lp = lq;
lq = l;
}
return _p_Mult_q_Bucket(p, lp, q, lq, copy, r);
}
}
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
l
int l
Definition cfEzgcd.cc:100
p
int p
Definition cfModGcd.cc:4086
singclap_pmult
poly singclap_pmult(poly f, poly g, const ring r)
Definition clapsing.cc:597
res
CanonicalForm res
Definition facAbsFact.cc:60
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition facFqBivarUtil.cc:364
h
STATIC_VAR Poly * h
Definition janet.cc:971
assume
#define assume(x)
Definition mod2.h:389
p_GetComp
#define p_GetComp(p, r)
Definition monomials.h:64
lq
Definition lq.h:40
ndConvSingNFactoryN
CanonicalForm ndConvSingNFactoryN(number, BOOLEAN, const coeffs)
Definition numbers.cc:313
NULL
#define NULL
Definition omList.c:12
TEST_OPT_NOT_BUCKETS
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
pqLengthApprox
static void pqLengthApprox(poly p, poly q, int &lp, int &lq, const int min)
Definition p_Mult_q.cc:69
_p_Mult_q_Normal
poly _p_Mult_q_Normal(poly p, poly q, const int copy, const ring r)
Definition p_Mult_q.cc:223
MIN_FLINT_Z
#define MIN_FLINT_Z
Definition p_Mult_q.cc:304
_p_Mult_q_Bucket
poly _p_Mult_q_Bucket(poly p, const int lp, poly q, const int lq, const int copy, const ring r)
Definition p_Mult_q.cc:100
MIN_LENGTH_MAX
#define MIN_LENGTH_MAX
Definition p_Mult_q.cc:301
MIN_FLINT_QQ
#define MIN_FLINT_QQ
Definition p_Mult_q.cc:302
MIN_FLINT_Zp
#define MIN_FLINT_Zp
Definition p_Mult_q.cc:303
MIN_LENGTH_BUCKET
#define MIN_LENGTH_BUCKET
Definition p_Mult_q.h:21
pLength
static int pLength(poly a)
Definition p_polys.h:190
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
rField_is_Z
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515
rField_is_Zp
static BOOLEAN rField_is_Zp(const ring r)
Definition ring.h:506
rField_is_Q
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:512

## _p_Mult_q_Bucket()

poly _p_Mult_q_Bucket | ( | poly | p,
|  | const int | lp,
|  | poly | q,
|  | const int | lq,
|  | const int | copy,
|  | const ring | r )

Definition at line 100 of file p_Mult_q.cc.

{
assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
pAssume1(! pHaveCommonMonoms(p, q));
assume(!rField_is_Ring(r) || rField_is_Domain(r));
assume(lp >= 1 && lq >= 1);
p_Test(p, r);
p_Test(q, r);
poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
poly qq = pNext(q); // we iter of this
poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
poly pp = pNext(p); // used for Lm(qq)*pp
poly rr = res; // last monom which is surely not NULL
poly rn = pNext(res); // pNext(rr)
number n, n1;
kBucket_pt bucket = kBucketCreate(r);
// initialize bucket
kBucketInit(bucket, pNext(rn), lp - 2);
pNext(rn) = NULL;
// now the main loop
Top:
if (rn == NULL) goto Smaller;
p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
Greater:
// rn > qn, so iter
rr = rn;
pNext(rn) = kBucketExtractLm(bucket);
pIter(rn);
goto Top;
// rn < qn, append qn to rr, and compute next Lm(qq)*pp
Smaller:
pNext(rr) = qn;
rr = qn;
pIter(qn);
Work: // compute res + Lm(qq)*pp
if (rn == NULL)
{
pNext(rr) = pp_Mult_mm(pp, qq, r);
kBucketInit(bucket, pNext(pNext(rr)), lp - 2);
pNext(pNext(rr)) = NULL;
}
else
{
kBucketSetLm(bucket, rn);
kBucket_Plus_mm_Mult_pp(bucket, qq, pp, lp - 1);
pNext(rr) = kBucketExtractLm(bucket);
}
pIter(qq);
if (qq == NULL) goto Finish;
rn = pNext(rr);
goto Top;
Equal:
n1 = pGetCoeff(rn);
n = n_Add(n1, pGetCoeff(qn), r->cf);
n_Delete(&n1, r->cf);
if (n_IsZero(n, r->cf))
{
n_Delete(&n, r->cf);
p_LmFree(rn, r);
}
else
{
pSetCoeff0(rn, n);
rr = rn;
}
rn = kBucketExtractLm(bucket);
n_Delete(&pGetCoeff(qn),r->cf);
qn = p_LmFreeAndNext(qn, r);
goto Work;
Finish:
assume(rr != NULL && pNext(rr) != NULL);
pNext(pNext(rr)) = kBucketClear(bucket);
kBucketDestroy(&bucket);
if (!copy)
{
p_Delete(&p, r);
p_Delete(&q, r);
}
p_Test(res, r);
return res;
}
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
n_Add
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition coeffs.h:653
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:470
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
Equal
static BOOLEAN Equal(number a, number b, const coeffs)
Definition flintcf_Q.cc:381
Greater
static bool Greater(mono_type m1, mono_type m2)
Definition interpolation.cc:285
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:216
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition kbuckets.cc:493
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition kbuckets.cc:511
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
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
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
pAssume1
#define pAssume1(cond)
Definition monomials.h:171
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1033
p_LmCmpAction
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition p_polys.h:1740
p_LmFreeAndNext
static poly p_LmFreeAndNext(poly p, ring)
Definition p_polys.h:713
p_LmFree
static void p_LmFree(poly p, ring)
Definition p_polys.h:685
pHaveCommonMonoms
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition pDebug.cc:174
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:493
kBucket_pt
kBucket * kBucket_pt
Definition ring.h:26
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491

## _p_Mult_q_Normal()

poly _p_Mult_q_Normal | ( | poly | p,
|  | poly | q,
|  | const int | copy,
|  | const ring | r )

Definition at line 223 of file p_Mult_q.cc.

{
assume(r != NULL);
assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
#ifdef HAVE_RINGS
assume(nCoeff_is_Domain(r->cf));
#endif
pAssume1(! p_HaveCommonMonoms(p, q, r));
p_Test(p, r);
p_Test(q, r);
poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
poly qq = pNext(q); // we iter of this
poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
poly pp = pNext(p); // used for Lm(qq)*pp
poly rr = res; // last monom which is surely not NULL
poly rn = pNext(res); // pNext(rr)
number n, n1;
// now the main loop
Top:
if (rn == NULL) goto Smaller;
p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
Greater:
// rn > qn, so iter
rr = rn;
pIter(rn);
goto Top;
// rn < qn, append qn to rr, and compute next Lm(qq)*pp
Smaller:
pNext(rr) = qn;
rr = qn;
pIter(qn);
Work: // compute res + Lm(qq)*pp
if (rn == NULL)
pNext(rr) = pp_Mult_mm(pp, qq, r);
else
{
pNext(rr) = p_Plus_mm_Mult_qq(rn, qq, pp, r);
}
pIter(qq);
if (qq == NULL) goto Finish;
rn = pNext(rr);
goto Top;
Equal:
n1 = pGetCoeff(rn);
n = n_Add(n1, pGetCoeff(qn), r->cf);
n_Delete(&n1, r->cf);
if (n_IsZero(n, r->cf))
{
n_Delete(&n, r->cf);
rn = p_LmFreeAndNext(rn, r);
}
else
{
pSetCoeff0(rn, n);
rr = rn;
pIter(rn);
}
n_Delete(&pGetCoeff(qn),r->cf);
qn = p_LmFreeAndNext(qn, r);
goto Work;
Finish:
if (!copy)
{
p_Delete(&p, r);
p_Delete(&q, r);
}
p_Test(res, r);
return res;
}
nCoeff_is_Domain
static FORCE_INLINE BOOLEAN nCoeff_is_Domain(const coeffs r)
returns TRUE, if r is a field or r has no zero divisors (i.e is a domain)
Definition coeffs.h:736
p_Plus_mm_Mult_qq
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition p_polys.h:1204

## _p_Mult_q_Normal_ZeroDiv()

poly _p_Mult_q_Normal_ZeroDiv | ( | poly | p,
|  | poly | q,
|  | const int | copy,
|  | const ring | r )

Definition at line 195 of file p_Mult_q.cc.

{
assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
pAssume1(! pHaveCommonMonoms(p, q));
p_Test(p, r);
p_Test(q, r);
poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
poly qq = pNext(q); // we iter of this
while (qq != NULL)
{
res = p_Plus_mm_Mult_qq(res, qq, p, r);
pIter(qq);
}
if (!copy)
{
p_Delete(&p, r);
p_Delete(&q, r);
}
p_Test(res, r);
return res;
}

## pqLength()

BOOLEAN pqLength | ( | poly | p,
|  | poly | q,
|  | int & | lp,
|  | int & | lq,
|  | const int | min )

return TRUE and lp == pLength(p), lq == pLength(q), if min(pLength(p), pLength(q)) >= min FALSE if min(pLength(p), pLength(q)) < min and lp >= lq if pLength(p) >= pLength(lq) lp < lq if pLength(p) < pLength(q)

Definition at line 31 of file p_Mult_q.cc.

{
int l = 0;
do
{
if (p == NULL)
{
lp = l;
if (l < min)
{
if (q != NULL)
lq = l+1;
else
lq = l;
return FALSE;
}
lq = l + pLength(q);
return TRUE;
}
pIter(p);
if (q == NULL)
{
lq = l;
if (l < min)
{
lp = l+1;
return FALSE;
}
lp = l + 1 + pLength(p);
return TRUE;
}
pIter(q);
l++;
}
while (1);
}
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
min
static int min(int a, int b)
Definition fast_mult.cc:268

## pqLengthApprox()

void pqLengthApprox | ( | poly | p,
|  | poly | q,
|  | int & | lp,
|  | int & | lq,
|  | const int | min )

static

Definition at line 69 of file p_Mult_q.cc.

{
int l = 0;
do
{
if (p == NULL)
{
lp=l;
lq=l+(q!=NULL);
return;
}
if (q == NULL) /* && p!=NULL */
{
lp=l+1;
lq=l;
return;
}
if (l>min) /* && p,q!=NULL */
{
lp=l; lq=l;
return;
}
pIter(p);
pIter(q);
l++;
}
while (1);
}