Functions
ppinitialReduction.cc File Reference
#include "polys/monomials/p_polys.h"
#include "Singular/ipid.h"
#include "singularWishlist.h"
#include "ppinitialReduction.h"

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

479 {
480  for (unsigned i=0; i<T.size(); i++)
481  {
482  if (T[i].first>=newEntry)
483  T[i].first = T[i].first+1;
484  }
485  return;
486 }
int i
Definition: cfEzgcd.cc:125

◆ cleanupMarks()

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

Definition at line 489 of file ppinitialReduction.cc.

490 {
491  for (unsigned i=0; i<T.size();)
492  {
493  if (getTerm(H,T[i])==NULL)
494  T.erase(T.begin()+i);
495  else
496  i++;
497  }
498  return;
499 }
static poly getTerm(const ideal H, const mark ab)
int i
Definition: cfEzgcd.cc:125
CanonicalForm H
Definition: facAbsFact.cc:64
#define NULL
Definition: omList.c:12

◆ divideByCommonGcd()

void divideByCommonGcd ( poly &  g,
const ring  r 
)

Definition at line 21 of file ppinitialReduction.cc.

22 {
23  number commonGcd = n_Copy(p_GetCoeff(g,r),r->cf);
24  for (poly gCache=pNext(g); gCache; pIter(gCache))
25  {
26  number commonGcdCache = n_Gcd(commonGcd,p_GetCoeff(gCache,r),r->cf);
27  n_Delete(&commonGcd,r->cf);
28  commonGcd = commonGcdCache;
29  if (n_IsOne(commonGcd,r->cf))
30  {
31  n_Delete(&commonGcd,r->cf);
32  return;
33  }
34  }
35  for (poly gCache=g; gCache; pIter(gCache))
36  {
37  number oldCoeff = p_GetCoeff(gCache,r);
38  number newCoeff = n_Div(oldCoeff,commonGcd,r->cf);
39  p_SetCoeff(gCache,newCoeff,r);
40  }
41  p_Test(g,r);
42  n_Delete(&commonGcd,r->cf);
43  return;
44 }
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:686
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:468
g
Definition: cfModGcd.cc:4031
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:411
#define pIter(p)
Definition: monomials.h:37
#define p_Test(p, r)
Definition: p_polys.h:162
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:451
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
#define pNext(p)
Definition: monomials.h:36
#define p_GetCoeff(p, r)
Definition: monomials.h:50
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455

◆ getTerm()

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

Definition at line 470 of file ppinitialReduction.cc.

471 {
472  int a = ab.first;
473  int b = ab.second;
474  return ppNext(H->m[a],b);
475 }
static poly ppNext(poly p, int l)
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm H
Definition: facAbsFact.cc:64

◆ 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:55
poly p_One(const ring r)
Definition: p_polys.cc:1303
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1496
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:856
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:487
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232

◆ p_xLeadmonomDivisibleBy()

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

Definition at line 118 of file ppinitialReduction.cc.

119 {
120  poly gx = p_Head(g,r);
121  poly fx = p_Head(f,r);
122  p_SetExp(gx,1,0,r);
123  p_SetExp(fx,1,0,r);
124  p_Setm(gx,r);
125  p_Setm(fx,r);
126  bool b = p_LeadmonomDivisibleBy(gx,fx,r);
127  p_Delete(&gx,r);
128  p_Delete(&fx,r);
129  return b;
130 }
g
Definition: cfModGcd.cc:4031
CanonicalForm b
Definition: cfModGcd.cc:4044
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:824
FILE * f
Definition: checklibs.c:9
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:856
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:487
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
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 430 of file ppinitialReduction.cc.

431 {
432  poly q = p;
433  for (int i=0; i<l; i++)
434  {
435  if (q==NULL)
436  break;
437  pIter(q);
438  }
439  return q;
440 }
#define pIter(p)
Definition: monomials.h:37
int i
Definition: cfEzgcd.cc:125
#define NULL
Definition: omList.c:12
int p
Definition: cfModGcd.cc:4019
int l
Definition: cfEzgcd.cc:93

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

