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...
 
BOOLEAN pReduceDebug (leftv res, leftv args)
 
BOOLEAN reduceInitiallyDebug (leftv res, leftv args)
 
BOOLEAN ptNormalize (leftv res, leftv args)
 
BOOLEAN ppreduceInitially3 (leftv res, leftv args)
 

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:1313
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 773 of file ppinitialReduction.cc.

774 {
775  assume(!n_IsUnit(p,r->cf));
776 
777  /***
778  * Step 1: split up I into components of same degree in x
779  * the lowest component should only contain p-t
780  **/
781  std::map<long,ideal> H; int n = IDELEMS(I);
782  for (int i=0; i<n; i++)
783  {
784  if(I->m[i]!=NULL)
785  {
786  I->m[i] = p_Cleardenom(I->m[i],r);
787  long d = 0;
788  for (int j=2; j<=r->N; j++)
789  d += p_GetExp(I->m[i],j,r);
790  std::map<long,ideal>::iterator it = H.find(d);
791  if (it != H.end())
792  idInsertPoly(it->second,I->m[i]);
793  else
794  {
795  std::pair<long,ideal> Hd(d,idInit(1));
796  Hd.second->m[0] = I->m[i];
797  H.insert(Hd);
798  }
799  }
800  }
801 
802  std::map<long,ideal>::iterator it=H.begin();
803  ideal Hi = it->second;
804  idShallowDelete(&Hi);
805  it++;
806  Hi = it->second;
807 
808  /***
809  * Step 2: reduce each component initially with respect to itself
810  * and all lower components
811  **/
812  if (ppreduceInitially(Hi,p,r)) return true;
813  idSkipZeroes(Hi);
814  id_Test(Hi,r);
815  id_Test(I,r);
816 
817  ideal G = idInit(n); int m=0;
818  ideal GG = (ideal) omAllocBin(sip_sideal_bin);
819  GG->nrows = 1; GG->rank = 1; GG->m=NULL;
820 
821  for (it++; it!=H.end(); it++)
822  {
823  int l=IDELEMS(Hi); int k=l; poly cache;
824  /**
825  * sorts Hi according to degree in t in descending order
826  * (lowest first, highest last)
827  */
828  do
829  {
830  int j=0;
831  for (int i=1; i<k; i++)
832  {
833  if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
834  {
835  cache=Hi->m[i-1];
836  Hi->m[i-1]=Hi->m[i];
837  Hi->m[i]=cache;
838  j = i;
839  }
840  }
841  k=j;
842  } while(k);
843  int kG=n-m, kH=0;
844  for (int i=n-m-l; i<n; i++)
845  {
846  if (kG==n)
847  {
848  memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
849  break;
850  }
851  if (kH==l)
852  break;
853  if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
854  G->m[i] = G->m[kG++];
855  else
856  G->m[i] = Hi->m[kH++];
857  }
858  m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
859  id_Test(it->second,r);
860  id_Test(GG,r);
861  if (ppreduceInitially(it->second,p,GG,r)) return true;
862  id_Test(it->second,r);
863  id_Test(GG,r);
864  idShallowDelete(&Hi); Hi = it->second;
865  }
866  idShallowDelete(&Hi);
867 
868  ptNormalize(I,p,r);
870  idShallowDelete(&G);
871  return false;
872 }
#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:118
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:403
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
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:2716
int l
Definition: cfEzgcd.cc:94
void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it

§ ppreduceInitially3()

BOOLEAN ppreduceInitially3 ( leftv  res,
leftv  args 
)

Definition at line 739 of file ppinitialReduction.cc.

