My Project
Loading...
Searching...
No Matches
Typedefs | Functions
ppinitialReduction.h File Reference
#include "kernel/structs.h"
#include "tropicalStrategy.h"

Go to the source code of this file.

Typedefs

typedef std::pair< int, int > mark
 
typedef std::vector< std::pair< int, int > > marks
 

Functions

bool isOrderingLocalInT (const ring r)
 
void pReduce (ideal &I, const number p, const ring r)
 
void pReduceInhomogeneous (poly &g, const number p, const ring r)
 
bool ppreduceInitially (ideal I, const ring r, const number p)
 reduces I initially with respect to itself. More...
 

Typedef Documentation

◆ mark

typedef std::pair<int,int> mark

Definition at line 7 of file ppinitialReduction.h.

◆ marks

typedef std::vector<std::pair<int,int> > marks

Definition at line 8 of file ppinitialReduction.h.

Function Documentation

◆ isOrderingLocalInT()

bool isOrderingLocalInT ( const ring  r)

Definition at line 8 of file ppinitialReduction.cc.

9{
10 poly one = p_One(r);
11 poly t = p_One(r);
12 p_SetExp(t,1,1,r);
13 p_Setm(t,r);
14 int s = p_LmCmp(one,t,r);
15 p_Delete(&one,r);
16 p_Delete(&t,r);
17 return (s==1);
18}
const CanonicalForm int s
Definition: facAbsFact.cc:51
poly p_One(const ring r)
Definition: p_polys.cc:1313
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:486
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1578
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899

◆ ppreduceInitially()

bool ppreduceInitially ( ideal  I,
const ring  r,
const number  p 
)

reduces I initially with respect to itself.

assumes that the generators of I are homogeneous in x and that p-t is in I.

sorts Hi according to degree in t in descending order (lowest first, highest last)

Definition at line 597 of file ppinitialReduction.cc.

598{
599 assume(!n_IsUnit(p,r->cf));
600
601 /***
602 * Step 1: split up I into components of same degree in x
603 * the lowest component should only contain p-t
604 **/
605 std::map<long,ideal> H; int n = IDELEMS(I);
606 for (int i=0; i<n; i++)
607 {
608 if(I->m[i]!=NULL)
609 {
610 I->m[i] = p_Cleardenom(I->m[i],r);
611 long d = 0;
612 for (int j=2; j<=r->N; j++)
613 d += p_GetExp(I->m[i],j,r);
614 std::map<long,ideal>::iterator it = H.find(d);
615 if (it != H.end())
616 idInsertPoly(it->second,I->m[i]);
617 else
618 {
619 std::pair<long,ideal> Hd(d,idInit(1));
620 Hd.second->m[0] = I->m[i];
621 H.insert(Hd);
622 }
623 }
624 }
625
626 std::map<long,ideal>::iterator it=H.begin();
627 ideal Hi = it->second;
628 idShallowDelete(&Hi);
629 it++;
630 Hi = it->second;
631
632 /***
633 * Step 2: reduce each component initially with respect to itself
634 * and all lower components
635 **/
636 if (ppreduceInitially(Hi,p,r)) return true;
637 idSkipZeroes(Hi);
638 id_Test(Hi,r);
639 id_Test(I,r);
640
641 ideal G = idInit(n); int m=0;
642 ideal GG = (ideal) omAllocBin(sip_sideal_bin);
643 GG->nrows = 1; GG->rank = 1; GG->m=NULL;
644
645 for (it++; it!=H.end(); it++)
646 {
647 int l=IDELEMS(Hi); int k=l; poly cache;
648 /**
649 * sorts Hi according to degree in t in descending order
650 * (lowest first, highest last)
651 */
652 do
653 {
654 int j=0;
655 for (int i=1; i<k; i++)
656 {
657 if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
658 {
659 cache=Hi->m[i-1];
660 Hi->m[i-1]=Hi->m[i];
661 Hi->m[i]=cache;
662 j = i;
663 }
664 }
665 k=j;
666 } while(k);
667 int kG=n-m, kH=0;
668 for (int i=n-m-l; i<n; i++)
669 {
670 if (kG==n)
671 {
672 memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
673 break;
674 }
675 if (kH==l)
676 break;
677 if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
678 G->m[i] = G->m[kG++];
679 else
680 G->m[i] = Hi->m[kH++];
681 }
682 m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
683 id_Test(it->second,r);
684 id_Test(GG,r);
685 if (ppreduceInitially(it->second,p,GG,r)) return true;
686 id_Test(it->second,r);
687 id_Test(GG,r);
688 idShallowDelete(&Hi); Hi = it->second;
689 }
690 idShallowDelete(&Hi);
691
692 ptNormalize(I,p,r);
695 return false;
696}
void * ADDRESS
Definition: auxiliary.h:119
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
const CanonicalForm & GG
Definition: cfModGcd.cc:4076
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition: coeffs.h:512
CanonicalForm H
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define assume(x)
Definition: mod2.h:389
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
#define NULL
Definition: omList.c:12
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2845
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:467
void ptNormalize(poly *gStar, const number p, const ring r)
bool ppreduceInitially(poly *hStar, const poly g, const ring r)
reduces h initially with respect to g, returns false if h was initially reduced in the first place,...
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
VAR omBin sip_sideal_bin
Definition: simpleideals.cc:27
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23
#define id_Test(A, lR)
Definition: simpleideals.h:87
static void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it