283 {
284  poly h = *hStar;
285  if (h==NULL || g==NULL)
286  return false;
287  p_Test(h,r);
288  p_Test(g,r);
289  poly hCache;
290  for (hCache=h; hCache; pIter(hCache))
291  if (p_LeadmonomDivisibleBy(g,hCache,r)) break;
292  if (hCache)
293  {
294  number gAlpha = p_GetCoeff(g,r);
295  poly hAlphaT = p_Init(r);
296  p_SetCoeff(hAlphaT,n_Copy(p_GetCoeff(hCache,r),r->cf),r);
297  p_SetExp(hAlphaT,1,p_GetExp(hCache,1,r)-p_GetExp(g,1,r),r);
298  for (int i=2; i<=r->N; i++)
299  p_SetExp(hAlphaT,i,0,r);
300  p_Setm(hAlphaT,r); p_Test(hAlphaT,r);
301  poly q1 = p_Mult_nn(h,gAlpha,r); p_Test(q1,r);
302  poly q2 = p_Mult_q(p_Copy(g,r),hAlphaT,r); p_Test(q2,r);
303  q2 = p_Neg(q2,r); p_Test(q2,r);
304  h = p_Add_q(q1,q2,r);
305  p_Test(h,r);
306  p_Test(g,r);
307  *hStar = h;
308  return true;
309  }
310  p_Test(h,r);
311  p_Test(g,r);
312  return false;
313 }
g
Definition: cfModGcd.cc:4031
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:411
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:811
#define pIter(p)
Definition: monomials.h:37
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:468
int i
Definition: cfEzgcd.cc:125
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:913
#define p_Test(p, r)
Definition: p_polys.h:162
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:487
#define NULL
Definition: omList.c:12
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:451
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
#define p_GetCoeff(p, r)
Definition: monomials.h:50
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1042
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:891
static Poly * h
Definition: janet.cc:971
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1255
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1049
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 321 of file ppinitialReduction.cc.

322 {
323  idSkipZeroes(I);
324  int m=IDELEMS(I),n=m; poly cache;
325  do
326  {
327  int j=0;
328  for (int i=1; i<n; i++)
329  {
330  if (p_LmCmp(I->m[i-1],I->m[i],r)<0) /*p_LmCmp(p,q): requires: p,q!=NULL*/
331  {
332  cache=I->m[i-1];
333  I->m[i-1]=I->m[i];
334  I->m[i]=cache;
335  j = i;
336  }
337  }
338  n=j;
339  } while(n);
340  for (int i=0; i<m; i++)
341  pReduce(I->m[i],p,r);
342 
343  /***
344  * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
345  **/
346  for (int i=0; i<m-1; i++)
347  for (int j=i+1; j<m; j++)
348  if (ppreduceInitially(&I->m[j], I->m[i], r))
349  pReduce(I->m[j],p,r);
350 
351  /***
352  * the second pass. removing terms divisible by lt(g_j) out of g_i for i<j
353  **/
354  for (int i=0; i<m-1; i++)
355  for (int j=i+1; j<m; j++)
356  if (ppreduceInitially(&I->m[i], I->m[j],r))
357  pReduce(I->m[i],p,r);
358 
359  /***
360  * removes the elements of I which have been reduced to 0 in the previous two passes
361  **/
362  idSkipZeroes(I);
363  return false;
364 }
int j
Definition: facHensel.cc:105
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 pReduce(poly &g, const number p, const ring r)
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1496
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
#define IDELEMS(i)
Definition: simpleideals.h:23
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
int p
Definition: cfModGcd.cc:4019

◆ ppreduceInitially() [3/5]

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

Definition at line 372 of file ppinitialReduction.cc.

373 {
374  id_Test(I,r);
375  p_Test(g,r);
376  idInsertPoly(I,g);
377  idSkipZeroes(I);
378  int n=IDELEMS(I);
379  int j;
380  for (j=n-1; j>0; j--)
381  {
382  if (p_LmCmp(I->m[j], I->m[j-1],r)>0) /*p_LmCmp(p,q) requires: p,q!=NULL */
383  {
384  poly cache = I->m[j];
385  I->m[j] = I->m[j-1];
386  I->m[j-1] = cache;
387  }
388  else
389  break;
390  }
391 
392  /***
393  * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
394  * removing terms with the same monomials in x as lt(g_j) out of g_k for j<k
395  **/
396  for (int i=0; i<j; i++)
397  if (ppreduceInitially(&I->m[j], I->m[i], r))
398  pReduce(I->m[j],p,r);
399  for (int k=j+1; k<n; k++)
400  if (ppreduceInitially(&I->m[k], I->m[j], r))
401  {
402  pReduce(I->m[k],p,r);
403  for (int l=j+1; l<k; l++)
404  if (ppreduceInitially(&I->m[k], I->m[l], r))
405  pReduce(I->m[k],p,r);
406  }
407 
408  /***
409  * the second pass. removing terms divisible by lt(g_j) and lt(g_k) out of g_i for i<j<k
410  * removing terms divisible by lt(g_k) out of g_j for j<k
411  **/
412  for (int i=0; i<j; i++)
413  for (int k=j; k<n; k++)
414  if (ppreduceInitially(&I->m[i], I->m[k], r))
415  pReduce(I->m[i],p,r);
416  for (int k=j; k<n-1; k++)
417  for (int l=k+1; l<n; l++)
418  if (ppreduceInitially(&I->m[k], I->m[l], r))
419  pReduce(I->m[k],p,r);
420 
421  /***
422  * removes the elements of I which have been reduced to 0 in the previous two passes
423  **/
424  idSkipZeroes(I);
425  id_Test(I,r);
426  return j;
427 }
int j
Definition: facHensel.cc:105
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:79
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
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:1496
int i
Definition: cfEzgcd.cc:125
#define IDELEMS(i)
Definition: simpleideals.h:23
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define p_Test(p, r)
Definition: p_polys.h:162
int p
Definition: cfModGcd.cc:4019
int l
Definition: cfEzgcd.cc:93

