Loading...
Searching...
No Matches
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.

## 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.

{
poly one = p_One(r);
poly t = p_One(r);
p_SetExp(t,1,1,r);
p_Setm(t,r);
int s = p_LmCmp(one,t,r);
p_Delete(&one,r);
p_Delete(&t,r);
return (s==1);
}
s
const CanonicalForm int s
Definition facAbsFact.cc:51
p_One
poly p_One(const ring r)
Definition p_polys.cc:1314
p_SetExp
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:490
p_Setm
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1601
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903

## 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.

{
assume(!n_IsUnit(p,r->cf));
/***
* Step 1: split up I into components of same degree in x
* the lowest component should only contain p-t
**/
std::map<long,ideal> H; int n = IDELEMS(I);
for (int i=0; i<n; i++)
{
if(I->m[i]!=NULL)
{
I->m[i] = p_Cleardenom(I->m[i],r);
long d = 0;
for (int j=2; j<=r->N; j++)
d += p_GetExp(I->m[i],j,r);
std::map<long,ideal>::iterator it = H.find(d);
if (it != H.end())
idInsertPoly(it->second,I->m[i]);
else
{
std::pair<long,ideal> Hd(d,idInit(1));
Hd.second->m[0] = I->m[i];
H.insert(Hd);
}
}
}
std::map<long,ideal>::iterator it=H.begin();
ideal Hi = it->second;
idShallowDelete(&Hi);
it++;
Hi = it->second;
/***
* Step 2: reduce each component initially with respect to itself
* and all lower components
**/
if (ppreduceInitially(Hi,p,r)) return true;
idSkipZeroes(Hi);
id_Test(Hi,r);
id_Test(I,r);
ideal G = idInit(n); int m=0;
ideal GG = (ideal) omAllocBin(sip_sideal_bin);
GG->nrows = 1; GG->rank = 1; GG->m=NULL;
for (it++; it!=H.end(); it++)
{
int l=IDELEMS(Hi); int k=l; poly cache;
/**
* sorts Hi according to degree in t in descending order
* (lowest first, highest last)
*/
do
{
int j=0;
for (int i=1; i<k; i++)
{
if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
{
cache=Hi->m[i-1];
Hi->m[i-1]=Hi->m[i];
Hi->m[i]=cache;
j = i;
}
}
k=j;
} while(k);
int kG=n-m, kH=0;
for (int i=n-m-l; i<n; i++)
{
if (kG==n)
{
memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
break;
}
if (kH==l)
break;
if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
G->m[i] = G->m[kG++];
else
G->m[i] = Hi->m[kH++];
}
m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
id_Test(it->second,r);
id_Test(GG,r);
if (ppreduceInitially(it->second,p,GG,r)) return true;
id_Test(it->second,r);
id_Test(GG,r);
idShallowDelete(&Hi); Hi = it->second;
}
idShallowDelete(&Hi);
ptNormalize(I,p,r);
omFreeBin((ADDRESS)GG, sip_sideal_bin);
idShallowDelete(&G);
return false;
}
ADDRESS
void * ADDRESS
Definition auxiliary.h:120
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
GG
const CanonicalForm & GG
Definition cfModGcd.cc:4084
n_IsUnit
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:521
H
CanonicalForm H
Definition facAbsFact.cc:60
j
int j
Definition facHensel.cc:110
idInsertPoly
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
Definition simpleideals.cc:832
G
STATIC_VAR TreeM * G
Definition janet.cc:31
assume
#define assume(x)
Definition mod2.h:389
omAllocBin
#define omAllocBin(bin)
Definition omAllocDecl.h:205
omFreeBin
#define omFreeBin(addr, bin)
Definition omAllocDecl.h:259
NULL
#define NULL
Definition omList.c:12
p_Cleardenom
poly p_Cleardenom(poly p, const ring r)
Definition p_polys.cc:2893
p_GetExp
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:471
ptNormalize
void ptNormalize(poly *gStar, const number p, const ring r)
Definition ppinitialReduction.cc:196
ppreduceInitially
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,...
Definition ppinitialReduction.cc:282
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
sip_sideal_bin
VAR omBin sip_sideal_bin
Definition simpleideals.cc:27
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
id_Test
#define id_Test(A, lR)
Definition simpleideals.h:89
idShallowDelete
static void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it
Definition singularWishlist.h:66

## pReduce()

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

Definition at line 261 of file ppinitialReduction.cc.

{
int k = IDELEMS(I);
for (int i=0; i<k; i++)
{
if (I->m[i]!=NULL)
{
number c = p_GetCoeff(I->m[i],r);
if (!n_DivBy(p,c,r->cf))
pReduce(I->m[i],p,r);
}
}
}
n_DivBy
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
p_GetCoeff
#define p_GetCoeff(p, r)
Definition monomials.h:50
pReduce
void pReduce(poly &g, const number p, const ring r)
Definition ppinitialReduction.cc:54

## pReduceInhomogeneous()

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

Definition at line 132 of file ppinitialReduction.cc.

{
if (g==NULL)
return;
p_Test(g,r);
poly toBeChecked = pNext(g);
pNext(g) = NULL; poly gEnd = g;
poly gCache;
number coeff, pPower; int power; poly subst;
while(toBeChecked)
{
for (gCache = g; gCache; pIter(gCache))
if (p_xLeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
if (gCache)
{
n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
}
else
{
if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
{
power=1;
coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
while (n_DivBy(coeff,p,r->cf))
{
power++;
number coeff0 = n_Div(coeff,p,r->cf);
n_Delete(&coeff,r->cf);
coeff = coeff0;
coeff0 = NULL;
if (power<1)
{
WerrorS("pReduce: overflow in exponent");
throw 0;
}
}
subst=p_LmInit(toBeChecked,r);
p_AddExp(subst,1,power,r);
p_SetCoeff(subst,coeff,r);
p_Setm(subst,r); p_Test(subst,r);
toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
toBeChecked=p_Add_q(toBeChecked,subst,r);
p_Test(toBeChecked,r);
}
else
{
pNext(gEnd)=toBeChecked;
pIter(gEnd); pIter(toBeChecked);
pNext(gEnd)=NULL;
p_Test(g,r);
}
}
}
p_Test(g,r);
divideByCommonGcd(g,r);
return;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
g
g
Definition cfModGcd.cc:4098
n_Mult
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:639
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_Power
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:635
n_Div
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:618
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition facAlgFuncUtil.cc:120
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
p_AddExp
static long p_AddExp(poly p, int v, long ee, ring r)
Definition p_polys.h:608
p_LmInit
static poly p_LmInit(poly p, const ring r)
Definition p_polys.h:1356
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:414
p_LmDeleteAndNext
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition p_polys.h:757
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
pPower
#define pPower(p, q)
Definition polys.h:205
divideByCommonGcd
void divideByCommonGcd(poly &g, const ring r)
Definition ppinitialReduction.cc:21
p_xLeadmonomDivisibleBy
bool p_xLeadmonomDivisibleBy(const poly g, const poly f, const ring r)
Definition ppinitialReduction.cc:118