740 {
741  leftv u = args;
742  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
743  {
744  leftv v = u->next;
745  if ((v != NULL) && (v->Typ() == NUMBER_CMD))
746  {
747  leftv w = v->next;
748  if ((w != NULL) && (w->Typ() == IDEAL_CMD))
749  {
750  ideal H,G; number p;
751  omUpdateInfo();
752  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
753  H = (ideal) u->CopyD();
754  p = (number) v->CopyD();
755  G = (ideal) w->CopyD();
756  (void) ppreduceInitially(H,p,G,currRing);
757  n_Delete(&p,currRing->cf);
758  id_Delete(&G,currRing);
759  res->rtyp = IDEAL_CMD;
760  res->data = (char*) H;
761  return FALSE;
762  }
763  }
764  }
765  return TRUE;
766 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:84
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
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...
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define TRUE
Definition: auxiliary.h:101
static TreeM * G
Definition: janet.cc:38
int Typ()
Definition: subexpr.cc:979
void * data
Definition: subexpr.h:90
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
omInfo_t om_Info
Definition: omStats.c:13
CanonicalForm H
Definition: facAbsFact.cc:64
leftv next
Definition: subexpr.h:88
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
const CanonicalForm & w
Definition: facAbsFact.cc:55
int rtyp
Definition: subexpr.h:93
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
void * CopyD(int t)
Definition: subexpr.cc:679

§ pReduce()

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

Definition at line 301 of file ppinitialReduction.cc.

302 {
303  int k = IDELEMS(I);
304  for (int i=0; i<k; i++)
305  {
306  if (I->m[i]!=NULL)
307  {
308  number c = p_GetCoeff(I->m[i],r);
309  if (!n_Equal(p,c,r->cf))
310  pReduce(I->m[i],p,r);
311  }
312  }
313 }
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)
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
#define NULL
Definition: omList.c:10
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:464
#define p_GetCoeff(p, r)
Definition: monomials.h:57

§ pReduceDebug()

BOOLEAN pReduceDebug ( leftv  res,
leftv  args 
)

Definition at line 277 of file ppinitialReduction.cc.

278 {
279  leftv u = args;
280  if ((u != NULL) && (u->Typ() == POLY_CMD))
281  {
282  poly g; number p = n_Init(3,currRing->cf);
283  omUpdateInfo();
284  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
285  g = (poly) u->CopyD();
286  (void) pReduce(g,p,currRing);
287  p_Delete(&g,currRing);
288  omUpdateInfo();
289  Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
290  g = (poly) u->CopyD();
291  (void) pReduce(g,p,currRing);
292  n_Delete(&p,currRing->cf);
293  res->rtyp = POLY_CMD;
294  res->data = (char*) g;
295  return FALSE;
296  }
297  return TRUE;
298 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:84
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:542
#define TRUE
Definition: auxiliary.h:101
g
Definition: cfModGcd.cc:4031
int Typ()
Definition: subexpr.cc:979
void * data
Definition: subexpr.h:90
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
omInfo_t om_Info
Definition: omStats.c:13
void pReduce(poly &g, const number p, const ring r)
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
int rtyp
Definition: subexpr.h:93
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
void * CopyD(int t)
Definition: subexpr.cc:679

§ 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

§ ptNormalize()

BOOLEAN ptNormalize ( leftv  res,
leftv  args 
)

Definition at line 253 of file ppinitialReduction.cc.

254 {
255  leftv u = args;
256  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
257  {
258  leftv v = u->next;
259  if ((v!=NULL) && (v->Typ()==NUMBER_CMD))
260  {
261  omUpdateInfo();
262  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
263  ideal I = (ideal) u->CopyD();
264  number p = (number) v->CopyD();
265  ptNormalize(I,p,currRing);
266  n_Delete(&p,currRing->cf);
267  res->rtyp = IDEAL_CMD;
268  res->data = (char*) I;
269  return FALSE;
270  }
271  }
272  return TRUE;
273 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:84
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:101
int Typ()
Definition: subexpr.cc:979
void * data
Definition: subexpr.h:90
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
omInfo_t om_Info
Definition: omStats.c:13
void ptNormalize(poly *gStar, const number p, const ring r)
leftv next
Definition: subexpr.h:88
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
int rtyp
Definition: subexpr.h:93
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
void * CopyD(int t)
Definition: subexpr.cc:679

§ reduceInitiallyDebug()

BOOLEAN reduceInitiallyDebug ( leftv  res,
leftv  args 
)

Definition at line 876 of file ppinitialReduction.cc.

877 {
878  leftv u = args;
879  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
880  {
881  leftv v = u->next;
882  if ((v != NULL) && (v->Typ() == NUMBER_CMD))
883  {
884  omUpdateInfo();
885  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
886  ideal I = (ideal) u->CopyD();
887  number p = (number) v->Data();
888  (void) ppreduceInitially(I,currRing,p);
889  res->rtyp = IDEAL_CMD;
890  res->data = (char*) I;
891  return FALSE;
892  }
893  }
894  return TRUE;
895 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:84
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
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 TRUE
Definition: auxiliary.h:101
int Typ()
Definition: subexpr.cc:979
void * data
Definition: subexpr.h:90
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
omInfo_t om_Info
Definition: omStats.c:13
leftv next
Definition: subexpr.h:88
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
int rtyp
Definition: subexpr.h:93
void * Data()
Definition: subexpr.cc:1121
void * CopyD(int t)
Definition: subexpr.cc:679