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

typedef std::pair<int,int> mark

Definition at line 7 of file ppinitialReduction.h.

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

Definition at line 8 of file ppinitialReduction.h.

Function Documentation

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:1318
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1472
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:850
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:484
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
polyrec * poly
Definition: hilb.h:10
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 759 of file ppinitialReduction.cc.

760 {
761  assume(!n_IsUnit(p,r->cf));
762 
763  /***
764  * Step 1: split up I into components of same degree in x
765  * the lowest component should only contain p-t
766  **/
767  std::map<long,ideal> H; int n = idSize(I);
768  for (int i=0; i<n; i++)
769  {
770  I->m[i] = p_Cleardenom(I->m[i],r);
771  long d = 0;
772  for (int j=2; j<=r->N; j++)
773  d += p_GetExp(I->m[i],j,r);
774  std::map<long,ideal>::iterator it = H.find(d);
775  if (it != H.end())
776  idInsertPoly(it->second,I->m[i]);
777  else
778  {
779  std::pair<long,ideal> Hd(d,idInit(1));
780  Hd.second->m[0] = I->m[i];
781  H.insert(Hd);
782  }
783  }
784 
785  std::map<long,ideal>::iterator it=H.begin();
786  ideal Hi = it->second;
787  idShallowDelete(&Hi);
788  it++;
789  Hi = it->second;
790 
791  /***
792  * Step 2: reduce each component initially with respect to itself
793  * and all lower components
794  **/
795  if (ppreduceInitially(Hi,p,r)) return true;
796  id_Test(Hi,r);
797  id_Test(I,r);
798 
799  ideal G = idInit(n); int m=0;
800  ideal GG = (ideal) omAllocBin(sip_sideal_bin);
801  GG->nrows = 1; GG->rank = 1; GG->m=NULL;
802 
803  for (it++; it!=H.end(); it++)
804  {
805  int l=idSize(Hi); int k=l; poly cache;
806  /**
807  * sorts Hi according to degree in t in descending order
808  * (lowest first, highest last)
809  */
810  do
811  {
812  int j=0;
813  for (int i=1; i<k; i++)
814  {
815  if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
816  {
817  cache=Hi->m[i-1];
818  Hi->m[i-1]=Hi->m[i];
819  Hi->m[i]=cache;
820  j = i;
821  }
822  }
823  k=j;
824  } while(k);
825  int kG=n-m, kH=0;
826  for (int i=n-m-l; i<n; i++)
827  {
828  if (kG==n)
829  {
830  memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
831  break;
832  }
833  if (kH==l)
834  break;
835  if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
836  G->m[i] = G->m[kG++];
837  else
838  G->m[i] = Hi->m[kH++];
839  }
840  m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
841  id_Test(it->second,r);
842  id_Test(GG,r);
843  if (ppreduceInitially(it->second,p,GG,r)) return true;
844  id_Test(it->second,r);
845  id_Test(GG,r);
846  idShallowDelete(&Hi); Hi = it->second;
847  }
848  idShallowDelete(&Hi);
849 
850  ptNormalize(I,p,r);
852  idShallowDelete(&G);
853  return false;
854 }
#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:516
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:161
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:465
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:405
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 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 int idSize(const ideal id)
Count the effective size of an ideal (without the trailing allocated zero-elements) ...
Definition: ideals.h:43
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:2682
int l
Definition: cfEzgcd.cc:94
void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it
BOOLEAN ppreduceInitially3 ( leftv  res,
leftv  args 
)

Definition at line 725 of file ppinitialReduction.cc.

726 {
727  leftv u = args;
728  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
729  {
730  leftv v = u->next;
731  if ((v != NULL) && (v->Typ() == NUMBER_CMD))
732  {
733  leftv w = v->next;
734  if ((w != NULL) && (w->Typ() == IDEAL_CMD))
735  {
736  ideal H,G; number p;
737  omUpdateInfo();
738  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
739  H = (ideal) u->CopyD();
740  p = (number) v->CopyD();
741  G = (ideal) w->CopyD();
742  (void) ppreduceInitially(H,p,G,currRing);
743  n_Delete(&p,currRing->cf);
744  id_Delete(&G,currRing);
745  res->rtyp = IDEAL_CMD;
746  res->data = (char*) H;
747  return FALSE;
748  }
749  }
750  }
751  return TRUE;
752 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:140
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:144
static TreeM * G
Definition: janet.cc:38
int Typ()
Definition: subexpr.cc:969
void * data
Definition: subexpr.h:89
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
omInfo_t om_Info
Definition: omStats.c:13
CanonicalForm H
Definition: facAbsFact.cc:64
leftv next
Definition: subexpr.h:87
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:92
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
void * CopyD(int t)
Definition: subexpr.cc:676
void pReduce ( ideal &  I,
const number  p,
const ring  r 
)

Definition at line 301 of file ppinitialReduction.cc.

302 {
303  int k = idSize(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;
314 }
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 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:461
#define p_GetCoeff(p, r)
Definition: monomials.h:57
static int idSize(const ideal id)
Count the effective size of an ideal (without the trailing allocated zero-elements) ...
Definition: ideals.h:43
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:83
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:140
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:539
#define TRUE
Definition: auxiliary.h:144
g
Definition: cfModGcd.cc:4031
int Typ()
Definition: subexpr.cc:969
void * data
Definition: subexpr.h:89
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
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:850
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
int rtyp
Definition: subexpr.h:92
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
polyrec * poly
Definition: hilb.h:10
void * CopyD(int t)
Definition: subexpr.cc:676
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:721
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:401
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:635
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:465
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:655
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:771
#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:631
#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:615
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:1263
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:602
#define p_GetCoeff(p, r)
Definition: monomials.h:57
#define pPower(p, q)
Definition: polys.h:175
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:884
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:83
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:144
int Typ()
Definition: subexpr.cc:969
void * data
Definition: subexpr.h:89
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
omInfo_t om_Info
Definition: omStats.c:13
void ptNormalize(poly *gStar, const number p, const ring r)
leftv next
Definition: subexpr.h:87
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:92
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
void * CopyD(int t)
Definition: subexpr.cc:676
BOOLEAN reduceInitiallyDebug ( leftv  res,
leftv  args 
)

Definition at line 858 of file ppinitialReduction.cc.

859 {
860  leftv u = args;
861  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
862  {
863  leftv v = u->next;
864  if ((v != NULL) && (v->Typ() == NUMBER_CMD))
865  {
866  omUpdateInfo();
867  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
868  ideal I = (ideal) u->CopyD();
869  number p = (number) v->Data();
870  (void) ppreduceInitially(I,currRing,p);
871  res->rtyp = IDEAL_CMD;
872  res->data = (char*) I;
873  return FALSE;
874  }
875  }
876  return TRUE;
877 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:140
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:144
int Typ()
Definition: subexpr.cc:969
void * data
Definition: subexpr.h:89
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
omInfo_t om_Info
Definition: omStats.c:13
leftv next
Definition: subexpr.h:87
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:92
void * Data()
Definition: subexpr.cc:1111
void * CopyD(int t)
Definition: subexpr.cc:676