◆ ppreduceInitially() [4/5]

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

Definition at line 508 of file ppinitialReduction.cc.

509 {
510  /***
511  * Step 1: reduce H initially with respect to itself and with respect to p-t
512  **/
513  if (ppreduceInitially(H,p,r)) return true;
514 
515  /***
516  * Step 2: initialize an ideal I in which the reductions will take place-
517  * along the reduction it will be enlarged with elements that will be discarded at the end
518  * initialize a working list T which keeps track.
519  * the working list T is a vector of pairs of integer.
520  * if T contains a pair (i,j) then that means that in the i-th element of H
521  * term j and subsequent terms need to be checked for reduction.
522  * T is sorted by the ordering on the temrs the pairs correspond to.
523  **/
524  int m=IDELEMS(H);
525  ideal I = idInit(m);
526  std::vector<mark> T;
527  for (int i=0; i<m; i++)
528  {
529  if(H->m[i]!=NULL)
530  {
531  I->m[i]=H->m[i];
532  if (pNext(I->m[i])!=NULL)
533  T.push_back(std::pair<int,int>(i,1));
534  }
535  }
536 
537  /***
538  * Step 3: as long as the working list is not empty, successively reduce terms in it
539  * by adding suitable elements to I and reducing it initially with respect to itself
540  **/
541  int k=IDELEMS(G);
542  while (T.size()>0)
543  {
544  sortMarks(I,r,T);
545  int i=0;
546  for (; i<k; i++)
547  {
548  if(G->m[i]!=NULL)
549  {
550  if (p_LeadmonomDivisibleBy(G->m[i],getTerm(I,T[0]),r)) break;
551  }
552  }
553  if (i<k)
554  {
555  poly g = p_One(r); poly h0 = getTerm(I,T[0]);
556  assume(h0!=NULL);
557  for (int j=2; j<=r->N; j++)
558  p_SetExp(g,j,p_GetExp(h0,j,r)-p_GetExp(G->m[i],j,r),r);
559  p_Setm(g,r);
560  g = p_Mult_q(g,p_Copy(G->m[i],r),r);
561  int newEntry = ppreduceInitially(I,p,g,r);
562  adjustMarks(T,newEntry);
563  }
564  else
565  T[0].second = T[0].second+1;
566  cleanupMarks(I,T);
567  }
568 
569  /***
570  * Step 4: cleanup, delete all polynomials in I which have been added in Step 3
571  **/
572  k=IDELEMS(I);
573  for (int i=0; i<k; i++)
574  {
575  if(I->m[i]!=NULL)
576  {
577  for (int j=0; j<m; j++)
578  {
579  if ((H->m[j]!=NULL)
580  && (p_LeadmonomDivisibleBy(H->m[j],I->m[i],r)))
581  {
582  I->m[i]=NULL;
583  break;
584  }
585  }
586  }
587  }
588  id_Delete(&I,r);
589  return false;
590 }
int j
Definition: facHensel.cc:105
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:92
static void cleanupMarks(const ideal H, std::vector< mark > &T)
static TreeM * G
Definition: janet.cc:31
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:811
poly p_One(const ring r)
Definition: p_polys.cc:1303
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:468
#define assume(x)
Definition: mod2.h:390
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
CanonicalForm H
Definition: facAbsFact.cc:64
#define IDELEMS(i)
Definition: simpleideals.h:23
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
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:487
#define NULL
Definition: omList.c:12
static void adjustMarks(std::vector< mark > &T, const int newEntry)
#define pNext(p)
Definition: monomials.h:36
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
int p
Definition: cfModGcd.cc:4019
static jList * T
Definition: janet.cc:30
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1049
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 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 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
int j
Definition: facHensel.cc:105
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:515
omBin sip_sideal_bin
Definition: simpleideals.cc:27
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:79
void * ADDRESS
Definition: auxiliary.h:133
int k
Definition: cfEzgcd.cc:92
static TreeM * G
Definition: janet.cc:31
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
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:468
#define assume(x)
Definition: mod2.h:390
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:121
int i
Definition: cfEzgcd.cc:125
CanonicalForm H
Definition: facAbsFact.cc:64
#define IDELEMS(i)
Definition: simpleideals.h:23
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:35
#define NULL
Definition: omList.c:12
static void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it
int p
Definition: cfModGcd.cc:4019
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2791
int l
Definition: cfEzgcd.cc:93

