ringgb.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: ringgb interface
6 */
7 //#define HAVE_TAIL_RING
8 #define NO_BUCKETS
9 
10 
11 
12 
13 #include <kernel/mod2.h>
14 #include <kernel/GBEngine/kutil.h>
15 #include <kernel/structs.h>
16 #include <omalloc/omalloc.h>
17 #include <kernel/polys.h>
19 #include <kernel/ideals.h>
20 #include <kernel/GBEngine/kstd1.h>
21 #include <kernel/GBEngine/khstd.h>
22 #include <polys/kbuckets.h>
23 #include <polys/weight.h>
24 #include <misc/intvec.h>
25 #include <kernel/polys.h>
26 #ifdef HAVE_PLURAL
27 #include <polys/nc/nc.h>
28 #endif
29 
30 #include <kernel/GBEngine/ringgb.h>
31 
32 #ifdef HAVE_RINGS
34 {
35  return kFindZeroPoly(p, r, r);
36 }
37 
38 /*
39  * Returns maximal k, such that
40  * 2^k | n
41  */
42 int indexOf2(number n)
43 {
44  long test = (long) n;
45  int i = 0;
46  while (test%2 == 0)
47  {
48  i++;
49  test = test / 2;
50  }
51  return i;
52 }
53 
54 /***************************************************************
55  *
56  * Lcm business
57  *
58  ***************************************************************/
59 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
60 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
61 BOOLEAN ring2toM_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
62  poly &m1, poly &m2, const ring m_r)
63 {
64  int i;
65  int x;
66  m1 = p_Init(m_r);
67  m2 = p_Init(m_r);
68 
69  for (i = p_r->N; i; i--)
70  {
71  x = p_GetExpDiff(p1, p2, i, p_r);
72  if (x > 0)
73  {
74  p_SetExp(m2,i,x, m_r);
75  p_SetExp(m1,i,0, m_r);
76  }
77  else
78  {
79  p_SetExp(m1,i,-x, m_r);
80  p_SetExp(m2,i,0, m_r);
81  }
82  }
83  p_Setm(m1, m_r);
84  p_Setm(m2, m_r);
85  long cp1 = (long) pGetCoeff(p1);
86  long cp2 = (long) pGetCoeff(p2);
87  if (cp1 != 0 && cp2 != 0)
88  {
89  while (cp1%2 == 0 && cp2%2 == 0)
90  {
91  cp1 = cp1 / 2;
92  cp2 = cp2 / 2;
93  }
94  }
95  p_SetCoeff(m1, (number) cp2, m_r);
96  p_SetCoeff(m2, (number) cp1, m_r);
97  return TRUE;
98 }
99 
100 void printPolyMsg(const char * start, poly f, const char * end)
101 {
102  PrintS(start);
103  wrp(f);
104  PrintS(end);
105 }
106 
108 {
109  poly m1 = NULL;
110  poly m2 = NULL;
111  ring2toM_GetLeadTerms(f, g, r, m1, m2, r);
112  // printPolyMsg("spoly: m1=", m1, " | ");
113  // printPolyMsg("m2=", m2, "");
114  // PrintLn();
115  poly sp = pSub(p_Mult_mm(f, m1, r), pp_Mult_mm(g, m2, r));
116  pDelete(&m1);
117  pDelete(&m2);
118  return(sp);
119 }
120 
121 poly ringRedNF (poly f, ideal G, ring r)
122 {
123  // If f = 0, then normal form is also 0
124  if (f == NULL) { return NULL; }
125  poly h = NULL;
126  poly g = pCopy(f);
127  int c = 0;
128  while (g != NULL)
129  {
130  Print("%d-step RedNF - g=", c);
131  wrp(g);
132  PrintS(" | h=");
133  wrp(h);
134  PrintLn();
135  g = ringNF(g, G, r);
136  if (g != NULL) {
137  h = pAdd(h, pHead(g));
138  pLmDelete(&g);
139  }
140  c++;
141  }
142  return h;
143 }
144 
145 #endif
146 
147 #ifdef HAVE_RINGS
148 
149 /*
150  * Find an index i from G, such that
151  * LT(rside) = x * LT(G[i]) has a solution
152  * or -1 if rside is not in the
153  * ideal of the leading coefficients
154  * of the suitable g from G.
155  */
156 int findRingSolver(poly rside, ideal G, ring r)
157 {
158  if (rside == NULL) return -1;
159  int i;
160 // int iO2rside = indexOf2(pGetCoeff(rside));
161  for (i = 0; i < IDELEMS(G); i++)
162  {
163  if // (indexOf2(pGetCoeff(G->m[i])) <= iO2rside && / should not be necessary any more
164  (p_LmDivisibleBy(G->m[i], rside, r))
165  {
166  return i;
167  }
168  }
169  return -1;
170 }
171 
173 {
174  number cf = nCopy(pGetCoeff(f)), cg = nCopy(pGetCoeff(g));
175  (void)ksCheckCoeff(&cf, &cg, currRing->cf); // gcd and zero divisors
176  poly fm, gm;
177  k_GetLeadTerms(f, g, currRing, fm, gm, currRing);
178  pSetCoeff0(fm, cg);
179  pSetCoeff0(gm, cf); // and now, m1 * LT(p1) == m2 * LT(p2)
180  poly sp = pSub(ppMult_mm(f, fm), ppMult_mm(g, gm));
181  pDelete(&fm);
182  pDelete(&gm);
183  return(sp);
184 }
185 
186 /*2
187 * Generates spoly(0, h) if applicable. Assumes ring in Z/2^n.
188 */
190 {
191  poly p = NULL;
192  number gcd = n_Gcd((number) 0, pGetCoeff(h), currRing->cf);
193  if (!n_IsOne( gcd, currRing->cf ))
194  {
195  number tmp=n_Ann(gcd,currRing->cf);
196  p = p_Copy(h->next, currRing);
197  p = p_Mult_nn(p, tmp, currRing);
198  n_Delete(&tmp,currRing->cf);
199  }
200  return p;
201 }
202 
203 poly ringNF(poly f, ideal G, ring r)
204 {
205  // If f = 0, then normal form is also 0
206  if (f == NULL) { return NULL; }
207  poly tmp = NULL;
208  poly h = pCopy(f);
209  int i = findRingSolver(h, G, r);
210  int c = 1;
211  while (h != NULL && i >= 0) {
212 // Print("%d-step NF - h:", c);
213 // wrp(h);
214 // PrintS(" ");
215 // PrintS("G->m[i]:");
216 // wrp(G->m[i]);
217 // PrintLn();
218  tmp = h;
219  h = plain_spoly(h, G->m[i]);
220  pDelete(&tmp);
221 // PrintS("=> h=");
222 // wrp(h);
223 // PrintLn();
224  i = findRingSolver(h, G, r);
225  c++;
226  }
227  return h;
228 }
229 
230 int testGB(ideal I, ideal GI) {
231  poly f, g, h, nf;
232  int i = 0;
233  int j = 0;
234  PrintS("I included?");
235  for (i = 0; i < IDELEMS(I); i++) {
236  if (ringNF(I->m[i], GI, currRing) != NULL) {
237  PrintS("Not reduced to zero from I: ");
238  wrp(I->m[i]);
239  PrintS(" --> ");
240  wrp(ringNF(I->m[i], GI, currRing));
241  PrintLn();
242  return(0);
243  }
244  PrintS("-");
245  }
246  PrintS(" Yes!\nspoly --> 0?");
247  for (i = 0; i < IDELEMS(GI); i++)
248  {
249  for (j = i + 1; j < IDELEMS(GI); j++)
250  {
251  f = pCopy(GI->m[i]);
252  g = pCopy(GI->m[j]);
253  h = plain_spoly(f, g);
254  nf = ringNF(h, GI, currRing);
255  if (nf != NULL)
256  {
257  PrintS("spoly(");
258  wrp(GI->m[i]);
259  PrintS(", ");
260  wrp(GI->m[j]);
261  PrintS(") = ");
262  wrp(h);
263  PrintS(" --> ");
264  wrp(nf);
265  PrintLn();
266  return(0);
267  }
268  pDelete(&f);
269  pDelete(&g);
270  pDelete(&h);
271  pDelete(&nf);
272  PrintS("-");
273  }
274  }
275  if (!(rField_is_Domain(currRing)))
276  {
277  PrintS(" Yes!\nzero-spoly --> 0?");
278  for (i = 0; i < IDELEMS(GI); i++)
279  {
280  f = plain_zero_spoly(GI->m[i]);
281  nf = ringNF(f, GI, currRing);
282  if (nf != NULL) {
283  PrintS("spoly(");
284  wrp(GI->m[i]);
285  PrintS(", ");
286  wrp(0);
287  PrintS(") = ");
288  wrp(h);
289  PrintS(" --> ");
290  wrp(nf);
291  PrintLn();
292  return(0);
293  }
294  pDelete(&f);
295  pDelete(&nf);
296  PrintS("-");
297  }
298  }
299  PrintS(" Yes!");
300  PrintLn();
301  return(1);
302 }
303 
304 #endif
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:685
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition: kInline.h:964
void PrintLn()
Definition: reporter.cc:322
#define Print
Definition: emacs.cc:83
#define pAdd(p, q)
Definition: polys.h:174
Compatiblity layer for legacy polynomial operations (over currRing)
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:973
#define ppMult_mm(p, m)
Definition: polys.h:172
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
int ksCheckCoeff(number *a, number *b)
int findRingSolver(poly rside, ideal G, ring r)
Definition: ringgb.cc:156
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:962
#define TRUE
Definition: auxiliary.h:144
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:440
poly reduce_poly_fct(poly p, ring r)
Definition: ringgb.cc:33
g
Definition: cfModGcd.cc:4031
int testGB(ideal I, ideal GI)
Definition: ringgb.cc:230
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
static TreeM * G
Definition: janet.cc:38
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:401
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:811
static FORCE_INLINE number n_Ann(number a, const coeffs r)
if r is a ring with zero divisors, return an annihilator!=0 of b otherwise return NULL ...
Definition: coeffs.h:700
poly spolyRing2toM(poly f, poly g, ring r)
Definition: ringgb.cc:107
Definition: gnumpfl.cc:60
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition: p_polys.h:631
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
const ring r
Definition: syzextra.cc:208
BOOLEAN ring2toM_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition: ringgb.cc:61
#define pSub(a, b)
Definition: polys.h:258
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:902
void printPolyMsg(const char *start, poly f, const char *end)
Definition: ringgb.cc:100
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
#define IDELEMS(i)
Definition: simpleideals.h:24
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1676
int indexOf2(number n)
Definition: ringgb.cc:42
poly ringRedNF(poly f, ideal G, ring r)
Definition: ringgb.cc:121
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:295
poly plain_spoly(poly f, poly g)
Definition: ringgb.cc:172
CanonicalForm test
Definition: cfModGcd.cc:4037
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
CanonicalForm cf
Definition: cfModGcd.cc:4024
#define NULL
Definition: omList.c:10
CanonicalForm cg
Definition: cfModGcd.cc:4024
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define pDelete(p_ptr)
Definition: polys.h:157
Variable x
Definition: cfModGcd.cc:4023
#define nCopy(n)
Definition: numbers.h:15
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
#define pSetCoeff0(p, n)
Definition: monomials.h:67
poly plain_zero_spoly(poly h)
Definition: ringgb.cc:189
END_NAMESPACE const void * p2
Definition: syzextra.cc:202
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
void wrp(poly p)
Definition: polys.h:281
polyrec * poly
Definition: hilb.h:10
poly ringNF(poly f, ideal G, ring r)
Definition: ringgb.cc:203
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:131
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1248
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156