◆ pReduce()

void pReduce ( ideal &  I,
const number  p,
const ring  r 
)

Definition at line 261 of file ppinitialReduction.cc.

262{
263 int k = IDELEMS(I);
264 for (int i=0; i<k; i++)
265 {
266 if (I->m[i]!=NULL)
267 {
268 number c = p_GetCoeff(I->m[i],r);
269 if (!n_DivBy(p,c,r->cf))
270 pReduce(I->m[i],p,r);
271 }
272 }
273}
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition: coeffs.h:750
#define p_GetCoeff(p, r)
Definition: monomials.h:50
void pReduce(poly &g, const number p, const ring r)

◆ pReduceInhomogeneous()

void pReduceInhomogeneous ( poly &  g,
const number  p,
const ring  r 
)

Definition at line 132 of file ppinitialReduction.cc.

133{
134 if (g==NULL)
135 return;
136 p_Test(g,r);
137
138 poly toBeChecked = pNext(g);
139 pNext(g) = NULL; poly gEnd = g;
140 poly gCache;
141
142 number coeff, pPower; int power; poly subst;
143 while(toBeChecked)
144 {
145 for (gCache = g; gCache; pIter(gCache))
146 if (p_xLeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
147 if (gCache)
148 {
149 n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
150 coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
151 p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
152 n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
153 toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
154 }
155 else
156 {
157 if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
158 {
159 power=1;
160 coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
161 while (n_DivBy(coeff,p,r->cf))
162 {
163 power++;
164 number coeff0 = n_Div(coeff,p,r->cf);
165 n_Delete(&coeff,r->cf);
166 coeff = coeff0;
167 coeff0 = NULL;
168 if (power<1)
169 {
170 WerrorS("pReduce: overflow in exponent");
171 throw 0;
172 }
173 }
174 subst=p_LmInit(toBeChecked,r);
175 p_AddExp(subst,1,power,r);
176 p_SetCoeff(subst,coeff,r);
177 p_Setm(subst,r); p_Test(subst,r);
178 toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
179 toBeChecked=p_Add_q(toBeChecked,subst,r);
180 p_Test(toBeChecked,r);
181 }
182 else
183 {
184 pNext(gEnd)=toBeChecked;
185 pIter(gEnd); pIter(toBeChecked);
186 pNext(gEnd)=NULL;
187 p_Test(g,r);
188 }
189 }
190 }
191 p_Test(g,r);
193 return;
194}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
g
Definition: cfModGcd.cc:4090
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:633
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:647
static FORCE_INLINE void n_Power(number a, int b, number *res, const coeffs r)
fill res with the power a^b
Definition: coeffs.h:629
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:612
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:604
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1333
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:410
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:753
#define p_Test(p, r)
Definition: p_polys.h:159
#define pPower(p, q)
Definition: polys.h:204
void divideByCommonGcd(poly &g, const ring r)
bool p_xLeadmonomDivisibleBy(const poly g, const poly f, const ring r)