◆ pReduce() [1/2]

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

Definition at line 54 of file ppinitialReduction.cc.

55 {
56  if (g==NULL)
57  return;
58  p_Test(g,r);
59 
60  poly toBeChecked = pNext(g);
61  pNext(g) = NULL; poly gEnd = g;
62  poly gCache;
63 
64  number coeff, pPower; int power; poly subst;
65  while(toBeChecked)
66  {
67  for (gCache = g; gCache; pIter(gCache))
68  if (p_LeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
69  if (gCache)
70  {
71  n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
72  coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
73  p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
74  n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
75  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
76  }
77  else
78  {
79  if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
80  {
81  power=1;
82  coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
83  while (n_DivBy(coeff,p,r->cf))
84  {
85  power++;
86  number coeff0 = n_Div(coeff,p,r->cf);
87  n_Delete(&coeff,r->cf);
88  coeff = coeff0;
89  coeff0 = NULL;
90  if (power<1)
91  {
92  WerrorS("pReduce: overflow in exponent");
93  throw 0;
94  }
95  }
96  subst=p_LmInit(toBeChecked,r);
97  p_AddExp(subst,1,power,r);
98  p_SetCoeff(subst,coeff,r);
99  p_Setm(subst,r); p_Test(subst,r);
100  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
101  toBeChecked=p_Add_q(toBeChecked,subst,r);
102  p_Test(toBeChecked,r);
103  }
104  else
105  {
106  pNext(gEnd)=toBeChecked;
107  pIter(gEnd); pIter(toBeChecked);
108  pNext(gEnd)=NULL;
109  p_Test(g,r);
110  }
111  }
112  }
113  p_Test(g,r);
114  divideByCommonGcd(g,r);
115  return;
116 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:724
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:411
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
#define pIter(p)
Definition: monomials.h:37
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:636
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:468
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:656
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:775
#define p_Test(p, r)
Definition: p_polys.h:162
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:632
#define NULL
Definition: omList.c:12
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:36
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1270
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:605
#define p_GetCoeff(p, r)
Definition: monomials.h:50
#define pPower(p, q)
Definition: polys.h:199
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455
int p
Definition: cfModGcd.cc:4019
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:891
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 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 }
int k
Definition: cfEzgcd.cc:92
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:775
int i
Definition: cfEzgcd.cc:125
#define IDELEMS(i)
Definition: simpleideals.h:23
#define NULL
Definition: omList.c:12
#define p_GetCoeff(p, r)
Definition: monomials.h:50
int p
Definition: cfModGcd.cc:4019

◆ 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
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:724
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:411
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
#define pIter(p)
Definition: monomials.h:37
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:636
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:468
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:656
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:775
#define p_Test(p, r)
Definition: p_polys.h:162
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:632
#define NULL
Definition: omList.c:12
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:36
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1270
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:605
#define p_GetCoeff(p, r)
Definition: monomials.h:50
#define pPower(p, q)
Definition: polys.h:199
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455
int p
Definition: cfModGcd.cc:4019
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:891

◆ ptNormalize() [1/3]

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

Definition at line 196 of file ppinitialReduction.cc.

197 {
198  poly g = *gStar;
199  if (g==NULL || n_DivBy(p_GetCoeff(g,r),p,r->cf))
200  return;
201  p_Test(g,r);
202 
203  // create p-t
204  poly pt = p_Init(r);
205  p_SetCoeff(pt,n_Copy(p,r->cf),r);
206 
207  pNext(pt) = p_Init(r);
208  p_SetExp(pNext(pt),1,1,r);
209  p_Setm(pNext(pt),r);
210  p_SetCoeff(pNext(pt),n_Init(-1,r->cf),r);
211 
212  // make g monic with the help of p-t
213  number a,b;
214  number gcd = n_ExtGcd(p_GetCoeff(g,r),p,&a,&b,r->cf);
215  assume(n_IsUnit(gcd,r->cf));
216  // now a*leadcoef(g)+b*p = gcd with gcd being a unit
217  // so a*g+b*(p-t)*leadmonom(g) should have a unit as leading coefficient
218  poly m = p_Head(g,r);
219  p_SetCoeff(m,n_Init(1,r->cf),r);
220  g = p_Add_q(p_Mult_nn(g,a,r),p_Mult_nn(p_Mult_mm(pt,m,r),b,r),r);
221  n_Delete(&a,r->cf);
222  n_Delete(&b,r->cf);
223  n_Delete(&gcd,r->cf);
224  p_Delete(&m,r);
225 
226  p_Test(g,r);
227  return;
228 }
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:515
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:996
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:538
g
Definition: cfModGcd.cc:4031
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:411
CanonicalForm b
Definition: cfModGcd.cc:4044
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:824
#define assume(x)
Definition: mod2.h:390
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:775
int m
Definition: cfEzgcd.cc:121
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:913
#define p_Test(p, r)
Definition: p_polys.h:162
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:856
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:693
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:487
#define NULL
Definition: omList.c:12
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:451
int gcd(int a, int b)
Definition: walkSupport.cc:836
#define pNext(p)
Definition: monomials.h:36
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
#define p_GetCoeff(p, r)
Definition: monomials.h:50
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455
int p
Definition: cfModGcd.cc:4019
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:891
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1255

◆ ptNormalize() [2/3]

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

Definition at line 230 of file ppinitialReduction.cc.

231 {
232  for (int i=0; i<IDELEMS(I); i++)
233  ptNormalize(&(I->m[i]),p,r);
234  return;
235 }
int i
Definition: cfEzgcd.cc:125
#define IDELEMS(i)
Definition: simpleideals.h:23
void ptNormalize(poly *gStar, const number p, const ring r)
int p
Definition: cfModGcd.cc:4019

◆ ptNormalize() [3/3]

BOOLEAN ptNormalize ( leftv  res,
leftv  args 
)

Definition at line 238 of file ppinitialReduction.cc.

239 {
240  leftv u = args;
241  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
242  {
243  leftv v = u->next;
244  if ((v!=NULL) && (v->Typ()==NUMBER_CMD))
245  {
246  omUpdateInfo();
247  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
248  ideal I = (ideal) u->CopyD();
249  number p = (number) v->CopyD();
250  ptNormalize(I,p,currRing);
251  n_Delete(&p,currRing->cf);
252  res->rtyp = IDEAL_CMD;
253  res->data = (char*) I;
254  return FALSE;
255  }
256  }
257  return TRUE;
258 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
#define Print
Definition: emacs.cc:80
#define FALSE
Definition: auxiliary.h:94
#define TRUE
Definition: auxiliary.h:98
int Typ()
Definition: subexpr.cc:1033
void * data
Definition: subexpr.h:88
omInfo_t om_Info
Definition: omStats.c:16
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:12
int rtyp
Definition: subexpr.h:91
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455
int p
Definition: cfModGcd.cc:4019
#define omUpdateInfo()
Definition: xalloc.h:270
void * CopyD(int t)
Definition: subexpr.cc:739

◆ sortMarks()

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

Definition at line 443 of file ppinitialReduction.cc.

444 {
445  std::pair<int,int> pointerToTerm;
446  int k=T.size();
447  do
448  {
449  int j=0;
450  for (int i=1; i<k-1; i++)
451  {
452  int generatorA = T[i-1].first;
453  int termA = T[i-1].second;
454  int generatorB = T[i].first;
455  int termB = T[i].second;
456  if (p_LmCmp(ppNext(H->m[generatorA],termA),ppNext(H->m[generatorB],termB),r)<0)
457  {
458  mark cache=T[i-1];
459  T[i-1]=T[i];
460  T[i]=cache;
461  j = i;
462  }
463  }
464  k=j;
465  } while(k);
466  return;
467 }
int j
Definition: facHensel.cc:105
static poly ppNext(poly p, int l)
std::pair< int, int > mark
int k
Definition: cfEzgcd.cc:92
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1496
int i
Definition: cfEzgcd.cc:125
CanonicalForm H
Definition: facAbsFact.cc:64