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 13 of file ppinitialReduction.cc.

14 {
15  poly one = p_One(r);
16  poly t = p_One(r);
17  p_SetExp(t,1,1,r);
18  p_Setm(t,r);
19  int s = p_LmCmp(one,t,r);
20  p_Delete(&one,r);
21  p_Delete(&t,r);
22  return (s==1);
23 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const ring r
Definition: syzextra.cc:208
poly p_One(const ring r)
Definition: p_polys.cc:1314
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1467
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
polyrec * poly
Definition: hilb.h:10

◆ 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 612 of file ppinitialReduction.cc.

613 {
614  assume(!n_IsUnit(p,r->cf));
615 
616  /***
617  * Step 1: split up I into components of same degree in x
618  * the lowest component should only contain p-t
619  **/
620  std::map<long,ideal> H; int n = IDELEMS(I);
621  for (int i=0; i<n; i++)
622  {
623  if(I->m[i]!=NULL)
624  {
625  I->m[i] = p_Cleardenom(I->m[i],r);
626  long d = 0;
627  for (int j=2; j<=r->N; j++)
628  d += p_GetExp(I->m[i],j,r);
629  std::map<long,ideal>::iterator it = H.find(d);
630  if (it != H.end())
631  idInsertPoly(it->second,I->m[i]);
632  else
633  {
634  std::pair<long,ideal> Hd(d,idInit(1));
635  Hd.second->m[0] = I->m[i];
636  H.insert(Hd);
637  }
638  }
639  }
640 
641  std::map<long,ideal>::iterator it=H.begin();
642  ideal Hi = it->second;
643  idShallowDelete(&Hi);
644  it++;
645  Hi = it->second;
646 
647  /***
648  * Step 2: reduce each component initially with respect to itself
649  * and all lower components
650  **/
651  if (ppreduceInitially(Hi,p,r)) return true;
652  idSkipZeroes(Hi);
653  id_Test(Hi,r);
654  id_Test(I,r);
655 
656  ideal G = idInit(n); int m=0;
657  ideal GG = (ideal) omAllocBin(sip_sideal_bin);
658  GG->nrows = 1; GG->rank = 1; GG->m=NULL;
659 
660  for (it++; it!=H.end(); it++)
661  {
662  int l=IDELEMS(Hi); int k=l; poly cache;
663  /**
664  * sorts Hi according to degree in t in descending order
665  * (lowest first, highest last)
666  */
667  do
668  {
669  int j=0;
670  for (int i=1; i<k; i++)
671  {
672  if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
673  {
674  cache=Hi->m[i-1];
675  Hi->m[i-1]=Hi->m[i];
676  Hi->m[i]=cache;
677  j = i;
678  }
679  }
680  k=j;
681  } while(k);
682  int kG=n-m, kH=0;
683  for (int i=n-m-l; i<n; i++)
684  {
685  if (kG==n)
686  {
687  memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
688  break;
689  }
690  if (kH==l)
691  break;
692  if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
693  G->m[i] = G->m[kG++];
694  else
695  G->m[i] = Hi->m[kH++];
696  }
697  m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
698  id_Test(it->second,r);
699  id_Test(GG,r);
700  if (ppreduceInitially(it->second,p,GG,r)) return true;
701  id_Test(it->second,r);
702  id_Test(GG,r);
703  idShallowDelete(&Hi); Hi = it->second;
704  }
705  idShallowDelete(&Hi);
706 
707  ptNormalize(I,p,r);
709  idShallowDelete(&G);
710  return false;
711 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
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:519
return P p
Definition: myNF.cc:203
omBin sip_sideal_bin
Definition: simpleideals.cc:30
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...
#define id_Test(A, lR)
Definition: simpleideals.h:80
void * ADDRESS
Definition: auxiliary.h:115
int k
Definition: cfEzgcd.cc:93
static TreeM * G
Definition: janet.cc:38
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
const ring r
Definition: syzextra.cc:208
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:394
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted ...
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
CanonicalForm H
Definition: facAbsFact.cc:64
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void ptNormalize(poly *gStar, const number p, const ring r)
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
#define NULL
Definition: omList.c:10
static void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it
polyrec * poly
Definition: hilb.h:10
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2755
int l
Definition: cfEzgcd.cc:94

◆ pReduce()

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

Definition at line 276 of file ppinitialReduction.cc.

277 {
278  int k = IDELEMS(I);
279  for (int i=0; i<k; i++)
280  {
281  if (I->m[i]!=NULL)
282  {
283  number c = p_GetCoeff(I->m[i],r);
284  if (!n_DivBy(p,c,r->cf))
285  pReduce(I->m[i],p,r);
286  }
287  }
288 }
return P p
Definition: myNF.cc:203
int k
Definition: cfEzgcd.cc:93
const ring r
Definition: syzextra.cc:208
void pReduce(poly &g, const number p, const ring r)
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether &#39;a&#39; is divisible &#39;b&#39;; for r encoding a field: TRUE iff &#39;b&#39; does not represent zero in Z:...
Definition: coeffs.h:787
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
#define NULL
Definition: omList.c:10
#define p_GetCoeff(p, r)
Definition: monomials.h:57

◆ pReduceInhomogeneous()

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

Definition at line 137 of file ppinitialReduction.cc.

138 {
139  if (g==NULL)
140  return;
141  p_Test(g,r);
142 
143  poly toBeChecked = pNext(g);
144  pNext(g) = NULL; poly gEnd = g;
145  poly gCache;
146 
147  number coeff, pPower; int power; poly subst;
148  while(toBeChecked)
149  {
150  for (gCache = g; gCache; pIter(gCache))
151  if (p_xLeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
152  if (gCache)
153  {
154  n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
155  coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
156  p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
157  n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
158  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
159  }
160  else
161  {
162  if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
163  {
164  power=1;
165  coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
166  while (n_DivBy(coeff,p,r->cf))
167  {
168  power++;
169  number coeff0 = n_Div(coeff,p,r->cf);
170  n_Delete(&coeff,r->cf);
171  coeff = coeff0;
172  coeff0 = NULL;
173  if (power<1)
174  {
175  WerrorS("pReduce: overflow in exponent");
176  throw 0;
177  }
178  }
179  subst=p_LmInit(toBeChecked,r);
180  p_AddExp(subst,1,power,r);
181  p_SetCoeff(subst,coeff,r);
182  p_Setm(subst,r); p_Test(subst,r);
183  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
184  toBeChecked=p_Add_q(toBeChecked,subst,r);
185  p_Test(toBeChecked,r);
186  }
187  else
188  {
189  pNext(gEnd)=toBeChecked;
190  pIter(gEnd); pIter(toBeChecked);
191  pNext(gEnd)=NULL;
192  p_Test(g,r);
193  }
194  }
195  }
196  p_Test(g,r);
198  return;
199 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:720
return P p
Definition: myNF.cc:203
g
Definition: cfModGcd.cc:4031
void WerrorS(const char *s)
Definition: feFopen.cc:24
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
#define pIter(p)
Definition: monomials.h:44
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
const ring r
Definition: syzextra.cc:208
bool p_xLeadmonomDivisibleBy(const poly g, const poly f, const ring r)
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether &#39;a&#39; is divisible &#39;b&#39;; for r encoding a field: TRUE iff &#39;b&#39; does not represent zero in Z:...
Definition: coeffs.h:787
#define p_Test(p, r)
Definition: p_polys.h:160
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:636
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:619
void divideByCommonGcd(poly &g, const ring r)
#define pNext(p)
Definition: monomials.h:43
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1258
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:601
#define p_GetCoeff(p, r)
Definition: monomials.h:57
#define pPower(p, q)
Definition: polys.h:187
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877