nc.cc
Go to the documentation of this file.
1 #define PLURAL_INTERNAL_DECLARATIONS
2 
3 
4 
5 
6 #include <kernel/mod2.h>
7 
8 #include <misc/options.h>
9 
10 #include <polys/simpleideals.h>
11 #include <polys/prCopy.h>
12 #include <polys/nc/gb_hack.h>
13 
14 #include <kernel/polys.h>
15 
16 #include <kernel/ideals.h>
17 #include <kernel/GBEngine/kstd1.h>
18 
19 #include <kernel/GBEngine/nc.h>
20 
21 ideal twostd(ideal I) // works in currRing only!
22 {
23  ideal J = kStd(I, currRing->qideal, testHomog, NULL, NULL, 0, 0, NULL); // in currRing!!!
24  idSkipZeroes(J); // ring independent!
25 
26  const int rN = currRing->N;
27 
28  loop
29  {
30  ideal K = NULL;
31  const int s = idElem(J); // ring independent
32 
33  for(int i = 0; i < s; i++)
34  {
35  const poly p = J->m[i];
36 
37 #ifdef PDEBUG
38  p_Test(p, currRing);
39 #if 0
40  PrintS("p: "); // !
41  p_Write(p, currRing);
42 #endif
43 #endif
44 
45  for (int j = 1; j <= rN; j++) // for all j = 1..N
46  {
47  poly varj = p_One( currRing);
48  p_SetExp(varj, j, 1, currRing);
49  p_Setm(varj, currRing);
50 
51  poly q = pp_Mult_mm(p, varj, currRing); // q = J[i] * var(j),
52 
53 #ifdef PDEBUG
54  p_Test(varj, currRing);
55  p_Test(p, currRing);
56  p_Test(q, currRing);
57 #if 0
58  PrintS("Reducing p: "); // !
59  p_Write(p, currRing);
60  PrintS("With q: "); // !
61  p_Write(q, currRing);
62 #endif
63 #endif
64 
65  p_Delete(&varj, currRing);
66 
67  if (q != NULL)
68  {
69 #ifdef PDEBUG
70 #if 0
71  Print("Reducing q[j = %d]: ", j); // !
72  p_Write(q, currRing);
73 
74  PrintS("With p:");
75  p_Write(p, currRing);
76 
77 #endif
78 #endif
79 
80  // bug: lm(p) may not divide lm(p * var(i)) in a SCA!
81  if( p_LmDivisibleBy(p, q, currRing) )
82  q = nc_ReduceSpoly(p, q, currRing);
83 
84 
85 #ifdef PDEBUG
86  p_Test(q, currRing);
87 #if 0
88  PrintS("reductum q/p: ");
89  p_Write(q, currRing);
90 
91  // PrintS("With J!\n");
92 #endif
93 #endif
94 
95 // if( q != NULL)
96  q = kNF(J, currRing->qideal, q, 0, KSTD_NF_NONORM); // in currRing!!!
97 
98 #ifdef PDEBUG
99  p_Test(q, currRing);
100 #if 0
101  PrintS("NF(J/currRing->qideal)=> q: "); // !
102  p_Write(q, currRing);
103 #endif
104 #endif
105  if (q!=NULL)
106  {
107  if (p_IsConstant(q, currRing)) // => return (1)!
108  {
109  p_Delete(&q, currRing);
110  id_Delete(&J, currRing);
111 
112  if (K != NULL)
113  id_Delete(&K, currRing);
114 
115  ideal Q = idInit(1,1); // ring independent!
116  Q->m[0] = p_One(currRing);
117 
118  return(Q);
119  }
120 
121 // flag = false;
122 
123  // K += q:
124 
125  ideal Q = idInit(1,1); // ring independent
126  Q->m[0]=q;
127 
128  if( K == NULL )
129  K = Q;
130  else
131  {
132  ideal id_tmp = idSimpleAdd(K, Q); // in currRing
133  id_Delete(&K, currRing);
134  id_Delete(&Q, currRing);
135  K = id_tmp; // K += Q
136  }
137  }
138 
139 
140  } // if q != NULL
141  } // for all variables
142 
143  }
144 
145  if (K == NULL) // nothing new: i.e. all elements are two-sided
146  return(J);
147  // now we update GrBasis J with K
148  // iSize=IDELEMS(J);
149 #ifdef PDEBUG
150  idTest(J); // in currRing!
151 #if 0
152  PrintS("J:");
153  idPrint(J);
154  PrintLn();
155 #endif // debug
156 #endif
157 
158 
159 
160 #ifdef PDEBUG
161  idTest(K); // in currRing!
162 #if 0
163  PrintS("+K:");
164  idPrint(K);
165  PrintLn();
166 #endif // debug
167 #endif
168 
169 
170  int iSize = idElem(J); // ring independent
171 
172  // J += K:
173  ideal id_tmp = idSimpleAdd(J,K); // in currRing
175 
176 #if 1
177  BITSET save1;
178  SI_SAVE_OPT1(save1);
179  si_opt_1|=Sy_bit(OPT_SB_1); // ring independent
180  J = kStd(id_tmp, currRing->qideal, testHomog, NULL, NULL, 0, iSize); // J = J + K, J - std // in currRing!
181  SI_RESTORE_OPT1(save1);
182 #else
183  J=kStd(id_tmp, currRing->qideal,testHomog,NULL,NULL,0,0,NULL);
184 #endif
185 
186  id_Delete(&id_tmp, currRing);
187  idSkipZeroes(J); // ring independent
188 
189 #ifdef PDEBUG
190  idTest(J); // in currRing!
191 #if 0
192  PrintS("J:");
193  idPrint(J);
194  PrintLn();
195 #endif // debug
196 #endif
197  } // loop
198 }
199 
200 
201 
202 
203 static ideal idPrepareStd(ideal T, ideal s, int k)
204 {
205  // T is a left SB, without zeros, s is a list with zeros
206 #ifdef PDEBUG
207  if (IDELEMS(s)!=IDELEMS(T))
208  {
209  PrintS("ideals of diff. size!!!");
210  }
211 #endif
212  ideal t = idCopy(T);
213  int j,rs=id_RankFreeModule(s, currRing);
214  poly p,q;
215 
216  ideal res = idInit(2*idElem(t),1+idElem(t));
217  if (rs == 0)
218  {
219  for (j=0; j<IDELEMS(t); j++)
220  {
221  if (s->m[j]!=NULL) pSetCompP(s->m[j],1);
222  if (t->m[j]!=NULL) pSetCompP(t->m[j],1);
223  }
224  k = si_max(k,1);
225  }
226  for (j=0; j<IDELEMS(t); j++)
227  {
228  if (s->m[j]!=NULL)
229  {
230  p = s->m[j];
231  q = pOne();
232  pSetComp(q,k+1+j);
233  pSetmComp(q);
234 #if 0
235  while (pNext(p)) pIter(p);
236  pNext(p) = q;
237 #else
238  p = pAdd(p,q);
239  s->m[j] = p;
240 #ifdef PDEBUG
241  pTest(p);
242 #endif
243 #endif
244  }
245  }
246  res = idSimpleAdd(t,s);
247  idDelete(&t);
248  res->rank = 1+idElem(T);
249  return(res);
250 }
251 
252 
253 ideal Approx_Step(ideal L)
254 {
255  int N=currRing->N;
256  int i,j; // k=syzcomp
257  int flag, flagcnt=0, syzcnt=0;
258  int syzcomp = 0;
259  ideal I = kStd(L, currRing->qideal,testHomog,NULL,NULL,0,0,NULL);
260  idSkipZeroes(I);
261  ideal s_I;
262  int idI = idElem(I);
263  ideal trickyQuotient;
264  if (currRing->qideal !=NULL)
265  {
266  trickyQuotient = idSimpleAdd(currRing->qideal,I);
267  }
268  else
269  trickyQuotient = I;
270  idSkipZeroes(trickyQuotient);
271  poly *var = (poly *)omAlloc0((N+1)*sizeof(poly));
272  // poly *W = (poly *)omAlloc0((2*N+1)*sizeof(poly));
273  resolvente S = (resolvente)omAlloc0((N+1)*sizeof(ideal));
274  ideal SI, res;
275  matrix MI;
276  poly x=pOne();
277  var[0]=x;
278  ideal h2, s_h2, s_h3;
279  poly p,q;
280  // init vars
281  for (i=1; i<=N; i++ )
282  {
283  x = pOne();
284  pSetExp(x,i,1);
285  pSetm(x);
286  var[i]=pCopy(x);
287  }
288  // init NF's
289  for (i=1; i<=N; i++ )
290  {
291  h2 = idInit(idI,1);
292  flag = 0;
293  for (j=0; j< idI; j++ )
294  {
295  q = pp_Mult_mm(I->m[j],var[i],currRing);
296  q = kNF(I,currRing->qideal,q,0,0);
297  if (q!=0)
298  {
299  h2->m[j]=pCopy(q);
300  // p_Shift(&(h2->m[flag]),1, currRing);
301  flag++;
302  pDelete(&q);
303  }
304  else
305  h2->m[j]=0;
306  }
307  // W[1..IDELEMS(I)]
308  if (flag >0)
309  {
310  // compute syzygies with values in I
311  // idSkipZeroes(h2);
312  // h2 = idSimpleAdd(h2,I);
313  // h2->rank=flag+idI+1;
314  idTest(h2);
315  //idShow(h2);
316  ring orig_ring = currRing;
317  ring syz_ring = rAssure_SyzComp(orig_ring, TRUE);
318  syzcomp = 1;
319  rSetSyzComp(syzcomp, syz_ring);
320  if (orig_ring != syz_ring)
321  {
322  rChangeCurrRing(syz_ring);
323  s_h2=idrCopyR_NoSort(h2,orig_ring, syz_ring);
324  // s_trickyQuotient=idrCopyR_NoSort(trickyQuotient,orig_ring);
325  // rDebugPrint(syz_ring);
326  s_I=idrCopyR_NoSort(I,orig_ring, syz_ring);
327  }
328  else
329  {
330  s_h2 = h2;
331  s_I = I;
332  // s_trickyQuotient=trickyQuotient;
333  }
334  idTest(s_h2);
335  // idTest(s_trickyQuotient);
336  Print(".proceeding with the variable %d\n",i);
337  s_h3 = idPrepareStd(s_I, s_h2, 1);
338  BITSET save1;
339  SI_SAVE_OPT1(save1);
341  idTest(s_h3);
342  idDelete(&s_h2);
343  s_h2=idCopy(s_h3);
344  idDelete(&s_h3);
345  PrintS("...computing Syz");
346  s_h3 = kStd(s_h2, currRing->qideal,(tHomog)FALSE,NULL,NULL,syzcomp,idI);
347  SI_RESTORE_OPT1(save1);
348  //idShow(s_h3);
349  if (orig_ring != syz_ring)
350  {
351  idDelete(&s_h2);
352  for (j=0; j<IDELEMS(s_h3); j++)
353  {
354  if (s_h3->m[j] != NULL)
355  {
356  if (p_MinComp(s_h3->m[j],syz_ring) > syzcomp) // i.e. it is a syzygy
357  p_Shift(&s_h3->m[j], -syzcomp, currRing);
358  else
359  pDelete(&s_h3->m[j]);
360  }
361  }
362  idSkipZeroes(s_h3);
363  s_h3->rank -= syzcomp;
364  rChangeCurrRing(orig_ring);
365  // s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
366  s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
367  rDelete(syz_ring);
368  }
369  idTest(s_h3);
370  S[syzcnt]=kStd(s_h3,currRing->qideal,(tHomog)FALSE,NULL,NULL);
371  syzcnt++;
372  idDelete(&s_h3);
373  } // end if flag >0
374  else
375  {
376  flagcnt++;
377  }
378  }
379  if (flagcnt == N)
380  {
381  PrintS("the input is a two--sided ideal");
382  return(I);
383  }
384  if (syzcnt >0)
385  {
386  Print("..computing Intersect of %d modules\n",syzcnt);
387  if (syzcnt == 1)
388  SI = S[0];
389  else
390  SI = idMultSect(S, syzcnt);
391  //idShow(SI);
392  MI = id_Module2Matrix(SI,currRing);
393  res= idInit(MATCOLS(MI),1);
394  for (i=1; i<= MATCOLS(MI); i++)
395  {
396  p = NULL;
397  for (j=0; j< idElem(I); j++)
398  {
399  q = pCopy(MATELEM(MI,j+1,i));
400  if (q!=NULL)
401  {
402  q = pMult(q,pCopy(I->m[j]));
403  p = pAdd(p,q);
404  }
405  }
406  res->m[i-1]=p;
407  }
408  PrintS("final std");
409  res = kStd(res, currRing->qideal,testHomog,NULL,NULL,0,0,NULL);
410  idSkipZeroes(res);
411  return(res);
412  }
413  else
414  {
415  PrintS("No syzygies");
416  return(I);
417  }
418 }
#define pSetmComp(p)
TODO:
Definition: polys.h:255
const CanonicalForm int s
Definition: facAbsFact.cc:55
unsigned si_opt_1
Definition: options.c:5
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
#define pSetm(p)
Definition: polys.h:253
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
#define pAdd(p, q)
Definition: polys.h:186
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
loop
Definition: myNF.cc:98
#define pSetExp(p, i, v)
Definition: polys.h:42
#define FALSE
Definition: auxiliary.h:94
Compatiblity layer for legacy polynomial operations (over currRing)
return P p
Definition: myNF.cc:203
#define pTest(p)
Definition: polys.h:398
#define idSimpleAdd(A, B)
Definition: ideals.h:42
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:957
#define TRUE
Definition: auxiliary.h:98
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2231
ideal idMultSect(resolvente arg, int length)
Definition: ideals.cc:340
#define SI_SAVE_OPT1(A)
Definition: options.h:20
int k
Definition: cfEzgcd.cc:93
#define Q
Definition: sirandom.c:25
#define BITSET
Definition: structs.h:18
#define Sy_bit(x)
Definition: options.h:30
#define pIter(p)
Definition: monomials.h:44
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
#define idPrint(id)
Definition: ideals.h:46
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
poly p_One(const ring r)
Definition: p_polys.cc:1312
tHomog
Definition: structs.h:37
int j
Definition: myNF.cc:70
#define pSetCompP(a, i)
Definition: polys.h:285
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1876
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition: ring.cc:4349
static ideal idPrepareStd(ideal T, ideal s, int k)
Definition: nc.cc:203
static poly nc_ReduceSpoly(const poly p1, poly p2, const ring r)
Definition: nc.h:271
#define pSetComp(p, v)
Definition: polys.h:38
static int si_max(const int a, const int b)
Definition: auxiliary.h:120
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:308
#define pOne()
Definition: polys.h:297
matrix id_Module2Matrix(ideal mod, const ring R)
#define IDELEMS(i)
Definition: simpleideals.h:24
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1768
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
ideal idCopy(ideal A)
Definition: ideals.h:60
#define p_Test(p, r)
Definition: p_polys.h:160
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:4954
ideal Approx_Step(ideal L)
Ann: ???
Definition: nc.cc:253
void rChangeCurrRing(ring r)
Definition: polys.cc:12
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4514
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define KSTD_NF_NONORM
Definition: kstd1.h:21
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 MATCOLS(i)
Definition: matpol.h:28
#define NULL
Definition: omList.c:10
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
#define pMult(p, q)
Definition: polys.h:190
#define pDelete(p_ptr)
Definition: polys.h:169
Variable x
Definition: cfModGcd.cc:4023
#define pNext(p)
Definition: monomials.h:43
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
ideal * resolvente
Definition: ideals.h:18
int idElem(const ideal F)
count non-zero elements
#define OPT_SB_1
Definition: options.h:90
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:206
static jList * T
Definition: janet.cc:37
polyrec * poly
Definition: hilb.h:10
#define SI_RESTORE_OPT1(A)
Definition: options.h:23
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:206
#define omAlloc0(size)
Definition: omAllocDecl.h:211
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:262
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168
#define MATELEM(mat, i, j)
Definition: matpol.h:29
#define idTest(id)
Definition: ideals.h:47
ideal twostd(ideal I)
Compute two-sided GB:
Definition: nc.cc:21