Functions
ppinitialReduction.cc File Reference
#include <polys/monomials/p_polys.h>
#include <Singular/ipid.h>
#include "singularWishlist.h"
#include "ppinitialReduction.h"
#include <map>
#include <set>
#include <exception>

Go to the source code of this file.

Functions

bool isOrderingLocalInT (const ring r)
 
void divideByCommonGcd (poly &g, const ring r)
 
void pReduce (poly &g, const number p, const ring r)
 
bool p_xLeadmonomDivisibleBy (const poly g, const poly f, const ring r)
 
void pReduceInhomogeneous (poly &g, const number p, const ring r)
 
void ptNormalize (poly *gStar, const number p, const ring r)
 
void ptNormalize (ideal I, const number p, const ring r)
 
BOOLEAN ptNormalize (leftv res, leftv args)
 
void pReduce (ideal &I, 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, returns true if reductions have taken place. More...
 
bool ppreduceInitially (ideal I, const number p, const ring r)
 
int ppreduceInitially (ideal I, const number p, const poly g, const ring r)
 
static poly ppNext (poly p, int l)
 
static void sortMarks (const ideal H, const ring r, std::vector< mark > &T)
 
static poly getTerm (const ideal H, const mark ab)
 
static void adjustMarks (std::vector< mark > &T, const int newEntry)
 
static void cleanupMarks (const ideal H, std::vector< mark > &T)
 
bool ppreduceInitially (ideal &H, const number p, const ideal G, const ring r)
 
bool ppreduceInitially (ideal I, const ring r, const number p)
 reduces I initially with respect to itself. More...
 

Function Documentation

◆ adjustMarks()

static void adjustMarks ( std::vector< mark > &  T,
const int  newEntry 
)
static

Definition at line 493 of file ppinitialReduction.cc.

494 {
495  for (unsigned i=0; i<T.size(); i++)
496  {
497  if (T[i].first>=newEntry)
498  T[i].first = T[i].first+1;
499  }
500  return;
501 }
int i
Definition: cfEzgcd.cc:123
static jList * T
Definition: janet.cc:37

◆ cleanupMarks()

static void cleanupMarks ( const ideal  H,
std::vector< mark > &  T 
)
static

Definition at line 504 of file ppinitialReduction.cc.

505 {
506  for (unsigned i=0; i<T.size();)
507  {
508  if (getTerm(H,T[i])==NULL)
509  T.erase(T.begin()+i);
510  else
511  i++;
512  }
513  return;
514 }
static poly getTerm(const ideal H, const mark ab)
int i
Definition: cfEzgcd.cc:123
CanonicalForm H
Definition: facAbsFact.cc:64
#define NULL
Definition: omList.c:10
static jList * T
Definition: janet.cc:37

◆ divideByCommonGcd()

void divideByCommonGcd ( poly g,
const ring  r 
)

Definition at line 26 of file ppinitialReduction.cc.

27 {
28  number commonGcd = n_Copy(p_GetCoeff(g,r),r->cf);
29  for (poly gCache=pNext(g); gCache; pIter(gCache))
30  {
31  number commonGcdCache = n_Gcd(commonGcd,p_GetCoeff(gCache,r),r->cf);
32  n_Delete(&commonGcd,r->cf);
33  commonGcd = commonGcdCache;
34  if (n_IsOne(commonGcd,r->cf))
35  {
36  n_Delete(&commonGcd,r->cf);
37  return;
38  }
39  }
40  for (poly gCache=g; gCache; pIter(gCache))
41  {
42  number oldCoeff = p_GetCoeff(gCache,r);
43  number newCoeff = n_Div(oldCoeff,commonGcd,r->cf);
44  p_SetCoeff(gCache,newCoeff,r);
45  }
46  p_Test(g,r);
47  n_Delete(&commonGcd,r->cf);
48  return;
49 }
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of &#39;a&#39; and &#39;b&#39; in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:690
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:472
g
Definition: cfModGcd.cc:4031
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
#define pIter(p)
Definition: monomials.h:44
const ring r
Definition: syzextra.cc:208
#define p_Test(p, r)
Definition: p_polys.h:160
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:455
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
#define pNext(p)
Definition: monomials.h:43
#define p_GetCoeff(p, r)
Definition: monomials.h:57
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

◆ getTerm()

static poly getTerm ( const ideal  H,
const mark  ab 
)
static

Definition at line 485 of file ppinitialReduction.cc.

486 {
487  int a = ab.first;
488  int b = ab.second;
489  return ppNext(H->m[a],b);
490 }
const poly a
Definition: syzextra.cc:212
static poly ppNext(poly p, int l)
CanonicalForm H
Definition: facAbsFact.cc:64
const poly b
Definition: syzextra.cc:213

◆ 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

◆ p_xLeadmonomDivisibleBy()

bool p_xLeadmonomDivisibleBy ( const poly  g,
const poly  f,
const ring  r 
)

Definition at line 123 of file ppinitialReduction.cc.

124 {
125  poly gx = p_Head(g,r);
126  poly fx = p_Head(f,r);
127  p_SetExp(gx,1,0,r);
128  p_SetExp(fx,1,0,r);
129  p_Setm(gx,r);
130  p_Setm(fx,r);
131  bool b = p_LeadmonomDivisibleBy(gx,fx,r);
132  p_Delete(&gx,r);
133  p_Delete(&fx,r);
134  return b;
135 }
g
Definition: cfModGcd.cc:4031
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:812
const ring r
Definition: syzextra.cc:208
FILE * f
Definition: checklibs.c:9
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
const poly b
Definition: syzextra.cc:213
static BOOLEAN p_LeadmonomDivisibleBy(poly a, poly b, const ring r)
p_LmDivisibleBy checks also the divisibility of coefficients

◆ ppNext()

static poly ppNext ( poly  p,
int  l 
)
static

Definition at line 445 of file ppinitialReduction.cc.

446 {
447  poly q = p;
448  for (int i=0; i<l; i++)
449  {
450  if (q==NULL)
451  break;
452  pIter(q);
453  }
454  return q;
455 }
return P p
Definition: myNF.cc:203
#define pIter(p)
Definition: monomials.h:44
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
polyrec * poly
Definition: hilb.h:10
int l
Definition: cfEzgcd.cc:94

◆ ppreduceInitially() [1/5]

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, returns true if reductions have taken place.

assumes that h and g are in pReduced form and homogeneous in x of the same degree

Definition at line 297 of file ppinitialReduction.cc.

298 {
299  poly h = *hStar;
300  if (h==NULL || g==NULL)
301  return false;
302  p_Test(h,r);
303  p_Test(g,r);
304  poly hCache;
305  for (hCache=h; hCache; pIter(hCache))
306  if (p_LeadmonomDivisibleBy(g,hCache,r)) break;
307  if (hCache)
308  {
309  number gAlpha = p_GetCoeff(g,r);
310  poly hAlphaT = p_Init(r);
311  p_SetCoeff(hAlphaT,n_Copy(p_GetCoeff(hCache,r),r->cf),r);
312  p_SetExp(hAlphaT,1,p_GetExp(hCache,1,r)-p_GetExp(g,1,r),r);
313  for (int i=2; i<=r->N; i++)
314  p_SetExp(hAlphaT,i,0,r);
315  p_Setm(hAlphaT,r); p_Test(hAlphaT,r);
316  poly q1 = p_Mult_nn(h,gAlpha,r); p_Test(q1,r);
317  poly q2 = p_Mult_q(p_Copy(g,r),hAlphaT,r); p_Test(q2,r);
318  q2 = p_Neg(q2,r); p_Test(q2,r);
319  h = p_Add_q(q1,q2,r);
320  p_Test(h,r);
321  p_Test(g,r);
322  *hStar = h;
323  return true;
324  }
325  p_Test(h,r);
326  p_Test(g,r);
327  return false;
328 }
g
Definition: cfModGcd.cc:4031
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
#define pIter(p)
Definition: monomials.h:44
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 i
Definition: cfEzgcd.cc:123
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:895
#define p_Test(p, r)
Definition: p_polys.h:160
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
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:455
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
#define p_GetCoeff(p, r)
Definition: monomials.h:57
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1013
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
static Poly * h
Definition: janet.cc:978
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1243
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020
static BOOLEAN p_LeadmonomDivisibleBy(poly a, poly b, const ring r)
p_LmDivisibleBy checks also the divisibility of coefficients

◆ ppreduceInitially() [2/5]

bool ppreduceInitially ( ideal  I,
const number  p,
const ring  r 
)

Definition at line 336 of file ppinitialReduction.cc.

337 {
338  idSkipZeroes(I);
339  int m=IDELEMS(I),n=m; poly cache;
340  do
341  {
342  int j=0;
343  for (int i=1; i<n; i++)
344  {
345  if (p_LmCmp(I->m[i-1],I->m[i],r)<0) /*p_LmCmp(p,q): requires: p,q!=NULL*/
346  {
347  cache=I->m[i-1];
348  I->m[i-1]=I->m[i];
349  I->m[i]=cache;
350  j = i;
351  }
352  }
353  n=j;
354  } while(n);
355  for (int i=0; i<m; i++)
356  pReduce(I->m[i],p,r);
357 
358  /***
359  * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
360  **/
361  for (int i=0; i<m-1; i++)
362  for (int j=i+1; j<m; j++)
363  if (ppreduceInitially(&I->m[j], I->m[i], r))
364  pReduce(I->m[j],p,r);
365 
366  /***
367  * the second pass. removing terms divisible by lt(g_j) out of g_i for i<j
368  **/
369  for (int i=0; i<m-1; i++)
370  for (int j=i+1; j<m; j++)
371  if (ppreduceInitially(&I->m[i], I->m[j],r))
372  pReduce(I->m[i],p,r);
373 
374  /***
375  * removes the elements of I which have been reduced to 0 in the previous two passes
376  **/
377  idSkipZeroes(I);
378  return false;
379 }
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...
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
void pReduce(poly &g, const number p, const ring r)
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1467
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
polyrec * poly
Definition: hilb.h:10

◆ ppreduceInitially() [3/5]

int ppreduceInitially ( ideal  I,
const number  p,
const poly  g,
const ring  r 
)

Definition at line 387 of file ppinitialReduction.cc.

388 {
389  id_Test(I,r);
390  p_Test(g,r);
391  idInsertPoly(I,g);
392  idSkipZeroes(I);
393  int n=IDELEMS(I);
394  int j;
395  for (j=n-1; j>0; j--)
396  {
397  if (p_LmCmp(I->m[j], I->m[j-1],r)>0) /*p_LmCmp(p,q) requires: p,q!=NULL */
398  {
399  poly cache = I->m[j];
400  I->m[j] = I->m[j-1];
401  I->m[j-1] = cache;
402  }
403  else
404  break;
405  }
406 
407  /***
408  * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
409  * removing terms with the same monomials in x as lt(g_j) out of g_k for j<k
410  **/
411  for (int i=0; i<j; i++)
412  if (ppreduceInitially(&I->m[j], I->m[i], r))
413  pReduce(I->m[j],p,r);
414  for (int k=j+1; k<n; k++)
415  if (ppreduceInitially(&I->m[k], I->m[j], r))
416  {
417  pReduce(I->m[k],p,r);
418  for (int l=j+1; l<k; l++)
419  if (ppreduceInitially(&I->m[k], I->m[l], r))
420  pReduce(I->m[k],p,r);
421  }
422 
423  /***
424  * the second pass. removing terms divisible by lt(g_j) and lt(g_k) out of g_i for i<j<k
425  * removing terms divisible by lt(g_k) out of g_j for j<k
426  **/
427  for (int i=0; i<j; i++)
428  for (int k=j; k<n; k++)
429  if (ppreduceInitially(&I->m[i], I->m[k], r))
430  pReduce(I->m[i],p,r);
431  for (int k=j; k<n-1; k++)
432  for (int l=k+1; l<n; l++)
433  if (ppreduceInitially(&I->m[k], I->m[l], r))
434  pReduce(I->m[k],p,r);
435 
436  /***
437  * removes the elements of I which have been reduced to 0 in the previous two passes
438  **/
439  idSkipZeroes(I);
440  id_Test(I,r);
441  return j;
442 }
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 id_Test(A, lR)
Definition: simpleideals.h:80
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
void pReduce(poly &g, const number p, const ring r)
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 int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1467
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define p_Test(p, r)
Definition: p_polys.h:160
polyrec * poly
Definition: hilb.h:10
int l
Definition: cfEzgcd.cc:94

◆ ppreduceInitially() [4/5]

bool ppreduceInitially ( ideal &  H,
const number  p,
const ideal  G,
const ring  r 
)

Definition at line 523 of file ppinitialReduction.cc.

524 {
525  /***
526  * Step 1: reduce H initially with respect to itself and with respect to p-t
527  **/
528  if (ppreduceInitially(H,p,r)) return true;
529 
530  /***
531  * Step 2: initialize an ideal I in which the reductions will take place-
532  * along the reduction it will be enlarged with elements that will be discarded at the end
533  * initialize a working list T which keeps track.
534  * the working list T is a vector of pairs of integer.
535  * if T contains a pair (i,j) then that means that in the i-th element of H
536  * term j and subsequent terms need to be checked for reduction.
537  * T is sorted by the ordering on the temrs the pairs correspond to.
538  **/
539  int m=IDELEMS(H);
540  ideal I = idInit(m);
541  std::vector<mark> T;
542  for (int i=0; i<m; i++)
543  {
544  if(H->m[i]!=NULL)
545  {
546  I->m[i]=H->m[i];
547  if (pNext(I->m[i])!=NULL)
548  T.push_back(std::pair<int,int>(i,1));
549  }
550  }
551 
552  /***
553  * Step 3: as long as the working list is not empty, successively reduce terms in it
554  * by adding suitable elements to I and reducing it initially with respect to itself
555  **/
556  int k=IDELEMS(G);
557  while (T.size()>0)
558  {
559  sortMarks(I,r,T);
560  int i=0;
561  for (; i<k; i++)
562  {
563  if(G->m[i]!=NULL)
564  {
565  if (p_LeadmonomDivisibleBy(G->m[i],getTerm(I,T[0]),r)) break;
566  }
567  }
568  if (i<k)
569  {
570  poly g = p_One(r); poly h0 = getTerm(I,T[0]);
571  assume(h0!=NULL);
572  for (int j=2; j<=r->N; j++)
573  p_SetExp(g,j,p_GetExp(h0,j,r)-p_GetExp(G->m[i],j,r),r);
574  p_Setm(g,r);
575  g = p_Mult_q(g,p_Copy(G->m[i],r),r);
576  int newEntry = ppreduceInitially(I,p,g,r);
577  adjustMarks(T,newEntry);
578  }
579  else
580  T[0].second = T[0].second+1;
581  cleanupMarks(I,T);
582  }
583 
584  /***
585  * Step 4: cleanup, delete all polynomials in I which have been added in Step 3
586  **/
587  k=IDELEMS(I);
588  for (int i=0; i<k; i++)
589  {
590  if(I->m[i]!=NULL)
591  {
592  for (int j=0; j<m; j++)
593  {
594  if ((H->m[j]!=NULL)
595  && (p_LeadmonomDivisibleBy(H->m[j],I->m[i],r)))
596  {
597  I->m[i]=NULL;
598  break;
599  }
600  }
601  }
602  }
603  id_Delete(&I,r);
604  return false;
605 }
return P p
Definition: myNF.cc:203
static void sortMarks(const ideal H, const ring r, std::vector< mark > &T)
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...
static poly getTerm(const ideal H, const mark ab)
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
static void cleanupMarks(const ideal H, std::vector< mark > &T)
static TreeM * G
Definition: janet.cc:38
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
const ring r
Definition: syzextra.cc:208
poly p_One(const ring r)
Definition: p_polys.cc:1314
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
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
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
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
#define NULL
Definition: omList.c:10
static void adjustMarks(std::vector< mark > &T, const int newEntry)
#define pNext(p)
Definition: monomials.h:43
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
static jList * T
Definition: janet.cc:37
polyrec * poly
Definition: hilb.h:10
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020
static BOOLEAN p_LeadmonomDivisibleBy(poly a, poly b, const ring r)
p_LmDivisibleBy checks also the divisibility of coefficients
idhdl h0
Definition: libparse.cc:1141

◆ ppreduceInitially() [5/5]

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() [1/2]

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

Definition at line 59 of file ppinitialReduction.cc.

60 {
61  if (g==NULL)
62  return;
63  p_Test(g,r);
64 
65  poly toBeChecked = pNext(g);
66  pNext(g) = NULL; poly gEnd = g;
67  poly gCache;
68 
69  number coeff, pPower; int power; poly subst;
70  while(toBeChecked)
71  {
72  for (gCache = g; gCache; pIter(gCache))
73  if (p_LeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
74  if (gCache)
75  {
76  n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
77  coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
78  p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
79  n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
80  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
81  }
82  else
83  {
84  if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
85  {
86  power=1;
87  coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
88  while (n_DivBy(coeff,p,r->cf))
89  {
90  power++;
91  number coeff0 = n_Div(coeff,p,r->cf);
92  n_Delete(&coeff,r->cf);
93  coeff = coeff0;
94  coeff0 = NULL;
95  if (power<1)
96  {
97  WerrorS("pReduce: overflow in exponent");
98  throw 0;
99  }
100  }
101  subst=p_LmInit(toBeChecked,r);
102  p_AddExp(subst,1,power,r);
103  p_SetCoeff(subst,coeff,r);
104  p_Setm(subst,r); p_Test(subst,r);
105  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
106  toBeChecked=p_Add_q(toBeChecked,subst,r);
107  p_Test(toBeChecked,r);
108  }
109  else
110  {
111  pNext(gEnd)=toBeChecked;
112  pIter(gEnd); pIter(toBeChecked);
113  pNext(gEnd)=NULL;
114  p_Test(g,r);
115  }
116  }
117  }
118  p_Test(g,r);
120  return;
121 }
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
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
static BOOLEAN p_LeadmonomDivisibleBy(poly a, poly b, const ring r)
p_LmDivisibleBy checks also the divisibility of coefficients

◆ pReduce() [2/2]

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

◆ ptNormalize() [1/3]

void ptNormalize ( poly gStar,
const number  p,
const ring  r 
)

Definition at line 201 of file ppinitialReduction.cc.

202 {
203  poly g = *gStar;
204  if (g==NULL || n_DivBy(p_GetCoeff(g,r),p,r->cf))
205  return;
206  p_Test(g,r);
207 
208  // create p-t
209  poly pt = p_Init(r);
210  p_SetCoeff(pt,n_Copy(p,r->cf),r);
211 
212  pNext(pt) = p_Init(r);
213  p_SetExp(pNext(pt),1,1,r);
214  p_Setm(pNext(pt),r);
215  p_SetCoeff(pNext(pt),n_Init(-1,r->cf),r);
216 
217  // make g monic with the help of p-t
218  number a,b;
219  number gcd = n_ExtGcd(p_GetCoeff(g,r),p,&a,&b,r->cf);
220  assume(n_IsUnit(gcd,r->cf));
221  // now a*leadcoef(g)+b*p = gcd with gcd being a unit
222  // so a*g+b*(p-t)*leadmonom(g) should have a unit as leading coefficient
223  // but first check whether b is 0,
224  // since p_Mult_nn doesn't allow 0 as number input
225  if (n_IsZero(b,r->cf))
226  {
227  n_Delete(&a,r->cf);
228  n_Delete(&b,r->cf);
229  n_Delete(&gcd,r->cf);
230  p_Delete(&pt,r);
231  return;
232  }
233  poly m = p_Head(g,r);
234  p_SetCoeff(m,n_Init(1,r->cf),r);
235  g = p_Add_q(p_Mult_nn(g,a,r),p_Mult_nn(p_Mult_mm(pt,m,r),b,r),r);
236  n_Delete(&a,r->cf);
237  n_Delete(&b,r->cf);
238  n_Delete(&gcd,r->cf);
239  p_Delete(&m,r);
240 
241  p_Test(g,r);
242  return;
243 }
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
const poly a
Definition: syzextra.cc:212
return P p
Definition: myNF.cc:203
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:968
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
g
Definition: cfModGcd.cc:4031
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:812
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:394
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 m
Definition: cfEzgcd.cc:119
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:895
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
#define p_Test(p, r)
Definition: p_polys.h:160
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
static FORCE_INLINE number n_ExtGcd(number a, number b, number *s, number *t, const coeffs r)
beware that ExtGCD is only relevant for a few chosen coeff. domains and may perform something unexpec...
Definition: coeffs.h:697
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
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:455
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define pNext(p)
Definition: monomials.h:43
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
#define p_GetCoeff(p, r)
Definition: monomials.h:57
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
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1243
const poly b
Definition: syzextra.cc:213

◆ ptNormalize() [2/3]

void ptNormalize ( ideal  I,
const number  p,
const ring  r 
)

Definition at line 245 of file ppinitialReduction.cc.

246 {
247  for (int i=0; i<IDELEMS(I); i++)
248  ptNormalize(&(I->m[i]),p,r);
249  return;
250 }
return P p
Definition: myNF.cc:203
const ring r
Definition: syzextra.cc:208
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
void ptNormalize(poly *gStar, const number p, const ring r)

◆ ptNormalize() [3/3]

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();
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:82
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:94
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:98
int Typ()
Definition: subexpr.cc:995
poly res
Definition: myNF.cc:322
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:86
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
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:707

◆ sortMarks()

static void sortMarks ( const ideal  H,
const ring  r,
std::vector< mark > &  T 
)
static

Definition at line 458 of file ppinitialReduction.cc.

459 {
460  std::pair<int,int> pointerToTerm;
461  int k=T.size();
462  do
463  {
464  int j=0;
465  for (int i=1; i<k-1; i++)
466  {
467  int generatorA = T[i-1].first;
468  int termA = T[i-1].second;
469  int generatorB = T[i].first;
470  int termB = T[i].second;
471  if (p_LmCmp(ppNext(H->m[generatorA],termA),ppNext(H->m[generatorB],termB),r)<0)
472  {
473  mark cache=T[i-1];
474  T[i-1]=T[i];
475  T[i]=cache;
476  j = i;
477  }
478  }
479  k=j;
480  } while(k);
481  return;
482 }
static poly ppNext(poly p, int l)
std::pair< int, int > mark
int k
Definition: cfEzgcd.cc:93
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1467
int i
Definition: cfEzgcd.cc:123
CanonicalForm H
Definition: facAbsFact.cc:64
static jList * T
Definition: janet.cc:37