My Project
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);
694  idShallowDelete(&G);
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:2841
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);
192  divideByCommonGcd(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)