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