My Project
Loading...
Searching...
No Matches
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
8#include "polys/prCopy.h"
9#include "polys/nc/gb_hack.h"
10
11#include "kernel/polys.h"
12
13#include "kernel/ideals.h"
15
16#include "kernel/GBEngine/nc.h"
17
18ideal 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
36#if 0
37 PrintS("p: "); // !
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);
53 p_Test(q, currRing);
54#if 0
55 PrintS("Reducing p: "); // !
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:");
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);
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
200static 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
250ideal 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);
408 return(res);
409 }
410 else
411 {
412 PrintS("No syzygies");
413 return(I);
414 }
415}
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
#define Print
Definition: emacs.cc:80
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
ideal idMultSect(resolvente arg, int length, GbVariant alg)
Definition: ideals.cc:472
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
#define idPrint(id)
Definition: ideals.h:46
#define idTest(id)
Definition: ideals.h:47
ideal idCopy(ideal A)
Definition: ideals.h:60
ideal * resolvente
Definition: ideals.h:18
STATIC_VAR jList * T
Definition: janet.cc:30
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3182
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:2447
#define KSTD_NF_NONORM
Definition: kstd1.h:21
static poly nc_ReduceSpoly(const poly p1, poly p2, const ring r)
Definition: nc.h:254
#define MATELEM(mat, i, j)
1-based access to matrix
Definition: matpol.h:29
#define MATCOLS(i)
Definition: matpol.h:27
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
ideal Approx_Step(ideal L)
Ann: ???
Definition: nc.cc:250
static ideal idPrepareStd(ideal T, ideal s, int k)
Definition: nc.cc:200
ideal twostd(ideal I)
Compute two-sided GB:
Definition: nc.cc:18
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define NULL
Definition: omList.c:12
VAR unsigned si_opt_1
Definition: options.c:5
#define OPT_SB_1
Definition: options.h:96
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define Sy_bit(x)
Definition: options.h:31
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4706
poly p_One(const ring r)
Definition: p_polys.cc:1313
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:342
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1029
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:486
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:311
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1962
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1889
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
#define p_Test(p, r)
Definition: p_polys.h:159
void rChangeCurrRing(ring r)
Definition: polys.cc:15
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatibility layer for legacy polynomial operations (over currRing)
#define pAdd(p, q)
Definition: polys.h:203
#define pTest(p)
Definition: polys.h:414
#define pDelete(p_ptr)
Definition: polys.h:186
#define pSetm(p)
Definition: polys.h:271
#define pSetCompP(a, i)
Definition: polys.h:303
#define pSetComp(p, v)
Definition: polys.h:38
#define pMult(p, q)
Definition: polys.h:207
#define pSetmComp(p)
TODO:
Definition: polys.h:273
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define pOne()
Definition: polys.h:315
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:261
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:205
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition: ring.cc:4435
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:5086
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
matrix id_Module2Matrix(ideal mod, const ring R)
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23
static int idElem(const ideal F)
number of non-zero polys in F
Definition: simpleideals.h:67
#define Q
Definition: sirandom.c:26
tHomog
Definition: structs.h:35
@ testHomog
Definition: structs.h:38
#define BITSET
Definition: structs.h:16
#define loop
Definition: structs.h:75