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